博弈论-公平组合游戏

本文主要是介绍博弈论-公平组合游戏，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

常规思路：
先找到必胜点或者必输点，反推出可以一步让对方变成必输的点；
思路要清晰，分类讨论，从特殊到普通。(奇异局势)
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值。

这篇关于博弈论-公平组合游戏的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！