20231015NOIP训练赛

时间安排

7:50-8:10 写T1

8:10-11:50写T2

总结

T2写了分段但是因为太过自信然后全删了

题解

T1

板子题，建一个超级源点即可

T2

数学题，用组合数计算，然后再用前缀和优化

T3

先建出S到T的最短路图，然后在在这个DAG上进行DP，注意还要再建出T到S的最短路图再跑一遍。

T4

我们发现最优策略一定是跑到一个能到达的最优的点，然后在那个点等待被抓。

设\(f_i\)表示i这个点被抓需要的时间，显然如果u和v之间的距离小于\(f_v\)，u就能跑到v点等着被抓。

最后使用点分治优化。