下午和晚上打 USACO 了,咕了一会儿。
T1 husky排队吃糖
吃到糖的是一个前缀,二分第一次产生环的前缀。如果每个 husky 有一个循环的区间 \([1,n-a_i]\),如果存在一个位置 \(k\) 满足循环在 \([1,k]\) 以内的狗的数量 \(\ge k\),就一定能产生环。
T2 粒子
Luogu P7453 [THUSCH2017] 大魔法师
操作只有常系数的乘法和加法,用矩阵维护,然后写个线段树。
T3 小清新签到题
和他们相比,我搬的题就是小清新啊。
CF1202F. You Are Given Some Letters…
T4 大绿虫子很美味
在每个连通块最高处统计。设 \(f(u,i)\) 表示 \(u\) 子树包含 \(u\) 的连通块,颜色集合为 \(\{a_u\}\) 或者 \(\{a_u,i\}\) 的所有连通块答案(\(0\) 次和和 \(1\)次和)。
观察转移,可以整体 DP,写个线段树合并。对于 \(u\) 的儿子 \(v\),如果 \(a_u=a_v\),合并两者的线段树;否则只需要在 \(f(v,\cdot)\) 里单点查询。