题目传送门

从题目中我们可以看出,这道题显然是用滑动窗口来完成的。

是的,滑动窗口!而且这个滑动窗口比较容易维护,因为它窗口的大小”基本”固定,(因为还需要考虑不完整的段),只需使用一个变量来标记,而且所有的数都是从1~s的整数,因此,只需用一个数组便可以保存每个数在窗口中出现的次数。在用一个b数组来记录不合法(窗口中含有相同的歌),在最后再用s减去不合法的个数就行了。 代码如下:

#include using namespace std;int a[1000100],tmp[1000100],b[1000100];int main(){    int n,m,s;    cin>>m;    while(m--){        cin>>s>>n;        memset(a,0,sizeof(a));        memset(tmp,0,sizeof(tmp));        memset(b,0,sizeof(b));        int ans = s;        int p = 0;//右端        for (int i=1;i<=n;i++){            cin>>a[i];        }        for (int i=1;i<=n+s;i++){            if (i>s){                tmp[a[i-s]]--;                if (tmp[a[i-s]] == 1) p--;            }            tmp[a[i]]++;//个数加一            if (tmp[a[i]]>1&&a[i]) p++;            if (p>0) b[i%s] = 1;//防止溢出         }        int wrongful = 0;        for (int i=0;i<s;i++){            wrongful+=b[i];        }        cout<<ans-wrongful<<endl;    }    return 0;}

注意: 你的tmp数组必须开得足够大,否则会RE

惨痛教训: