BZOJ分析后手必胜当且仅当每堆石子个数异或和为 $0$。设 $dp_{i,j,k}$ 表示前 $i$ 堆石子,扔掉的堆数模 $d$ 等于 $j$,扔掉的每堆石子个数异或和为 $k$ 的方案数。然而这样子复杂度是 $\mathcal{O}(nmd)$ 的,显然过不了。考虑一个优化:把所有堆按石子个数从小到大排序,这样子加进第 $i$ 堆时异或和不会超过 $2^{\operatorname{h...
AtCoderLuogu分析考虑 $u$ 是必胜点的条件是什么。显然,应该存在一个相连的节点 $v$ ,满足 $a_v<a_u$ 且 $v$ 是必败点。这样子的话,先后手就会在 $(u,v)$ 上反复横跳,然后后手就输了。正确性应该比较显然...?代码// =================================== // author: M_sea // websi...
UVaLuoguVjudge分析SG 函数好题。我们把一个石头当做一个游戏,那么终态就是在一个没有出边的点上。考虑如何计算 SG 函数。注意到有些点可能会重复选,而选 $2$ 次对 SG 函数不会有影响( $a\oplus a=0$ ),于是只需要枚举 $2^{deg}$ 种状态,算出 SG 函数然后取 $\operatorname{mex}$ 即可。注意这里选的点数和选的次数的奇偶性要相同...
UVaLuoguVjudge分析设 $SG(i,j)$ 表示一堆是 $i$ ,另一堆是 $j$ 的 SG 函数值。打个表看下有没有规律:0 1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 0 16 8 17 4 18 9 19 2 20 10 21 5 22 11 23 1 24 12 25 6 26 13 27...
CodeforcesLuogu分析博弈论好题。首先可以发现,不到最后是不会选择猜的。假设你问了一张牌,对手没有,那么对手就会怀疑这张牌是桌上那张。考虑这样一种神奇的操作:询问一张自己手上有的牌。这样子对手就会怀疑这张牌是桌上的,然后如果他问了他就输了。我们把这种操作称为欺骗。考虑 DP 。设 $f_{n,m}$ 表示先手有 $n$ 张牌、后手有 $m$ 张牌时,先手的获胜概率。我们列一个表格...
之前好像写过一篇,结果被我误删了...所以重新补一下。比赛地址Parity简单分类讨论。如果$b$是奇数显然此时$b^{k-i}$全部为奇数。于是$a_i\cdot b^{k-i}$是奇数当且仅当$a_i$是奇数。于是统计$a$中奇数的个数$s$。如果$s$为奇数,则整个式子为奇数;否则整个式子为偶数。如果$b$是偶数显然仅有$b^0$为奇数,其它的$b_i(0)$都为偶数。于是整个式子的奇...
CodeForcesLuogu分析不会做.jpg以下所有图片均来自官方题解。首先初始就为白色的点不太好搞,考虑怎么样把它当成无色点。假设 $A$ 是一个白色点,我们在它上面挂 $3$ 个新点:可以发现这样子对游戏胜负没有影响。可以这么考虑:如果白方把 $A$ 涂白了,那么黑方只能把 $B$ 涂黑。所以这就相当于多用一轮回到了给定的状态。现在是一个没有颜色的树,考虑这上面的胜负情况。显然黑色不...
AtCoderLuogu分析好神啊...先考虑如果先手已经给出了序列,后手怎么做才能让字典序最大。容易发现,两个不互质的数的相对位置一定不会改变。对于每个数,向后面的与它不互质的数连边,然后在做一遍字典序最大的拓扑排序即可。考虑先手怎么做。我们把不互质的数间连双向边,那么先手的任务就相当于给每条边定向。手玩一下发现,先手从每个连通块中最小的点出发给所有边定向即可。正确性证明不会,感性理解一下...
LuoguBZOJ分析显然,合法的状态数不会太多。于是可以状压一下轮廓线 (其实就是记录一下每行填到了哪一列) ,然后写一发对抗搜索。然后如果用 $\mathrm{map}$ 记状态的话可能会T,于是用 $\mathrm{unordered\_map}$ 就行了。具体实现及细节见代码。代码//It is made by M_sea #include <unordered_map>...
LuoguBZOJ分析很神仙的一道博弈论题。首先发现必败态一定是所有的豆子都装在最后一个瓶子里。然后,每次的转移一定是拿出一颗豆子,放入两颗豆子。于是我们可以把每颗豆子看做一个单独的游戏了。继续观察发现,如果有两个在同一个瓶子里的豆子,那么可以直接忽略掉这两个,因为后手可以模仿先手。于是所有位置的豆子等价于$\text{这个位置上的豆子数}\%2$。现在问题成功简化为,有一颗在$i$位置的豆...