一、定义
只有一堆n个物品,两个人轮流从这堆物品中取物, 规定每次至少取一个,最多取m个。最后取光者得胜。
二、分析
我们从最简单的情景开始分析
当石子有1−m1−m个时,毫无疑问,先手必胜
当石子有m+1m+1个时,先手无论拿几个,后手都可以拿干净,先手必败
当石子有m+2−2mm+2−2m时,先手可以拿走几个,剩下m+1m+1个,先手必胜
我们不难发现,面临m+1m+1个石子的人一定失败。
这样的话两个人的最优策略一定是通过拿走石子,使得对方拿石子时还有m+1m+1个
我们考虑往一般情况推广
-
设当前的石子数为n=k∗(m+1)+rn=k∗(m+1)+r
先手会首先拿走rr个,接下来假设后手拿走xx个,先手会拿走m+1−xm+1−x个,这样博弈下去后手最终一定失败
-
设当前的石子数为n=k∗(m+1)n=k∗(m+1)
假设先手拿xx个,后手一定会拿m+1−xm+1−x个,这样下去先手一定失败
三、变形
两个人轮流报数,每次至少报一个,最多报十个,谁能报到100者胜。
对于巴什博弈,那么我们规定,如果最后取光者输,那么又会如何呢?
(n-1)%(m+1)==0则后手胜利
先手会重新决定策略,所以不是简单的相反行的
例如n=15,m=3
后手 先手 剩余
0 2 13
1 3 9
2 2 5
3 1 1
1 0 0
先手胜利 输的人最后必定只抓走一个,如果>1个,则必定会留一个给对手
四、解决方案
1、结论
#include<cstdio>
int main()
{
int n,m;
scanf("%d%d",&n,&m);
if(n % (m+1) !=0) printf("first win");
else printf("second win");
return 0;
}
二、SG定理
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 10, INF = 0x3f3f3f3f;
int sg[N], sm[N];
bool vis[N];
void SG(int n, int m)
{
for(int i = 0; i <= n; i++)
{
memset(vis, 0, sizeof vis);
for(int j = max(i-m, 0); j < i; j++) vis[sg[j]] = true;//i的后继是[max(i-m,0), i-1]
for(int j = 0; j <= n; j++)//mex运算
if(! vis[j])
{
sg[i] = j; break;
}
}
}
int main()
{
int t, n, m;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &m);
SG(n, m);
puts(sg[n] ? "first" : "second");
}
return 0;
}
三、DFS
可以解决,但是TLE!!!
五、例题
http://poj.org/problem?id=2348
http://acm.hdu.edu.cn/showproblem.php?pid=1846
http://acm.hdu.edu.cn/showproblem.php?pid=4764
http://acm.hdu.edu.cn/showproblem.php?pid=1848
六、参考文章
https://www.cnblogs.com/zwfymqz/p/8460192.html
https://blog.csdn.net/luomingjun12315/article/details/45479073