20240711

T1

NFLSOJ P14050 送外卖

考虑每个双向边连通块构成一张 DAG，可以想到按照拓扑序扩展每个双向边连通块，在连通块内 dijkstra，然后更新所有该连通块的后继连通块。拓扑套 dijkstra。

T2

NFLSOJ P14051 旅行

枚举在哪个点结束，考虑此时答案的变化。

T3

NFLSOJ P14052 门把手集合

异或按位独立，考虑拆位，注意到贡献里出现了交叉项，于是枚举每两位，考虑这两位的交叉项对答案的贡献。注意到我们此时已经不再注意每个数在其他位是什么，这样每个数只有四种可能性。我们统计每个点集合中四种可能性分别有几种，其中能够贡献交叉项的是两对可能性。随便算一下就好了。

T4

NFLSOJ P14053 武装直升机

\(f_i = \min\limits_j \{ \max \{ f_j, w(j, i) \} \}\)，考虑拆开内层 \(\max\) 然后分讨。注意到 \(w(j, i)\) 在 \(j\) 单调变化时单调变化，因此 \(f\) 的转移点也必是单调变化。这样两个东西都是单调的，转移点就只可以在两条折线交点的两侧。又注意到一条折线单调上移，另一条单调上移，因此交点也单调移动，使用单调队列维护即可。