[bzoj3105] [cqoi2013] 新Nim游戏

Description

传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。 本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和Nim游戏一样。 如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。

Input

第一行为整数k。即火柴堆数。第二行包含k个不超过\(10^9\)的正整数，即各堆的火柴个数。

Output

输出第一回合拿的火柴数目的最小值。如果不能保证取胜，输出-1。

Sample Input

6

5 5 6 6 5 5

Sample Output

21

HINT

k<=100

---

想法

其实这道题只要知道传统Nim游戏的结论就好做了。即\[ a_1 \quad XOR \quad a_2 \quad XOR \quad a_3 …\quad XOR \quad a_n = 0 \quad \to 必败态 \\ a_1\quad XOR\quad a_2 \quad XOR \quad a_3 …\quad XOR\quad a_n \neq 0 \quad \to 必胜态 \] 简单说一下为什么： 1.当 \(a_1=a_2=…=a_n=0\) 时，显然是必败态， \(a_1 \quad XOR\quad a_2\quad XOR\quad a_3 … \quad XOR \quad a_n = 0\) 2.必胜态一定可以走到必败态 观察 \(a_1\quad XOR\quad a_2\quad XOR\quad a_3 …\quad XOR\quad a_n\) 的值的二进制中第一位1，选取火柴数的二进制表示该位也是1的某堆火柴，从中取走可使该位为1，且其余XOR中1也反转的数量的火柴，XOR就变为0。 3.必败态不管怎么走都到必胜态 显然。在某一堆取走一个后\(a_1\quad XOR\quad a_2\quad XOR\quad a_3 …\quad XOR\quad a_n \neq 0\)

有了这个结论，再考虑原题。 第二个游戏者显然是要需走若干堆火柴使剩下所有火柴的XOR为0 那么第一个游戏者就是要取走若干堆火柴使剩下不存在某些火柴XOR为0

XOR是否为0可用线性基维护。 取走的火柴数最少，即要剩下的火柴数最多。 将火柴数从大到小排个序贪心考虑就行了。

---

代码

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N = 105; int n; int a[N],p[35]; bool cmp(int x,int y) { return x>y; } bool ins(int x){ for(int i=31;i>=0;i--){ if((x&(1<<i))==0) continue; if(!p[i]) { p[i]=x; return true; } x^=p[i]; } return false; } int main() { ll sum=0; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); sum+=a[i]; } sort(a,a+n,cmp); for(int i=0;i<n;i++) if(ins(a[i])) sum-=a[i]; printf("%lld\n",sum); return 0; }

转载于:https://www.cnblogs.com/lindalee/p/8543685.html

相关资源：数据结构—成绩单生成器