首页 > 代码库 > 初赛第五场C

初赛第五场C

题意:和B一样,数据变大了而已

思路:对于子串,它最多改变2个数字的不同,具体看代码。

 1 #include<bits/stdc++.h> 2 using namespace std; 3  4 int d[50005]; 5 int a[50005],b[50005]; 6 int c[50005]; 7 int main(){ 8     int n,m; 9     scanf("%d",&n);10     int x;11     for(int i=1;i<=n;i++){12        scanf("%d",&d[i]);13     }14     int q;15     scanf("%d",&q);16     for(int ii=1;ii<=q;ii++){17         scanf("%d",&m);18         memset(a,0,sizeof(a));19         memset(b,0,sizeof(b));20         for(int i=1;i<=m;i++){21             scanf("%d",&c[i]);22             b[c[i]]++; a[d[i]]++;23         }24         int ans=0;25         int sum=0;26         for(int i=1;i<=n;i++) if(b[i]!=a[i]) sum++;27         if(sum==0) ans++;28 29         for(int i=m+1;i<=n;i++){30             if(a[d[i-m]]==b[d[i-m]]) sum++;31             else if(a[d[i-m]]-1==b[d[i-m]]) sum--;32             a[d[i-m]]--;33             if(a[d[i]]==b[d[i]]) sum++;34             else if(a[d[i]]+1==b[d[i]]) sum--;35             a[d[i]]++;36             if(sum==0) ans++;37         }38          printf("%d\n",ans);39     }40     return 0;41 }

 

初赛第五场C