标签：使用 bre http ike nim 关于 lib ast ons
博弈论的题目有如下特点：
简单博弈的基本题型
1：bash博弈；2：nim博弈；3：威佐夫博弈；5：Fibonacci博弈；6：sg函数；
bash博弈 (巴什博奕)
Nim游戏
-
假设有n堆石子，每堆石子分别有\(a_1,a_2,…,a_n个\),每次可以选择任意一堆且至少取1枚石子, 甲乙两个玩家轮流取石子, 最后把石子取完的人获胜, 保证甲乙每一步的决策都是最优的, 甲为先手操作, 问甲胜还是乙胜。
-
结论:
- 设若\(a_1^{ ∧ }a_2^{∧}…^{∧}a_n = 0\)则先手必败, 反之必胜。
-
证明
-
当\(a\)不全为\(0\)时, 任意一个\(res!=0\)的局面, 先手可以通过一定的操作让后手面对\(res=0\)的局面。
-
对于任意一个\(res=0\)的局面, 先手无法通过任何操作让后手面对\(res=0\)的局面。
-
得出结论, 当\(res=0\)时先手必败, 反之必胜。
Nim博弈拓展-台阶Nim
-
问题描述: 有一个\(n\)级台阶的楼梯, 每级台阶上有若干个石子, 其中第i级台阶上有aiai个石子\((i≥1)\)。两位玩家路轮流操作, 每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶上(不能不拿)。
-
已经拿到地面的石子不能再拿, 最后无法进行操作的人视为失败。
-
问如果两人都采取最优策略, 先手是否必胜.
-
结论
-
\(res=a_1∧a_3∧a_5∧,…,∧a_n=0\)(当然这里的n是奇数)先手必败, 反之先手必胜。
-
证明
-
1): 考虑极端情况, 当\(a1,a3,…,an\)全为0时, \(res=0\), 此时先手只能将偶数级台阶往下搬, 后手只需要将先手从偶数级台阶上搬下来的石子全部搬到下一级偶数级台阶, 先手必败。
-
2): 当\(res=x≠0\)时, 通过经典\(Nim\)游戏的证明, 我们知道一定有一种方法搬一定的石子到下一级让后手面对res为0的局面。
-
3):当\(res=x=0\)且\(a\)不全为\(0\)时, 我们无法通过任何操作让下一个状态的\(res\)也为\(0\)。
-
即对于\(res\)不为\(0\)的情况, 先手总能通过一定的操作让后手面对\(res\)为\(0\)的情况,。
-
然而\(res\)为\(0\)时, 先手无论做什么操作都无法让后手面对\(res\)为\(0\)的情况。
-
那么此刻我们就将题目转化为在奇数台阶上的经典Nim游戏。
-
思考题:
-
为什么不用\(res=a_2∧a_4∧a_6∧,…,∧a_n=0\)(n为偶数)来判定胜负？
- 因为当先手搬去一定的石子让后手面对res=0res=0的情况, 后手可以搬去一号台阶的石子到地面让先手重新面对res=0res=0的情况
例题:
-
hdu_1850(经典Nim)
-
#include
using namespace std;
const int maxn = 100 + 10;
int n, a[maxn], res;
int main() {
//freopen("in.txt","r",stdin);
while (cin >> n,n)
{
res = 0;
for (int i = 1; i > a[i];
res ^= a[i];
}
if (res == 0) puts("0");
else{
int ans = 0;
for (int i = 1; i
-
hdu_1730(经典Nim)
-
#include
using namespace std;
int main() {
//freopen("in.txt","r",stdin);
int n, m;
while (cin >> n >> m) {
int res = 0;
for (int i = 1; i > a >> b;
res = res ^ (abs(a - b) - 1);
}
if (res == 0) puts("BAD LUCK!");
else puts("I WIN!");
}
return 0;
}
-
poj_1704(台阶Nim)
-
#include
#include
#include
using namespace std;
const int N = 1000 + 10;
int a[N];
int main() {
//freopen("in.txt", "r", stdin);
int t, n;
cin >> t;
while (t--) {
int ans = 0;
cin >> n;
for (int i = 1; i > a[i];
sort(a + 1, a + n + 1);
if (n % 2)
{
ans ^= (a[1] - 1);
for (int i = 3; i
-
hdu_4315(台阶Nim)
-
#include
using namespace std;
const int maxn = 1e3 + 10;
int a[maxn];
int n, k;
int main() {
//freopen("in.txt","r",stdin);
while(cin >> n >> k)
{
memset(a, 0, sizeof a);
for(int i = 1; i
Wythoff 游戏 (威佐夫博弈)
-
两堆石子各有若干个, 两人轮流从一堆取至少一个石子或从两堆取同样多的物品, 最后一名取完石子者胜利。
-
结论:
- 当两堆石子各有\(n\)和\(m\)个且不妨设\(n。
- 当(m?n)(√5+1)/2=n时, 先手必败。
-
证明
-
?首先考虑最(zhao)极(gui)端(lv)的情况, (0, 0), (1, 2), (3, 5)局面为先手必败局面。而且这样的数字对被称为奇异局势。
-
奇异局势的定义如下：
- 设数字对为\(a[(i),b(i)]\)
- 1:\(a(0)=b(0)=0\);
- 2: \(a(k)\)是前面数字对中未出现的最小的自然数, 且\(a(k)+k=b(k)\)。
-
接下来我们看奇异局势的几个性质:
-
性质1: 任何自然数都包含在一个且仅有一个奇异局势中。
-
性质2: 任意操作都能将奇异局势转变为非奇异局势.
-
性质3: 采取适当的方法, 可将非奇异局势转变为奇异局势。
证明略
例题
-
hdu_2177
-
#include using namespace std;
int n, m;
bool check(int n, int m) {
int x = min(n, m), y = max(n, m);
double c = (sqrt(5.00000) + 1) / 2;
double d = (double)(y - x);
if(x == int(c*d)) return 1; // 必败 return 0;
}
void work() {
if(n > m) swap(n, m); // (n, m) //第一个模块 我们能一起减去让他成为必败态 {
int tem = m - n;
double c = (sqrt(5.00000) + 1) / 2;
int a = double(tem) * c;
int b = a + tem;
if(n - a == m - b) cout y) cout > n >> m)
{
if(!(n + m)) break;
if(check(n, m)) puts("0");
else
{
puts("1");
work();
}
}
return 0;
}
斐波那契博弈(Fibonacci Nim Game)
例题：
SG函数
-
\(mex\)运算:
- 定义\(mex(S)\)为不属于集合S的最小非负整数运算。
- ?举个栗子: \(S=1,2,3,mex(s)=0\);
-
SG函数:
- ?\(SG\)函数: 设对于每个节点x, 设从x出发有k条有向边分别到达节点\(y1,y2,…,yk\), 定义SG(x)函数为后继节点\(y1,y2,…,yk\)的SG函数值构成的集合再执行
mex运算的结果。
- 特别的, 整个有向图GG的SGSG函数被定义为有向图起点
s的SG函数值, 即\(SG(G)=SG(s)\)
- 有向图终点的
SG函数为0。
-
结论:
- ?先手必败, 则该局面对应\(SG函数=0\)。反之必胜。
例题
-
hdu_1524
#include using namespace std;
const int maxn = 1e3 + 10;
int n, num;
int sg[maxn];
int head[maxn], ver[maxn], nex[maxn], tot;
void add(int x, int y) {
ver[++tot] = y; nex[tot] = head[x]; head[x] = tot;
}
int GetSg(int x) {
if(sg[x] != -1) return sg[x];
bool vis[maxn];
memset(vis, 0, sizeof(vis));
for(int i = head[x]; i; i = nex[i]) // 扫描所有出边 {
int y = ver[i];
sg[y] = GetSg(y);
vis[sg[y]] = 1; //所有出边的sg函数值 }
for(int i = 0; i > n)
{
init();
for(int i = 0; i > num;
while(num--)
{
int x; scanf("%d", &x);
add(i, x);
}
}
while(cin >> num)
{
if(!num) break;
int res = 0;
while(num--)
{
int x; scanf("%d", &x);
res ^= GetSg(x);
}
if(res) puts("WIN");
else puts("LOSE");
}
}
return 0;
}
-
hdu_1536
#include
using namespace std;
const int maxn = 1e4 + 10;
int s[maxn], sg[maxn];
int k;
void init() {
memset(sg, -1, sizeof(sg));
}
int GetSg(int x) {
if(sg[x] != -1) return sg[x];
bool vis[maxn]; memset(vis, 0, sizeof(vis));
for(int i = 1; i = s[i])
{
sg[x - s[i]] = GetSg(x - s[i]);
vis[sg[x - s[i]]] = 1;
}
for(int i = 0; ; i++)
if(!vis[i]) return sg[x] = i;
return 0;
}
int main() {
ios::sync_with_stdio(false);
while(cin >> k)
{
init();
if(k == 0) break;
for(int i = 1; i > s[i];
int num; cin >> num;
while(num--)
{
int x, res = 0; cin >> x;
for(int i = 1; i > y;
res ^= GetSg(y);
}
if(res) cout
参考
【博弈论】关于三姬分金(五海盗分赃)的博弈论问题分析
李永乐老师对三姬分金视频讲解
ACM集训队讲解
算法讲堂一：博弈论入门
标签：使用 bre http ike nim 关于 lib ast ons
原文地址：https://www.cnblogs.com/RioTian/p/13032919.html
