P3150 pb的游戏（1）

题意

游戏规则：每次一个人可以对给出的数进行分割，将其割成两个非零自然数，之后由另一个人选择留下两个数中的其中一个；之后由另一个人进行分割这个剩下的数，重复步骤……

当一个人无法对数进行分割的时候游戏结束，另一个人获胜。判断每局是否先手必胜。

点击查看题解

题解

~~语言入门题，判断数的奇偶性。~~

$sg(1)=0$ 。
$sg(2)=1$ ，因为 $1+1=2$ 。
$sg(3)=0$ ，因为 $1+2=3$ ，对手一定选择 $2$ 。
依次类推，发现 SG 函数的值与参数奇偶性有关。

严谨证明游戏胜负与奇偶性有关？

归纳法：

$n=1$ ，N 态。
$n=2$ ，P 态。
假设 $n\le k$ $n \leq k$ ，奇数为 N 态，偶数为 P 态。则：
- 若 $k+1$ 为奇数，则一定可化为偶数和奇数，对手肯定选偶数，所以是 N 态。
- 若 $k+1$ 为偶数，则化为奇数 $k$ 和 $1$ ，对手只能选 $k$ ，所以是 P 态。

证毕。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace _yz
{
	int m;ll n;
	void yzmain()
	{
		cin>>m;
		for(int i=1;i<=m;i++)
		{
			cin>>n;
			if(n%2==0) cout<<"pb wins"<<endl;
			else cout<<"zs wins"<<endl;
		}
		return;
	}
} 
int main()
{
	_yz::yzmain();
	return 0; 
}

P2197 【模板】nim 游戏

题意

游戏规则：有 $n$ 堆石子（每堆石子数量小于 $10^4$ ），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。

判断是否存在先手必胜的策略。

点击查看题解

题解

定义 Nim 和为所有 $a_i$ 的异或和。当且仅当 Nim 和为 $0$ 时，该状态为必败状态；否则该状态为必胜状态。

为了证明该定理，只需要证明下面三个定理（引用自 OI Wiki）：

定理 1：没有后继状态的状态是必败状态。
定理 2：对于异或和不为 $0$ 的局面，一定存在某种移动使之为 $0$ 。
定理 3：对于异或和为 $0$ 的局面，一定不存在某种移动使之不为 $0$ 。

对于定理 1，没有后继状态的状态只有一个，即全 $0$ 局面（此时游戏结束，当前玩家失败）。此时异或和为 $0$ 。

对于定理 2，不妨假设异或和等于 $k$ （ $k\not=0$ ）。如果我们要将 $a_i$ 改为 $a_i'$ ，则易知 $a_i'=a_i\oplus k$ 。根据异或定义，一定存在 $a_i$ 使得 $a_i'<a_i$ （详细见下文，分割线下），因而这是个合法的移动。

对于定理 3，如果我们要将 $a_i$ 改为 $a_i'$ ，则根据异或运算律可以得出 $a_i=a_i'$ ，因而这不是个合法的移动。

既然异或和不为 $0$ ，那么存在某一位，对于所有数这一位是 $1$ 的个数是奇数。所以 $k$ 的二进制位数就被限制住了。实际上，对于异或运算，所得结果的二进制位数不会大于所有参与运算的数最大的二进制位数。

既然 $a_i'=a_i\oplus k$ 且 $a_i\ge k$ ，则 $a_i'\le a_i$ 。然而，如果 $a_i'=a_i$ ， $k$ 应等于 $0$ 。所以一定存在 $a_i$ 使得 $a_i'<a_i$ 。

代码

/*这个代码也是个反例。
  既然你用了命名空间，为什么不在命名空间里把所有程序写完？
  导致这个程序最初有个小错误，
  交了 3 发，WA 0 pts。
*/
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	int n,a,c; 
	void yzmain()
	{
		scanf("%d",&n);c=0; 
		while(n--) scanf("%d",&a),c^=a;
		if(c) printf("Yes\n");
		else printf("No\n");
		return;
	}
}
int main()
{
	int b;
	scanf("%d",&b);
	while(b--)
		_yz::yzmain();
	return 0;
}

以下是 zzy 大佬的题解。

P1290 欧几里德的游戏

题意：

给定两个正整数 M 和 N，从 Stan 开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于 0。然后是 Ollie，对刚才得到的数，和 M,NM,N 中较小的那个数，再进行同样的操作……直到一个人得到了 0，他就取得了胜利。

解析：

假设状态为（xx，yy）假定y>=x ; y=k*x+z（z为余数）
显然，当x==y时；或者当y为x的倍数时，当前这个人会获胜
所以(x,x+z)与(x,z)是两个截然相反的情形,必定满足一个先手必胜，一个后手必胜
所以在模拟的过程中如果k>=2或z==0先手胜

code:

#include<bits/stdc++.h>
using namespace std;
int n,a,b;

int gcd(int x,int y,int temp)
{
	if(x<y) swap(x,y);

int t=x/y;
int md=x%y;

if(t>=2||md==0) return temp;

gcd(y,x%y,temp^1);

}

int main()
{
	cin>>n;

for(int i=1;i<=n;++i)
{
	cin>>a>>b;	
	if(gcd(a,b,1))	
	{
		cout<<"Stan wins"<<endl;
	}
	else
	{
		cout<<"Ollie wins"<<endl;
	}
}	
return 0;	

}

P3150 pb的游戏

题意：

A和B玩游戏,每个人轮流对给出的一个数进行分割，将其割成两个非零自然数，另一个人分割这个剩下的数，帮他们求出N次游戏的胜败。

解析：

当这个数不是1还可以再拆（没什么好说的）
于是这个数a拆到最后变成了n个1
说白了就是判断这个数的奇偶性

code：

#include<bits/stdc++.h>

using namespace std;
int main()
{
    int n,a;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a;
        if(a%2==0)
        {
            cout<<"pb wins"<<endl;
        }
        else
        {cout<<"zs wins"<<endl;
        }
    }
    return 0;
}

P4136 谁能赢呢？

题意：

小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。

假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？

解析：

至于不走完全部的格子会发生什么我们先不讨论 (没有较为严谨的证明)

棋盘大小为 n\times nn×n，左上角已有一枚棋子，那么剩下的可选格子有 n^2-1n2-1 个
一个人想赢必须抢占到最后一个格子。
所以当 n^2-1 为奇数时先手胜，偶数时后手胜（n与n^方奇偶性相同）
所以这道题还是奇偶性问题

code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a;
    while(1)
    {
        cin>>a;
        if(a==0) break;
        if(a%2==0)
        {
            cout<<"Alice"<<endl;
        }
        else
        {cout<<"Bob"<<endl;
        }
    }
    return 0;
}

P4576 [CQOI2013]棋盘游戏

题意

一个n*n（n>=2）棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子，A先走。

A的移动规则：只能移动白棋子。可以往上下左右四个方向之一移动一格。
B的移动规则：只能移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。

和通常的“吃子”规则一样，当某游戏者把自己的棋子移动到对方棋子所在的格子时，他就赢了。

两个游戏者都很聪明，当可以获胜时会尽快获胜，只能输掉的时候会尽量拖延时间。告诉你n和黑白棋子的坐标，你的任务是判断谁会赢，需要多少回合。

点击查看题解

题解

我们先理性分析一下：白棋子可以往四个方向移动一格，然而黑棋子可以往四个方向移动一格或者两格。

除非白棋开始时挨着围棋，否则黑棋赢,想想为什么；

证明：

我们先不考虑消耗的步数，黑棋想赢就必须把白棋逼到角落。当黑棋和白棋对峙时；

空	白
黑	空

首先 $n\not=1$ （摆不开）

当 $n=2$ 时（黑白不挨着），如图，白无论往哪都会被吃

当 $n\ge3$ 时：

黑棋只移动 1 格能把白棋逼到角落里
黑棋只移动 1 格会被白棋逼到角落里，期间黑棋在和白棋对峙时,黑棋可以移动两格从侧面穿过白棋进而转为第 1 种情况

所以就有了这个叫对抗搜索的东西。

代码

#include<bits/stdc++.h>
using namespace std;
const int inf=1e8;
int dp[21][21][21][21][61][2];//距离黑棋吃掉白棋还剩多少步
int a[8]={-1,0,1,0,-2,0,2,0};//模拟x轴移动
int b[8]={0,1,0,-1,0,2,0,-2};//模拟y轴移动
int n,x,y,X,Y;

int dfs(int x1,int y1,int x2,int y2,int step,int op) //op=1轮到黑,op=0轮到白 
{
	if(step>3*n) return inf; //想想为啥递归边界是3*n
	if(x1==x2&&y1==y2) return op*inf; 
    //当 op=1 时，说明上一轮白棋选择吃掉黑棋，是不合法的，op*inf刚好赋予正无穷
   	//当 op=0 时，说明上一轮黑棋选择吃掉白棋，是目标完成，op*inf刚好为赋值0
	if(dp[x1][y1][x2][y2][step][op]) return dp[x1][y1][x2][y2][step][op];//记忆化
    dp[x1][y1][x2][y2][step][op]=op*inf; //同理
	for(int i=0;i<(op?8:4);++i)
	{
		int xx=x1+a[i],yy=y1+b[i];
		if(xx<1||xx>n||yy<1||yy>n) continue; //边界判断                                                                                                  | 提醒:不要把yy写成y,我就这么错了
		if(!op) dp[x1][y1][x2][y2][step][op]=max(dp[x1][y1][x2][y2][step][op],dfs(x2,y2,xx,yy,step+1,1)); //如果此时轮到白棋，白棋将会选择最强抵抗
		else dp[x1][y1][x2][y2][step][op]=min(dp[x1][y1][x2][y2][step][op],dfs(x2,y2,xx,yy,step+1,0)); //如果此时轮到黑棋，黑棋将会选择最快胜利
	}
	return ++dp[x1][y1][x2][y2][step][op];//移动一次 步数+1
}

int main()
{
	cin>>n>>x>>y>>X>>Y;
	if(abs(x-X)+abs(y-Y)==1) //abs()绝对值函数,判断白棋是否挨着黑棋
	{
		cout<<"WHITE 1";
		return 0; 
	}
	cout<<"BLACK "<<dfs(x,y,X,Y,0,0);
	return 0;
}

本文作者：Yurchiu,zzy

本文链接：https://yz-hs.github.io/799c9d39b0d6/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

博弈论 OI 一些

最后更新：2023-08-21, 23:18:21

By Yurchiu.

一些关于博弈论的题目

P3150 pb的游戏（1）

题意

题解

代码

P2197 【模板】nim 游戏

题意

题解

代码

P1290 欧几里德的游戏

题意：

解析：

code:

P3150 pb的游戏

题意：

解析：

code：

P4136 谁能赢呢？

题意：

解析：

code:

P4576 [CQOI2013]棋盘游戏

题意

题解

证明：

代码