黑皇帝 feat. Eili —— 儀 -lirile-

48 [CTSC2011] 幸福路径

走的足够远的时候精度就丢没了,因此直接让其倍增地走。视作每个点都可以有自环,这样直接跑一定轮数的 Floyd 即可。

49 [CF1696F] Tree Recovery

如果树上有一条边,我们只需要根据已经存在的一条边去找哪些点对之间的距离都是 11 就可以确定所有的边,最后检查合法性即可。这样是 O(n4)O(n^4),代码。

50 [CF1519F] Chests and Keys

相当于对于所有宝箱的集合 SS,有:

∑i∈Sai≤∑i∈lock(S)bi\sum_{i\in S} a_i\le \sum_{i\in \text{lock}(S)}b_i

这是什么?完美匹配!相当于我们要将箱子和锁进行匹配,连一条边的代价是给某个箱子上锁的代价。

发现数据范围小的离谱,因此直接按照每一条边作为阶段进行 DP,存下当前 bb 的情况和当前 aa 的值。代码。


做 ICPC 2020 Shanghai Regional。

D. Walker

对于 p1 左边一定由第一个人完成 p2 右边一定由第二个人完成,这时候直接二分答案能减少大量的分讨。代码。


Nothing built can last forever.
本站由 iznomia 使用 Stellar 1.30.4 主题创建。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。