题解 CF1365F 【Swaps Again】
ShineEternal
2020-06-10 20:40:27
[更佳的阅读效果](https://vipblog.github.io/fFLyfTS-c/)
## description：
把一个数字串进行若干次前缀与对应长度的后缀交换位置的操作，问是否能够变成另一个字符串。
## solution：
观察 swap 时的性质：任意一对原本在对称位置的数在 swap 后仍然会保持对称。
因为交换 $k$ 长度的前缀也就会对应 $k$ 长度的后缀，一组对称位置的数永远会要么同时互换位置，要不都不变。
这样就简化了题目，我们考虑把每一组对称数的位置都存到一个 map 中，直接 check 对数上是否对等即可。
## code：
上一个版本贴错代码了，感谢评论区 1 楼的神仙指出，已更换。
```cpp
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
int a[505],b[505];
map<pair<int,int>,int>mp;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
mp.clear();
int n;
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%2==1&&a[(n+1)/2]!=b[(n+1)/2])
{
printf("No\n");
continue;
}
for(int i=1;i<=(n+1)/2;i++)
{
mp[make_pair(min(a[i],a[n-i+1]),max(a[i],a[n-i+1]))]++;
}
int flag=0;
for(int i=1;i<=(n+1)/2;i++)
{
//mp[make_pair(min(b[i],b[n-i+1]),max(b[i],b[n-i+1]))]--;
if(--mp[make_pair(min(b[i],b[n-i+1]),max(b[i],b[n-i+1]))]<0)
{
flag=1;
break;
}
}
if(flag==1)
{
printf("No\n");
}
else
{
printf("Yes\n");
}
}
return 0;
}
```