hihoCoder#: 博弈游戏·Nim游戏 | 您所在的位置:网站首页 › 取硬币游戏必胜 › hihoCoder#: 博弈游戏·Nim游戏 |
【题目链接】:click here~~ 【题目大意】: #1163 : 博弈游戏·Nim游戏
10000ms
1000ms
256MB 描述 今天我们要认识一对新朋友,Alice与Bob。 Alice与Bob总是在进行各种各样的比试,今天他们在玩一个取石子的游戏。 在这个游戏中,Alice和Bob放置了N堆不同的石子,编号1..N,第i堆中有A[i]个石子。 每一次行动,Alice和Bob可以选择从一堆石子中取出任意数量的石子。至少取1颗,至多取出这一堆剩下的所有石子。 Alice和Bob轮流行动,取走最后一个石子的人获得胜利。 假设每一轮游戏都是Alice先行动,请你判断在给定的情况下,如果双方都足够聪明,谁会获得胜利? 提示:Nim?! 输入第1行:1个整数N。表示石子堆数。1≤N≤100 第2行:N个整数,第i个整数表示第i堆石子的个数A[i],1≤A[i]≤10000 输出第1行:1个字符串,若Alice能够获胜输出"Alice",否则输出"Bob"
样例输入 3 3 2 1 样例输出 Bob 【思路】: 古老而又经典的博弈问题:Nim游戏。 Nim游戏是经典的公平组合游戏(ICG),对于ICG游戏我们有如下定义:1、两名选手;2、两名选手轮流行动,每一次行动可以在有限合法操作集合中选择一个;3、游戏的任何一种可能的局面(position),合法操作集合只取决于这个局面本身;局面的改变称为“移动”(move)。4、若轮到某位选手时,该选手的合法操作集合为空,则这名选手判负。 对于第三条,我们有更进一步的定义Position,我们将Position分为两类:P-position:在当前的局面下,先手必败。N-position:在当前的局面下,先手必胜。 他们有如下性质:1.合法操作集合为空的局面是P-position;2.可以移动到P-position的局面是N-position;3.所有移动都只能到N-position的局面是P-position。 在这个游戏中,我们已经知道A[] = {0,0,...,0}的局面是P局面,那么我们可以通过反向枚举来推导出所有的可能局面,总共的状态数量为A[1]*A[2]*...*A[N]。并且每一次的状态转移很多。虽然耗时巨大,但确实是一个可行方法。 当然,我们这里会讲这个题目就说明肯定没那么复杂。没错,对于这个游戏有一个非常神奇的结论: 对于一个局面,当且仅当A[1] xor A[2] xor ... xor A[N] = 0时,该局面为P局面。 对于这个结论的证明如下:1. 全0状态为P局面,即A[i]=0,则A[1] xor A[2] xor ... xor A[N] = 0。2. 从任意一个A[1] xor A[2] xor ... xor A[N] = k != 0的状态可以移动到A[1] xor A[2] xor ... xor A[N] = 0的状态。由于xor计算的特殊性,我们知道一定有一个A[i]最高位与k最高位的1是相同的,那么必然有A[i] xor k < A[i]的,所以我们可以通过改变A[i]的值为A[i]',使得A[1] xor A[2] xor ... xor A[i]' xor ... xor A[N] = 0。3. 对于任意一个局面,若A[1] xor A[2] xor ... xor A[N] = 0,则不存在任何一个移动可以使得新的局面A[1] xor A[2] xor ... xor A[N] = 0。由于xor计算的特殊性,我们可以知道,一定是存在偶数个1时该位置的1才会被消除。若只改变一个A[i],无论如何都会使得1的数量发生变化,从而导致A[1] xor A[2] xor ... xor A[N] != 0。以上三条满足ICG游戏中N,P局面的转移性质,所以该结论的正确性也得到了证明。 代码: #includeusing namespace std;int main(){ int n,m,k; scanf("%d", &n); for(int i=0; i0。那么增加了这一条规则后,在Alice总先手的情况下,请你根据石子堆的情况判断是Alice会获胜还是Bob会获胜?提示:Sprague-Grundy 输入第1行:1个整数N。表示石子堆数。1≤N≤100 第2行:N个整数,第i个整数表示第i堆石子的个数A[i],1≤A[i]≤20000 输出第1行:1个字符串,若Alice能够获胜输出"Alice",否则输出"Bob"
样例输入 3 1 2 4 样例输出 Bob
【思路】:
居然最佳代码都是找规律的。。没有想出来怎么推导的,于是也只能找规律了~~ 规律见代码! 对于ICG游戏,我们可以将游戏中每一个可能发生的局面表示为一个点。并且若存在局面i和局面j,且j是i的后继局面(即局面i可以转化为局面j),我们用一条有向边,从i出发到j,连接表示局面i和局面j的点。则整个游戏可以表示成为一个有向无环图: 根据ICG游戏的定义我们知道,任意一个无法继续进行下去的局面为终结局面,即P局面(先手必败)。在上图中我们可以标记所有出度为0的点为P点。接着根据ICG游戏的两条性质,我们可以逆推出所有点为P局面还是N局面: 因此,对于任意一个ICG游戏,我们可以采取逆推的方法,标记出所有局面是N局面还是P局面。 但仅仅只是标记N、P,所能得到的信息太少,于是我们定义了Sg(Sprague-Grundy)函数: 对于一个游戏可能发生的局面x,我们如下定义它的sg值: (1)若当前局面x为终结局面,则sg值为0。 (2)若当前局面x非终结局面,其sg值为:sg(x) = mex{sg(y) | y是x的后继局面}。 mex{a[i]}表示a中未出现的最小非负整数。举个例子来说: mex{0, 1, 2} = 3, mex{1, 2}=0, mex{0,1,3}=2 我们将上图用sg函数表示后,得到: 可以发现,若一个局面x为P局面,则有sg(x)=0;否则sg(x)>0。同样sg值也满足N、P之间的转换关系: 若一个局面x,其sg(x)>0,则一定存在一个后续局面y,sg(y)=0。 若一个局面x,其sg(x)=0,则x的所有后续局面y,sg(y)>0。 由上面的推论,我们可以知道用N、P-Position可以描述的游戏用sg同样可以描述。并且在sg函数中还有一个非常好用的定理,叫做sg定理: 对于多个单一游戏,X=x[1..n],每一次我们只能改变其中一个单一游戏的局面。则其总局面的sg值等于这些单一游戏的sg值异或和。 即: sg(X) = sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) 要证明这一点我们只要证明: (1) 假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A,对于任意一个0 |
CopyRight 2018-2019 实验室设备网 版权所有 |