比赛日志

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

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

思维广度待进一步提升。

一句话题解

A – 道路

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

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

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

B – 地震后的H市

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

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

解一(刘晟林)

(更多…)

More
  • 2022年10月6日