A:
自己找规律就好了...
- B:
- https://codeforces.ml/problemset/problem/1333/B
你会发现题目只需要 bi-ai 与前面的 aj 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;
- }
来源: http://www.bubuko.com/infodetail-3500983.html