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