A
自己找规律就好了。。。
B
https://codeforces.ml/problemset/problem/1333/B
你会发现题目只需要 bi-ai 能用 前面的i-1个数表示就可以了
但是题目又说a只有0，-1，1
显然0对答案没有什么用，相当于占位，1~i 里面无论有几个1 其实都相当于1个1 的作用（-1同理）
bi-ai>0 则说明它要被1能得出 <==> 1~i-1 里面至少含有一个1
bi-ai<0 同理
bi==ai 直接跳过即可（因为a1~i-1系数全为0都可以满足）
要特判一下a1是否等于b1
#include<bits/stdc++.h> using namespace std; const int N=1e5+5,inf=0x3f3f3f3f; int T,a[N],b[N],c[N],n,pos1,pos2,flag;// 1 B 0 W int main() { scanf("%d ",&T); while(T--) { scanf("%d",&n); flag=0; pos1=inf; pos2=inf; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]==1&&pos1==inf) pos1=i; if(a[i]==-1&&pos2==inf) pos2=i; } for(int i=1;i<=n;i++) { scanf("%d",&b[i]); c[i]=b[i]-a[i]; if((c[i]>0&&i>pos1)||(c[i]<0&&i>pos2)||(c[i]==0)) continue; else flag=1; } if(flag) printf("NO\n"); else printf("YES\n"); } return 0; }
C题
https://codeforces.ml/problemset/problem/1333/C
1. 因为tot [i~j] =0 <==> sum[i-1]==sum[j] 注意是i-1
2. tot i~j =0 对于任意pos1< i , pos2 > j ，[apos1 ... apos2 ] 这个集合都是not good
3. 假设 [ai ... aj] is good 如果set.count(sum[j+1])!=0 说明里面存在一个pos,sum[pos] = sum[j+1] 这时候对答案有的贡献是j-i（i~i,i~i+1，i~i+2 ...i~j)
4 .删去sum[i] ,如果仍有set.count(sum[j+1])!=0 说明 i~j+1 not good,继续删
否则 i+1~j good 回到 3
5. longlong不能忘
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; long long n,x[N],sum[N],pos1,pos2,ans; set < long long > s; int main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&x[i]); sum[i]=sum[i-1]+x[i]; } //sum i =tot 1~i-1 //从1开始枚举，直到发现一个不满足条件的位置pos // 这时有1~2，1~3...1~pos个序列满足，ans+=pos-1 //如果恰好是sum pos==sum 1 ,则去掉sum1后继续找一个pos，ans+=pos-2 //如果 sum pos!=sum 1 pos1=1,pos2=1; s.insert(0); while(pos1<=n) { while(pos2<=n) { if(s.count(sum[pos2])==0) { s.insert(sum[pos2]); pos2++; } else break; } ans+=pos2-pos1; s.erase(sum[pos1-1]); pos1++; } printf("%lld\n",ans); return 0; }
原文链接: https://www.cnblogs.com/cherrypill/p/12672381.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/341292
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
