2017ACM萧山训练第5场(2016 Pacific Northwest – Division 1)

2017年8月11日1430

E.Enclosure

做出大小两个凸包,即所有点的凸包和前 k 个点的凸包

按动态凸包的思路,新加入的点会把小凸包上连续的一些点弹出,这些点是一个连续的区间

相当于切掉凸包的一个角,加入一个三角形

若在大凸包上顺时针枚举一个加入的点,这个区间左右端点也是顺时针转的,类似旋转卡壳

切掉部分的面积顺便维护

由于坐标范围较大,用 double 精度会炸

G.Maximum Islands

L 的上下左右直接贪心为 W

然后剩下的就是个经典的骑士共存问题,黑白染色最小割

H.Paint

离散化,f(i)表示考虑前 i 个段,最多能染多少

将区间按照右端点排序后树状数组优化 dp

J.Shopping

从左端点开始,设剩下的钱为 S,每次二分 + rmq找到之后第一个小等于 S 的物品

由于 S 每次减半,复杂度 \(O(30nlogn)\)