题解 CF1365F 【Swaps Again】

更佳的阅读效果

description:

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

solution:

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

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

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

code:

上一个版本贴错代码了,感谢评论区 1 楼的神仙指出,已更换。

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

发表于 2020-06-10 20:40:27 in 题解