「题解」Codeforces Round 994 (Div.2)

Mohao2024/12/23大约 6 分钟

A. MEX Destruction

龙 Evirir 溜进了巫师的城堡，发现了一个神秘的装置，他们贪玩的本能让他们玩弄（毁坏）了它......
埃维里尔龙发现了一个由 $n$ 个非负整数组成的数组 $a_1, a_2, \ldots, a_n$ 。
在一次操作中，他们可以选择一个非空的子数组 $^{\text{*}}$ 。 $b$ 的子数组 $a$ ，并将其替换为整数 $\operatorname{mex}(b)$ $^{\dagger}$ 。他们想多次使用这种运算使 $a$ 只包含零。可以证明，在问题的限制条件下，这总是可行的。
所需的最少运算次数是多少？
$^{\text{*}}$ 一个数组 $c$ 是一个数组 $d$ 的子数组，如果 $c$ 可以从 $d$ 中通过删除开头的几个（可能是零或全部）元素和结尾的几个（可能是零或全部）元素得到。
$^{\dagger}$ 整数集合 $f_1, f_2, \ldots, f_k$ 的最小排除数（MEX）定义为在集合 $f$ 中不出现的最小非负整数 $x$ 。

看起来有点神秘。看数据范围以为是暴力，仔细观察样例答案只有 $0, 1, 2$ ，三种情况。于是写出代码：

void solve() {
    int n;
    cin >> n;
    vector a(n, 0);
    for (auto &x : a)
        cin >> x;
    int cnt = 0;
    vector<int> z;
    bool nz = false;
    for (int i = 0; i < a.size(); i ++) {
        if (a[i] == 0) {
            if (nz)
                cnt ++;
            nz = false;
            continue;
        }
        nz = true;
    }
    if (nz)
        cnt ++;
    if (cnt == 0)
        cout << 0;
    else if (cnt == 1)
        cout << 1;
    else
        cout << 2;
    cout << "\n";
}

遂 AC。

但现在是考后写题解的时候，因此我们有必要好好地证明一下。

考虑到我们要让这个 $a$ 变成一个全 $0$ 的数组，我们唯一可以的操作就是选择一个子数组（连续）使得这个数组变成一个单独的 $\text{mex}(b)$ ，求最小的操作次数。

一般的，当这个数组全由 $0$ 组成的时候，操作数为 $0$ ；此外，当一个数组不包含 $0$ ，的时候，这个数组的 $MEX$ 为 $0$ 。

我们假设这个原数组是由正整数组成的数组，由上性质可知经过一次操作就能完成。

那如果这个数组中存在 $0$ 呢？我们经过一次操作就能使得这个数组变成一个正整数，然后再当成一个正整数数组处理即可（两步操作），这是可能发生的操作次数最多的情况。

也就是说，当数组 $a$ 全为 $0$ 时，答案为 $0$ ；当数组全为正整数的时候，答案为 $1$ ；其他情况答案为 $2$ 。

~~不知道为什么我答案写得那么别扭~~

原代码中相当于往数组的最后添加一个 $0$ ，cnt 统计的就是被 $0$ 分割的段数。根据我们已知的结论输出答案即可（段数为 $1$ 相当于全是正整数）。

B. pspspsps

Cats are attracted to pspspsps, but Evirir, being a dignified dragon, is only attracted to pspspsps with oddly specific requirements...
Given a string $s = s_1s_2\ldots s_n$ of length $n$ consisting of characters p, s, and . (dot), determine whether a permutation $^{\text{*}}$ $p$ of length $n$ exists, such that for all integers $i$ ( $1 \le i \le n$ ):
If $s_i$ is p, then $[p_1, p_2, \ldots, p_i]$ forms a permutation (of length $i$ );
If $s_i$ is s, then $[p_i, p_{i+1}, \ldots, p_{n}]$ forms a permutation (of length $n-i+1$ );
If $s_i$ is ., then there is no additional restriction.
$^{\text{*}}$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ( $2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ( $n=3$ but there is $4$ in the array).

翻译后公式抽风了就不放翻译了。

这个题目写的语焉不详的，简单来说就是对于字符 p，要求我们构造的排列能满足 $[a_1,a_2,\dots,a_i]$ ，（其中 $i$ 代表字符的位置，下同）是一个排列；对于字符 s 要求 $[a_i,\dots ,a_n]$ 也是一个排列。

我们首先考虑字符串中顺序出现的 p，假如 $[a_1,a_2,\dots,a_i]$ 是一个排列，那么我们一定能构造一个排列 $[a_1,a_2,\dots,a_j],(i<j\le n)$ ，所以我们能做到从第一个出现的 p 生成的排列上不断添油让最后一个位置的 p 也能满足题设。因此我们只考虑最后一个 p 的位置即可。同理可得，对于 s，我们只需要关注第一个的位置即可。

有且仅有如下三种情况能满足题设：

仅存在 s；
仅存在 p；
某一个的排列区间包含于另外一个的排列区间。

对于 s，这个区间是 $[pos_s, n]$ ，而对于 p，这个区间是 $[1,pos_p]$ ；因此第三个条件等同于 $pos_s = 1$ 或者 $pos_p = n$ 。

我们扫一遍字符串即可（代码略）

C. MEX Cycle

Evirir the dragon has many friends. They have 3 friends! That is one more than the average dragon.
You are given integers $n$ , $x$ , and $y$ . There are $n$ dragons sitting in a circle. The dragons are numbered $1, 2, \ldots, n$ . For each $i$ ( $1 \le i \le n$ ), dragon $i$ is friends with dragon $i - 1$ and $i + 1$ , where dragon $0$ is defined to be dragon $n$ and dragon $n + 1$ is defined to be dragon $1$ . Additionally, dragons $x$ and $y$ are friends with each other (if they are already friends, this changes nothing). Note that all friendships are mutual.
Output $n$ non-negative integers $a_1, a_2, \ldots, a_n$ such that for each dragon $i$ ( $1 \le i \le n$ ), the following holds:
Let $f_1, f_2, \ldots, f_k$ be the friends of dragon $i$ . Then $a_i = \operatorname{mex}(a_{f_1}, a_{f_2}, \ldots, a_{f_k})$ . $^{\text{*}}$
$^{\text{*}}$ The minimum excluded (MEX) of a collection of integers $c_1, c_2, \ldots, c_m$ is defined as the smallest non-negative integer $t$ which does not occur in the collection $c$ .

可以把龙之间的朋友关系看作一个图，要求对于点 $v$ ，其对应的值 $a_v=\text{mex}(N(v))$ ，其中 $N(v)$ 代表与 $v$ 相邻的点。

感觉认真的考虑这个问题对我来说可能有点困难。但不难注意到一个龙最多只能有 $3$ 个好友，至少也有 $2$ 个好友。同时这个图肯定存在一个环。所以我们可以多跑几遍暴力算法直到每一个元素都满足题设即可。

inline int mex(set<int> &x) {
    for (int i = 0; i <= inf; i ++) {
        if (!x.count(i))
            return i;
    }
    return 0;
}

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    vector vec(n + 1, set<int>());
    vector a(n + 1, 0ll);
    vec[x].insert(y); vec[y].insert(x);
    for (int i = 1; i <= n; i ++)  {
        int a = i % n + 1, b = (n + i - 2) % n + 1;
        vec[i].insert(a); vec[i].insert(b);
        vec[a].insert(i); vec[b].insert(i);
    }
    bool ok = false;
        ok = true;
        for (int i = 1; i <= n; i ++) {
            set<int> tmp;
            for (auto &v : vec[i])
                tmp.insert(a[v]);
            if (a[i] != mex(tmp))
                ok = false;
            a[i] = mex(tmp);
        }
    for (int i = 1; i <= n; i ++)
        cout << a[i] << " ";
    cout << "\n";
}

D.

const int inf = 1e18;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector a(n + 1, vector(m, 0ll));
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j < m; j ++)
            cin >> a[i][j];
    }
    vector f(n + 1, vector(m + 1, inf));
    f[0][0] = 0;
    for (int i = 1; i <= n; i ++) {
        for (int x = 0; x < m; x ++) {
            vector g(m, inf);
            for(int j = 0; j < m; j ++)
                g[j] = f[i - 1][j] + a[i][(j + x) % m] + k * x;
            for (int j = 0; j < m; j ++)
                g[j] = min(g[j], g[(j + m - 1) % m] + a[i][(j + x) % m]);
            for (int j = 0; j < m; j ++)
                f[i][j] = min(f[i][j], g[j]);
        }
    }
    cout << f[n][m - 1] << endl;
}

如上。