「BZOJ-3105」[cqoi2013]新Nim游戏(博弈+线性基)

发表于 | 分类于 ，

BZOJ3105-[cqoi2013]新Nim游戏
有n堆火柴堆，先手和后手可以依次取走若干堆火柴堆（不能全部取走），然后进行Nim游戏，先手如何取才能保证必胜，并在保证胜利的情况下使他取的火柴总数最小。

题解

标准的Nim游戏中，只要是所有火柴堆的火柴数目异或值为0，那么先手必败，否则先手必胜。

在取完前两轮后这个游戏就是个标准的Nim博弈。那么在先手取完后，后手一定会取走若干个火柴堆，使剩下的异或和为0。

那么对于先手，应该取走若干个火柴堆，使剩下的火柴堆不存在异或和为0的子集，也就是使剩下的火柴堆成为一个线性极大无关组。

又因为要使先手所取的火柴总数最小，我们把火柴堆从大到小排序，依次插入线性基，不能插入线性基的元素就是先手要取的火柴堆。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>

using namespace std;

int d[32];

bool ins(int x)
{
    for(int i = 31; i >= 0; i --)
    {
        if((x >> i) & 1)
        {
            if(d[i]) x ^= d[i];
            else { d[i] = x; return true; }
        }
    }
    return false;
}

int main()
{
    int n, a[105];
    long long res = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    sort(a, a + n);
    for(int i = n - 1; i >= 0; i --) if(!ins(a[i])) res += a[i];
    printf("%lld\n", res);
    return 0;
}