链接：https://ac.nowcoder.com/acm/contest/67743/B 来源：牛客网 alt

题目大意：

有一个环形数字手串，清楚姐姐先手，智乃后手，谁先不能取数，谁输，输出赢的人的名字。

取数的规则是：如果有两个相邻的数，和为偶数，则可以取，且取完之后可以调换任意两颗数字

做题历程：

定位题目：博弈论/贪心。看榜一眼贪心，AC率非常可观，于是大致读题。随便提交了个贪心代码过了，但没看题解前确实没想出合理的证明。只能隐隐约约感觉跟奇偶性相关

正解的思路：

博弈论的题目一般需要从下一步就败情况入手，这题中，败的情况也很明显，即1 2 1 2 1 2...中间以及首尾都不能同奇数或者偶数。暂且先不考虑只存在奇/偶，最终的数组一定会变成这样。所以最终数组个数一定是偶数

然后推上一步：（先不考虑先手一步都无法走的情况）一定是有两个连续的数出现同奇，或同偶。上一步的数组一定是奇数。并且奇数个数组成的串，一定有相连和为偶数。所以数组的最终个数一定不为奇数（暂且不考虑全奇/偶）

于是答案显而易见，原数组为偶数，则先手必败，因为如果偶数有连续的，拿了之后的奇数一定有连续的，无论怎么移动。后手拿完剩偶数...直到最后两个。原数组为奇数，则后手必败，原理同理。

再考虑特殊情况，全奇全偶。则能全部拿完（完全连续），那最后拿的那个人就是赢家。清楚姐姐先手，于是奇数(1个)则智乃败，偶数(2个)则清楚姐姐败。

代码

题目要求输出获胜者名字，于是：

    if(n%2==0) cout<<"zn\n";
    else cout<<"qcjj\n";

关于博弈论

邓学姐讲了一些博弈论的基本技巧，还给出了几个题目（还翻车了，节目效果拉满）

常用技巧：

1.奇偶性（此题）+2019 HONGKONG B

2.对称性（抄作业）如https://ac.nowcoder.com/acm/problem/223888