一、题意

输入n、m、k，你可以根据m得到一个长度为n的序列a[maxn]（即a[maxn]已知）。
现在要你在a[maxn]中找到一个包含 1~k 这k个整数的最短连续子序列。
输出符合要求的最短连续子序列的长度。无解时输出无解。

二、解析

看到连续子序列，马上就觉得可以用滑动窗口或者说双指针的方法来做。

同时还需要用一个 cnt[maxk] 来存放当前“窗口”中 1 ~ k 的数字分别有多少个。通过 j 递增来滑动窗口，同时当 i 所指向的值不属于 1 ~ k 或者它所指向的值在窗口中已经有多个时，可以将其弹出窗口（以使得窗口尽可能小）。然后通过对cnt数组中1~k的元素是否有值来判断当前窗口是否ok。

用一个ans值记录一个ok的窗口的最短长度即可。

三、代码

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 1000000 + 5, maxk = 100 + 5;
int kase, n, m, k, a[maxn], cnt[maxk];

bool isOK() {
    for(int i = 1; i <= k; i ++) if(cnt[i] == 0) return 0;
    return 1;
}

int main() {
    cin >> kase;
    a[0] = 1, a[1] = 2, a[2] = 3;
    for(int K = 1; K <= kase; K ++) {
        cin >> n >> m >> k;
        fill(cnt, cnt + k + 1, 0);
        for(int i = 3; i < n; i ++) a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % m + 1;

        bool ok = 0;
        int ans = n;
        for(int i = 0, j = 0; j < n; j ++) if(a[j] <= k) {
            cnt[a[j]] ++;
            if(!ok && isOK()) ok = 1;
            while(a[i] > k || cnt[a[i]] > 1) {  // 注意不在1~k范围内的值也可以直接出列
                if(a[i] <= k) cnt[a[i]] --;
                i ++;
            }
            if(ok) ans = min(ans, j - i + 1);
        }
        if(!ok) cout << "Case " << K << ": sequence nai" << endl;
        else cout << "Case " << K << ": " << ans << endl;
    }
}

四、归纳

  • 双指针问题注意 i++ 的条件，不要遗漏。