2021.09.17模拟赛

早岁那知世事艰，中原北望气如山

2021.09.17模拟赛

没做T4大失误

A. Sequence

Sequence

简单题，预处理出每个点的前后最长的差为 $1$ 的序列，二分长度判定即可

code

B. Tree

Tree

发现一个点从 $a \rightarrow b$ 之后连通块的变化是先减去与他相邻的点颜色为 $a$ 的数量，然后加上颜色为 $b$ 的数量

开个 map 维护儿子颜色数量即可

code

C. Backpack

Backpack

背包没法删除，所以考虑合并

类似一道不能删的区间乘积，分成 $k$ 段，每段处理前后缀的背包，每个 $k$ 区间 $O(W)$ 合并背包即可

复杂度 $O(TnW)$ 巨大卡常题

code

D. Chain

Chain

考虑每个点选取 $0/1$ 都是从上一个点的 $0/1$ 转移来的，直接保存每个点的前 $k$ 小的路径，每次 $O(k)$ 归并

总复杂度 $O(nk)$

code