T2 Game 题解

cff_0102 · 2025-03-23 00:29:11 · 题解

为了方便，设 p_i 表示当前满足 a_k=i 的 k 的值。交换两个位置 i 和 j 表示交换 a_i 和 a_j（此时 p_{a_i},p_{a_j} 也会更新）。

首先考虑 t\le 2 的情况。

如果 t=1，先手一定会交换第一个满足 a_i\ne i 的位置 i 和后面的位置 p_i，这样可以做到字典序最小。

如果 t=2，先考虑第二步后手会干什么。类似上面 t=1 时先手的策略，后手会交换此时第一个满足 a_i\ne n-i+1 的位置 i 和后面的位置 p_{n-i+1}。

接着考虑先手：

• 如果刚开始 a_1=n，先手的最优策略显然是将这个数移走，这样后手只能把这个数移回来。否则，后手可能在后面找到一个比原来字典序更大的方案。这样，最终得到的答案会和刚开始的排列完全相同。
• 如果 a_1\ne n，先手不会傻到去交换位置 1 和 p_n。因此后手的操作肯定是交换先手操作后的位置 1 和 p_n。可以发现，在这种情况下，等价于后手先交换现在的位置 1 和 p_n，先手再按最优方式操作（这个证明比较显然，能够自己理解的可以直接跳过下面一段）：
  • 如果先手的操作不涉及位置 1 和 p_n，那么这两个操作先后显然是无关的。
  • 如果先手交换了位置 1 和 i，后手交换新的位置 1 和 p_n，那么现在的情况是位置 1 变成了 n，位置 i 变成了 a_1，位置 p_n 变成了 a_i。可以发现这种情况和先交换位置 1 和 p_n，再交换（原来的）位置 p_n 和 i 是等价的。
  • 先手交换位置 p_n 和 i 的情况同理。
• 因此在这种情况下，可以直接交换位置 1 和 p_n，剩下的问题是位置 2\sim n 里面交换两个数使得字典序最小，就变成了前面 t=1 时讨论的方法。

代码模拟，不难做到 \mathcal{O}(n)。

现在考虑 t>2 的情况。

对于 2\nmid t，答案和 t=1 时答案一样。因为先手先按最优完成第一步后，a_1 必然为 1，这样就和前面 t=2,a_1=n 的情况是一样的：此时后手的最优策略只能是把位置 1 再移走，否则先手可能在下一步又找到一个字典序更小的方法。如果后手把位置 1 移走了，后面先手就只能选择撤销后手的操作。

对于 2\mid t，类似的，和 t=2 答案一样。可以把这种情况看成先手先操作一步，接着后手变成新的“先手”，进行 t'=t-1 次操作，最终“先手”的目标是字典序最大，“后手”的目标是字典序最小。由前面同理可得，2\nmid t' 的这种情况相当于 t'=1 的情况。因此 2\mid t 也就相当于 t=2 的情况。

那么就可以把 t 的范围缩小成 \le 2，再用上面的方法解决。总复杂度 \mathcal{O}(n)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],p[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    long long t;int n;cin>>t>>n;
    for(int i=1;i<=n;i++)cin>>a[i],p[a[i]]=i;
    if(t&1){
        for(int i=1;i<=n;i++){
            if(a[i]!=i){
                swap(a[i],a[p[i]]);
                break;
            }
        }
        for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    }else{
        if(a[1]==n){
            for(int i=1;i<=n;i++)cout<<a[i]<<" ";
        }else{
            p[a[1]]=p[n];
            swap(a[1],a[p[n]]);
            p[n]=1;//这句实际可以删掉
            for(int i=2;i<=n;i++){
                if(a[i]!=i-1){
                    swap(a[i],a[p[i-1]]);
                    break;
                }
            }
            for(int i=1;i<=n;i++)cout<<a[i]<<" ";
        }
    }
    return 0;
}