Gym 101669 题解

A

f_{i,j} 表示前 i 天看了 j 场的方案数。

B

如果一段格子长度等于方块数,那么一定有方法刚好铺满。枚举空格转移 dp。

D

每两个 1 对应的行之间连边,每个连通块对答案贡献 size-1

E

预处理合法状态,枚举开始时的音节往后贪心。

F

枚举多少个 1 先变成 0 再变成 1,然后一定是从大到小把 1 变成 0,再从小到大把 0 变成 1

G

排序模拟。

J

S_1,S_2,S_3 表示 =1,=2,\ge 3 的石堆数量,分类讨论一下:

只有 S_1 的时候显然答案与 S_1\bmod 3 相关。

对于 (S_3,S_2)=(1,2)S_2>2S_3>1,总可以在某个时刻,B 和 C 把 S_1 \bmod 3 变成 0

对于 (S_3,S_2)=(1,0),(0,1),A 直接取成 S_1 \bmod 3 \ne 0 即可。

对于 (S_3,S_2) = (1,1),(0,2),当 S_1\bmod 3 = 0 时 B 和 C 总可以把它变成 0,否则不行。

K

按值小为第一关键字,位置靠前为第二关键字,依次放 n\sim1


C

对某个颜色对应的一条极长链,要求这个颜色比链上的其它颜色先选,所以相当于是这个颜色向这上面其他颜色连边,跑一个拓扑序。用倍增优化这个连边。

H

考虑这样一个二元组 (u,v),表示猫在 u,老鼠在 v,假设 w 是从 v 出发除开 u 的最大值。

如果老鼠走了猫跟上去,就是一步转移到 (v,w)

如果 vw 出发的最大值,那么老鼠走到 w,猫不动,老鼠走回来,猫怼上去,老鼠走到 w,猫跟着,老鼠走回来,猫不动,那么就是四步转移到 (w,v)

对着这两种情况建边跑最短路。

枚举一下猫和老鼠第一次在哪里遇见,更新答案。

I

状压一下直接往后记忆化搜索,状态数很少。如果搜的时候出现了环答案就是 -1

L

m<4n 所以答案一定是 2 或者 3。一定有一棵树只删除了一条边,对这棵树某个子树染色,在另一棵树上看有多少条边两端不同色。染色可以在第一棵树上用 dsu on tree。

发表评论

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