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点等着被抓。
最后使用点分治优化。