CF1365F Swaps Again 题解

description：

把一个数字串进行若干次前缀与对应长度的后缀交换位置的操作，问是否能够变成另一个字符串。

solution：

观察 swap 时的性质：任意一对原本在对称位置的数在 swap 后仍然会保持对称。

因为交换 $k$ 长度的前缀也就会对应 $k$ 长度的后缀，一组对称位置的数永远会要么同时互换位置，要不都不变。

这样就简化了题目，我们考虑把每一组对称数的位置都存到一个 map 中，直接 check 对数上是否对等即可。

code：

#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;
}