Making Anti-Palindromes
Codeforces Round 867 (Div. 3)
E. Making Anti-Palindromes
挺好的一道鸽巢原理题。
思路：
贪心地来想，我们没必要动本来就不同的一对，而对相同的对，我们可以让它们互相之间进行交换，这样一次交换就可以拆散两对相同的字符对。
不过理想很美好，实际实施会发现会出现问题。首先，如果长度为奇数，中间的那个字符一定等于自己，这时一定无解，所以要特判。其次，有可能相同的对都是同一种字符，它们相互之间相互交换的都是相同的字符，这时就会出错。
所以我们需要保证某两对字符之间交换的两个字符是不同的。其实换个想法，就相当于不同的两对字符进行一次操作抵消掉了（也就是变成两对满足条件的对了）。这就和这种鸽巢原理的板题很像了，题解。
我们设字符串长度为
n
n
n，其中一共有
t
o
t
tot
tot 对相同的对，其中出现次数最多的字符
c
h
ch
ch 的对有
m
x
mx
mx 对。依据上面那道题的分析可以分成两部分：
-
m
x
≤
t
o
t
−
m
x
mxle{tot-mx}
mx≤tot−mx 时，这时可以两两配对抵消，总共需要交换⌈
t
o
t
2
⌉
leftlceildfrac{tot}2rightrceil
⌈2tot⌉ 次。 -
m
x
>
t
o
t
−
m
x
mxgt{tot-mx}
mx>tot−mx 时，这时单靠相同的对之间两两抵消会剩下一些相同的对，它们都是字符c
h
ch
ch。不过我们还可以用其他的不相同的对来交换。不过也有限制，如果一对不相同的对中有一个字符为c
h
ch
ch，我们就不能拿这个对的字符来换。最后换好后，最多是每个对都含一个c
h
ch
ch，也就是字符的个数最多不能超过n
2
frac n2
2n。满足条件则一定可以换出满足条件的串。所以还是两种情况：- 字符
c
h
ch
ch 的总个数l
s
t
≤
n
2
lstledfrac n2
lst≤2n 时，因为每次交换一定选择一个c
h
ch
ch，交换次数等于相同的c
h
ch
ch 的对数m
x
mx
mx。 - 字符
c
h
ch
ch 的总个数l
s
t
>
n
2
lstgtdfrac n2
lst>2n 时，无解。
- 字符
code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
int T,n;
string s;
int main(){
cin>>T;
while(T--){
cin>>n>>s;
if(n&1){
puts("-1");
continue;
}
s=" "+s;
map<char,int> mp;
int tot=0,maxx=0,lst=0;
char ch;
for(int i=1;i<=n/2;i++)
if(s[i]==s[n-i+1]){
mp[s[i]]++;
tot++;
if(mp[s[i]]>maxx){
maxx=mp[s[i]];
ch=s[i];
}
}
if(tot==0){
puts("0");
continue;
}
for(int i=1;i<=n;i++)lst+=(s[i]==ch);
if(lst>n-lst)puts("-1");
else if(tot-maxx>=maxx)cout<<(tot+1)/2<<endl;
else cout<<maxx<<endl;
}
return 0;
}