算法基础之台阶-Nim游戏

台阶-Nim游戏

• 核心思想：博弈论

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

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