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

Submission #116877845 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #117027679 - Codeforces
Codeforces. Programming competitions and contests, programming community