Description

两个人玩 $Nim$ 游戏，但后手打算在开始游戏前作弊，选择某几堆各拿走一颗石子，从而使自己必胜。问后手最少要拿走几颗石子。若后手无论如何也不能必胜，输出 -1。

Solution

如果不提前拿走石子，那么当 $a_1⊕a_2⊕…⊕a_n=ans=0$ 时后手必胜。设从第 $i$ 堆拿出一个石子，那么对应项 $a_i$ 变为 $a_i-1$ ，相当于等式两边异或上 $a_i⊕(a_i-1)$ 。

注意到 $a_i⊕(a_i-1)$ 一定形如 $2^k-1$ ，即每一位都是 1。要让 $ans$ 为 0，即二进制下每一位都是 0，考虑从高位到低位枚举 $ans$ 在二进制下为 1 的位 $k$ ，如果存在 $i$ 使得 $a_i⊕(a_i-1)$ 恰好有 $k$ 位，那么一定从第 $i$ 堆石子拿走一个，等价于使 $ans$ 异或上 $a_i⊕(a_i-1)$ ，这样 $ans$ 第 $k$ 位就变为 0。最后，如果无法使 $ans=0$ 则后手必败。

Code

Cheating Nim

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAXN = 1E5 + 5;
int n, a[MAXN], sum, f[31], cnt;

template <class T>
void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        sum ^= a[i];
        a[i] ^= a[i] - 1;
        for (int j = 30; ~j; j--)
            if ((a[i] >> j) & 1) {
                f[j] = 1;
                break;
            }
    }
    for (int i = 30; ~i; i--)
        if ((sum >> i) & 1)
            if (f[i]) sum ^= (1 << (i + 1)) - 1, cnt++;
    printf("%d\n", sum ? -1 : cnt);
    return 0;
}