BZOJ3105:[CQOI2013]新Nim游戏(线性基,贪心)

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #define N (109)
 6 #define LL long long
 7 using namespace std;
 8 
 9 int n,a[N],d[31];
10 LL ans;
11 
12 inline int read()
13 {
14     int x=0,w=1; char c=getchar();
15     while (c<‘0‘ || c>‘9‘) {if (c==‘-‘) w=-1; c=getchar();}
16     while (c>=‘0‘ && c<=‘9‘) x=x*10+c-‘0‘, c=getchar();
17     return x*w;
18 }
19 
20 bool Insert(int x)
21 {
22     for (int i=30; i>=0; --i)
23         if (x&(1<<i))
24         {
25             if (!d[i]) {d[i]=x; break;}
26             x^=d[i];
27         }
28     return x;
29 }
30 
31 int main()
32 {
33     n=read();
34     for (int i=1; i<=n; ++i) a[i]=read();
35     sort(a+1,a+n+1);
36     for (int i=n; i>=1; --i)
37         if (!Insert(a[i])) ans+=a[i];
38     printf("%lld\n",ans);
39 }