HDU 1730 Northcott Game 博弈论 尼姆博弈

妖狐艹你老母 2022-12-02 10:54 280阅读 0赞

原题链接:HDU 1730 Northcott Game

题目描述

hdu1730
1730


思路

我们先从最终态也就是必败态看,最终所有黑白两棋之间的距离为0,也就是说,每个黑白棋之间的距离异或起来是0,这就是必败态。
为什么呢,我们来推一下,当前一个人走完,后一个人一定可以走到使得所有距离异或起来为0的某个位置,而另一个人只能面对这个状态走棋而不能再创造这个状态,如此反复,直到最后一轮,其面对的状态仍是必败态,也就是最终态,所有黑白棋距离为0,则其必输。注: 博弈时,每个人都会走当前最优策略,所以每个人都会尽量给对方创造必败态,给自己创造必胜态。
那么我们就看最初时刻,每行的黑白棋距离异或起来是否为0,若为0,先手必输,因为这就已经是必败态了;若不为0,则先手必赢,因为先手可以首先创造一个必败态给后手。
这就是四大博弈之一的尼姆博弈


代码解析

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int main()
  5. {
  6. int n,m,a,b,s;
  7. while(cin >> n >> m)
  8. {
  9. s = 0;
  10. for(int i = 0;i < n;i++)
  11. {
  12. cin >> a >> b;
  13. int d = max(a,b) - min(a,b) - 1;
  14. s ^= d;
  15. }
  16. if(s)
  17. cout << "I WIN!" << endl;
  18. else
  19. cout << "BAD LUCK!" << endl;
  20. }
  21. return 0;
  22. }

发表评论

表情:
评论列表 (有 0 条评论,280人围观)

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

相关阅读

    相关 博弈 HDU2176

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