题解：P11969 「ALFR Round 7」T2 Game

· · 题解

这道题使用博弈论，需要对 t 的奇偶性进行分类讨论。

Part 1 思路

当 t = 1 时，相当于只有先手一次操作机会。那么，想让字典序最小，只需要把 1 提到第一位即可。但要是 1 已经在第一位了，那我们就把 2 提到第一位，以此类推。形式化的，我们找到第一个 a_i \ne i，将 i 放到第 i 个位置即可。 \ 我们推广一下，当 t 为奇数且 t > 1 时，第 2 次操作后手只能将 1 挪作（目的是维持现状，否则先手就会把 2 再放到第二个位置上，更加不利），先手再把 1 挪回来，以此反复。所以，当 t 为奇数时，情况和 t = 1 是一样的。 \ 再来考虑 t = 2 时的情况。此时先手后手各操作一次。先从后手开始考虑，后手肯定会把 n 放到第一位，让字典序最大。先手此时不可能将第一位更改成小于 n 的数，所以退而求其次，将第二位降低，越小越好。所以，先手会把 1 放到第二位。但是，如果 1 已经在第二位，那么我们不妨把 2 放到第三位，以此类推。形式化的，我们找到第一个 a_i \ne i - 1 且 i \ge 2 的，将 i - 1 放到第 i 位上。 \ 接着推广一下，当 t 是偶数且 t > 2，第 3 次操作先手唯一的策略就是把现在在第一位上的 n 移走（目的还是维持现状，因为如果不挪走 n，那么后手就会将 n - 1 放到第二位上，更加不利），后手会再把 n 放回来，以此类推。所以，当 t 为偶数时，和 t = 2 的情况是一样的。

Part 2 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int M = 1e5 + 10;
int n, t, a[M], p[M];

signed main() {

    cin >> t >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i], p[a[i]] = i;
    if (t % 2 == 1) {
        for (int i = 1; i <= n; i ++) {
            if (i != a[i]) {
                int pos = p[i];
                swap(a[i], a[pos]);
                break ;
            }
        }
    }
    if (t % 2 == 0) {
        if (a[1] == n) {
            for (int i = 1; i <= n; i ++) cout << a[i] << " "; 
            return 0;
        }
        if (a[1] == 1 && a[2] == n) {
            for (int i = 3; i <= n; i ++) {
                if (a[i] != a[i - 1]) {
                    int pos = p[i - 1];
                    swap(a[i], a[pos]);
                    break ;
                }
            }
            swap(a[1], a[2]);
            for (int i = 1; i <= n; i ++) cout << a[i] << " "; 
            return 0;           
        } 
        for (int i = 2; i <= n; i ++) {
            if (a[i] != i - 1) {
                int pos = p[i - 1];
                swap(a[pos], a[i]);
                break ;
            }
        }
        swap(a[1], a[p[n]]);
    }
    for (int i = 1; i <= n; i ++) cout << a[i] << " ";
    cout << "\n";

    return 0;
}

说明一下，代码中 p_i 表示的是 i 在 a 数组中的位置，这样查找方便。

Part 3 其他注意事项

我们考虑一种情况：若 t 为偶数且 a_1 = n，那么直接输出原数组。原因：先手只能把 n 移走。假设先手没有移走 n，后手就可以把 n - 1 移到第二个位置上，这样肯定不优于原数组，所以先手只能把 n 移走，后手再放回来，陷入死循环，所以直接输出原数组。 \ 另外一种情况：若 t 为偶数且 a_1 = 1 且 a_2 = n，先手只需要将 2 移到第三位上，后手便会把 n 放到第一位上，1 也就到了第二位上，符合先手的需求。形式化的，我们只需要找到第一个 a_i \ne i - 1 且 i \ge 3，将 i - 1 移到第 i 位上，交换第一位第二位即可。