20231015NOIP训练赛#21总结

Timeline

07:50-08:30

先把 A 暴力打了

08:30-09:00

把 B 最低档暴力打了

09:00-09:20

把 C 暴力打了

09:20-09:50

把 D 暴力打了

09:50-10:15

把 A 正解打了

10:15-10:40

B 冲了一点部分分

剩下时间

摆烂。

Result

$100+35+10+0=145$

Solution

T1

超级源点板题。

T2

枚举操作点，在极长子串间计数。

T3

若有 $A\rightarrow B$ 的最短路经过了 $U\rightarrow V$ 的最短路，那么一定是 $A\rightarrow X\rightarrow Y\rightarrow B$，其中 $X,Y$ 在 $U\rightarrow V$ 的最短路上。

那么分别对四个点跑一遍 Dijkstra，找出最短路上的边建个图，建出 DAG 后跑个 拓扑排序 + DP 即可。

T4

跑到一个能跑到的最久被抓住的点，然后原地等似，这点用点分治实现。