[BZOJ1188][HNOI2007]*游戏(博弈论)

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1188

分析:

设SG[i]表示一个石子在位置i上的SG值

这个很容易暴力求,因为i的后继状态肯定是所有的(j,k),其后继状态的SG值就是SG[j]^SG[k]

然后整个游戏的SG值就是SG[1]^SG[1]^SG[1]^...^SG[2]^SG[2]^......也就是说一个堆有多少个石子就要异或多少下。

因为异或的特殊性质,所以如果一个堆的石子个数是偶数,那么就是偶数个同样的数相异或,结果为0,不考虑。如果一个堆的石子个数是奇数,可以看作偶数+1,所以只要异或1次

至于题目还要求第一步的方法和方案数,可以枚举解决。

设整个游戏的SG值为ans

那么我们枚举(i,j,k)作为第一步,那么什么样的(i,j,k)可以作为第一步呢?最直接的想法对于每个i,j,k,把a[i]-=1,a[j]+=1,a[k]+=1,对整个局面重新异或计算下新的全局SG值。当然其实没必要这么做,这样很慢的。再次根据异或的特殊性质,可以直接新的SG=ans^SG[i]^SG[j]^SG[K]。为什么呢?因为我在原来的基础上,再次异或一个SG[i]就相当于减去一个i位置上的石子,异或一个SG[J]就相当于加上一个j位置上的石子,异或一个SG[k]就相当于加上一个k位置上的石子。

于是就解决了。

原文地址:https://www.cnblogs.com/wmrv587/p/4399301.html