当前位置：网站首页>Nim博奔问题

Nim博奔问题

2022-07-17 01:52:00 【小卢要刷力扣题】

文章目录

题目
题目意思
结论
- 例子
代码

题目

给定一个正数数组arr
先手和后手每次可以选择在一个位置拿走若干值，
值要大于0，但是要小于该处的剩余
谁最先拿空arr，谁赢。根据arr，返回谁赢

题目意思

所有的数>=0,每一轮不管谁都不能拿0
谁最先把最后一点数拿完谁赢
在这里插入图片描述
先手跟后手,绝顶聪明,每一个人都充分为所有为自己打算,
而且绝对理智,问你,给你一个数组状况返回谁会赢

结论

所有的数异或起来,如果异或和不等于零先手赢,如果异或和等于0后手赢
在这里插入图片描述
先手的大目标:
让后手最先面对所有数组中都是0的状态。
大目标不知道怎么实现,转换一下目标,

所有数都异或起来的异或和,我如果先手能够做到我面对这些数的异或和它不等于零。
但是我拿完之后每一次都让后手面对的异或和等于0,那么最后胜利是先手
我们知道最后全0的时候异或和是0。所以就这么玩下去,它总有一个时刻全0的时候,而我是遇不到的,只会让后手遇到,所以我必胜的大目标被我们变成一个看似更难的目标。

例子

在这里插入图片描述
把二进制写出来,数组7,5,3整体异或和001

先手在1这拿一个,变成6,更后面的5,3异或和为6的合起来异或和为0

后手再拿的时候,他不管在哪个位置上拿哪个数都一定会让异或和从0变成不是零,
因为他必然会改变某一个位置上一的数量,改变了它的异或和就不是0,然后先手继续让它异或和变0,先手必胜.
但是这样做的前提是什么?初始的时候异或和得是非零的先手才能这么干,如果先手面对一个一上来就是异或和等于0的状态,后手赢

代码

	public static void printWinner(int[] arr) {
    
		int eor = 0;
		for (int num : arr) {
    
			eor ^= num;
		}
		if (eor == 0) {
    
			System.out.println("后手赢");
		} else {
    
			System.out.println("先手赢");
		}
	}