Solution. LG4301 [CQOI2013] 新Nim游戏

Description

$k$ 堆石子，两人轮流操作，第一轮中，双方可以拿走若干整堆的石子，可以一堆不拿，不能拿走所有的堆，接下来的游戏规则和 nim 游戏一样。

如果后手必胜，输出 $-1$。否则，输出在先手必胜的情况下，先手第一回合至少要拿的石子个数。

$k\le100$

Solution

不难发现先手一定存在必胜策略，只需拿的只剩一堆即可，所以 $-1$ 情况是不存在的。

nim 游戏的结论是，先手必败当且仅当石子数的异或和为 $0$，要想先手必胜，我们只需让第一回合过后，不存在若干堆石子的石子数异或和为 $0$。

考虑用线性基解决这一问题。

假设现在我们有一个线性基，已经被成功插入的数的集合为 $S$，如果一个数 $x$ 无法被插入线性基，说明这个数能够用 $S$ 中的若干个数异或表示出来，i.e. $S\cup\{x\}$ 中存在若干个数异或和为 $0$。

那么，我们只需要按照某种顺序将每堆的石子个数插入线性基，无法成功插入的堆就是我们需要拿走的堆。

一个显而易见的贪心是从大到小插入，但这样做的正确性保障呢？

如果插入一个大数 $a$ 会导致多于一个小数 $b_{1\dots k}$ 无法插入，我们的贪心就可能是错误的，只需证明不存在这种情况。

具体的，导致多于一个小数无法插入指的是：

• 如果插入 $a$，则 $b_{1\dots k}$ 无法插入线性基。

• 如果不插入 $a$，则 $b_{1\dots k}$ 均能够插入线性基。

前者显然是可能发生的，考虑 $b_{1\dots k}$ 中的一个数 $b_i$，令线性基中已经被成功插入的数的集合为 $S$，不妨设 $b_i=\bigoplus_{x\in S_i}x$，$a\in S_i$，$S_i\setminus a\subseteq S$。

此时，如果不插入 $a$，我们将 $b_i$ 插入线性基，$S$ 变为 $S\cup\{b_i\}$，由 $b_i$ 的表示，其张成的线性空间等价于 $S\cup\{a\}$，那么对于任意一个其他的数 $b_j$，其仍然无法插入线性基。

那么，我们可以得到，插入一个大数，至多会导致一个小数无法插入，于是我们就证明了贪心的正确性。

Code

namespace Main{
    const int N = 105;
    const int L = 30;
    ll k, sum, a[N];
    struct linearBasis{
        int t[L];
        bool insert(int x){
            int save = x;
            for(ri i = L - 1; i >= 0; i--){
                if(!(x >> i & 1)) continue;
                if(!t[i]) return t[i] = x, true;
                else x ^= t[i];
            }
            return false;
        }
    }lb;
    void Main(){
        input(k);
        for(ri i = 0; i < k; i++) input(a[i]);
        sort(a, a + k, greater<int>());
        for(ri i = 0; i < k; i++) if(!lb.insert(a[i])) sum += a[i];
        write(sum);
        return;
    }
} // namespace

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。