JOI 2022 Final

Posted on 2022-02-16 Edited on 2022-02-24

#3662. 「JOI 2022 Final」星际蛋糕推销

~~implement useful algorithm~~

useful algorithm\(\times2\).

直接枚举最终一共有\(m\)人在演讲.考虑当确定哪些city需要招人, 另外哪些要拿到选票时, 一定是先把人招全, 再拿到剩下的选票更优. 并且招人的顺序一定是按\(b_i\)不减.

于是按照\(b_i\)排序, 发现去掉只拿选票的城市以后, 招到人的城市一定在剩余城市中构成一个前缀.

定义\(f[n][k]\)表示前\(n\)个城市, \(k\)个只拿选票的最短时间. \(O(n^2k)\) DP.

另外据说可以三分\(m\), 正确性不明. link

经典的倍增+维护可达区间. 这次转移需要用RMQ. \(O(n\log^2 n + q \log n)\), 空间2log 或 \(O((n+q)\log^2 n)\), 空间1log.

idea: 1. 对于合法状态的判定, 尝试把它写成一个对每一个元素相对独立的函数(即每个元素的贡献具有局部性), 方便后续各种操作. 2. 扫描线

考虑到对于每个数, 我们显然会走它在相邻格子中的前驱和后继, 考虑连一条有向边, 这样一个矩形合法, 也就是成链, 当且仅当\(0\)入度点只有\(1\)个.

而每个点的入度只在border在它附近的时候会变化.

大力前缀和即可.

做到\(O(H^2W)\)需要枚举一维, 用一个桶计数另一维.