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

相关文章

来自专栏猿人谷

如何养成良好的c++编程习惯(1)——内存管理

开篇导读   “养成良好的编程习惯”其实是相当综合的一个命题,可以从多个角度、维度和层次进行论述和评判。如代码的风格、效率和可读性;模块设计的灵活 性、可扩展性...

3155
来自专栏python3

习题32:分支和函数(函数调用函数)

在很多类型的操作系统里,exit(0)表示正常退出程序,exit(1)则表示发生了错误

772
来自专栏数据结构与算法

1291 火车线路

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解  查看运行结果 题目描述 Description 某列火车行使...

3148
来自专栏区块链大本营

智能合约中的“高铁座霸”|存储器局部变量未初始化——漏洞分析连载之七

我们在上一期的区块链游戏漏洞的汇总和分析中将目前游戏合约出现的问题与前几期的漏洞连载分析进行了联动,发现游戏合约的漏洞很大一部分是在重复之前代币合约的重大错误。...

722
来自专栏JackieZheng

如何写出好代码

如何写出好代码 这个题目把我自己都看傻了,因为仔细想想,这不是一个命题,是对代码的思考,对细节的推敲和打磨。写好代码是一门学问,还是一种修行。 以前是公众号(...

2215
来自专栏ACM算法日常

勇士与公主(组合+完全背包)- HDU 1028

这是一道排列组合题,然而却用到了完全背包的思想,寻找真相并不是件容易的事情,先简单看下题目,慢慢进入正题

913
来自专栏YoungGy

ML基石_8_NoiseAndError

recap Noise and Probabilistic Target noise来源 Probabilistic Target Error Measure ...

1855
来自专栏C/C++基础

C++字节流与二进制字符串相互转换(一个简单的明文加解密程序)

作为一名程序猿,在我们写文章、文字片段或者一句简短的话语,对外发表或者告之他人时,是否想过带点新意和创意呢?如果想过,那么这篇文章会给你一点帮助。

812
来自专栏Python中文社区

Python时间处理完全手册

專 欄 ❈ gw1770df,Python中文社区专栏作者,从事Python开发工作,全栈工程师。 博客: https://word.gw1770df.cc ...

2786
来自专栏张俊红

房天下数据爬取及简单数据分析

总第64篇 01|明确本次爬虫以及目的: ---- 我是想看看太原的房地产情况,包括楼盘名称、价格、所处区域、评论数(一定程度上可以反映出该楼盘受欢迎程度)...

3437

扫码关注云+社区