UVA 12171 Shuffle的播放记录（滑动窗口）

￡神魔★判官ぃ 2024-02-17 22:47 47阅读 0赞

题意：假设一共有首歌，则一开始会给这s首歌随排列，全部播放完毕后再重新随机排序，继续播放，依次类推。当s首歌播放完毕之前不会重新排序；这样，播放记录里的没s首歌都是1~n的一个排列。给一个长度为n的播放记录，统计给出序列中第一个数在某个排序中的播放位置的种类。

例如：s=4，播放记录是 3，4 ，4， 1 , 3 ，2， 1 , 2 ，3 ，4，只有一种可能性：前两首是一个段的最后两首，后面是完整的段。故答案是1.

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn = 1e5+10;
    int f[maxn*3],ok[maxn*2],cnt[maxn];
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		int s,n;
    		scanf("%d%d",&s,&n);
    	    
    	    memset(f,0,sizeof(f));
    	    memset(ok,0,sizeof(ok));
    	    memset(cnt,0,sizeof(cnt));
    		for(int i = 0; i < n; i++){
    			scanf("%d",&f[i+s]);
    		}
            
           int tot = 0; // 窗口中不同的个数  
           for(int i = 0; i < s+n; i++){
            	if(tot == s)ok[i] = 1;
            	if(i < s && i == tot)ok[i] = 1;   //left
            	if(i > n && n+s-i == tot)ok[i] = 1;   //right
            	
            	//move windows
            	if(f[i] != 0 && --cnt[f[i]] == 0)tot--;
            	if(f[i+s] != 0 && cnt[f[i+s]]++ == 0)tot++;
    	   }
    	   
    	   int total =0;
    	   for(int i = 0; i < s; i++){
    	   	int flag = 0;
    	   	for(int j = i; j < n+s; j = j+s){
    	   		if(ok[j] == 0) {
    	   			flag = 1;
    	   			break;
    			   }
    		   }	   
    		   if(!flag) total++;
    	   }
    	   //特判原因是当n<s时，ok[]标记不会被执行
    	   if(total == n+1) total = s;  //spacial case
    	   
    	   printf("%d\n",total);
           }
    	return 0;
    }