模拟赛
T1
- 15 分 ：状压， 50 分： $ O(n ^ 2) $
- $ O(n ^ 2) $ 的 check ：赛时代码
- 正解：贪心
- 根据鸽巢原理：$ a_1, a_2, a_3 $ 至少会有两项是同一个等差数列的前两项
- $ O(n) $
T2
第二种路径：$ u_i \ge v_i $
期望路径数：路径的长度
起点为 1 号（随机起点 -> 新题）
-
期望的可加性：整个过程的期望 = 各条边期望的和
- 推式子 ？？？
-
扩展：随机起点
T3
-
树形DP
-
二分发药的点与患病奶牛之间的最大距离 k
- 选 m 个点， 与目标的距离不超过 k
-
类似最小点覆盖 （？）
-
很多树形DP都要特判根
T4
-
线段树
-
只有 opt1, opt2
- $trans_i $ 表示区间所有颜色为 i 的点操作后会变成 $ trans_i $ （懒标记）
- 操作 \(x, y\)
- Push_down：$ i \to trans_{x, i} \to trans_{y, trans_{x, i}}$
- rec 随之改变
-
opt3
CF1584D
- 二分找到 i
- 逆序对数
- [1, i] -> 0
- [i, n] - [i + 1, n] -> [i, j] 的长度
- j, k 同理
CF1605D
- $ u $ $xor $ $ v \le min(u, v) $ -> u, v 二进制最高位相同
- 树是二分图
- 按最高位分组
- 然后？？
CF1548C
- 生成函数
CF15801D
- 笛卡尔树
CF1552E
CF1552F
- 和今天 T2 的关系？