博弈论
总结模型和题目类型。。。
(1)简单模型:每次最多取m个,一共有n个东西,这个时候
是取到n%(m+1)==0的时候,后手赢
其他情况下,也就是n%(m+1)!=0的时候,先手赢
(显然,先手赢的概率更大,然后后手赢的条件会更苛刻一点……)
啊啊)
*** 在双方都取得最优状态下的,要么是必胜态,要么是必败态
【例题:】
有一堆n个石子,两人轮流从这堆石子中取石子,每人每次只能取(1,3,4)
最后取光的人获胜
先写一下判断小规律,最后总结,详细的过程我拍了一张在后面
【理科的东西要!!!要注意!!】
【不要不拘小节,不要差不多得了!!】
【这个地方并不是每次最多取n个,而是每次1 3 4 都可以,仔细分析,理性应对】
【啊// 所以要多写一点长记性...】
ps.我最擅长 刚讲过问问题的时候 说!!!
然后一说就说错!!!!!!!!!!!理科思维,仔细分析啊啊啊啊啊啊啊
(2)Nim Game
n堆不同的石子,双方轮流在任意一堆中取出至少一个
1 只有一个堆,那么先手赢,因为直接取完了
2 有两个堆:
当两个堆的数目相等时(先手输了)
达到【对称局面】
对手可以模仿你取的东西,从而让你没有可取
当两个堆数目不同时,(先手赢了)
因为他拿得使得两个堆一样,那么对方就达到了必败状态、
3 有很多堆的时候:需要用到SG函数
组合游戏的和通常是很复杂的,但是有一种新工具,可以使组合问题变得简单————SG函数和SG定理。
首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。
例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
这样其实也相当于模拟了通过拿棋子,然后,mex的是不能拿的。
我们知道,0是失败的状态,1是胜利的状态
这个SG是由这样转移过来的
SG[0]=0 还剩下0个的时候 是输了的(已经知道)
x=1时 (以下为转载)
x=1 时,可以取走1 - f{1}个石子,剩余{0}个,所以 SG[1] = mex{ SG[0] }= mex{0} = 1;
x=2 时,可以取走2 - f{1}个石子,剩余{1}个,所以 SG[2] = mex{ SG[1] }= mex{1} = 0;
x=3 时,可以取走3 - f{1,3}个石子,剩余{2,0}个,所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;
x=4 时,可以取走4- f{1,3,4}个石子,剩余{3,1,0}个,所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;
x=5 时,可以取走5 - f{1,3,4}个石子,剩余{4,2,1}个,所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;
以此类推.....
x 0 1 2 3 4 5 6 7 8....
SG[x] 0 1 0 1 2 3 2 0 1....
由上述实例我们就可以得到SG函数值求解步骤,那么计算1~n的SG函数值步骤如下:
1、使用 数组f 将 可改变当前状态 的方式记录下来。
2、然后我们使用 另一个数组 将当前状态x 的后继状态标记。
3、最后模拟mex运算,也就是我们在标记值中 搜索 未被标记值 的最小值,将其赋值给SG(x)。
4、我们不断的重复 2 - 3 的步骤,就完成了 计算1~n 的函数值。
自己总结一下,就是,把每次能走多少步,记录在f数组里面去。
对于每一个值(对于每次能走多少步)都算一下,然后这些记录在x数组里面去。
x就是初始值,减去f里面的每一个值能达到的结果。
然后再找一下没被标记过的最小的x值
(如果x有1 2 3 这样那么x就是0)
(如果0 2 3 )这样就是1
需要用到记忆化搜索。
理解的话,就是如果能达到0这个状态,那么它就是必胜的。
如果不能达到0这个状态,那么它就是必败的。
(减去之后-有什么呢,有1 2 3 能达到三个必胜的状态,那么它是必须败的)
这个就相当于例题里面啊,也就是我最后拍的那张纸上面的东西。
我感觉剩下的那个非空最小的是 距离必败状态还差多少的。。
反正就那样-。- 记住了也还行吧
//f[N]:可改变当前状态的方式,N为方式的种类
//f[N]要在getSG之前先预处理
f n 也就是每一次能走的不熟
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
int f[N],SG[MAXN],S[MAXN];
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 <= N; j++)
S[SG[i-f[j]]] = 1; //将后继状态的SG函数值进行标记
for(j = 0;; j++) if(!S[j]){ //查询当前后继状态SG值中最小的非零值
SG[i] = j;
break;
}
}
啊...... 就按照那个理解,其实也相当于就是把那个手写的过程转换成SG函数。。。。
下面我开始要做题了~
for(j = 0;; j++) if(!S[j]){ 这里其实就是 当s[j]==0的时候进入里面去循环..
https://cn.vjudge.net/contest/240695#problem/C
B是最简单的那种 E 就是样例(上文 )
---D
格子画了很半天,但我其实理解错了、
这个的意思就是给一个n*n的棋盘,只能走隔壁没走过的。
那么,第一个地方不能走,A走第一步,(减去2)
剩下的里面,无论B走什么,整个地图都可以分成一个2个格子的pair对儿~
B走啥,A都另外一个
(因为是偶数,可以直接平着铺开)
奇数的时候,没有这个格子,单从数字上看的话,A也不能走了....肯定失败的
如果有什么A能赢的,B肯定不会让A 到达那个状态... 所以A一定输...\
B就按照和偶数一样的时候的排列状态,就可以让A输了,而且A不能控制... 步数上就败了-.-
思路:格子总会走完的,所以说根据格子数量判断奇偶性就可以了.
【不能一下走很多,要一个一个走。。】
哎 我还想了一下 如果每次一走就走很多很多步的话 那么把对方逼到死角里面才能胜
逼到死角就是一下子把这一行走完 这样B只能转弯
B如果不走完的话 直接就死了 (A每次还是强迫他转弯 转弯就是只能每次走一个)
那么看一下一共能转弯几次..... 如果是奇数那么A赢了
发现... n是几的时候都只能n次
(大概n和m不一样的时候不一样吗??
不知... 不知道解答=- =
待续///
参考 https://blog.csdn.net/kimsimple/article/details/76043160
===花絮===
我:如果有一个m长,n宽的桌子,……
zj:你只要放他对称的就可以了 ,这是个经典问题!
我:我还没说完你就……
===花絮2===
理科啊啊啊!nim问题是,几个状态,直接就是石子数进行异或。
因为2 2 这样的,(就到了对称局面)
只有这种情况,异或的结果是输了的
【异或是无进位的加法!!!所以!!而且一般只对于二进制,所以一般。。 是异或不到0的】
所以 对于 3+5 就是(011+101) 本来应该等于1000但是每一位都不进位 所以还是110 是达到不了0的状态的
所以 对于3 3 3 先拿成3 3 1 这时 对手取1 你就到了必胜客 (tai太难打了) 对手取其他的 你模仿他 最后一步的时候多拿一根
反正对手必胜客+1啦。。。 赢不了的就败了
_(:з」∠)_
===花絮3===
SG函数其实是虚的 都是虚的 在这个例子里写成 1 也没有关系啊 f s什么的都是虚的
你最后想要的只不过是这个点能不能到达必胜客 那个状态--。-
他们也不过都是你实现问题的手段
===花絮4===
zj觉得我想错的那个题想法很不错,还说我又不是因为学了博弈论,才会这个东西的……