\(\qquad\!\!\)博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。
博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。生物学家使用博弈理论来理解和预测进化论的某些结果。
\(\qquad\!\!\)在此总结四种常见的博弈结论：
\(\qquad\!\!\)例题：
\(\qquad\!\!\)只有一堆 \(n\)
个石子，两个人轮流从中取，规定每次最少取一个，最多取 \(m\) 个，最后取光者为胜。
\(\qquad\!\!n \bmod (m+1)\) 不为
\(0\) 则先手必胜，反之则后手必胜：
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
int n,m;
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
int main()
{
n=qread();
m=qread();
if(n%(m+1))
{
printf("先手必胜\n");
}
else
{
printf("后手必胜\n");
}
return 0;
}
|
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P2252
[SHOI2002]取石子游戏|【模板】威佐夫博弈
\(\qquad\!\!\)规定 \(n<m\)，则\(n
\not = \left\lfloor \dfrac{1+\sqrt{5}}{2}(m-n) \right\rfloor\)
时先手必胜，反之后手必胜。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
int n,m;
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
int main()
{
n=qread();
m=qread();
if(n>m)
{
swap(n,m);
}
if(n==(int)((1+sqrt(5))*0.5*(m-n)))
{
putchar('0');
putchar('\n');
}
else
{
putchar('1');
putchar('\n');
}
return 0;
}
|
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P2197
【模板】nim游戏：
\(\qquad\!\!\)所有数的异或和不为
\(0\) 则先手必胜，反之后手必胜。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
int t,n;
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
int main()
{
t=qread();
while(t--)
{
int k=0,b;
n=qread();
while(n--)
{
b=qread();
k^=b;
}
if(k)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return 0;
}
|
\(\qquad\!\!\)例题：
\(\qquad\!\!\)有一堆 \(n\)
个石子，两人轮流取，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。
\(\qquad\!\! n\not\in\)
斐波那契列，则先手必胜，反之后手必胜。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
int n,pre,now;
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
int main()
{
n=qread();
pre=now=1;
while(now<=n)
{
if(now==n)
{
printf("后手必胜\n");
return 0;
}
swap(pre,now);
now+=pre;
}
printf("先手必胜\n");
return 0;
}
|