一、题意

每组数据输入一个s和一个n，s表示歌曲的数目，n表示歌曲乱序循环播放列表的长度，然后输入一个数组a[maxn]表示该播放列表。
要求统计乱序播放列表的的开头位置有多少种可能性。

二、解析

一个位置如果是乱序循环播放列表的开头，那么从它开始的后s首歌曲一定互不相同，再后s首也是互不相同.....因此我们需要统计出一个isOK[pos]数组，表示从pos开始的后s首是否满足互不相同。

这实际上是一个滑动窗口，窗口的长度固定为s。由于开头位置可能出现在播放列表开始播放的位置更之前的位置（即播放列表可能是中间截取的一段），因此我们需要在a[maxn]数组之前空出s个位置，即a数组表示为a[0...s-1, s,...s+n-1]，这样的a数组的下标就包含了所有可能的开头位置。

接下来我们就要让一个滑动窗口从划过这个a数组。滑动窗口初始位置为a[0...s-1]，这是里面是没有重复的歌曲的，即dup_num=0，因此isOK[0]=1，接下来我们就要随着窗口的滑动维护、更新这个出现重复的歌曲的数目dup_num。当dup_num==0时对应的滑动窗口是没有重复歌曲的，即isOK的。

窗口滑动完毕后，我们就得到了这个isOK[0...s+n-1]数组，之后只要枚举0...s检查是否满足我们最开始说的条件即可。然后统计出ans值。

三、代码

#include <iostream>
using namespace std;
const int maxn = 100000 + 5;
int kase, s, n, a[maxn * 2], cnt[maxn];
bool isOK[maxn * 2];

int main() {
    cin >> kase;
    while(kase --) {
        cin >> s >> n;
        fill(cnt, cnt + s + 1, 0);
        for(int i = s; i < s + n; i ++) cin >> a[i];

        int dup_num = 0;
        for(int l = 0; l < s + n; l ++) {
            isOK[l] = (dup_num == 0);

            int r = l + s;
            if(l >= s && cnt[a[l]]-- > 1) dup_num --;
            if(r < s + n && ++cnt[a[r]] > 1) dup_num ++;
        }

        int ans = 0;
        for(int start = 0; start < s; start ++) {
            bool ok = 1;
            for(int l = start; ok && l < s + n; l += s) if(!isOK[l]) ok = 0;
            if(ok) ans ++;
        }
        cout << ans << endl;
    }
}

四、归纳

  • 有时可以给数组多开一些空位，以方便边界处理。
  • 滑动窗口问题一般会同时维护一个关键量或全局数组等来统计信息。