20231011 NOIP#18总结
时间安排
7:50~8:30
看题，\(A,C\) 一眼切，\(B\) 不会一点，\(D\) 应该能爆搜不知道拿多少分。
8:30~8:40
写 \(A\) 的正解。
8:40~9:40
写 \(C\) 的正解。
9:40~10:20
写 \(D\) 的爆搜再加点剪枝，打点数据特判希望骗分。
10:20~11:50
写了 \(B\) 的爆搜，然后打特殊性质，快结束发现假了改不了了。
总结反思
题解
A.线段树
线段树板子。
B.二分+贪心
二分答案，对于距离型骑手，将其能配送的重量从大到小排序，对于 \(i\) 骑手，将 \([a_{i-1},a_i-1]\) 的订单加入堆。那么当前在堆中的所有订单都是 \(i\) 骑手可以配送的，则贪心的从堆中取出最大的 \(mid\) 个交给 \(i\)，以此类推对于重量型骑手同理，判断所有订单是否能在 \(mid\) 小时内送完。（此题卡常）
C.前缀和优化换根DP
设 \(f[x]\) 表示 \(x\) 子树内的所有林场，都有消防队的最短时间。
设 \(x\) 有儿子 \(v_1,\cdots,v_k\) 满足 \(f[v_1]\geq \cdots \geq f[v_k]\)，则有 \(f[x]=\max_{i=1}^k\{f[v_i]+i\}\)
考虑换根，当根从 \(u\) 转移到 \(v_i\) 时，\(f[u]=\max\{f[x]+i\},x\in \{v}+\{fa\}-\{v_i\}\)，计算答案同上。
这个式子可以通过排序后预处理前后缀 \(\max\) 优化。
D.搜索
一通爆搜+玄学剪枝（正解是状压+折半，还是放弃吧/kk）