Codeforces Round #721 Palindrome Game (easy/hard) 题解 (Java/C++)

题意

给你一个01构成的字符串，现在Alice和Bob完游戏，两人轮流进行操作，Alice先手。
每一步玩家可以做两种操作。1. 花费1，把一个0改成1。2. 如果当前串不是回文串，则可以把当前字符串反转，且没有花费，且下个人不得立刻再次执行此操作。
当所有0改成1，游戏结束，花费少者得胜。

对于easy version，一开始给你的字符串就是回文串。对于hard version可能是任意串。

题解

1: 考虑最朴素的情况：字符串是回文的，且长度为偶数的情况。那么排除1的点，可以得到形如000000的字符串。对于这种情况，Bob必胜。操作如下：
A:100000; B:100001; A:110001; B:110011; A:111011; B: reverse; A: 111111。
也就是：Alice把任意的0变成1后，Bob就把相应的0也改成1，使字符串保持回文。直到剩下最后两个0，Bob做一次reverse操作。

但是有一个例外：如果字符串是回文的，且长度为偶数，但本身都全是1。那么直接平局。

2: 现在考虑字符串是回文，且长度是奇数的情况。我们发现对于本身回文的字符串几乎是后手必胜，且后手会赢2分。因此如果中间的值是0，那么Alice就会利用此机会获得必胜。

3: 接着考虑不是回文的情况。这种情况Alice可太开心了。首先考虑有超过2个不回文的点。比如00000111。
A:reverse; B:10000111; A:reverse...
我们注意到对于前两种朴素的情况，赢家最多赢2分。因此在达到回文之前，A可以通过reverse获得至少2分的优势。因此处于必胜态。

4: 对于不回文的点不超过2个情况。如果只有1个这样的点，那和第2种情况一样，Alice会利用这一步获胜。

但有一个例外：排除不回文的点后，只剩下一个0。也就是原串形如：001，排除不回文的点后：0。对于这种情况如果Alice第一步是reverse，则Bob会101，这样Alice就必须111。如果Alice第一步011，那么Bob只能111。都是平局。

5: 现在只剩下不回文的点刚好有两个的情况了，比如000011。对于这种情况：
A:reverse; B:100011;
此时A:110011，获得后手。处于必胜态。

代码

Java

C++