【POJ】2234 - Matches Game（尼姆博弈 / Nim游戏）

比眉伴天荒 2023-05-28 14:20 99阅读 0赞

原题链接：http://poj.org/problem?id=2234

思路： 尼姆博弈的裸题。

  • 如果 n = 1，那么先取的玩家将这堆火柴全取完获得胜利，输出 “Yes”
  • 如果 n = 2，每堆的数量分别为 n1，n2
    ①：n1 = n2 ，第一个玩家取一部分火柴，第二个玩家在另一堆通过取与第一个玩家相等数量的火柴获得胜利，输出“No”
    ②：n1 ≠ n2 ，第一个玩家先把两堆多出来的火柴取走，再取与第二个玩家相等数量的火柴获得胜利，输出“Yes”
  • 如果 n > 2，先手能够在非平衡状态下取胜，后手能够在平衡状态下取胜。

结论：n 堆石子异或和不为 0 ，先手必胜，否则先手必输。

Code：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <queue>
  6. using namespace std;
  7. typedef long long ll;
  8. int main(){ 
  9.     int n;
  10.     while(cin>>n){ 
  11.         int ans=0,x;
  12.         for(int i=1;i<=n;i++){ 
  13.             cin>>x;
  14.             ans^=x;
  15.         }
  16.         if(ans) cout<<"Yes"<<endl;
  17.         else    cout<<"No"<<endl;
  18.     }
  19.     return 0;
  20. }

发表评论

表情：
评论列表 （有 0 条评论，99人围观）

还没有评论，来说两句吧...

相关阅读

    相关 尼姆博弈 HDU2176

    有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。 这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，

    àì夳堔傛蜴生んèńàì夳堔傛蜴生んèń/ 0 赞/ 216 阅读

    相关 LeetCode 292 Nim Game（Nim游戏）

    你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。 你们是聪明人，每一步都是最优解

    电玩女神电玩女神/ 0 赞/ 318 阅读