CF276B Little Girl and Game
Tag：字符串、博弈
题目描述
给定一个字符串， 一个玩家在一次操作中可以选择删除一个字符。 如果一个玩家能在删除一个字符之后把这个字符串重排成一个回文串， 那么这个玩家就获胜。
问谁会获胜。
数据说明：
\(1 \le |s| \le 10^3\)
分析
首先看到回文串可以很自然的想到回文串的两种形式：
-
所有字符都出现了两次。
-
有一个字符出现了一次，其他字符出现两次。
所以显而易见的一开始要先计数一下。 考虑一下比较显然的两个先手必胜：
-
全部都是偶数
-
只有一个奇数
然后我们考虑有多个奇数的时候。
假设有奇数个奇数，先手取一个奇数， 后手如果也跟着取奇数，最后会给先手送一个必胜态， 如果取偶数，先手只要也继续取奇数，这样就建立了一个岛取奇数的双射。 所以可以证明奇数个奇数的时候是先手必胜。
反之，偶数个奇数是后手必胜。
按照上述分析开个桶计数， 统计奇数个数，判断答案。
代码实现
void NeverSayNever() {
string str; cin >> str;
vector<int> cnt(26);
for(auto &x : str){
cnt[x - 'a']++;
}
int cnt1 = 0;
for(auto &x : cnt){
if(x & 1) cnt1++;
}
if(cnt1 == 0 || cnt1 & 1){
cout << "First" << endl;
}else{
cout << "Second" << endl;
}
}
额外思考
无思考价值。
日志
本页面创建于 2024/6/26 23:51