标签: 基环树

  • MOCK NOIP 20221006 日志

    策略和思维活跃度都极其糟糕的一个上午。

    那么“在能力不足以保证完成更多正解”的情况下获取尽可能多的暴力分从而提高总分下限,又被重新提上议程。切记切记。

    思维广度待进一步提升。

    一句话题解

    A – 道路

    发现了是平面图,想到了数据结构与区间可达性,就是没把俩概念结合起来。

    由题目保证的“两边不交”性质,可以发现,若不考虑无法从任何一个左侧点到达的右侧点,如有 $(A,y_1),(A,y_2),y_1<y_2$ 均可从 $(0,y_0)$ 达,则若有 $(A,y_3),y_3\in [y_1,y_2]$,则其必然亦可达。

    缩点后拓扑排序求出每个连通块能到达的右侧点 $y$ 坐标区间即可。复杂度 $\operatorname(O)(n\log n+m)$。

    B – 地震后的H市

    联想到了 HDU “杭电杯”超级联赛(3) Spanning Tree Game 钦定最小生成树,按边权从小到大依次加边的动规方法。

    可惜这是最小瓶颈生成树。

    解一(刘晟林)

    (更多…)