第四届蓝桥杯决赛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 条评论
登录 后参与评论

相关文章

来自专栏编程之旅

iOS开发——影响图形性能的因素以及检测方法

我想各位攻城狮们肯定听过一句话:“过早的优化是万恶之源”。若是你有着丰富的项目经验,一定会对这句话有着自己的体会,而若是编程新手,那么,请牢记这句话。在一个项目...

722
来自专栏IMWeb前端团队

利用canvas实现一个抠图小工具

利用canvas实现一个抠图小工具 0 前言 作为新一代的前端开发工程师,PS抠图切图已经不是必备技能了,我们有UI/交互/视觉等更专业的设计同学帮我们做这个事...

2985
来自专栏自由而无用的灵魂的碎碎念

关于Serif与Sans-Serif字体

在西方国家罗马字母阵营中,字体分为两大种类:Sans Serif和 Serif,打字机体虽然也属于 Sans Serif,但由于是等宽字体,所以另外独立出 Mo...

873
来自专栏racaljk

A星寻路算法(A* Search Algorithm)

你是否在做一款游戏的时候想创造一些怪兽或者游戏主角,让它们移动到特定的位置,避开墙壁和障碍物呢?

1353
来自专栏落影的专栏

iOS开发-视图渲染与性能优化

前言 关于iOS的视图渲染流程,以及性能优化的建议。 源于WWDC视频。 我假设你是一个这样的开发者: 了解OpenGL ES; 了解view hierar...

3837
来自专栏cs

学markdown怎能不知道与之相关的html了include <iostream>

<h2>导言</h2> <strong> markdown,hthl都是超文本标记语言,markdown是简化版本的html,兼容html语言,熟悉一下ht...

2224
来自专栏wym

牛客练习赛19 E托米的饮料

链接:https://www.nowcoder.com/acm/contest/111/E 来源:牛客网

681
来自专栏Sorrower的专栏

Android绘制(三):Path结合属性动画, 让图标动起来!

932
来自专栏DannyHoo的专栏

改变UITextField的光标颜色

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

732
来自专栏jojo的技术小屋

原 荐 CSS深入理解之border

作者:汪娇娇 时间:2017年10月20日 前段时间看过有关border比较好的视频,想着就写成博客给大家分享一下吧~ 说起border,想必大家都很熟悉,简单...

2844

扫码关注云+社区