17-09-29模拟赛-白红宇的个人博客

17-09-29模拟赛

发布日期：2021-08-11 02:51:17 浏览次数：53 分类：技术文章

本文共 2437 字，大约阅读时间需要 8 分钟。

T1:排序后离散化。pos[i]记录第i块骨牌倒塌后会影响到的最远骨牌数，可以通过二分查找求得。

枚举放置骨牌能够使某一位置及其之后的骨牌全部倒塌时被毁坏的骨牌个数，对所有值取min即可。

Code:

1 #include
     
       2 #include
      
        3 #include
       
         4 #define inf 0x7fffffff 5 #define MN 100005 6 using namespace std; 7 inline int in(){ 8     int x=0;bool f=0; char c; 9     for (;(c=getchar())<'0'||c>'9';f=c=='-');10     for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');11     return f?-x:x;12 }13 struct st{14     int p,t;15 }a[MN];16 int pos[MN],sum[MN],p2[MN],n,res=inf;17 inline bool cmp(st a,st b){
   return a.p
        
         0) sum[i]=sum[pos[i]-1]+(i-pos[i]);27         res=min(res,sum[i]+(n-i));28     }printf("%d",res);return 0;29 }

T2:可被看作为点与点的斜率的绝对值。

可以发现，当选取三个点A(x₁,y₁),B(x₂,y₂),C(x₃,y₃)(x₁<x₂<x₃)时，k_AC一定小于或等于k_AB或k_BC.(k_XY即为直线XY的斜率)

以此类推，选取多个点时的最大值只可能在相邻位置取到。

考虑将原数组差分后求绝对值，则一个数组的所有子数组的值之和即变为一个数组的所有子数组的最大值之和。

单调栈维护差分求绝对值后的值。注意不能取到l前的数。

Code:

1 #include
     
       2 #include
      
        3 #include
       
         4 #define ll long long 5 #define MN 100005 6 #define zxyer array 7 using namespace std; 8 inline int in(){ 9     int x=0;bool f=0; char c;10     for (;(c=getchar())<'0'||c>'9';f=c=='-');11     for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');12     return f?-x:x;13 }14 int d[MN],st[MN],a[MN];15 int n,q,l,r,top;16 ll sum[MN],ans;17 int main()18 {19     n=in();q=in();20     for (int i=1;i<=n;++i) a[i]=in(),d[i]=abs(a[i]-a[i-1]);21     for (int i=1;i<=q;++i){22         l=in();r=in();top=0;23         st[top]=l;ans=0ll;24         for (int j=l+1;j<=r;++j){25             while (top&&d[st[top]]

T3:将所有数据按照生命值净收益与净损失分类排序。

对于净收益类，按a[i]从小到大排序，若当前生命值小于或等于a[i]，则输出-1，否则生命值加上b[i]-a[i]记录答案。

对于净损失类，可以发现可以求出过程结束后的总生命值。

考虑逆向按b[i]从小到大排序，若当前生命值小于或等于b[i]，则输出-1，否则生命值加上a[i]-b[i]并记录答案。

注意输出时净收益类正序输出，净损失类倒序输出。

Code:

1 #include
     
       2 #include
      
        3 #include
       
         4 #define MN 200005 5 using namespace std; 6 inline int in(){ 7     int x=0;bool f=0; char c; 8     for (;(c=getchar())<'0'||c>'9';f=c=='-'); 9     for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');10     return f?-x:x;11 }12 struct mon{13     int a,b,id;14 }p1[MN],p2[MN];15 int st1[MN],st2[MN];16 int n,h,k,cnt1=0,cnt2=0,top1=0,top2=0,s,t;17 inline bool cmp1(mon x,mon y){
   return x.a==y.a?x.b>y.b:x.a
        
         y.a:x.b

转载于:https://www.cnblogs.com/codingutopia/p/test170929.html

转载地址：https://blog.csdn.net/weixin_30609287/article/details/98618189 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：EIP权限工作流平台总结-3后端框架

下一篇：【 imgproc 模块. 图像处理】腐蚀与膨胀(Eroding and Dilating)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章