P10032 「Cfz Round 3」Mex of Sequence

· · 题解

有人说这道题不能用桶，我说：这是不可能的！

如果我们要求出一个序列中未出现过的最小自然数，那么，我们肯定要用一个同来记录那些数出现过，那些数没出现过。由于 a_{i} 的值最大为 10^9，所以我们需要巧妙的换个角度想一下：一个序列中有 n 个数，那么在 0 到 n 这 n+1 个数里，必然有一个数没有出现。所以，桶的大小应设为 n 的最大值，也即 10^6。

我们用一个桶来记录每个小于等于 n 的数的出现的次数，并且还要知道那些数没有出现，还是最小的，也即我们要将一些没出现的数按照升序排序。那么，我们会自然而然地想到堆。

有如上思想后，这道题便很容易解决了。由于操作数 m 的上限为 10^9，所以，我们不能单纯地模拟。由于序列的每个数改来改去，它的值终究还是在几个数中来回改变，所以，由经验得：序列在改变多次后，肯定会陷入循环。

证明：当序列进行第一次改变后，在以后的改变中，每个元素要么变成比它大或小的数，而变成比它大或小的数后又会便成原来的数（因为第 i 次改变后的数补充了第 i-1 次序列的未出现最小自然数，而第 i+1 次改变又需要补充第 i 次序列的未出现最小自然数）。

那么，我们只要像算小数的循环节一样，算序列的循环节。为了方便起见，我们将一个序列用字符串表示，那么判断这个序列有没有出现过时便很简单了。

下面给出代码，有很多巧妙的地方还是要在代码中感悟、理解，望大家看懂。

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int tt[1000005];//tt数组为桶
int b[1000005];
string c[1000005];//记录循环

string zhuan(int x) {//将数字转换为字符串，注意字符串的顺序别反了
    string p = "";
    if (x == 0)
        p += '0';
    while (x) {
        p += char(x % 10 + '0');
        x /= 10;
    }
    string ppp = p;
    for (int i = 0, j = p.size() - 1; i < p.size(); i++, j--)
        ppp[j] = p[i];
    return ppp;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        set<int>Q;
        map<string, int>qq;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (a[i] <= n)
                tt[a[i]]++;
        }
        for (int i = 0; i <= n; i++)
            if (!tt[i])
                Q.insert(i);//将没出现过的数加入set
        for (int i = 1; i <= q; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[j] <= n) {//如果将a[j]删去，a[j]这个数便没有出现时
                    if (tt[a[j]] == 1) {
                        int x;
                        for (int k : Q) {
                            x = k;
                            break;
                        }
                        b[j] = min(x, a[j]);
                    } else {
                        for (int k : Q) {
                            b[j] = k;
                            break;
                        }
                    }
                } else {
                    for (int k : Q) {
                        b[j] = k;
                        break;
                    }
                }
            }
            string pp = "";//序列转字符串
            for (int j = 1; j <= n; j++) {
                if (a[j] <= n) {
                    tt[a[j]]--;
                    if (tt[a[j]] == 0)
                        Q.insert(a[j]);
                }
                a[j] = b[j];
                if (a[j] <= n) {
                    tt[a[j]]++;
                    if (tt[a[j]] == 1)
                        Q.erase(a[j]);
                }
                pp += zhuan(a[j]);
                pp += " ";
            }
            if (qq[pp]) {//算循环节
                if (i - qq[pp] == 1)
                    cout << c[qq[pp]];
                else if ((q - qq[pp] + 1) % (i - qq[pp]) == 0)
                    cout << c[i - 1];
                else
                    cout << c[qq[pp] - 1 + (q - qq[pp] + 1) % (i - qq[pp])];
                for (int j = 1; j <= i; j++)
                    c[j] = "";
                break;
            }
            qq[pp] = i;
            c[i] = pp;
            if (i == q) {
                cout << pp;
                for (int j = 1; j <= i; j++)
                    c[j] = "";
            }
        }
        cout << endl;
        memset(tt, 0, sizeof(tt));
    }
}

给个赞吧！ 赛时记录