题目链接:https://codeforces.com/problemset/problem/1256/F
解题思路:
任意的翻转都可以认为是翻转若干个长度为2的,交换两个数主要奇数次翻转。两个串可以翻转成一样,那么一定可以再花费一样的翻转次数变成有序的字符串,连续两个相等的字符翻转任意数次是一样的,所以只要有两个字符一样一定可以。接下来就是看冒泡排序的次数了。很明显两个字符翻转偶数次等于没有翻转,所以只要看他们取模二的区别。
#include<bits/stdc++.h>
using namespace std;
const int mx = 2e5+10;
char s1[mx];
char s2[mx];
int cnt1[30],cnt2[30];
int n;
bool solve() {
memset(cnt1,0,sizeof(cnt1));
memset(cnt2,0,sizeof(cnt2));
for (int i=0;i<n;i++) {
cnt1[s1[i]-'a']++;
cnt2[s2[i]-'a']++;
}
for (int i=0;i<26;i++) if (cnt1[i] != cnt2[i])
return 0;
for (int i=0;i<26;i++) if (cnt1[i] > 1)
return 1;
int rex1 = 0,rex2 = 0;
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
if (s1[j] < s1[i]) rex1++,swap(s1[j],s1[i]);
if (s2[j] < s2[i]) rex2++,swap(s2[j],s2[i]);;
}
}
return rex1%2 == rex2%2;
}
int main() {
int t;
scanf("%d",&t);
while (t--) {
scanf("%d",&n);
scanf("%s%s",s1,s2);
puts(solve()?"YES":"NO");
}
return 0;
}
标签:思维,字符,int,1256F,cnt2,cnt1,CodeForcese,mx,翻转 From: https://blog.51cto.com/u_12468613/6384516