博弈论补充 异或(不进位加法)
博弈论 小游戏(可以和家人玩..讲真)
(1)每次最多拿m+1个
(2)大脸盘子 放对称的
(3)有两堆石子 怎么放(数量不同)
tips 1
在典型的nim问题中,一堆石子,(每次拿任意个)先手如果要赢,(输了就是-1),有多少种走法
***
通过公式(石子数量直接异或可以拿到结果)
这个时候,先手是怎么赢的?
走任意的,就可以赢吗?并不是。
要想达到能够赢了的状态，要达到的是必胜客的状态，也就是异或起来等于0的状态
设本来不等于0的是k，如果通过拿了能拿到ai’=ai^k就可以 拿多少个没事 只要拿了就可以... ai^k
因为不进位的加法（否则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^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） 【模板】 记得你读入的时候那个就是j<=t的 以及，下面的j是可以为0的 （G） 我觉得关键在于一个状态，在这个状态里不管它是必胜还是必败，我都有可能完全自己掌控-/ 完全掌控别人 就是(a>2*b的时候) 可以变成a%b+b 对手只能-b和a%b,b 参考博客： （主要就是找到一个确定的状态。 这个确定状态的前面- b-a*x和b-2*a*x都可以达到..） （参考博客）http://www.cnblogs.com/caijiaming/p/9313671.html 这篇里面很有用的! [1] [2]注意 “达到对称状态”这里（很重要-。-） ====例行花絮==== /*
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是跳出了上面的循环..}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！