BZOJ3105 [CQOI2013] 新Nim游戏
2018 年 03 月 14 日发布.
Description
$k$堆石子,两个人游戏:
首先,A拿走若干堆石子(不能全部拿走)
之后,B拿走若干堆石子(不能全部拿走)
然后从A开始$Nim$游戏。
问A能不能取胜。如果能,A第一步至少要拿走多少石子?
Solution
显然可以取胜。A拿的只剩1堆,B不能拿走,A全拿完,B输了。
考虑A第一次拿完之后,剩下的石子在异或意义下必须线性无关。否则B找出一组石子异或为0,A就输掉了。
那么A拿走的石子尽量少等价于剩下的石子尽量多。
也就是求最大权线性无关组,权值即为石子个数。
线性无关组是一个拟阵(遗传性易证,交换性来说,如果两个线性无关组$X$和$Y$,$|X|<|Y|$,那么$X$张成的线性空间有$|X|$维,$Y$张成的线性空间有$|Y|$维,后者中必能选出一个元素加到$|X|$中线性无关)。
所以我们从大到小判断每堆石子能不能保留即可。
Code
#include <algorithm>
#include <cstdio>
const int K = 105;
int J[32], A[K];
bool mark[K];
bool cmp(int a, int b) { return b < a; }
int main() {
int k;
("%d", &k);
scanffor (int i = 0; i < k; ++i) scanf("%d", &A[i]);
std::sort(A, A + k, cmp);
long long ans = 0;
for (int i = 0, j, l; i < k; ++i) {
for (l = 31, j = A[i]; ~l; --l)
if ((j >> l) & 1) {
if (!J[l]) { J[l] = j; break; }
else j ^= J[l];
}
if (l == -1) ans += A[i];
}
("%lld\n", ans);
printfreturn 0;
}