国庆集训 Day 1
2024 年 10 月 1日
Status: CLOSED
\(\def\EZ{\textcolor{#51af44}{\text{EZ}}}\EZ\) 表示简单，10分钟内就能想到。
\(\def\HD{\textcolor{#3173b3}{\text{HD}}}\HD\) 表示中等，能独立想出
\(\def\IN{\textcolor{#be2d23}{\text{IN}}}\IN\) 表示困难，独立思考能想到 \(50\%\) 以上
\(\def\AT{\textcolor{#383838}{\text{AT}}}\AT\) 表示非常困难，独立思考只能想出 \(50\%\) 以下
Overall
\(\EZ\)
| game | car | candy | produce | total | |
|---|---|---|---|---|---|
| Score | 90 | 100 | 100 | 0 | 290 |
| Expected | 100 | 100 | 100 | 100 | 400 |
| Ideal | 100 | 100 | 100 | 100 | 400 |
T1 填数游戏 game
\(\EZ\) \(\text{pts: }\textcolor{#51af44}{90}/100\)
挂分：变量名写错 \(100\to 90\)
显然的贪心。
T2 摆渡车 car
\(\EZ\) \(\text{pts: }\textcolor{green}{100}/100\)
显然的贪心，考虑一定选择最小的那些数，则可以权值线段树上二分。
但是权值线段树上二分 (1log) 跑的没有二分+树状数组 (2log) 快就比较抽象了。
T3 分糖果 candy
\(\EZ^{+}\) \(\text{pts: }\textcolor{green}{100}/100\)
考虑进行二分判定，判定时作一个 dp，设 \(f_i\) 表示前 \(i\) 个数里面每一段的和都不超过 \(mid\) 最大能分多少段，这个的话，可以用线段树或者平衡树优化，我用了 FHQ-Treap 进行优化。
T4 宝石加工 produce
\(\HD\) \(\text{pts: }\textcolor{red}{0}/100\)
挂分：初始化写错 \(100\to 0\)
dp 是显然的，但是只能一个询问一个询问地做，但是转移方式全都是一样的。
这里有一个 Trick，在两维上加减 1 的这种 dp 可以称为是网格型 dp，把他看作是网格图上多次询问最长路，经典的技巧来自于 P3350 [ZJOI2016] 旅行者。
但是我们应该进一步查看这个 Trick，这要求一个询问它的贡献是可以拼起来的，中间计算拼起来这个过程的复杂度是可以接受的（但是直接每个询问计算不可以接受），所以我们就考虑最大化利用算出来的信息来尽量拼接出询问的答案，那么这个时候怎么决定计算哪些呢？可以进行分治，则可以得到询问的必经点，计算即可。
很好，但是本题有一个计算量正确的暴力。
考虑离线所有询问，并对每个左上角做一次，可以自行考虑为什么对。
来自 nie_zy 的分块算法，其实核心思想与正解类似：
考虑对 \(n,m\) 中较大者进行分块，在每一块的分界线上对下一个分界线计算最长路，每次询问时边角进行暴力，中间则再次进行 dp 获得最长路。
关键就是意识到这种 dp 相当于最长路，答案可以拼接。
标签：text,询问,集训,国庆,EZ,100,textcolor,Day,dp From： https://www.cnblogs.com/haozexu/p/18442970