Making Anti-Palindromes

题目链接

Codeforces Round 867 (Div. 3)

E. Making Anti-Palindromes

挺好的一道鸽巢原理题。

---

思路：

贪心地来想，我们没必要动本来就不同的一对，而对相同的对，我们可以让它们互相之间进行交换，这样一次交换就可以拆散两对相同的字符对。

不过理想很美好，实际实施会发现会出现问题。首先，如果长度为奇数，中间的那个字符一定等于自己，这时一定无解，所以要特判。其次，有可能相同的对都是同一种字符，它们相互之间相互交换的都是相同的字符，这时就会出错。

所以我们需要保证某两对字符之间交换的两个字符是不同的。其实换个想法，就相当于不同的两对字符进行一次操作抵消掉了（也就是变成两对满足条件的对了）。这就和这种鸽巢原理的板题很像了，题解。

我们设字符串长度为 $n$，其中一共有 $tot$ 对相同的对，其中出现次数最多的字符 $ch$ 的对有 $mx$ 对。依据上面那道题的分析可以分成两部分：

1. $mx\le tot-mx$ 时，这时可以两两配对抵消，总共需要交换 $\lceil \frac{tot}{2}\rceil$ 次。
2. $mx>tot-mx$ 时，这时单靠相同的对之间两两抵消会剩下一些相同的对，它们都是字符 $ch$。不过我们还可以用其他的不相同的对来交换。不过也有限制，如果一对不相同的对中有一个字符为 $ch$，我们就不能拿这个对的字符来换。最后换好后，最多是每个对都含一个 $ch$，也就是字符的个数最多不能超过 $\frac{n}{2}$。满足条件则一定可以换出满足条件的串。所以还是两种情况：
   1. 字符 $ch$ 的总个数 $lst\le \frac{n}{2}$ 时，因为每次交换一定选择一个 $ch$，交换次数等于相同的 $ch$ 的对数 $mx$。
   2. 字符 $ch$ 的总个数 $lst>\frac{n}{2}$ 时，无解。

code：

#include 
#include 
#include 
#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44