博弈论补充异或(不进位加法)

本文主要是介绍博弈论补充异或(不进位加法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

博弈论小游戏(可以和家人玩..讲真)
(1)每次最多拿m+1个
(2)大脸盘子放对称的
(3)有两堆石子怎么放(数量不同)

tips 1
在典型的nim问题中,一堆石子,(每次拿任意个)先手如果要赢,(输了就是-1),有多少种走法
***
通过公式(石子数量直接异或可以拿到结果)

这个时候,先手是怎么赢的?
走任意的,就可以赢吗?并不是。
要想达到能够赢了的状态，要达到的是必胜客的状态，也就是异或起来等于0的状态
设本来不等于0的是k，如果通过拿了能拿到ai’=ai^k就可以拿多少个没事只要拿了就可以... ai^k<ai
以及它的在k最高位是1
因为不进位的加法（否则k的最高位那个1是怎么得到的）
若a1^a2^...^an=k，则一定存在某个ai,它的二进制表示在k的最高位上是1
****以下为转载针对HDU 1850- I题****
Nim博弈

题意：有m堆牌，两个人先后取某堆中的任意（不少于一）张牌，最后取完者胜；问先手取胜第一次取牌有多少种取法。

思路：1）如若给出的是必败状态：a1^a2^......^an=0,则先手不会有任何可能获得胜利；

2）若给出的是必胜状态：a1^a2^.......^an=k,(其中k不为零)，那么我们的目的是要把必胜状态

转化为必败状态从而使得先手胜利。若a1^a2^...^an!=0，一定存在某个合法的移动，将ai

改变成ai'后满足a1^a2^...^ai'^...^an=0。若a1^a2^...^an=k，则一定存在某个ai，

它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定

成立。则我们可以将ai改变成ai'=ai^k，此时a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。

tips 2 HDU 第二场的game...

.. 还没打完先不剧透了

反正最后一个不能取了为止

A 可以取 1 B可以取其他的 B赢了

那么A可以第一次就把B要拿的和1都拿走

异或：

.....

bool竟然差了这么大。

sg函数不够熟悉吧，不理解的话看板子也要会用啊。

https://vjudge.net/problem/HDU-1536

（F）

【模板】

/*
void  getSG(int n) {int i, j;memset(SG, 0, sizeof(SG));//因为SG[0]始终等于0，所以i从1开始for (i = 1; i <= n; i++) {//每一次都要将上一状态 的 后继集合 重置memset(S, 0, sizeof(S));for (j = 0; f[j] <= i && j <= k; j++)S[SG[i - f[j]]] = 1;  //将后继状态的SG函数值进行标记for (j = 0;; j++) if (!S[j]) {   //查询当前后继状态SG值中最小的非零值SG[i] = j;break;}}
}*/
void sg_solve( int t)   ///N求解范围 S[]数组是可以每次取的值，t是s的长度。
{// t 是每次可以取的值的那个集合的大小...!!!//f是所有可能的取值 hash是int i, j;memset(sg, 0, sizeof(sg));for (i = 1; i <= N; i++){memset(Hash, 0, sizeof(Hash));for (j = 1; j <= t; j++)if (i - f[j] >= 0)//  if  这个i减去它有效....  有效就是 这一步和之后所有可达的点Hash[sg[i - f[j]]] = 1;// int reach=i-f[j]  Hash[sg[reach]]=1;//很多个reach都被标记了..//这里必须要是0 !!!!for (j =0; j <= N; j++) {if (!Hash[j]) {//if(hash[j])==0 break(没被访问过//(hash记录访问与否..sg[i] = j;break;}}//break是跳出了上面的循环..}
}

记得你读入的时候那个就是j<=t的以及，下面的j是可以为0的

（G）

我觉得关键在于一个状态，在这个状态里不管它是必胜还是必败，我都有可能完全自己掌控-/ 完全掌控别人

就是(a>2*b的时候) 可以变成a%b+b 对手只能-b和a%b,b

参考博客：