「HDU1850&POJ2975」题解

题目1

题目2

题意

Nim游戏的第一步有几种必胜走法

思路

考虑Nim游戏的模型

  1. 结束状态是全为$0$, 此时$a_1\otimes a_2\otimes\dots\otimes a_n=0$
  2. $a_1\otimes a_2\otimes\dots\otimes a_n=k$时, 考虑$k$最高的二进制为$1$的一位, 一定有奇数个$a_i$满足该位为$1$, 取其中的任意一个$a_i\otimes k$, 该位会变成$0$, 由于$k$的更高位为$0$, 所以$k$的更高位不会改变, 因此$a_i\otimes k<a_i$, 所以必定存在$a_i$使得$a_1\otimes a_2\otimes\dots\otimes (a_i\otimes k)\otimes\dots\otimes a_n=0$转移到必负状态
  3. $a_1\otimes a_2\otimes\dots\otimes a_n=0$时, 对于任意$a_i$和$k\in N^*$都有$a_1\otimes a_2\otimes\dots\otimes (a_i\otimes k)\otimes\dots\otimes a_n=k\neq0$转移到必胜状态

所以在初始状态, 只要把$a_i$变为$a_i\otimes k(k=\bigotimes_{i=1}^n a_i)$即可, 而初始状态可行方案的总数就是$\sum_{i=1}^n[(a_i\otimes k) < a_i]$

代码

const int N = 1005;

int a[N];

int main () {
  while (true) {
    int n;
    read(n);
    if (!n) {
      break;
    }
    int num = 0;
    for (int i = 1; i <= n; ++i) {
      read(a[i]);
      num ^= a[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      if ((num ^ a[i]) < a[i]) {
        ++ans;
      }
    }
    write(ans), EL;
  }
  return 0;
}

本博客采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可
本文链接:https://blog.seniorious.cc/2019/hdu-1850-poj-2975/