NC17370. Playing games
描述
Niuniu likes playing games. He has n piles of stones. The i-th pile has ai stones. He wants to play with his good friend, UinUin. Niuniu can choose some piles out of the n piles. They will play with the chosen piles of stones. UinUin takes the first move. They take turns removing at least one stone from one chosen pile. The player who removes the last stone from the chosen piles wins the game. Niuniu wants to choose the maximum number of piles so that he can make sure he wins the game. Can you help Niuniu choose the piles?
输入描述
The first line contains one integer n (1 ≤ n ≤ 500000), which means the number of piles.
The second line describes the piles, containing n non-negative integers, a1 a2 … an, separated by a space. The integers are less than or equal to 500000.
输出描述
Print a single line with one number, which is the maximum number of piles Niuniu can choose to make sure he wins. If Niuniu cannot always win whatever piles he chooses, print 0.
示例1
输入:
8 1 9 2 6 0 8 1 7
输出:
7
说明:
Niuniu can choose the piles {1,9,6,0,8,1,7} to make sure he wins the game.C++14(g++5.4) 解法, 执行用时: 242ms, 内存消耗: 4704K, 提交时间: 2018-09-11 21:17:14
#include<iostream>
#include<cstdio>
const int N = 1 << 21;
int a[N], n, b[N];
void FWT(int *a, int n, bool inv = 0) {
int x, y;
for (int i = 1; i<n; i <<= 1)
for (int j = 0, p = i << 1; j<n; j += p)
for (int k = 0; k<i; k++) {
x = a[j + k]; y = a[i + j + k];
a[j + k] = x + y; a[i + j + k] = x - y;
if (inv) a[j + k] >>= 1, a[i + j + k] >>= 1;
}
}
int main() {
scanf("%d", &n); int sum = 0, x;
for (int i = 0; i<n; i++) scanf("%d", &x), a[x] = 1, sum ^= x;
b[0] = 1;
int ans = 0; int m = 1 << 19; FWT(a, m);
while (!b[sum]) {
ans++;
FWT(b, m); for (int i = 0; i < m; i++) b[i] = b[i] * a[i];
FWT(b, m, 1);
for (int i = 0; i < m; i++) if (b[i]) b[i] = 1;
}
printf("%d\n", n - ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 121ms, 内存消耗: 4460K, 提交时间: 2018-08-11 16:48:58
#include<bits/stdc++.h>
using namespace std;
const int maxn=500011;
int a[maxn],n,Max;
int main(){
scanf("%d",&n); int aim=0;
for (int i=1;i<=n;++i) scanf("%d",a+i);
for (int i=1;i<=n;++i) aim^=a[i];
sort(a+1,a+n+1); int N=unique(a+1,a+n+1)-a-1;
Max = a[N];
for (; Max != (Max & -Max); Max += (Max & -Max)) ;
static int M[524288];
memset(M,63,sizeof(M));
if (aim==0){printf("%d\n",n); return 0;}
for (int i=1;i<=N;++i) if (a[i]==aim){printf("%d\n",n-1); return 0;}
for (int i=1;i<=N;++i) M[a[i]]=1;
for (int i=1;i<=N;++i) if (M[a[i]^aim]==1){printf("%d\n",n-2); return 0;}
for (int i=1;i<=N;++i){
for (int j=0;j<Max;++j)
M[j^a[i]]=min(M[j^a[i]],M[j]+1);
}
printf("%d\n",n-M[aim]);
}