策略和思维活跃度都极其糟糕的一个上午。
那么“在能力不足以保证完成更多正解”的情况下获取尽可能多的暴力分从而提高总分下限,又被重新提上议程。切记切记。
思维广度待进一步提升。
一句话题解
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 钦定最小生成树,按边权从小到大依次加边的动规方法。
可惜这是最小瓶颈生成树。