CF1365F Swaps Again 做题记录

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

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

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

1n5001\le n\le5001ai,bi1091\le a_i,b_i\le10^9

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

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

那么把 aa “对折”,把 (ai,ani+1)(a_i,a_{n-i+1}) 这一对记作 bib_i,那么每次操作相当于是交换了所有满足 ik2i\le \lfloor\frac{k}{2}\rfloorbib_ibki+1b_{k-i+1},并且所有满足 iki\le kbib_i 组内顺序都被交换了。

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

现在问题转化为:

有一个 nn 的排列 pp,请问能否通过任意次交换满足 1ik21\le i\le \lfloor\frac{k}{2}\rfloorpip_ipki+1p_{k-i+1},得到 nn 的另外的一个排列 bb

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


  • 引理:可以使用 22 次操作将 p1,p2,p3,,pip_1,p_2,p_3,\dots,p_i 变为 pi,p1,p2,pi1p_i,p_1,p_2,\dots p_{i-1},即让某个前缀往后循环移位一位。

    证明:一次 k=i1k=i-1,一次 k=ik=i 的操作即可。

不难发现,想要证明从任意 pp 出发可以到达任意 bb,只要证明能交换 pp 中任意相邻两项即可。

考虑相邻的两项 i,i+1i,i+1,我们只需要做一次 k=i1k=i-1 的操作,把 p[1,i+1]p_{[1,i+1]} 往后循环移位两位,再做一次 k=i+1k=i+1 的操作即可交换 pi,pi+1p_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;
}