博弈论-公平组合游戏

常规思路:
先找到必胜点或者必输点,反推出可以一步让对方变成必输的点;
思路要清晰,分类讨论,从特殊到普通。(奇异局势)
1,巴什游戏:(最多m,最少1)
n%(m+1)==0
无论对方拿多少,最后都可以拿一轮两人拿m+1个。
2,尼姆游戏:(异或运算)
异或为零Vs异或不为零
3,威佐夫游戏:(黄金分割率)
eg. – hdu1527
4,混合题:

https://www.acwing.com/problem/content/description/2753/

小约翰经常和他的哥哥玩一个非常有趣的游戏:

桌子上有 n 堆石子,小约翰和他的哥哥轮流取石子。

每个人取的时候,可以随意选择一堆石子,在这堆石子中取走任意多的石子,但不能一粒石子也不取,我们规定取到最后一粒石子的人算输。

小约翰相当固执,他坚持认为先取的人有很大的优势,所以他总是先取石子,而他的哥哥就聪明多了,他从来没有在游戏中犯过错误。

小约翰一怒之前请你来做他的参谋。

自然,你应该先写一个程序,预测一下谁将获得游戏的胜利。

输入格式
本题的输入由多组数据组成。

第一行包括一个整数 T,表示输入总共有 T 组数据。

每组数据的第一行包括一个整数 N,表示共有 N 堆石子。

接下来一行有 N 个不超过 5000 的整数,分别表示每堆石子的数目。

输出格式
每组数据的输出占一行,每行输出一个单词。

如果约翰能赢得比赛,则输出 John,否则输出 Brother。

数据范围
1≤T≤500,
1≤N≤50
输入样例:
2
3
3 5 1
1
1
输出样例:
John
Brother

#include <iostream>
using namespace std;
int main()
{
    int T;
    int n, x;
    cin >> T;
    while (T--) {
        int ans = 0;
        cin >> n;
        int t = 0;
        for (int i = 0; i < n; i++) {
            cin >> x;
            if (x > 1) t = 1;
            ans ^= x;
        }
        if (t && ans) {
            cout << "John\n";
            continue;
        }
        if (!t && n % 2 == 0) {
            cout << "John\n";
            continue;
        } else
            cout << "Brother\n";
    }
    return 0;
}
  • 考虑一下特殊情况
    解题模型:

5,SG函数
1.把原游戏分解成多个独立的子游戏,则原游戏的SG函数值是它的所有子游戏的SG函数值的异或。

   即sg(G)=sg(G1)^sg(G2)^...^sg(Gn)。

2.分别考虑没一个子游戏,计算其SG值。

上一篇:2021-07-09


下一篇:linux kernel变长数组使用示例