[较难] UVa OJ 12174 Shuffle 滑动窗口

题目描述

基本思路：

先通过滑动窗口求出所有s元素子序列是否不含重复元素。然后判断所有可能的分割位置是否可行。注意当输入序列元素数小于歌曲数的时候，是个个例，要单独处理。

书中页码247

具体代码：

#include <iostream>

using namespace std;
const int maxn=100000+5;
int f[maxn],h[maxn*3];
bool ok[maxn*3];
int main()
{
   // freopen("input.txt","r",stdin);
    int T;
    cin>>T;
    while(T--)
    {
        int s,n;
        cin>>s>>n;
        fill(f,f+maxn,0);
        fill(h,h+n+s*2+1,-1);
        fill(ok,ok+n+s*2+1,false);
        for(int i=0;i<n;++i)
        {
            cin>>h[s+i];
        }
        int tot=0;
        for(int i=0;i<n+s;++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(h[i]!=-1&&f[h[i]]--==1) --tot;
            if(h[i+s]!=-1&&f[h[i+s]]++==0) ++tot;
        }
        int ans=0;
        for(int i=0;i<s;++i)
        {
            bool valid=true;
            for(int j=i;j<n+s;j+=s)
            {
                if(!ok[j])
                {
                    valid=false;
                    break;
                }
            }
            if(valid) ++ans;
        }
        if(ans==n+1) ans=s;
        cout<<ans<<endl;

    }
    return 0;
}