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 
    
     #include 
     
      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;  scanf("%d", &k);  for (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];  }  printf("%lld\n", ans);  return 0;}