给出两个长度为 的数列 ,你需要判断能否在数次操作后使得 与 相同。
操作是指你可以选择一个 ,之后交换 的长度为 的前缀和长度为 的后缀。
例如对于 ,选择 ,那么交换后会得到 。
,。
结论题,别的题解都没给证明,我来证一下吧。
观察到每次操作中对于所有满足 的 都进行了 ,而和 以序列中点对称的元素是 ,操作中同时进行了 ,所以 和 在交换之后仍然以序列中点对称。
那么把 “对折”,把 这一对记作 ,那么每次操作相当于是交换了所有满足 的 和 ,并且所有满足 的 组内顺序都被交换了。
不难发现,组内顺序是可以随便交换的,只要做一次 ,一次 ,一次 即可。
现在问题转化为:
有一个 的排列 ,请问能否通过任意次交换满足 的 和 ,得到 的另外的一个排列 ?
这个问题对于任意 的答案都是可以,证明如下:
-
引理:可以使用 次操作将 变为 ,即让某个前缀往后循环移位一位。
证明:一次 ,一次 的操作即可。
不难发现,想要证明从任意 出发可以到达任意 ,只要证明能交换 中任意相邻两项即可。
考虑相邻的两项 ,我们只需要做一次 的操作,把 往后循环移位两位,再做一次 的操作即可交换 ,得证。
所以直接开桶做就行了。
代码如下:
#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;
}