UVa12174 Shuffle（滑动窗口）

题目链接

1.题目大意：一共有s首歌，音乐播放器有一个乱序的功能，一开始给s首歌随机排列，全部播放完后再随机排列，继续播放以此类推，当且仅当s首歌全部播放完成才随机。现在给出一个长度为n的播放序列（不一定从最开始记录），统计下次排序发生时间有多少种可能性

2.题意实际上就是最后一首或几首歌的种类，决定了有多少种答案。首先需要注意，当n<=s且n个数互不相同，那么答案就是s，因为可以以任意一首歌结束当前序列并开始下次排序。这个题写了很长时间，一开始一直看不懂题解，没办法只好自己慢慢敲，学到了不少东西，尽管最后自己写的RE且找不到错误，但是过了debug，也没有遗憾了。自己尝试后再去看LRJ的方法也很好懂了

3.当n>s时，我们只需要考虑前面s个数那么只要每次的分段都符合互不相同这一要求，就可以作为一个答案。如果暴力的话肯定超时，在这里我们预处理前缀的1-s-1长度的窗口以及整个区间s长度的窗口，那么可以得到以每个数结尾的长度为[1-s]的窗口是否符合答案，接着枚举每一个区间尾，接下来每次都加上s的长度，那么判断到最后。但是我们还跳过了一段区间，即最后的[s-1,1]长度的区间没有判断，因此我们还需要处理这s个后缀窗口是否符合互不相同。至于判断方法，使用cnt记录区间内互不相同数的个数，尺取的思想，首先将窗口由1逐渐扩大到s，mp记录当前区间内每个数的个数，当窗口达到s后，每次移动对应mp[a[L]]–,mp[a[R]]++。同样的方法处理后缀

4.LRJ的思路是，首先将整个序列扩展为n+2s长度，这样就只需要从一开始使用长度为s的窗口，不断向右滑动，每次更新cnt，这样就得到了每个数结尾的长度为s的窗口是否符合要求

标答

#include<iostream>
#include<vector>
using namespace std;

const int maxn = 100000 + 5;
int s, n, x[maxn*3], cnt[maxn], ok[maxn*2];

int main() {
  int T;
  cin >> T;
  while(T--) {
    cin >> s >> n;
    fill(x, x+n+2*s, -1);
    for(int i = 0; i < n; i++) cin >> x[i+s];
    int tot = 0; // 统计在滑动窗口中的不一样的数字的个数
    fill(cnt+1, cnt+s+1, 0); // cnt[i]保存数字i在窗口中出现的次数
    fill(ok, ok+n+s+1, 0);   // ok[i] = 1 当如果窗口中没有相同的数，那么一定是一个排列

    //更新ok数组
    for(int i = 0; i < n+s+1; i++) {
      if (tot == s) ok[i] = 1;              //完整的窗口
      if (i < s && tot == i) ok[i] = 1;     //在左端不完整的窗口
      if (i > n && tot == n+s-i) ok[i] = 1; //在右端不完整的窗口

      if (i == n+s) break; //没有更多的窗口
      if (x[i] != -1 && --cnt[x[i]]==0) tot--; //左端数字滑出窗口
      if (x[i+s] != -1 && cnt[x[i+s]]++==0) tot++; //右端数字滑进窗口
    }

    int ans = 0;
    for(int i = 0; i < s; i++) {
      int valid = 1;
      for (int j = i; j < n+s+1; j += s)
        if(!ok[j]) valid = 0;;
      if(valid) ans++;
    }
    if(ans == n+1) ans = s;
    cout << ans << "\n";
  }
  return 0;
}

RE的代码

#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int maxn=3e5+10;
unordered_map<int,int> mp;
int a[maxn];
bool ok[maxn],sub[maxn];
int t,n,s;

bool check(){
    mp.clear();
    for(int i=1;i<=n;i++){
        if(mp[a[i]]) return false;
        else mp[a[i]]=1;
    }
    return true;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>s>>n;
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++) cin>>a[i];
        if(n<=s && check()){  //特判
            cout<<s<<endl;
            continue;
        }
        int l=1,r=1;
        int cnt=0;
        mp.clear();
        while(r<=n){  //尺取，首先由1逐渐增加到s，接着保持s向右滑动
            while(r-l+1<=s && r<=n){
                if(!mp[a[r]]) cnt++;
                mp[a[r]]++;
                if(cnt==(r-l+1)) ok[r]=1;
                else ok[r]=0;
                r++;
            }
            if(--mp[a[l]]==0) cnt--;
            l++;
        }
        l=n-s+1,r=n,cnt=0;
        int tot=0;
        mp.clear();
        while(l<r){  //处理后缀，由1增加到s即可，无需在向左滑动
            tot++;
            if(!mp[a[r]]) cnt++;
            mp[a[r]]++;
            if(cnt==tot) sub[r]=1;
            else sub[r]=0;
            r--;
        }
        //验证两个数组都是对的
        //for(int i=1;i<=n;i++) cout<<ok[i]<<endl;
        //for(int i=n-s+2;i<=n;i++) cout<<sub[i]<<endl;
        int ans=0;
        for(int i=1,j;i<=s;i++){
            if(ok[i]){
                int flag=1;
                for(j=i;j<=n;j+=s)  
                    if(!ok[j]){
                        flag=0;
                        break;
                    }
                //cout<<flag<<"---"<<j-s+1<<endl;
                if(flag && j-s+1<=n){  //如果前面都符合，将后缀是否符合也判断
                    if(!sub[j-s+1]) flag=0;
                }
                if(flag) ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}