当前位置 : 主页 > 手机开发 > harmonyos >

北大ACM poj2234

来源:互联网 收集:自由互联 发布时间:2023-08-26
/*随机博弈指的是这样的一个博弈游戏,目前有任意堆石子,每堆石子个数也是任意的,双方轮流从中取出石子,规则如下:1)每一步应取走至少一枚石子;每一步只能从某一堆中取走部


/*随机博弈指的是这样的一个博弈游戏,目前有任意堆石子,每堆石子个数也是任意的,双方轮流从中取出石子,规则如下:
1)每一步应取走至少一枚石子;每一步只能从某一堆中取走部分或全部石子;
2)如果谁取到最后一枚石子就胜。
也就是尼姆博弈(Nimm Game)。
必败局面:也叫奇异局势。无论做出何出操作,最终结果都是输的局面。必败局面经过2次操作后,可以达到另一个必败局面。
必胜局面:经过1次操作后可以达到必败局面。
即当前局面不是必败局面就是必胜局面,而必胜局面可以一步转变成必败局面。
最终状态:
(1)最后剩下一堆石子;(必胜局面)
(2)剩下两堆,每堆一个;(必败局面)
(3)当石子剩下两堆,其中一堆只剩下1颗,另一堆剩下多于n颗石子时,当前取的人只需将多于1颗的那一堆取出n-1颗,则局面变为刚才提到的必败局面。(必胜局面)
判断当前局势是否为必胜(必败)局势:
1)把所有堆的石子数目用二进制数表示出来,当全部这些数按位异或结果为0时当前局面为必败局面,否则为必胜局面;
2)在必胜局面下,因为所有数按位异或的结果是大于零的,那么通过一次取,将这个(大于其它所有数按位异或的结果的)数下降到其它所有数按位异或的结果,这时局面就变为必败局面了。
定理:一组自然数中必然存在一个数,它大于等于其它所有数按位异或的结果。
证明:原命题等价于,设a1^a2^... ^an=p,p≠0时,必存在k,使得ak^p<ak(当p=0时,对于任意的k,有ak^p=ak)。
设p的最高位是第q位,则至少存在一个k,使得ak的第q位也是1,而ak^p的第q位为0,所以ak^p<ak
    补缀一点,(a^b)^b=a^(b^b)=a^0=a,所以ak^p相当于“其它所有数按位异或的结果”。
参考:https://sites.google.com/site/lene13/Home/sophi-mass/0-7

例1:2 45 45

45^45=0,45和45的异或等于0。
例 2:3 3 6 9

局势(3,6,9)因为3^6^9不等于0,所以这是一个必胜局势。
 3 011

^6 110

 5 101 
即从第3堆中的9个中取走9-5=4个,则(3,6,9)->(3,6,5),3^6^5=0,故(3,6,5)为奇异局势,即从必胜局势转变成必败局势
*/
#include<stdio.h>
#include<stdlib.h>
main()
{
	long pile[22];
	int m,i;
	while(scanf("%d",&m)!=EOF)
	{
		memset(pile,0,sizeof(pile));
		for(i=0;i<m;i++)
			scanf("%ld",&pile[i]);
		for(i=1;i<m;i++)
			pile[i]=pile[i-1]^pile[i];//异或
		puts(pile[m-1]?"Yes":"No");//不为0输出Yes,为0输出No 
	}
}



上一篇:北大ACM poj1555
下一篇:没有了
网友评论