Gym 101981 题解

A

k > 1 先手分成对称的两部分即可。

B

首先凸优化掉 k 这一维,然后直接一段一段地 dp,dp 式子可以斜率优化。

C

暴力做法是枚举 A 第一次选的点 x,那么 B 一定是选在某个子树 y 的重心 g 上,然后 A 再选这个子树里以 g 为根的最大的子树。

考虑 A 把 x 向远离 y 的方向移动,B 还是选 g 不动,那么 A 能够挡住的点数是不会更优的。所以不用再枚举 y 以外的点作为 x 的情况。用点分治来枚举 x

D

三分套三分套三分。

E

连续 k1 可以变成连续 k0,然后连续 k0 可以通过一波操作把这 k0 平移到最末尾去(每次把下一个往前移 k 个)。所以把两个串都表示成前面没有连续 k 个东西,后面全 0 的串再比较。

F

先高消出每个点回到自己的期望时间,然后解一个矩阵方程。但是矩阵的秩是 n-1,所以解出一组特解之后还要用主对角线调整。

G

答案是 \binom{n+3}{4}

H

如果最多的多于一半则可以把别的消完,否则如果是偶数一定可以全消完,如果是奇数一定只剩这一个。枚举剩哪一个的话,那么分拆出来的两边必须都是偶数且能消完。一边的贡献可以直接处理,另一边用树状数组,枚举颜色是 a,中间可能超出限制的颜色 b,记个关于这个区间中颜色 b 个数的式子。

I

网络流。

J

对每个质数算。

K

暴力每次合并两个。

L

先解决掉答案是 0-1。然后分两种,一种是把某种颜色 x/y 全部移走,可以直接算。另一种是没有移动的至少一个 x 一个 y,写一个 dp:f(i,j,S,L) 表示考虑了前 i 个,拿走的非 x/y 减去留下的 x\leftrightarrow y 个数是 j(即还有多少空余的分隔能用),有没有留下 x/y 的状态是 S,最后一个留下的是 L。转移 O(1)

M

反转 s,考虑枚举 s[l:r] 中自己回文的部分和匹配 t 的部分的分界线,左边是回文,可以 manacher,右边是以这个开头匹配 t​ 的前缀,是 z-algorithm。

发表评论

电子邮件地址不会被公开。 必填项已用*标注