CF1365F Swaps Again 做题记录

给出两个长度为 $n$ 的数列 $a,b$，你需要判断能否在数次操作后使得 $a$ 与 $b$ 相同。

操作是指你可以选择一个 $k(1\le k\le\lfloor\frac n2\rfloor)$，之后交换 $a$ 的长度为 $k$ 的前缀和长度为 $k$ 的后缀。

例如对于 $a=\{1,2,3,4,5,6\}$，选择 $k=2$，那么交换后会得到 $\{5,6,3,4,1,2\}$。

$1\le n\le500$，$1\le a_i,b_i\le10^9$。

结论题，别的题解都没给证明，我来证一下吧。

观察到每次操作中对于所有满足 $i\le \lfloor\frac{n}{2}\rfloor$ 的 $i$ 都进行了 $\operatorname{swap}(a_i,a_{n-k+i})$，而和 $a_i$ 以序列中点对称的元素是 $a_{n-i+1}$，操作中同时进行了 $\operatorname{swap}(a_{k-i+1},a_{n-i+1})$，所以 $(a_i,a_{n-i+1})$ 和 $(a_{k-i+1},a_{n-k+i})$ 在交换之后仍然以序列中点对称。

那么把 $a$ “对折”，把 $(a_i,a_{n-i+1})$ 这一对记作 $b_i$，那么每次操作相当于是交换了所有满足 $i\le \lfloor\frac{k}{2}\rfloor$ 的 $b_i$ 和 $b_{k-i+1}$，并且所有满足 $i\le k$ 的 $b_i$ 组内顺序都被交换了。

不难发现，组内顺序是可以随便交换的，只要做一次 $k=i$，一次 $k=1$，一次 $k=i$ 即可。

现在问题转化为：

有一个 $n$ 的排列 $p$，请问能否通过任意次交换满足 $1\le i\le \lfloor\frac{k}{2}\rfloor$ 的 $p_i$ 和 $p_{k-i+1}$，得到 $n$ 的另外的一个排列 $b$？

这个问题对于任意 $p,b$ 的答案都是可以，证明如下：

• 引理：可以使用 $2$ 次操作将 $p_1,p_2,p_3,\dots,p_i$ 变为 $p_i,p_1,p_2,\dots p_{i-1}$，即让某个前缀往后循环移位一位。

  证明：一次 $k=i-1$，一次 $k=i$ 的操作即可。

不难发现，想要证明从任意 $p$ 出发可以到达任意 $b$，只要证明能交换 $p$ 中任意相邻两项即可。

考虑相邻的两项 $i,i+1$，我们只需要做一次 $k=i-1$ 的操作，把 $p_{[1,i+1]}$ 往后循环移位两位，再做一次 $k=i+1$ 的操作即可交换 $p_i,p_{i+1}$，得证。

所以直接开桶做就行了。

代码如下：

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

const int S=505;

int n,a[S],b[S];
map<int,map<int,int> > mp;

inline void slove()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	if((n&1)&&a[n/2+1]!=b[n/2+1])
	{
		puts("No");
		return;
	}
	if(n==1)
	{
		puts("Yes");
		return;
	}
	mp.clear();
	for(int i=1;i<=n/2;i++) mp[a[i]][a[n-i+1]]++,mp[a[n-i+1]][a[i]]++;
	for(int i=1;i<=n/2;i++)
	{
		if(mp[b[i]][b[n-i+1]]==0)
		{
			puts("No");
			return;
		}
		mp[b[i]][b[n-i+1]]--;
		mp[b[n-i+1]][b[i]]--;
	}
	puts("Yes");
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--) slove();
	return 0;
}