给出一段播放记录，判断下次随机开始的地方有几种不同情况。
首先利用滑动窗口判断当前位置的前 s 个位置数字是否均不同。
然后枚举终点，每次进行验证。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<cstdio>
#include<cstring>
using namespace std;
const int maxn=200010;
int a[maxn];
int vis[maxn];
bool ok[maxn];
int main(){
int t;scanf("%d",&t);
while(t--){
int s,n,cnt=0,ans=0,ns;
scanf("%d%d",&s,&n);
memset(a,0,sizeof(a));
memset(ok,0,sizeof(ok));
memset(vis,0,sizeof(vis));
ns=n+2*s-n%s;
for(int i=0;i<ns;++i){
if(i<n){
scanf("%d",&a[i]);
if(++vis[a[i]]>1) ++cnt;
}
if(i>=s)
if(i-s<n&&--vis[a[i-s]]==1) --cnt;
if(cnt==0) ok[i]=true;
}
for(int i=0;i<s;++i){
bool flag=true;
for(int j=i;j<ns;j+=s)
if(!ok[j]){
flag=false;
break;
}
if(flag) ++ans;
}
printf("%d\n",ans);
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **