博弈:

1.跑完前三行前三列的dp值,会找到主对角线胜负一样的规律233

2.agc002e https://blog.csdn.net/zlttttt/article/details/78145947

思路,转化为图上,再利用规律结论

【p.s. 所有一步操作能进入必败点的都是必胜点(根据定理:必败点只能都进入必胜点 ; 如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点)】

【必胜点和必败点之间只是转移关系,当前在必败点则必败,在必胜点则必胜,不存在中途转移】

2.1.给定两个字符串S,T,两人轮流去S的首尾,当S变为T的子串是操作的那人输

思路,将l作为x轴,r作为y轴,那么就可以转化为刚才1或2的模型

3.k倍减法游戏 $O(n^3) ->O(n^2)​$ Poj-3922

https://blog.csdn.net/acm_cxlove/article/details/7836544

https://blog.csdn.net/tbl_123/article/details/24884861?utm_source=tuicool&utm_medium=referral

平等博弈问题{Aice和Bob能做的决策一样【每个游戏都有个SG的值(SG函数:

<font color=red>可以用SG函数来理解必胜点和必败点的转化关系</font>

几个单独游戏,整个游戏的SG值等于几个游戏的异或起来

$SG(G_1+G_2)=SG(G_1) xor SG(G_2)​$

e.g.取石子问题,可以把每一堆建成一个有向无环图,然后分别做

对一堆个数为i的石子,$SG(i)=i​$

1.对一堆个数为i的石子,可取1-k个,SG(i)=i%(k+1)

因为最多取k个,k个后继状态,然后画下图类似滑动窗口就行了

2.对一堆个数为i的石子,可取l-r个,SG(i)=i % (l+r) / l

3.对一堆个数为i的石子,每次可以s将一堆分裂为两堆,或在一堆取任意多个,

那么$sg[i]=mex(sg[j],sg[j] /xor/ sg[i-j])​$

4.取石子,每次能拿掉一个因子:_builtin_ctz(x) 返回<font color=red>末尾为0的个数</font>【<font color=orange>找规律从这方面考虑</font>

5.取石子,每次能拿掉一个互质的数

6.如果一个格子放了,那么其两边的都不能放,故被划分为两个独立的游戏

7.CF的睿智题http://codeforces.com/contest/1091/problem/H

8.https://blog.csdn.net/u014609452/article/details/60341287

9.区间mex的做法:

(1)莫队(2)主席树

https://blog.csdn.net/baidu_36797646/article/details/79997537

https://blog.csdn.net/includelhc/article/details/79593496

10.N阶nim

11.nim3

12.存在最大匹配不包含U,那么先手只能走非匹配边,所以先手必败

https://www.luogu.org/problemnew/show/P1971

http://codeforces.com/gym/100886/problem/B

13.

存在u,$deg_u>=4​$ ,则Alice胜,

14.cf 794 e

思路:先转化为0/1来想,让大于等于x的为1,小于等于x的为0

一般思路:由简至繁,考虑简单的情况

15.https://atcoder.jp/contests/agc010/tasks/agc010_f

Last modification:March 6th, 2019 at 12:20 pm