自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:11:46，当前版本为作者最后更新于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;
}