第四届蓝桥杯决赛B组C/C++——高僧斗法

标题:高僧斗法

古时丧葬活动中经常请高僧做法事。仪式结束后,有时会有“高僧斗法”的趣味节目,以舒缓压抑的气氛。节目大略步骤为:先用粮食(一般是稻米)在地上“画”出若干级台阶(表示N级浮屠)。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人,其它任意。(如图1所示)

图1

两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶,但会被站在高级台阶上的小和尚阻挡,不能越过。两个小和尚也不能站在同一台阶,也不能向低级台阶移动。两法师轮流发出指令,最后所有小和尚必然会都挤在高段台阶,再也不能向上移动。轮到哪个法师指挥时无法继续移动,则游戏结束,该法师认输。对于已知的台阶数和小和尚的分布位置,请你计算先发指令的法师该如何决策才能保证胜出。

输入数据为一行用空格分开的N个整数,表示小和尚的位置。台阶序号从1算起,所以最后一个小和尚的位置即是台阶的总数。(N<100, 台阶总数<1000)

输出为一行用空格分开的两个整数: A B, 表示把A位置的小和尚移动到B位置。若有多个解,输出A值较小的解,若无解则输出-1。

例如:

用户输入:

1 5 9

则程序输出:

1 4

用户输入:

1 5 8 10

则程序输出:

1 3

    这题困扰我还是蛮久的,为了解决这题并且为了免除后顾之忧,我把常见的四大博弈问题——巴什博弈、威佐夫博弈、斐波那契博弈、尼姆博弈都研究了遍。而这题要用到的就是尼姆博弈

    巴什博弈和斐波那契博弈适用于一堆的状态

    威佐夫博弈适用于两堆

    这题之所以用尼姆博弈就是因为它适用于n堆,没看过尼姆博弈的先去了解一下

    知道这题用什么模型之后,我们要把这题想办法抽象成”堆“的状态,其实也不难,两个两个和尚进行配对,他们楼梯号的差值再减一就是一堆的数量,就以1 5 8 10为例

图2

    我觉得这张图特别能帮助理解,我们看堆1,1楼的小和尚只有三种走法,可以抽象成堆1有三枚石子;同样的,8楼的小和尚只有一种走法,所以抽象成堆2有一枚石子,此时尼姆堆N={3 1}

    现在问题就来了,两两配对,那如果只有奇数个输入,也就是只有奇数个小和尚,应该怎么办?其实我们把题目抽象为尼姆堆最后都是要对尼姆堆里的数值进行异或运算,对于异或运算有一个性质:x^0=x,一个数对0异或还等于这个数。有了这个性质,我们其实只要在尼姆堆里增加个0就行,这个0就是我们判断如果小和尚个数是奇数,就在后面再增加一个数据,这个数据的值为输入数据的最后一个值+1。例如1 5 8 10 13,此时尼姆堆N={3,1,0}

    问题也抽象出来了,下面就好解决了。我方先手,堆元素全部异或起来结果为0,我方必输,输入-1;如果不为0,那我们可以改变某一堆的大小,使其异或起来为0,把必败局面留给对方

    这里注意最后一个问题,我们到底应该移动哪一个和尚,以1 5 8 10为例,假如我们移动5,使其产生一个必败局面,但是此时对手可以移动1,又返还给我们一个必败局面,那这样是没有任何意义的。但是如果我们通过改变1、8楼的和尚,形成一个必败局面,此时无论对手走什么,我们都可以跟随,或者是改变另一堆的大小再返还给对方一个必败局面

#include <bits/stdc++.h>
using namespace std;
int len = 0;
//判断一组Nim堆是否能赢 
bool Nim(int* x)
{
	int i,res = 0;
	int N[100];
	for(i = 0;i < len;i++)
	{ 
		N[i] = x[2 * i + 1] - x[2 * i] - 1;
		res ^= N[i];
	}
	if(res == 0)
		return true;
	return false;
}
int main()
{
	int x[100],N[100];
	memset(x,0,sizeof(x));
	int res = 0,i = 0,is = 1,old;
	char s;
	//输入 
	for(i = 0;i < 100 && s != '\n';i++)
	{
		scanf("%d",&x[i]);
		s = getchar(); 
	}
	len = i;
	//如果只有奇数个数据,那么要隐式的在最后增加一个,使其变为偶数 
	if(i % 2)
	{
		x[i] = x[i-1] + 1;
		len++;
	}
	//判断一开始的状态是否是输 
	if(Nim(x))
		cout<<-1;
	//移动和尚			
	else
	{
		for(i = 0;i < len && is == 1;i += 2)
		{
			for(int j = x[i] + 1;j < x[i+1] && is == 1;j++)
			{
				old = x[i];
				x[i] = j;
				if(Nim(x))
				{
					cout<<old<<" "<<x[i];
					is = 0;
				}
				x[i] = old;
			}
		} 
	}
	return 0;
}

    关于代码我还有两点说明:

    1.题目是输入一行数据,所以我以回车作为结束符,如果你不知道,就请记住这个框架

for(i = 0;i < 100 && s != '\n';i++)
	{
		scanf("%d",&x[i]);
		s = getchar(); 
	}

    2.关于移动和尚中的x[i] = old这一行代码,在试探的过程中,如果异或不为0,那么我们肯定要继续试探,但是应该将原有的改变全部还原,其实就跟搜索差不多吧,回溯的时候要还原,不然肯定会出现问题

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落花落雨不落叶

canvas画简单电路图

61811
来自专栏码匠的流水账

聊聊NettyConnector的start及shutdown

reactor-netty-0.7.6.RELEASE-sources.jar!/reactor/ipc/netty/NettyConnector.java

851
来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2536
来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2152
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2645
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2577
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.2K7
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5456
来自专栏hbbliyong

WPF Trigger for IsSelected in a DataTemplate for ListBox items

<DataTemplate DataType="{x:Type vm:HeaderSlugViewModel}"> <vw:HeaderSlug...

4064
来自专栏菩提树下的杨过

Flash/Flex学习笔记(23):运动学原理

先写一个公用的小球类Ball: package{ import flash.display.Sprite; //小球 类 public class B...

25310

扫码关注云+社区