首页 > 其他分享 >20231011

20231011

时间:2023-10-11 20:35:45浏览次数:37  
标签:剪枝 20231011 正解 max 40 骑手

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)

标签:剪枝,20231011,正解,max,40,骑手
From: https://www.cnblogs.com/programmingysx/p/17757618.html

相关文章