怎么这么难！
写 BCDE。
loj3663.「JOI 2022 Final」自学
tag：二分，贪心。
先不妨假设 \(A_i\geq B_i\)。二分，然后考虑怎么选。
发现方案一定是：如果能上课就先上课把需求填满，然后空出来的时间用来自学上课上不满的课程。
如何证明。只需要证明：
- 不存在上课能满足需求的，需要用别的课的时间来自学。
- 不存在上课满足不了需求的，会翘掉课去学别的科目。
对于第一个，假设自学了 \(x\) 次，相较于上满课多了 \(y\) 次自学机会。由于 \(A_i\geq B_i\)，所以 \(y<x\)，得不偿失。
第二个等价于一换一，调整回来不劣。
复杂度 \(\mathcal{O}(n\log V)\)。
*loj3664. 「JOI 2022 Final」选举
tag：最优性质优化 DP 状态。
假设钦定 \(S\) 集合使得在 \(S\) 里面搞到了协作者，\(T\) 里面只搞到了选票，满足 \(S\cap T=\varnothing\)。
刻画权值，显然我们会先搞协作者，时间是 \(S\) 按 \(b\) 排序后 \(\sum \dfrac{b_{S_i}}{i}\)，后面之前全部堆一个地方，时间 \(\sum \dfrac{a_{T_i}}{|S|+1}\)。
按照 \(b_i\) 排序，考虑枚举 \(|S|\)，那么设 \(f_{i,j,k}\) 表示前 \(i\) 个选了 \(j\) 个 \(S\) 和 \(k\) 个 \(T\)，直接 DP 总复杂度为 \(\mathcal{O}(n^4)\)。
发现不存在 \(j\) 还没到 \(|S|\) 的时候两个都不选这种决策，所以可以设 \(f_{i,j}\) 表示选了 \(j(j<|S|)\) 个 \(S\)，\(g_{i,j}\) 表示选了 \(j\) 个 \(T\) 且 \(S\) 已经选完。复杂度为 \(\mathcal{O}(n^3)\)。
*loj3665. 「JOI 2022 Final」铁路旅行 2
tag：倍增。
以为是什么高妙数据结构，然后做了好久。
题意等价于点向区间连有向边，求两点最短路。考虑倍增，倍增的同时维护 \(s\) 对应的区间。可以发现走 \(2^{j+1}\) 的区间为走 \(2^j\) 步的每一个位置走 \(2^j\) 步的区间的并，线段树维护就可以了。复杂度 \(\mathcal{O}(n\log^2 n)\)。
*loj3666. 「JOI 2022 Final」沙堡 2
tag：图形态判断条件，前缀和。
考虑一种判断方法：把一个位置 \(x\) 向它四周的比它小的最大的位置连边，然后判断图是否为一条链。
这个判断条件直接套用数据结构优化是不能的。考虑进一步转化。然后就可以发现条件等价于入度为 \(0\) 的点至多一个，而一个点的入度只和周围 \(5\times 5\) 的选择情况有关，所以对于一个矩形可以用前缀和分类快速计算入度为 \(0\) 的点的个数。
回到原题。\(\log\) 做法还是不行，但是发现可以 \(\mathcal{O}(H^2W)\)，然后就可以发现直接大力做是根号的了……
所以如果需要判断图的形态，条件一般是简洁的。