算法基础之台阶-Nim游戏

台阶-Nim游戏

• 核心思想：博弈论

  （）
  • 可以看作第i阶台阶上有i个含有i个石子的堆
  • 这样所有台阶上一共n!个堆就变成了经典Nim
  • 优化：发现偶数阶台阶上2n堆异或 = 0 , 奇数阶台阶异或 = 原本石子数量
    • 因此 当遍历到奇数阶时异或一下就行

    •   #include   #include     using namespace std;    const int N = 100010;    int main()  {      int n;      scanf("%d", &n);        int res = 0;      for (int i = 1; i           int x;          scanf("%d", &x);          if (i & 1) res ^= x;      }        if (res) puts("Yes");      else puts("No");        return 0;  }