• 欢迎光临~

CSP-S模拟18

开发技术 开发技术 2022-10-13 次浏览

A 最长反链

签到题,注意细节

B. 2A+x

比较妙,考场上看出来了区间的性质,但是没有想到处理区间问题的套路:minl - maxr
然后每次找到minr往上跑

C.No Rest for the Wicked

非常有趣,我们设 (f(u, c))(u) 在疫情程度为 (c) 时的答案,考虑从一条边上进行转移,我们发现如果
(max(c_i, c_j) leq c leq min(t_i, t_j)),我们可以互相转移
如果 (c_i leq c leq min(t_i, c_j - 1)),我们如果从(i)走到 (j),就再也走不回来了
线段树分治即可

D.

将底函数与带余除法联系起来
(lfloorfrac{a}{b}rfloor = frac{a - a mod b}{b})
线段树上分别维护。
每次push_up动态维护排名,利用二项式定理转移

程序员灯塔
转载请注明原文链接:CSP-S模拟18
喜欢 (0)