文档章节

历届试题 高僧斗法

李韬_varyshare
 李韬_varyshare
发布于 2017/05/13 17:55
字数 1609
阅读 247
收藏 1

题目描述

对应题目链接: http://lx.lanqiao.cn/problem.page?gpid=T37

问题描述

  古时丧葬活动中经常请高僧做法事。仪式结束后,有时会有“高僧斗法”的趣味节目,以舒缓压抑的气氛。
  节目大略步骤为:先用粮食(一般是稻米)在地上“画”出若干级台阶(表示N级浮屠)。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人,其它任意。(如图1所示)
  两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶,但会被站在高级台阶上的小和尚阻挡,不能越过。两个小和尚也不能站在同一台阶,也不能向低级台阶移动。
  两法师轮流发出指令,最后所有小和尚必然会都挤在高段台阶,再也不能向上移动。轮到哪个法师指挥时无法继续移动,则游戏结束,该法师认输。
  对于已知的台阶数和小和尚的分布位置,请你计算先发指令的法师该如何决策才能保证胜出。

输入格式

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

输出格式

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

样例输入

1 5 9

样例输出

1 4

样例输入

1 5 8 10

样例输出

1 3

测评结果:

 

算法思路

   一开始看到这道题基本是想用递归来求解,如果己方下一步对方必输则我方就赢了,如果没有办法让对方输己方就输了。但是这个复杂度有点高,假设小和尚n个台阶m个那么我们要选一个小和尚走大约是O(n*m)但是它又会产生O(n*m)种新的布局我们递归就是将这些布局继续算下去,因此是个指数级别的增长。靠递归完成这道题基本不可能。

   由于这道题是无偏差游戏,就是前后两个法师身份没有区别。也就是说他们只有前后的区别,小和尚没有归属于任何一方这就是身份无差别,如果游戏中某个角色归属于某一方这就不是无偏差游戏,比如象棋,它的棋子是分了红黑两边的就不是无偏差游戏。

    无偏差游戏可以利用尼姆定理去解决,说道尼姆定理你要看下尼姆堆这个游戏是啥。尼姆堆游戏就是给几堆东西然后让两个人选,一次可以从任意一堆选任意数量的物品。直到把所有的东西取完,当一个人没法取的时候他就是输了。

  而尼姆定理用计算机描述语言就是说当将尼姆堆的数字变成二进制时候如果任何一列的1的个数变成偶数那么对方就输了。

  我们就是要将高僧斗法这个游戏转换成类似尼姆堆这种游戏,有几堆东西,然后任意取,然后直到取完就输了。

  这样分析就可以发现如果我们把两个和尚之间的台阶数作为一堆东西,刚好满足上面的条件,高僧任意将两个小和尚之间距离变短,直到没法移动(取完了)就输了。注意一点的是:取任何一个堆的东西不能影响其他堆。因为尼姆堆就是一次只从一个堆里面取东西。

 我程序思路就是遍历一遍第一个法师第一次可以走的路,然后每走一次检查一下尼姆堆列方向1的个数是否是偶数如果所有列都是偶数则第一个法师必赢输出结果。下面是如何检查尼姆堆列方向1的个数是否是偶数的分析。如果不清楚建议可以看下代码再来这些分析:

从题目给的输入案例分析:

1 5 9

那么我们把1-5之间距离作为一个尼姆堆,他们之间台阶数是3,转换成二进制数是101.

我们遍历第一个法师可以走的方法,找到1移动到4可以使得尼姆堆变成0使得列方向的1个数为偶数下一个法师就必输.

再看一个案例:

1 5 8 10

我们将1-5  、 8-10组合成两个尼姆堆,台阶数分别是3,1。转换成二进制

101

    1

然后我们用程序遍历一次走法找到从1到3的时候尼姆堆变成了下面这个情况:

1

1

因此列就变成了偶数下一个法师必输。

 具体代码


import java.util.Scanner;

public class DouFa {
	public static int[] a;

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		String data = input.nextLine();
		input.close();
		String[] digitstr = data.split(" ");
		a = new int[digitstr.length];
		for (int i = 0; i < digitstr.length; i++)
			a[i] = Integer.parseInt(digitstr[i]);
		for (int i = 0; i < a.length - 1; i++) {//依次选一个和尚
			int origin = a[i];
			for (int j = a[i] + 1; j < a[i + 1]; j++) {
          //遍历选中和尚可以走的路
				a[i] = j;
				if (f()) {
       // 每走一次判断是否下一个法师输对方输己方赢,如果能赢直接输出结果
					System.out.println(origin + " " + a[i]);
					return;
				}
			}
			a[i] = origin;
		}
		System.out.println(-1);

	}

	// 检查当前情形是否能赢
	private static boolean f() {
		int[] onenum = new int[32];
		int maxlen = 0;
//统计分成的尼姆堆各列1的个数
		for (int i = 0; i < a.length-1; i += 2) {
			String tempbinary = Integer.toBinaryString(a[i + 1] - a[i] - 1);
//将两个和尚之间的台阶数转成二进制
			int len = tempbinary.length();
			if (len > maxlen)
				maxlen = len;
			for (int j = len - 1; j >= 0; j--)//
				if (tempbinary.charAt(j) == '1')
					onenum[len - j - 1]++;
		}
		for (int i = 0; i < maxlen; i++)
			if (onenum[i] % 2 != 0)
//如果有一列不满足1是偶数那么下一个法师肯定不会输,己方就会输
				return false;
		return true;//如果所有列1个数都是偶数己方必赢
	}
}

 

© 著作权归作者所有

李韬_varyshare

李韬_varyshare

粉丝 7
博文 27
码字总数 18588
作品 1
广州
个人站长
私信 提问
用java编写高僧斗法代码

问题描述   古时丧葬活动中经常请高僧做法事。仪式结束后,有时会有“高僧斗法”的趣味节目,以舒缓压抑的气氛。   节目大略步骤为:先用粮食(一般是稻米)在地上“画”出若干级台阶(表...

geduo67
2014/01/27
1K
0
科三考场为求平安,请高僧开光祈福:驾照考试有多危险?

说是湖南衡阳有一新开业的科目三考场(驾照考试),出现了请高僧现场祈福的奇特景象。一开始没注意看,还以为是考生为了顺利通过驾照考试,特地请高僧到考场来,沟通考神求过的。仔细的看了一...

有态度的互联网人
2018/06/07
0
0
《西游八十一案:大唐梵天记》王玄策比玄奘更出彩

最早看这个系列,是无意中在图书馆看到《大唐泥犁狱》,被介绍所吸引,对从另一个角度来讲述玄奘和西游的故事很感兴趣,对玄奘作为一个人的一面和破案的故事所吸引。借走读之,果然很有意思,...

Cloudox_
07/29
0
0
蓝桥杯 历届试题 分糖果

问题描述   有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果,然后进行下面的游戏:   每个小朋友都把自己的糖果分一半给左手边的孩子。   一轮分糖后,拥有奇数颗糖的孩子由...

xnh_565175944
2017/11/08
0
0
2018北京小学生信息学科普竞赛试题点评

今年的题量与往年一样。都是五道题。 第1题是近十三届比赛中最难的。往年的第一题,往往就是求一下两个数的积,或者字符串原样输出。而今年的第1题,则需要求开方和平方,难度明显增大了很多...

海天一树X
01/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用TensorFlow的AI程序运行报错AttributeError: module 'tensorflow' has no attribute 'xxx'

使用TensorFlow的AI程序,在运行时报错AttributeError: module 'tensorflow' has no attribute 'xxx',首先检查是否是包路径不对,一般是版本变化所致。...

织梦之魂
今天
3
0
提示浏览器版本低

本文转载于:专业的前端网站➭提示浏览器版本低 网站网页在遇到浏览器低版本(尤其是IE浏览器)时,提示浏览器版本低(如IE8以及以下),建议用户升级浏览器以获得最好体验。以下是代码: 1...

前端老手
今天
6
0
CentOS 7系统增加swap

转载请注明文章出处:CentOS 7系统增加swap swap是位于磁盘上的特殊文件(或分区),属于“虚拟内存”的一部分。通俗点就是内存的备胎,内存充足的情况下,基本上没swap什么事(和设置有关)...

tlanyan
今天
6
0
基于Prometheus和Grafana的监控平台 - 环境搭建

相关概念 微服务中的监控分根据作用领域分为三大类,Logging,Tracing,Metrics。 Logging - 用于记录离散的事件。例如,应用程序的调试信息或错误信息。它是我们诊断问题的依据。比如我们说...

JAVA日知录
今天
6
0
PHP运行时全局构造体

struct _php_core_globals { zend_bool magic_quotes_gpc; // 是否对输入的GET/POST/Cookie数据使用自动字符串转义。 zend_bool magic_quotes_runtime; //是否对运行时从外部资源产生的数据使...

冻结not
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部