分类: [博弈论]

BZOJ5248[2018多省省队联测]一双木棋

题目传送门 方法一 看完题目,觉得这是一个神奇的博弈论题目,不会做……然后,看了一眼数据范围,n,m<=10?!好像可以暴力DP啊?来算一下可能的状态数量,同一行中放棋子的点一定是最左边的若干个,令A[i]表示第i行左边的A[i]个格子里放了棋子,根据题目要求不难发现这些性质:m>=A[1]>=A[2]>=A[3]>=…>=A[n-2]>=A[n-1]>=A[n]>=0,可以算出状态A[1~n]只有${n+m+1}\choose{m+1}$个,也就最多只有352716,可以放心的DP。 code: #include&lt;bits/stdc++.h&g ......

BZOJ1188 分裂游戏

题目传送门 Description 有n堆石子,每次可以选三堆(i,j,k),满足i<j<=k,从i中取出一颗石子,在j和k中各放入一颗,发现有先手必胜的策略,问第一步有多少种取法并输出字典序最小的一组 Solution 一道博弈论的题目,可以发现对于每一堆石子,数量不是关键,关键在于奇偶,如果一堆石子有偶数个,则后手可以每次模仿先手在这堆石子上的操作,如果是奇数个则不一定。我们可以通过预处理出每一堆石子的sg函数(sg函数的求解只与n有关,与每堆石子的数量无关),对于一堆数量为偶数个的石子,可以不管,对于奇数个,则先将ans异 ......

计蒜客 A String Game

题目传送门 这道题是那场比赛里唯一一道比较容易的题目,也是我唯一那道AC的题…… 由于要在si后加字母,而且要保持si为t的子串,这很明显要用到SAM。任何这题就变成了在一张DAG中的某些点上有若干棋子,每次操作要把其中一个棋子沿着DAG的边移动一格,不能操作者负。这就是一个非常裸的博弈论问题了,求出DAG上每个点的SG函数,然后对每个棋子所在的点的SG函数求异或和,如果结果为0则Bob获胜,否则Alice获胜。 code #include&lt;cstdio&gt; #include&lt;cmath&gt; #include&lt ......

BZOJ4589 Hard Nim

题目传送门 只要知道NIM游戏是什么,就会发现这道题其实就是要求n个数异或和为0的方案数,其中这n个数能且只能取小于等于m的质数。 构造向量a[i]=[i为质数],将n个a做异或卷积得到的向量b,b[0]即为答案。 所以只要快速幂求异或卷积就行了。要注意的是,快速幂中求异或卷积的时候不用每次都FWT和UFWT,这样是两个log的,会TLE(观察代码会发现每次UFWT后就会紧接着做一次FWT……没有任何意义)。其实只要FWT一次,对a的每一位都求快速幂就行了,最后再UFWT。   code #include&lt;cstdio& ......