1068 Bash游戏 V3 【博弈】

题目链接51nod-1068


题目描述

有一堆石子共有N个。A B两个人轮流拿,A先拿。每次拿的数量只能是2的正整数次幂,比如(1,2,4,8,16….),拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N,问最后谁能赢得比赛。
例如N = 3。A只能拿1颗或2颗,所以B可以拿到最后1颗石子。(输入的N可能为大数)


思路

神奇的博弈论;
这个题就不是裸了,我们需要打出sg表,找出规律之后才可以做;关于sg的打表,看下面两个博客就可以学会啦!
关于博弈论的学习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
40
#include <bits/stdc++.h>
using namespace std;

#define N 10
#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()
{
for(int i = 0; i<N; i++)
f[i] = pow(2, i);
init(100);
for(int i = 0; i<100; i++)
{
cout << "i = " << i << " sg[i] = " << sg[i] << endl;
}
return 0;
}

结果是这样:

可以看出 当 n % 3 是 先手必败 否则先手必胜;
注意一点这里给出的n可能是大数,所以我们用string接受,然后逐位求和膜3即可;

AC代码

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