思维

· · 个人记录

思维

T1

最短路状物，最多只会走 1000 天，f_{u,t} 表示在第 t 天走到 u 的最大价值，有向无环图，跑什么都行。

时间复杂度 \Theta(nT)。

code

T2

Sol1

直接上二分图，显然 i \to i 是一组最大匹配，然后取消 i 的配对，在建的图上跑就得到了 i 的答案，时间复杂度玄学。

Sol2

连边后发现 i 想要得到 j，必须形成一个环执行轮换，直接 floyd 传递闭包即可。时间复杂度 \Theta(\frac{n^3}{\omega})。

Sol3

口胡。

两个点能换说明在同一个强连通分量中，直接 \Theta(n+m) 跑 tarjan。等待验证。

T3

对每个店 i 计算以它为直角顶点的答案，贡献是

\sum_{i=1}^{n} |x-x_i| \times \sum_{i=1}^{m} |y-y_i|

对于 x 坐标相同和 y 坐标相同的放入一个集合，预处理前缀后缀和。

时间复杂度 \Theta(n\log n)。

code

T4