LuoguLOJ分析一次移动后会让左边的空位减少若干,右边的空位增加若干,从而可以转化为一个阶梯博弈。不妨把左右反过来,那么就是要算有多少种方案满足编号为偶数的空位的异或和不为 $0$。再转化问题,相当于求 $n-m$ 个物品放进 $m+1$ 个盒子中,使得编号为偶数的盒子中的物品数的异或和不为 $0$ 的方案数。这个不为 $0$ 不好处理,可以容斥一下,变成算为 $0$ 的。那么就是每一位...
全是定义和结论,没有证明
LuoguUOJ分析考虑对每棵子树计算其 SG 函数值,即为每种删除情况得到的若干棵子树的 SG 函数的异或和的 mex。于是我们要想办法求出每种选择情况得到的 SG 函数异或和的集合。如果选择根节点,得到的就是它的每棵子树,子局面的 SG 函数值即为每棵子树的 SG 函数值的异或和。如果选择了某棵子树中的节点,那么相当于这棵子树的 SG 函数异或和的集合异或上了其它子树 SG 函数值的异或...
比赛地址Splitting Pile枚举即可。代码Fennec VS. Snuke双方显然是先把对方到自己这边来的路堵上。于是我们只要找到分界点,看看哪边的点多即可。需要注意的是,如果两边的点一样多,那么是后手胜。代码Awkward Response首先可以把 $N$ 的位数确定出来:依次问 $1,10,100,\cdots$ 直到回答是 N,则前一个数和 $N$ 的位数相同。那么可以考虑二...
比赛地址Sequence枚举第一个是正的还是负的,那么后面的符号都确定了。那么如果有一个前缀和不满足的话直接改成 -1 或 1 即可。可以证明这是最优的。代码Alice&Brown如果 $(n,m)$ 是先手必胜的,则存在一个 $(n-2x,m+x)$ 或一个 $(n+x,m-2x)$ 是先手必败的。于是手动打一个表可以发现 $(n,m)$ 必败当且仅当 $\lvert n-m\rvert ...
比赛地址Boxes and Candies从左往右扫一遍,尽量先拿走靠右的即可。正确性显然。代码An Ordinary Game这个 D 怎么比 E 难啊设 $s$ 为原串,$n$ 为串长。给出结论:当 $s_1=s_n$ 时,如果 $n$ 为奇数则后手必胜,否则先手必胜;当 $s_1\neq s_n$ 时,如果 $n$ 为奇数则先手必胜,否则后手必胜。先证明 $s_1=s_n$ 时的情况。...
Festival考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少,则若 $X_i+1=X_j$,则 $dis_{i,j}=-1,dis_{j,i}=1$,连边 $(i,j,-1)$ 和 $(j,i,1)$。若 $X_i\leq X_j$,则 $dis_{i,j}=0$,连边 $(i,j,0)$。考虑无解的情况。一种情况是出现负环,另一种情况是出现一个全是...
AtCoderLuogu分析考虑一个菊花、一开始在中心的情况。显然先手只会往一个 $a_i$ 小的方向走才能胜利,因为双方会在这条边上反复横跳,然后后手先跳完。考虑加上一层。假设一开始在 $u$,$v$ 子树先手必胜,则先手一定不会往 $v$ 走;假设一开始在 $u$,$v$ 子树先手必败,则先手可以往 $v$ 走,且后手一定回到 $u$,故当 $a_u<a_v$ 时先手胜利。因此只需...
比赛地址STring和括号匹配是类似的,开一个栈记一下就好了。事实上只要记栈中的元素个数。代码Minimum Sum单调栈板子题。代码Tree Restoring首先找到 $d=\max\left\{a_i\right\}$,那么直径的长度为 $d$。设 $cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的数量,分类讨论一下:若 $d$ 为奇数,则应有 考虑计算 $f_i$。容易发现一...
比赛地址Range Product简单讨论一下即可。代码Box and Ball简单模拟一下即可。注意盒子里仅有一个球的情况。代码Knot Puzzle能全部解开当且仅当存在两条相邻的绳子满足长度之和 $\geq L$。正确性显然。代码Stamp Rally先考虑怎么算从 $x,y$ 出发最多能到达的点数。显然,如果 $x,y$ 连通,则为 $sz_x$,否则为 $sz_x+sz_y$。这里...