Stone Game II

发表于2020-09-30更新于2023-09-17字数统计558阅读时长4分作者Shane

题目链接

Description

给出 NN 堆石子，现有两个人轮流取石子。假设当前这堆石子个数为 nn，那么一个人进行一次操作后，剩余石子数 kk 必须满足： 0<k<n0<k<n 且 n⊕k<nn⊕k<n。完成此次操作后会新增一堆数量为 n⊕kn⊕k 的石子。
除此之外，每个人有一次进行特殊操作的机会，使增加的一堆的石子数从 n⊕kn⊕k 变为 2n⊕k2n⊕k 。问是否先手必胜。

Solution

考虑每一次操作。经过一次操作（先不考虑特殊操作），一堆 nn 个石子会变成数目为 kk 和 k⊕nk⊕n 的两堆，且这两堆都小于 nn，同时，分开后的两堆数石子在二进制下 1 的个数总和与 nn 在二进制下 1 的个数的奇偶性相同。

容易发现，当每一堆石子个数都是 2 的次幂则无法继续操作，当前操作者输。设一堆 nn 个石子被拆成 mm 堆，每堆都不可再分，则每堆二进制下都只有 1 个 1， 即 nn 在二进制下 1 的个数和 mm 同奇偶。又因为分成 mm 堆需要 m−1m-1 次操作，那么操作次数和 nn 在二进制下 1 的个数的奇偶性是相反的，也就是说如果 nn 在二进制下的 1 的个数是偶数，则会进行奇数次操作，即先手必胜。

对于特殊操作，2k2k 和 2k⊕n2k⊕n 这两堆二进制下 1 的个数之和与 nn 在二进制下 1 的个数同奇偶，而 2k=k<<12k=k<<1 和 kk 在二进制下 1 的个数相同，因此对总的操作次数没有影响。

Code

Stone Game II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;
int T, n, x;

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        static int cntCase = 1;
        cin >> n;
        int cntOpt = 0;
        for (int i = 1; i <= n; i++) {
            cin >> x;
            for (int i = 17; ~i; i--)
                if ((x >> i) & 1) cntOpt ^= 1;
            cntOpt ^= 1;
        }
        printf("Case %d: %s\n", cntCase++, cntOpt & 1 ? "Yes" : "No");
    }
    return 0;
}