2021.12.19 互测

下午和晚上打 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)\) 里单点查询。

上一篇:2021-12-19每日一题


下一篇:JAVA学习第19天,数据库;