题目链接：hdu 4111 Alice and Bob
题目大意；Alice和Bob两个玩游戏，有N堆石子，每次可以从一堆中取走一个石子，或者是合并两堆石子，Alice先，问
说最后谁赢。
解题思路：NP定理，写出一些NP定理找到规律，再用归纳的方法证明。
统计1的个数c，以及非1情况下的步数s，包括合并。
- c为奇数，s不等于2：那么先手必胜。
- s为2或者为0：c为3的倍数是先手必败。
- 否则的话，s为奇数时先手必胜。
首先没有1的情况下很好证明，就是总的步数和为奇数时为先手必胜态，N点。相反，如果为偶数就是P点。（这种情况
下必胜的人只要保证任意一堆石子的个数不会小于2即可，直到最后只剩下一堆，因为1是一个比较特殊的存在）
再者证明奇数个1且s不为2的时候为必胜态，从一个1的开始，假设现在有一个1和s，如果s为奇数，那么先手可以合并
两堆石子；如果s是偶数，先手可以拿走1；所以这种情况下一定是先手必胜，因为移动1可以选择少掉一步或者两步。
那么现在就是两个1和s的情况，如果其中一个人先消耗掉一个1，和s合并，那么剩下的状态是(1,s+1)的N点；取走1，
剩下(1,s)同样是N点；合并两个1，(2,s)==>(s+3)的状态，如果s为奇数，那么即为P态，对应的刚才先手就是必胜，反之
则是必败，这种情况归纳到结论中的第三条。那么三个1的情况下就可以消耗一个1更变s的奇偶性。
不过在s=2或者s=0的时候属于特殊情况，因为2去掉一个之后就变成了1，s为0时为全1，通过上面的规律，我们已经知
道了1是比较特殊的。那么现在有NP图
不难发现，这是c如果是3的倍数，那么一定是先手必败态。#include#include #include using namespace std; bool judge (int c, int s) { if (c&1 && s > 2) return true; if (s == 0 || s == 2) return c % 3; return s&1; } int main () { int cas; scanf("%d", &cas); for (int kcas = 1; kcas <= cas; kcas++) { int n, s = 0, c = 0, x; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &x); if (x == 1) c++; else { if (s == 0) s = x; else s += x + 1; } } printf("Case #%d: %s\n", kcas, judge(c, s) ? "Alice" : "Bob"); } return 0; }