题意

给定两个字符串，可以任意选择s串的一段和t串的相同长度的一段进行翻转，无限次数，问能否通过翻转使得两个字符串相等。

分析

看了题解发现思路很巧妙。
无限次数的子串翻转其实就是相邻两个字符的交换。
首先字符串出现次数不同的肯定不行。
然后如果某个字符出现次数大于1的，肯定可以，证明就是，先将s串通过交换相邻两个字符得到有序字符串，t串对应的可以随便交换；此时s串是有序的，且存在至少一对相邻字符是相同的，那么接下来t串通过交换相邻的字符得到有序字符串，同时s串就只交换一对相同的字符，保证s串不变。
除去上面两个情况，剩下的就是字符最多只出现一次的，离散化就相当于一个排列，对于一个排列来说，交换两个相邻的数可以改变逆序数的奇偶性，两个串同时改变，也就是两个串的奇偶性保持一致，所以求出每个原串的逆序数判断即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+50;

char s[N],t[N];

int q,n,cnt[30];

int c[120];

int lowbit(int x){

    return x&(-x);

}

void add(int i,int x){

    while(i<=100){

        c[i]+=x;

        i+=lowbit(i);

    }

}

int sum(int i){

    int ans=0;

    while(i){

        ans+=c[i];

        i-=lowbit(i);

    }

    return ans;

}

int main(){

    scanf("%d",&q);

    while(q--){

        scanf("%d",&n);

        scanf("%s",s+1);

        scanf("%s",t+1);

        memset(cnt,0,sizeof(cnt));

        bool dou=false;

        for(int i=1;i<=n;i++){

            cnt[s[i]-'a']++;

            if(cnt[s[i]-'a']>=2){

                dou=true;

            }

        }

        for(int i=1;i<=n;i++){

            cnt[t[i]-'a']--;

        }

        bool flag=true;

        for(int i=0;i<26;i++){

            if(cnt[i]){

                flag=false;

                break;

            }

        }

        if(!flag){

            printf("NO\n");

        }else{

            if(dou){

                printf("YES\n");

            }else{

                memset(c,0,sizeof(c));

                int ss=0;

                for(int i=1;i<=n;i++){

                    ss+=i-1-sum(s[i]-'a'+1);

                    add(s[i]-'a'+1,1);

                }

                memset(c,0,sizeof(c));

                int tt=0;

                for(int i=1;i<=n;i++){

                    tt+=i-1-sum(t[i]-'a'+1);

                    add(t[i]-'a'+1,1);

                }

                if(ss%2==tt%2){

                    printf("YES\n");

                }else{

                    printf("NO\n");

                }

            }

        }

    }

    return 0;

}

巴特西

Codeforces1256F_Equalizing Two Strings

题意

分析

代码

最新文章

热门文章