题解：P10558 [ICPC2024 Xi'an I] XOR Game

· · 题解

虽然蒟蒻不是很会做博弈论的题，但是这题的结论还是很显然的。

先看只有一个数的情况：假设这个数有奇数个，那不难发现 Alice 是最后一个操作，那他总有办法把这个数得到，如果有偶数个那 Bob 就是最后一个，那他总有办法把这个数消除。

换言之：最后一个取这个数的人决定这个数的去留。

又会发现对于一个数如果有奇数个，那把这个数拿完之后下一个先操作的人会轮换，偶数个则不会。

那么我们分类讨论：

situation 1：有奇数个的数有奇数个

不难发现把个数是奇数的数拿完下一次操作就会变成 Bob，那他一定会把一个偶数变成奇数，那这个数 Alice 就可以得到。又因为这个数最开始是偶数，所以拿完之后又是 Bob 拿，那么这些有偶数个的数就都会被 Alice 得到。

那既然这样是不是只要有奇数个的数有奇数个就代表所有数 Alice 都可以得到呢？显然不是，如果有某个数只有 1 个，那么 Bob 直接拿这个数 Alice 就肯定无法得到，所以他们会轮流把 1 取完，剩下的数就都归 Alice。

situation 2：有奇数个的数有偶数个

这个时候则与上一个情况刚好相反，如果 Alice 拿一个奇数，Bob 跟着拿一个奇数，这样奇数个数还是偶数个。如果 Alice 拿一个偶数，Bob 继续拿这个数，那这个数就还是偶数，最后一定每一个数最后一个都是 Bob 来拿的，也就是说 Alice 一个也拿不到。

不过也和上一个一样，1 是特殊情况，只有 1 是 Alice 有可能得到的数，所以 Alice 又会和 Bob 轮流拿 1，剩下的数 Alice 都得不到。

简单模拟即可，复杂度 \Theta(n)。