1067 Bash游戏 V2 【博弈】

题目链接51nod-1067


题目描述

有一堆石子共有N个。A B两个人轮流拿,A先拿。每次只能拿1,3,4颗,拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N,问最后谁能赢得比赛。
例如N = 2。A只能拿1颗,所以B可以拿到最后1颗石子。


思路

神奇的博弈论;
这个题就不是裸了,我们需要打出sg表,找出规律之后才可以做;关于sg的打表,看下面两个博客就可以学会啦!but:发现大牛的小问题,就是

这个 j <= N 我觉得有问题, 他可能会把自己的sg加入到s序列 导致最后的sg表不正确;
【实例】取石子问题

有1堆n个的石子,每次只能取{ 1, 3, 4 }个石子,先取完石子者胜利,那么各个数的SG值为多少?

SG[0]=0,f[]={1,3,4},

x=1 时,可以取走1 - f{1}个石子,剩余{0}个,所以 SG1 = mex{ SG[0] }= mex{0} = 1;

x=2 时,可以取走2 - f{1}个石子,剩余{1}个,所以 SG2 = mex{ SG1 }= mex{1} = 0;

x=3 时,可以取走3 - f{1,3}个石子,剩余{2,0}个,所以 SG3 = mex{SG2,SG[0]} = mex{0,0} =1;

x=4 时,可以取走4- f{1,3,4}个石子,剩余{3,1,0}个,所以 SG[4] = mex{SG3,SG1,SG[0]} = mex{1,1,0} = 2;

x=5 时,可以取走5 - f{1,3,4}个石子,剩余{4,2,1}个,所以SG[5] = mex{SG[4],SG2,SG1} =mex{2,0,1} = 3;
以下是自己的延伸:
x=6时,可以取走6 - f{1, 3, 4}个石子,剩余{5, 3, 2}个,所以SG[5] = mae{SG[5], SG3, SG2} = mex{3, 1, 0}
终点来了,就是当x=7时会出现问题
x=7时,按原大牛的写法可以取走 7 - f{1,3,4}, 但是当 i == 7时, 两个条件都满足,会把 SG[7]也加进去, 导致SG[7]得到的不是正确的结果!
关于博弈论的学习Blog:
1.博弈论及算法实现
2.SG函数和SG定理【详解】

过程

我们先用sg函数打一个0-100的表 看一下规律;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

#define N 3
#define MAX 1000

int f[N], sg[MAX], vis[MAX];

void init(int n)
{
memset(sg, 0, sizeof(sg));
for(int i = 1; i<=n; i++)
{
memset(vis, 0, sizeof(vis));
for(int j = 0; f[j] <= i && j < N; j++)
{
vis[sg[i - f[j]]] = 1;
}
for(int j = 0; ; j++)
{
if(!vis[j])
{
sg[i] = j;
break;
}
}
}
}

int main()
{
f[0] = 1, f[1] = 3, f[2] = 4;
init(100);
for(int i = 0; i<100; i++)
{
cout << "i = " << i << " sg[i] = " << sg[i] << endl;
}
return 0;
}

结果是这样:

可以看出 当 n % 7 == 0 || (n - 2) % 7 == 0 是 先手必败 否则先手必胜;

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
if(n % 7 == 0 || (n - 2) % 7 == 0)
cout << "B" << endl;
else
cout << "A" << endl;
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------