小衣同学的博客

那么，如果l<=r且[l,r]内有下一个vector内必胜(sg=1)的元素，当前局面就必败(sg=0)不能再直接dp[i][j][k]表示数组a的第i个做开始局面时，位置(j,k)为起点时的获胜情况了。对于所有颜色v都处理出这样的位置集合，记为win[v]，表示v作为最后一步时的所有获胜位置。这个位置序列，是一个第一维增序，第二维降序的序列，形如(1,4)(2,3)(3,2)这种。只要能走到win[a[l]]内任意一个元素的都是必败的，否则就是必胜的。那么对于序列a的最后一个元素，考虑所有获胜位置，

如果能走旁边的链（也就是当前点，刨去标记链以外的子树中最长的链），使得对面走剩余的连通块无法比你大，就走旁边的链，并宣告获胜。维护实际是一个区间最值，可以用set或者st表。两个人的策略是一样的，把1到u的路径标记，否则沿着标记链，朝对面的方向走一步。

一条数轴，0和l+1两点有墙，[1,l]这l个点需要放2n头奶牛，其中n头属于FJ，n头属于FN。那么，有0<𝑎1<𝑏1<𝑎2<𝑏2<…<𝑎𝑛<𝑏𝑛<𝑙+1成立。每个间隔都是奇数，每个空隙都是>0的数，相加之和为n+1的方案数。如果 𝑎1,𝑎2,...,𝑎𝑛 代表一个农场主的奶牛的位置，而 𝑏1,𝑏2,...,𝑏𝑛 代表另一个农场主的奶牛的位置，每次一个人选一个数字k(1<=k<=n)，并选择k头奶牛，FJ先手，给定l(l<=1e6)和n(n<=l/2)，然后将问题转化成，n个间隔，此外还有n+1个空隙，

1. 如果第一个点是空，那么第n个点是球，长为n-2的链上选k-1对匹配的方案，k个空位对应n-k个字母，终态局面定下来之后，乘上俩人填n-k个字母的顺序，Alice和Bob在一个圆格上玩游戏，格子共有1，...，n个，格子i(i<n)与i+1相邻，n与1相邻，每个格子初始都是空的，特别地，填的时候，相邻的格子不能有相同的字母，否则无法填。所以，不妨认为是n个点的环上，选k对「左球右空」的方案。2. 如果第一个点不是空，长为n的链选k对匹配的方案，Alice先手，每次可以选一个空的格子，填A或者B，

有dp[i][j]=(dp[i-1][j]-k+dp[i-1][j-1]+k)/2=(dp[i-1][j]+dp[i-1][j-1])/2。第一步(i,i)只能向下，因为(i,i)和(i-1,i-1)之间不再满足dp关系式，是O(1)求的dp[i][i]=i。所以alice会这样选择k，使得两部分相等，有dp[i-1][j]-k=dp[i-1][j-1]+k，有dp[i][j]=min(dp[i-1][j]-k,dp[i-1][j-1]+k)终态dp[i][i]=i，即必须加i轮时，每轮都加1即可。

打表可知，当(b/a)%(a+1)为偶数时，先手必胜，(b/a)%(a+1)为奇数时，先手必败。这样若干轮后，(b/a）起到了对（a+1）取模的效果，即当前剩余石子数不超过a，t(t<=1e4)组询问，每次询问(a,b)（0<=a,b<=1e18），(b/a)%(a+1)为奇数总可以转移到(b/a)%(a+1)为偶数，(b/a)%(a+1)为偶数总可以转移到(b/a)%(a+1)为奇数，先手和后手可以取1（1个a）枚，a枚（a个a），a^2，...当(b/a)%(a+1)为偶数时，先手可以先取1个。

②如果仅右侧有棋子，说明当前位置必胜态，同行左侧都是必胜态，同行不可能再出现必败态了，但同列下方都是必胜态，还有可能在上方出现必败态，接着考虑(x-1,y)1. (x,y)在右下角，必败，sg(x,y)=0，同时第x行左侧和第y列上侧所有sg值为1，接着考虑(x-1,y-1)当你在(x,y)位置时，下一步可以走到同一行靠右的位置(x'=x,y'>y)或同一列靠下的位置(x'>x,y'=y)2. 间接获胜的情形也是不存在的，是因为上一个必败态(x',y')产生后，接下来考虑的是(x'-1,y'-1)

那如果Alice和Bob在这些点上玩的话，都只会走向状态未确定的点，使Alice永远走不到防御点。防御点是一个终态点，如果Alice不能到防御点，则Bob不能去指向防御点的点，以此类推…如果防御点位于左侧，则Alice到这个点就视为（在只考虑这个防御点时）获胜，置dp值为1。每次可以选择一个当前点有出边的点，走到那个点上，如果当前点没有出边，则游戏结束。枚举完所有点后，没被过滤掉的点，就是Alice的必胜起点，若不存在则Bob必胜。如果一个点的所有下游（反图的上游）都是对方的必胜点，则这个点是必败点。

算法学习笔记(74): 二分图博弈 - 知乎。

AtCoder Beginner Contest 278 G.Generalized Subtraction Game(思维题/博弈 multi-sg)

题目t(1<=t<=1e5)轮比赛，第一轮比赛主人公先手，第i轮比赛给出si,ei(1<=si<=ei<=1e18)，si为初始的值，ei为终止局面的值，对于当前为a的值，操作的一方可以将其变成a+1或2a，若一方操作之后，当前的数大于ei，则操作的这个人输，第i轮输的人会在第i+1轮先手，t轮过后，最后一轮的胜负情况是整个局面的胜负情况问，先手是否有策略最后一轮必胜，先手是否有策略最后一轮必败，输出1/0（能/不能）思路来源AlexPanda.

A. 才艺展示(sg找规律)题目Cuber QQ 和 Little Fang 两人会按照游戏规则轮流写 {1,2,⋯,N} （N是一个正整数）中的一个数。游戏的规则是这样的，若一个人写下数i， 则另一个人只能写i+1或2i（i,i+1,2i均不超过N）。两个人中，谁先写到N这个数字，谁就能获胜。当然 Cuber QQ 为了表现自己的绅士，他让 Lit...

题目给定w*h的格纸，轮流沿格线切割，当前有好几块格纸的，可以挑任意一块切，先切出一个1*1方格的一方获胜，给定w和h(2<=w,h<=200)，问谁必胜思路来源《挑战程序竞赛》第二版题解注意到如果切割出了1*h或者w*1的纸张则下一步对手一定会切这一张，使己方必败所以切的时候，只考虑在大于等于2的行和列里转移剩下答案就是两个子局面的异或了，...

题目给你一棵n（n&lt;=1e5）个节点的树Alice和Bob玩游戏，Alice先手 每次轮到某玩家的时候，①若该玩家无边可删，则该玩家输②否则该玩家可以选择一条边，删掉这条边，将原树划分成两棵树，一棵带根（root==1）的，一棵不带根的，并把不带根的这棵树的所有边全删掉 给定这棵树，问谁必胜思路来源https://blog.csdn.n...

题目有1*n(3&lt;=n&lt;=2000)长的格子，A和B轮流操作，A先，每个人可以选择一个格子并将其打勾轮到某人操作时，不得跳过如果A打完勾后，有三个勾连在一起，则A胜给定n，问谁必胜思路来源https://www.cnblogs.com/neighthorn/p/6441252.htmlhttps://www.cnblogs.com/Mrsrz/p/9...

题目有N个棋子，第i个在x轴上的ai位置，如果棋子左边有空，可以不越过其它棋子向左移动，特别地，最左边的棋子可以移动到1，然后就动不了了不能移动的输，对于给定局面，问谁必胜思路来源https://blog.csdn.net/qkoqhh/article/details/80434749题解Nim游戏的变种直观的来看，①有一个棋子的时候，如果在1处则先手败，否...

题目n个珠子开始是圆排列在一起的每人只能取m个连续的珠子不能取的判负给定n和m，问谁必胜思路来源自己一年多前的代码QAQ题解现在再补这个题的时候发现不会做了QAQ温故而知新吖，毕竟那个时候懵懵懂懂抄的题解然后现在也算是更深入了解Multi-SG这些东西了先预处理好&lt;=m的情况，注意长度为n的取了m之后变成n-m一条链，其充要条件是n&g...

题目n堆石子，每次可以选一堆石子取若干（像Nim游戏一样）也可以把一堆石子分成三堆非空石子，取走最后一颗石子的胜，给定局面问谁必胜思路来源https://blog.csdn.net/Code92007/article/details/87892307题解Multi-SG打表，考虑三个子状态为后继即可先把100以内表打出来，发现除以8余7的正整数和整除8的正整...

题目树形删边问题Anti-SG游戏思路来源https://blog.csdn.net/Code92007/article/details/87892307题解好叭，粘了个自己的知识总结的题解挺裸的题目，就是综合上两者规律即可树形删边：①叶子结点sg值为0②其余节点sg值为其(子节点sg值+1)的异或和Anti-SG先手必胜（SJ定理）：当且仅当①...

题目n堆苹果，每堆ai个每次可以选一堆然后取若干个连续的苹果最后一个取苹果的人输（Anti-SG）问先手是否有必胜策略思路来源https://blog.csdn.net/Code92007/article/details/87892307题解把所有后继状态打好，注意到也可从中间截取向两个子游戏转移的后继状态处理好1-100的sg值的表然后按Anti-SG...

题目有n组石子，每组石子有两堆石子，两人轮流对每个没有结束的游戏进行操作，每次可以从多的那一堆里减去少的的若干倍（当然不能超过多的这一堆的上界）两堆里至少有一堆为0就视为该子游戏结束给定局面，问谁必胜，胜当且仅当最后结束的一局胜，即对手此时无法操作思路来源https://www.cnblogs.com/cjyyb/p/9495063.htmlhttps:...

题目有n块xi*yi的巧克力，Alice(先手)可以选一块xi*yi的巧克力，并把它切成p*yi和q*yi（p+q==xi）两块巧克力，而Bob可以选一块xj*yj的巧克力，并把它切成xj*u和xj*v（u+v==yj）两块巧克力，简单来说，就是Alice竖着切而Bob横着切，给定局面，最优抉择，问谁必胜思路来源https://blog.csdn.net/qq_...

思路来源凯爷题解显然是一波SG函数的题，然后1e9的话肯定会T，1e5的话没准还好点……毕竟每个数都有因子1，会从1e9往下一直转移……然后就T了GG所以这题就是打表找规律找出来的规律是，SG值恰为该数能整除的2的最大幂次+1心得天天看逼乎上SG打表真到自己身上了不会打了……感谢凯爷给我这么一个打表机会……不然出去打不出来表都不好意思说自...