跳到主要内容

Codeforces Round 169 (Div. 2) B. Little Girl and Game

B. Little Girl and Game​

The Little Girl loves problems on games very much. Here's one of them.

Two players have got a string s, consisting of lowercase English letters. They play a game that is described by the following rules:

The players move in turns; In one move the player can remove an arbitrary letter from string s. If the player before his turn can reorder the letters in string s so as to get a palindrome, this player wins. A palindrome is a string that reads the same both ways (from left to right, and vice versa). For example, string "abba" is a palindrome and string "abc" isn't. Determine which player will win, provided that both sides play optimally well — the one who moves first or the one who moves second.

Input​

The input contains a single line, containing string s(1 ≤ ∣s∣  ≤  103)s (1 ≤ |s|  ≤  10^3) . String s consists of lowercase English letters.

Output​

In a single line print word "First" if the first player wins (provided that both players play optimally well). Otherwise, print word "Second". Print the words without the quotes.

题目大意​

给你一个字符串，每回合可以进行一次操作：

  • 删掉任意一个字符
  • 如果可以重组变成回文串，那么就赢了

问第一个人赢还是第二个人

思路​

很显然，答案和奇数字符出现的次数和偶数出现的次数有关，对于初始状态来说，偶数字符出现的次数不会影响到最后的答案，如果字符次数为奇数的个数大于1：

  • 字符次数为奇数的个数为奇数时，那么是必胜的，因为可以先把字符出现次数为偶数的都去掉，也可以把字符次数为奇数的个数的字符都去掉到只剩下一个，这样整个字符串变成了全是不同字符的字符串，同时字符串长度为奇数，那么每次没人拿一个，最后肯定只剩下一个给第一个人，此时这个为回文串，同时还需要注意一开始字符次数全为偶数的情况，也是第一个人获胜

代码​

#include <bits/stdc++.h>

using namespace std;


int main() {
#ifndef ONLINE_JUDGE
    freopen("../test.in", "r", stdin);
    freopen("../test.out", "w", stdout);
#endif
    string s;
    cin >> s;
    map<char, int> m;
    for (auto x: s) {
        m[x]++;
    }
    int cnt = 0;
    for (auto x: m) {
        if (x.second & 1)cnt++;
    }
    if (cnt==0 || cnt&1){
        cout<<"First"<<endl;
    }else{
        cout<<"Second"<<endl;
    }
    return 0;
}
0%