区块链技术博客
www.b2bchain.cn

B. Sequential Nim(先后手,博弈)的讲解

这篇文章主要介绍了B. Sequential Nim(先后手,博弈)的讲解,通过具体代码讲解7671并且分析了B. Sequential Nim(先后手,博弈)的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了B. Sequential Nim(先后手,博弈)的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7671.html。具体如下:

color{Red}考虑明显的必胜态

.,,Ⅰ.当我先手且面前只有一堆石子,全部拿掉,我必胜

.,1,Ⅱ.当有两堆石子,且第一堆石子只有1个,那我只能全拿走

,剩下一堆被对手全部拿走,我必败

.,1,,Ⅲ.当有两堆石子,且第一堆大于1个,那么我拿得只剩一个,对手再拿完这堆

,.............然后我再拿完第二堆,我必胜………….

根据上面的基本分析可以知道石子的数目只有两类

石子数目等于1,或者大于1,多大是没有影响的

,,,n这么想,一开始我是先手,要必胜,就要保证在拿第n堆石子后是后手

我们直接去维护color{Red}拿完每堆石子后的先后手情况

.ai=1,,Ⅰ.当出现a_i=1时,先手的人只能拿完,所以拿完这堆之后

,先手变后手,后手变先手

.ai>1,,Ⅱ.当出现a_i>1时,先手的人可以全部拿走,此时先手变后手

ai1,先手也可以只拿a_i-1个石子,那么另一个人只能拿完这堆

,所以拿完后,先手还是先手

?ai>1,color{Red}发现了什么?当a_i>1时,先手的人可以让自己保持先手

,color{Red}也可以选择变成后手,这其实已经包含了获胜的所有可能

所以碰到

a[i]a[i]

>1时,此时先手的人必胜

碰到

a[i]==1a[i]==1

时,改变先后手情况

#include <bits/stdc++.h> using namespace std; int t,n,a[100009]; int main() { 	cin >> t; 	while( t-- ) 	{ 		cin >> n; 		int xian=1,hou=0;//代表目前可以是先手  		for(int i=1;i<=n;i++)	cin >> a[i]; 		for(int i=1;i<=n;i++) 		{ 			if( a[i]==1 ) 			{ 				if(xian)	hou=1,xian=0; 				else if(hou)	xian=1,hou=0; 			} 			else 			{ 				if( xian )	xian=hou=1;//那我赢了呀!!先后后手任我选  				else	xian=hou=0;//那我输了呀,因为对手是先手,可以左右游戏了 				break;  			} 		} 		if( hou )	cout<<"First"<<endl; 		else cout<<"Second"<<endl; 	} }  

总的来说这种简单的博弈问题

.,Ⅰ.分析显然的必胜态,慢慢推出去

.Ⅱ.思考如何构造出上面最显然的必胜态

emmm讲完啦,希望对你有帮助,一起进步呀!

本文地址https://www.b2bchain.cn/7671.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » B. Sequential Nim(先后手,博弈)的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们