Title surface
Title surface
Problem solution
First of all, we know that the nim game must be the first player Failure is if and only if the exclusive OR sum of all stone piles is 0, so our goal is to make the opponent take the stone pile, in any case can not make the remaining stone pile exclusive or sum to 0.
For a situation, if we can select some piles of stones that can make up 0 and stay (because we can’t take all of them, we have to take at least one pile here), then obviously we will lose the first move.
Therefore, as a first mover, the state we leave behind must be a state that cannot make up 0.
Consider what kind of characteristics a situation will have if you can get zero.
For a situation, we find its linear basis. If there are other 01 strings besides the linear basis, then according to the definition of the linear basis, the string in the linear basis must be able to make up the outer string, and then we Then combine the string made with the linear basis and the original string xor to get 0.
So we need to make the remaining position, all strings are in the linear basis.
So we first find the linear basis of a given string, and then take all the strings outside the linear basis and we will definitely win first.
At the same time, in order to make as little as possible, that is to keep as much as possible, so we can according to the size of the string, from small to large linear base plug string.
#include
using namespace std;
#define R register int
#define AC 110
#define LL long long
int n; LL ans;
int s[AC], f[AC];
inline int read()
{
int x = 0;char c = getchar() ;
while(c> '9' || c <'0') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c-'0', c = getchar();
return x;
}
void pre()
{
n = read ();
for(R i = 1; i <= n; i ++) s[i] = read();
sort(s + 1, s + n + 1);< br />}
void work()
{
for(R i = n; i; i --)//Start greedy from high
{< br /> int x = s[i]; bool done = false;
for(R j = 30, maxn = 1 << 30; ~j; j --, maxn >>= 1)
{
if(!(x & maxn)) continue;
if(!f[j]) {f[j] = x, done = true; break;}
else x ^= f[j];
}
if(!done) ans += s[i];//not added to the linear basis Take it away
}
printf("%lld ", ans);
}
int main()
{
// freopen("in.in", "r", stdin);
pre();
work();
// fclose(stdin);
return 0;
}