题意
给定两个长度为\(n\)的字符串，\(k\in[1,n]\)，你可以把其中一个字符串长度为\(k\)的前缀与另一个字符串长度为\(k\)的后缀交换，问能不能通过若干次操作，使两个字符串完全相同
题解
我们将\(s1\)中位置\(i(i\in[1,n])\)上的字符和\(s2\)中位置\(n-i+1\)的字符划分为一组，一共有\(n\)组字符，可以发现无论怎么操作，每组两个字符所在的下标之和一定为\(n\)
对于\(s1\)中位置\(i\)的字符，如果要将其移到位置\(j\)，只要以下三步：
- 操作\(s1\)的后缀并令\(k=n-i+1\)
- 如果希望该字符最后出现在\(s2\)，操作\(s2\)前缀并令\(k=1\)
- 操作\(s2\)的前缀并令\(k=n-j+1\)
因此我们可以将任意字符移到任意位置
所以我们可以将问题转化为，给定\(n\)个无序字符组（因为操作2可以看成交换组内字符次序），问能否通过排列它们的次序，形如
\((x_1,y_1),(x_2,y_2)...(x_n,y_n)\)时，使得\(x_1x_2...x_n\)和\(y_1y_2....y_n\)都是回文串
实际上，\(x_i\)和\(y_{n-i+1}\)是位于同一位置的字符，上述条件满足时，由于\(x_i\)和\(y_i\)有可交换性，有\(x_i=x_{n-i+1}\)，通过交换就可以使得\(x_i=y_{n-i+1}\)，所有操作可逆，所以这就是有解的充要条件
当\(n\)是偶数时
每一种字符组出现次数全为偶数即可
当\(n\)是奇数时
中间位置需要特判，放置的字符组必须由两个相同的字符组成，除去该位置后，其余位置的条件与\(n\)为偶数相同
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
typedef pair<char,char> P;
int n;
char s1[N],s2[N];
map<P,int> mp;
void work(){
mp.clear();
int i;
scanf("%d",&n);
scanf("%s",s1+1);
scanf("%s",s2+1);
for(i=1;i<=n;++i){
if(s1[i]>s2[n-i+1]){
++mp[(P){s2[n-i+1],s1[i]}];
}
else{
++mp[(P){s1[i],s2[n-i+1]}];
}
}
if(n%2==0){
for(auto v:mp){
if(v.second%2){
puts("NO");
return;
}
}
puts("YES");
}
else{
bool flag=0;
for(auto v:mp){
if(!flag&&v.first.first==v.first.second){
if(v.second%2){
flag=1;
}
}
else if(v.second%2){
puts("NO");
return;
}
}
puts(flag?"YES":"NO");
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
work();
}
return 0;
}