图论

· · 个人记录

板刷 CF 2400 - 3000 的图论.

CF888F *2500. 独立做出. 为什么 tag 里有 graphs？神秘. 区间 dp. 维护 f_{l,r} 表示 l 到 r 的子问题的答案. g_{l,r} 表示若连接 l 和 r 这条边（不管有无），l 到 r 的子问题的答案. 转移手玩容易.

CF51F *2800. 独立做出. 可以瞪眼出边双缩树. 然后就比较显然的 guess 最后缩到直径. dirt 了一发，死因建树时忘记判同一个边双内，导致形成环.

CF1033E *2800. 独立做出. 挺有趣的交互. 比较显然的想到把操作放到类似线段树上进行. dirt 了三发，想漏了一个点.