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; i

#1173 : 博弈游戏·Nim游戏·三

描述

在这一次游戏中Alice和Bob决定在原来的Nim游戏上增加一条规则：每一次行动时，不仅可以选择一堆取走任意数量的石子(至少取1颗，至多取出这一堆剩下的所有石子)，还可以选择将一堆石子分成两堆石子，但并不取走石子。比如说有一堆石子为k个，当Alice或者Bob行动时，可以将这一堆石子分成两堆，分别为x,y。满足x+y=k,x,y>0。那么增加了这一条规则后，在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 <= B < A，总存在一个X的后续局面Y，使得sg(Y) = B。

(2) 假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A，不存在一个X的后续局面Y，使得sg(Y) = A。

下先证明(1)：

假设M = A xor

B，设M表示为二进制之后最高位的1为第k位。所以A的第k位为1，B的第k位为0。又因为A的第k位为1，至少存在一个i，sg(x[i])的第k位也为1。那么一定有sg(x[i]) xor M < sg(x[i])，即一定通过某个操作使x[i]变为x[i’]，且sg(x[i’]) = sg(x[i]) xor M。那么：

sg(x[i’]) xor Other = sg(x[i]) xor M xor Other = M xor A = B

下证明(2)：

若sg(X) = A，sg(Y) = A。不妨设我们改变的游戏为x[i]，则X=x[1..n], Y=x[1…i’…n]。有sg(x[i]) = sg(x[i’])，产生矛盾，所以sg(Y)不可能等于A。

现在让我们回到我们的题目上：

局面上一共有N堆石子，每一次我们只能改变一堆石子。那么我们可以将每一堆石子看作一个单一游戏。

对于一堆石子，若该堆石子数量为0，就达到了终止状态，所以sg(0) = 0。

若其石子数量为k，接下来我们从k=1开始枚举递推每一个sg(k)。对于k，其可能的后继状态有：

(1)不分堆：石子数量为k’=0..k-1，则sg(k’)

(2)分堆：石子变为2堆，数量为(1,k-1),(2,k-2),…,(k-1,1)。设第一堆的石子数量为i，则sg值为sg(i) xor sg(k-i)。(这里用到了sg定理)

那么可以推算出sg(k) = mex{sg(0), sg(i), sg(i) xor sg(k - i) | i = 1..k-1}。

k 0 1 2 3 4 5 6 7 8 9 10 11 12 …sg(k) 0 1 2 4 3 5 6 8 7 9 10 12 11 …

对于N堆石子，其sg值则为这N堆各自的sg值异或和。

代码：

#includeusing namespace std;int get_sg(int n){ if(n==0)return 0; int re=n%4; if(re==0) return n-1; else if(re==3) return n+1; else return n;}int main(){ int n, yihuo=0; scanf("%d", &n); for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。