传送门
F:Equalizing Two Strings(我见过最水的F)
题意:给你两个字符串S,T 你可以反转两个串的任意区间,任意次数,前提是两个串的翻转次数相同,每次反转区间的长度相同。问你能不能是这两个串相等
思路:首先两个串的不同字母的数量必须相等,
然后因为可以反转任意次,那么其实只要这两个串中有一个串是出现重复字母的 就一定能使这两个串相等(就相当于你一直翻转这俩重复的字母,然后去操作另一个串,
使他俩相等)
如果字母构成相同,并且没有重复字母。在s中选择一个len = 2的区间,再在t中选择一个len = 2的区间,就相当于在t中选择两个len = 2的区间。
那么只要t能在偶数次len = 2的操作中得到s,就可行,否则就不可行。n^2模拟一下就可以
#include<bits/stdc++.h>
using namespace std;
typedef long long L;
char s1[200010];
char s2[200010];
int n1[50];
int n2[50];
int main()
{
int q;
scanf("%d",&q);
while(q--){
int n,f=0;scanf("%d %s %s",&n,s1+1,s2+1);
for(int i=0;i<26;i++) n1[i]=0,n2[i]=0;
for(int i=1;i<=n;i++){
n1[s1[i]-'a']++;
n2[s2[i]-'a']++;
}
for(int i=0;i<26;i++){
if(n1[i]!=n2[i]){//cout<<i<<endl;
// cout<<n1[i]<<","<<n2[i]<<endl;
f=1;puts("NO");break;
}
}
if(f) continue;
for(int i=0;i<26;i++){
if(n1[i]>1||n2[i]>1){f=1;break;}
}
if(f){puts("YES");continue;}
int ans=0;
for(int i=1;i<n;i++){
for(int j=i;j<=n;j++){
if(s2[i]==s1[j]){
for(int k=j;k>i;k--){
ans++;
swap(s1[k],s1[k-1]);
}
break;
}
}
}
if(ans&1) puts("NO");
else puts("YES");
}
}
E Yet Another Division Into Teams
简单dp模拟一下就好了,就是太麻烦了