UOJ Logo henrytb的博客

博客

北京寒假noip day 1考挂记

2019-01-27 13:26:28 By henrytb

T1 弹簧振子

20pts:

枚举大法好!(逃

80pts:

DP!毒瘤

100pts:

1~n贪心,有问题就改掉

考场上我zz般地打了分治,结果爆零


T2 轻绳

  • 先对输入的点火位置拆出节点

  • 建立S向它们建立长度为点火时间的边

  • 节点被烧掉的时间就是最短路了...

超级源点...

毒瘤

PS:居然不卡SPFA...


T3 小滑块

珂以发现,对于三个相邻的障碍$a,b,c$满足$a\leq b\leq c$或$c\leq b\leq a$时,b是没有用的

把所有这样的b删掉

让l从小到大处理询问

  • 令$dlt[i]=|v[i]-v[i+1]|$

  • 令$w[i]$为处理到第i个障碍所需时间

  • 当l增长到超过某个dlt[i]了,意味着相当于v[i+1]和l一起增长,导致w[i]不在减小

  • 并查集维护

  • 当l增长到超过某个dlt[i]时,将i和i+1用并查集维护起来

  • 最后一段分类讨论特殊处理

啊啊啊要写long long啊啊啊

评论

暂无评论