26牛客暑假多校5

点击查看题面

K题 Sequence（Mex Version）

题目大意

给定一个长度为 $n$ 的环状整数序列 $a_0,a_1,\dots ,a_{n-1}$。定义一次变换如下：

1. 根据当前序列 $a$ 构造一个新序列 $b_0,b_1,\dots ,b_{n-1}$，其中 $b_i=\text{mex}\{a_i,a_{(i+1)modn},a_{(i-1+n)modn}\}$。这里 $\text{mex}$ 表示非负整数集合中最小的未出现的非负整数。
2. 将序列 $a$ 替换为 $b$。

求经过 $k$ 次变换后得到的最终序列。

数据范围：

• $1\le n,k\le {10}^6$
• $0\le a_i\le {10}^9$

---

思路

1. $\text{mex}$ 值域缩减： 对于任意三个非负整数计算 $\text{mex}$，其结果必然位于集合 $\{0,1,2,3\}$ 中。因此，经过 $1$ 次变换后，序列中的所有元素均会被限制在 $[0,3]$ 的范围内。
2. 周期性规律： 通过打表发现，序列在经历至多 $3$ 次变换后，其状态转移将进入一个周期为 $2$ 的稳定循环状态（即再做 $2$ 次变换后，序列保持不变或在两个固定状态间循环切换）。
3. 状态化简与模拟： 基于上述周期性，我们无需真正执行 $k$ 次变换：

• 先令 $d=min(3,k)$，模拟前 $d$ 次变换，将序列引导至稳定周期状态。
• 对于剩余的 $k-d$ 次变换，由于周期为 $2$，只需判断 $(k-d)$ 的奇偶性：
• 若 $(k-d)$ 为奇数，则额外再执行 $1$ 次变换；
• 若为偶数，则维持现状即可。

如此一来，序列变换的总次数被严格限制在至多 $4$ 次，从而极大优化了效率。

复杂度分析

时间复杂度：$\mathcal{O}(n)$。由于序列的最大模拟次数不超过 $4$ 次，每次变换需要遍历一次长度为 $n$ 的数组，因此整体运行时间与 $k$ 无关，时间复杂度为线性阶 $\mathcal{O}(n)$。

空间复杂度：$\mathcal{O}(n)$。需要额外的数组/向量来存储单次变换生成的新序列 $b$，空间开销为 $\mathcal{O}(n)$。

参考代码

参考代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int mex(int a, int b, int c) {
    if (a != 0 && b != 0 && c != 0) return 0;
    if (a != 1 && b != 1 && c != 1) return 1;
    if (a != 2 && b != 2 && c != 2) return 2;
    return 3;
}

void fc() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &i : a) {
        cin >> i;
    }

    int d = min(3, k);
    k -= d;

    while (d--) {
        vector<int> b(n);
        for (int i = 0; i < n; i++) {
            b[i] = mex(a[i], a[(i + 1) % n], a[(i + n - 1) % n]);
        }
        a = move(b);
    }

    if (k & 1) {
        vector<int> b(n);
        for (int i = 0; i < n; i++) {
            b[i] = mex(a[i], a[(i + 1) % n], a[(i + n - 1) % n]);
        }
        a = move(b);
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << (i == n - 1 ? "" : " ");
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    while (t--) {
        fc();
    }
    return 0;
}