JOI Final 2022

怎么这么难！

写 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)\)，然后就可以发现直接大力做是根号的了……

所以如果需要判断图的形态，条件一般是简洁的。