CF276B Little Girl and Game

本文主要是介绍CF276B Little Girl and Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://codeforces.com/problemset/problem/276/B

题意:

有一个字符串s,两个人轮流操作,每次操作必须删去一个字符

如果轮到B,玩家B可以把字符串重新排列成一个回文串,B就赢了

思考:

回文串,与字符的位置,数量都有关系,但是位置在这里可以被忽略掉

所以我们只考虑字符的数量

一般说到数量 就容易去想到 奇数 偶数

让我们来想想奇偶对于游戏胜负有什么影响

1:不妨先试试全是偶数的时候:比如aaaa,aabb,aabbcc...可以发现 这些都可以重新组合成一个回文串。 因此 先手赢

2:再去试试全是奇数的时候:比如aaa,aaabbb,abcde...可以发现 如果只有奇数次 那么只有一个字母的时候 先手赢

3:现在如果奇数偶数都有:aabbb,aaabb....可以发现 偶数次的字母不影响 因此可以去除出现过偶数次的字母 统计出现奇数次的字母 再判断奇偶性得出答案

#include<iostream>
#include<map>
using namespace std;
map<char,int>mp;
int main() {string s;cin>>s;for(auto c:s) {mp[c]++;}int sum=0;int even=0,odd=0;for(auto c:mp) {if(c.second%2!=0) {sum+=c.second;odd=1;} else {even=1;}}if(odd&&!even&&mp.size()==1) {cout << "First" << endl;} else if(even&&!odd) {cout << "First" << endl;} else {if(sum%2==0) {cout << "Second" << endl;} else cout << "First" << endl;}}

这篇关于CF276B Little Girl and Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---