251109 以前 x 天

P9755 [CSP-S 2023] 种树

首先二分答案，算出每个位置至少需要在 \(t_i\) 时刻及以前到达并种树，按 \(t_i\) 排序后从小往大取即可。难点在于计算 \(t_i\)。

P5688 [CSP-S 2019 江西] 散步

对每个出口维护左右两个相邻区间内的人即可，用堆维护。出口满了之后就用启发式合并合并两个堆（可并堆也行）。有一点细节。

P9678 [ICPC 2022 Jinan R] Tree Distance

请移步支配对。

P5305 [GXOI/GZOI2019] 旧词

把 \(\operatorname{LCA}\) 的贡献拆到根链上每一个点上，具体来说设点权 \(a_i=dep^k[i]-dep^k[fa(i)]\)，然后扫描线问题转化为链加链带权和，线段树做完了。

P10833 [COTS 2023] 下 Niz

先对每个数求出左边第一个 \(\ge\) 它的数 gel[i] 和右边第一个 \(\ge\) 它的数 ger[i]，然后再对每个左端点 \(i\) 求出最大的右端点 \(mx[i]\) 满足 \([i,mx[i]]\) 中所有数只出现了一次。钦定每个数作为区间中的最大值，可以知道区间长度，然后对 \((mx[i]-i+1,i)\) 进行二维数点即可。不知道为何题解里的做法都那么神秘。

P5664 [CSP-S 2019] Emiya 家今天的饭

枚举每一列并钦定该列选择了超过总数一半的菜。在状态中记录选择了该列多少个数和其他列多少个数，容易做到 \(O(n^3m)\)。发现 dp 时我们只关心两个维度的差，因此可以做到 \(O(n^2m)\)。

先 bfs 求出全源最短路。考虑如何令 \(A,B,C,D\) 两两不同。加入 \(C\) 的时候我们可以枚举 \(B\)，并同时记录最大值和次大值以此保证 \(A\ne C\)。加入 \(D\) 的时候先枚举 \(C\)，然后考虑 \(C\) 时前两个数的最优解 \((A,B)\)。若 \(A,B\ne D\)，那么万事大吉；若 \(A=D\)，我们在 \(C\) 处额外记录一组解 \((A',B')\) 满足 \(A'\ne A,B'\ne A\)；\(B=D\) 同理。