Codeforces 1602B Special Permutation

第一次写题解，大佬轻喷。

题目大意

给定数组 \(a\) ，每次变换将 \(a_i\) 变换为 \(a\) 中 \(a_i\) 出现的次数。询问 \(k\) 次变换后 \(a_x\) 的值。

\(e.g.\) \[ \begin{array}{cc} \text{初始数组} &2 \ 1 \ 1 \ 4 \ 3 \ 1 \ 2 \\ \text{第一次变换后} & 2 \ 3 \ 3 \ 1 \ 1 \ 3 \ 2 \\ \text{第二次变换后} & 2 \ 3 \ 3 \ 2 \ 2 \ 3 \ 2 \\ \text{第三次变换后} & 4 \ 3 \ 3 \ 4 \ 4 \ 3 \ 4 \\ \dots &\dots \\ \end{array} \]

分析

我们称 \(a\) 中所有相同的元素为一组。

容易发现，当一组内的元素等于其出现次数时，这组元素便不再变化。我们称这种状态为稳定。

所以说，当没有组发生合并，也就是所有元素都不发生变化时，以后也不会再有变化。此时整个数组稳定。

换言之，在整个数组稳定前，组的数量严格递减。

很容易得出最多变换 \(n\) 次整个数组便稳定的结论。

（官方题解说最多 \(\log n\) 次就会达到稳定，可是我不会证。不过 \(n\) 次的复杂度也足够通过此题了。）

代码

#include <cstdio>
#include <iostream>

const int MAX_N = 2050;

int a[MAX_N][MAX_N];

template <typename T>
T read();

int main() {
    std::ios::sync_with_stdio(false);

    int T = read<int>();
    while (T--) {
        int n = read<int>();

        for (int i = 1; i <= n; i++) {
            a[0][i] = read<int>();
        }
        for (int i = 1; i <= n; i++) {
            auto *cnt = new int[n + 1]{};
            for (int j = 1; j <= n; j++) {
                cnt[a[i - 1][j]]++;
            }
            for (int j = 1; j <= n; j++) {
                a[i][j] = cnt[a[i - 1][j]];
            }
        }

        int q = read<int>();
        while (q--) {
            int x = read<int>(), y = read<int>();
            std::cout << a[std::min(y, n)][x] << '\n';
        }
    }

    return 0;
}