UOJ Logo henrytb的博客

博客

北京寒假 noip D2

2019-01-28 13:21:07 By henrytb

比赛传送门

老师很惊讶...因为我们太弱了,最高分才70...

老师预估最高210来着...

PS:这个比赛每道题都很政治正确蛤


T1 洪水被赶跑

  • priority_queue维护泄洪点

  • 枚举每个特殊时刻:

  • 加入泄洪区的时刻

  • 泄洪区报废的时刻

  • $O(n)$模拟即可...

精度问题不大...


T2 风景这边更好

这种东西根本没法数据结构优化...

  • 如何优化暴力?

  • 有两种暴力:

  • 每次询问枚举所有之前的点算bitcount
  • 维护一个数组ans,ans[x]表示新加一个x的答案,询问后暴力更新ans
  • 拼起来?

  • 对高低位分块!

  • 前八位用第一种暴力,后八位用第二种暴力...

玄学


T3 改革春风吹满地

  • 对于两个点,其距离就是曼哈顿距离除以2下取整,看作一个边

  • 最小生成树...

够毒瘤的...


说句闲话:50分就并列第二(不看时间)也够毒瘤的...

北京寒假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啊啊啊

henrytb Avatar