[AtCoder ABC048] D- An Ordinary Game(博弈)

题意：

给一个字符串s,相邻字符都不相等。A,B两人博弈，取法是取走某一个字符后，这个字符的前后不能相等，否则就不能取。并且第一个和最后一个不能取。谁无法取谁就输了，A先手。

思路：

首先，我们看一下最不极端的字符串abcdef,在这种情况下。bcde都能够被取走，B赢。
然后，再看一下最极端的字符串ababab,在这种情况下。一个都不能被取走，B赢。
其实不难发现，在ababab中，去掉第二和第三个字符后为abab，此时中间ba又能够被取走。只剩下第一个和最后一个ab。既然如此，我们依然可以认为中间的baba是可以被取走的。
所以在前后不相等的情况下，任何一个字符串都可以由极端的和不极端的组合而成
（可以认为去掉所有不极端，就只剩下极端了）
既然如此，那么答案就是固定的了，字符串长度为奇数A赢，偶数B赢。
是不是很简单？其实还差一点。题目中还提到一点第一个和最后一个不能取，如果第一个和最后一个相等那么最后会剩下三个不能取，比如aba。所以加一个判断，相等长度减一即可。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s; cin>>s;
    int len=s.size();
    if(s[0]==s[s.size()-1]) len--;
    if(len%2==0)
        cout<<"Second"<<endl;
    else
        cout<<"First"<<endl;
    return 0;
}

最后

以上就是热心学姐最近收集整理的关于[AtCoder ABC048] D- An Ordinary Game(博弈)的全部内容，更多相关[AtCoder内容请搜索靠谱客的其他文章。