当前位置: 代码迷 >> 综合 >> HDOJ 2509 Nim博弈
  详细解决方案

HDOJ 2509 Nim博弈

热度:89   发布时间:2024-01-20 20:22:11.0

这题只是一只纸老虎。但是我确实被它吓到了。

你瞧瞧题中说的,一个堆可以分裂成两个堆,这么复杂的问题实在不会做啊!

准备搜题解,看看别人都是寥寥数句结题。于是我也赌气不看题解了,自己推。

分析:

照样设置T0,S0点。根据题意可知T0为必胜点,S0为必败点。

S1点:有且仅有一堆的数量>=2,这里为啥不用考虑分割堆呢?

S1能转变为S0点,主动权当然在面临这个选择的人身上,显然是必胜点。

这一步分析完,豁然开朗了!

接下来推S2以及T2。

显然的T2可推S1以及S2。S2可推T2以及S1。

S2一定可推T2,T2不一定可推S2。故S2为必胜点,T2为必败点。

故,必胜点为T0,S1,S2。和前面那题一样....

#include<iostream>
using namespace std;int main()
{int n;while( scanf("%d",&n)!=EOF ){int num[111],xo=0;int sin=0,mul=0;for( int i=1;i<=n;i++ ){scanf( "%d",&num[i] );num[i]==1?sin++:mul++;xo^=num[i];}if( (mul==0&&xo==0)|| mul==1 || (mul>1&&xo) )printf( "Yes\n" );elseprintf( "No\n" );}return 0;
}