JOISC 2023 记录

JOISC 的题咋都这么有水平。

Day1

Two Currencies (Easy)

建主席树，然后二分出最大的 $L$，只用银币能解决花费在 $[0, L]$ 的所有收费站。

然后看剩下的银币能解决多少收费为 $L + 1$ 的收费站。

主席树上二分不难做到 $O((n + q)\log V)$。

喜报：我不会写主席树。

Festivals in JOI Kingdom 2 (Hard+*)

真贪心显然是按右端点排序。

考虑容斥，统计真贪心和假贪心答案相同的方案数，再用总方案数 $(2n - 1)!!$ 减掉相同的即为答案。

我们设真贪心选择的区间为红区间，假贪心选择的区间为蓝区间，真假贪心同时选择的区间为紫区间，同时不选择的区间为黑区间。

观察合法方案的形态，可以发现：

• 把所有区间按右端点排序后，红蓝区间交替出现。
• 相邻的两个红区间，它们的右端点之间不存在完整区间；第一个红区间的右端点之前不存在完整区间。
• 相邻的两个蓝区间，前者的右端点与后者的左端点之间不存在某个区间的左端点；第一个蓝区间的左端点之前不存在某个区间的左端点。

容易想到线头 dp，设 $f_{i, j, p, q}$ 表示考虑 $[1\dots i]$，剩下 $j$ 个左端点未匹配，红蓝区间右端点分别为 $p, q$ 的方案数。这个转移是简单的。

红蓝区间是交替出现的，所以可以转成插入 dp。设 $f_{i, j, 0/1}$ 表示已有 $i$ 个完整区间，剩下 $j$ 个左端点未匹配的方案数。另外还要记一维 $0/1$ 表示最后一组区间是不是紫区间。

每次转移需要枚举有多少黑区间的右端点在上个红区间右端点与当前红区间右端点之间。然后统计给这些黑区间分配左端点的贡献。另外，一个位置是合法的左端点当且仅当它被某个蓝区间包含。可以做到 $O(n^3)$。还需要压缩状态数。

发现这里 dp 状态需要记两维的原因是，蓝区间对左端点的限制很强，而对右端点的限制很弱。一个巧妙的做法是，从右往左 dp，每次插入左端点在相邻两个红区间右端点之间的黑区间。这样就把左端点的限制放到了枚举里而不是状态里。而右端点可以在后面的任意两个位置之间插入，不需要往状态里加更多信息。

具体地，设 $f_{i, 0/1}$ 表示从右到左考虑，已有 $i$ 个完整区间，（从右到左）最后一组区间是否是紫区间的方案数。

但是这样还不够，我们还要额外记录最后一组红蓝区间左端点的信息，因为这部分信息会影响分配黑区间的方案数。

不妨延后分配最后一组红蓝区间的左端点，而红区间右端点一定在蓝区间右端点左侧，无需记录。然后原 dp 状态就可以转移了。

以 $0\to 0$ 的转移为例。首先我们要分配 $j$ 个黑区间的左端点，上一组红蓝区间的左端点，以及当前这一组蓝区间的右端点。相邻蓝区间的右端点和左端点之间不能有其它左端点，于是可以把它俩缩起来当一个点处理，方案数是 $(j + 2)(j + 1)$。后面有 $(2i - 2)$ 个间隔可以插入右端点，方案数是 $(2i - 2)^{\overline{j}}$。

剩下三种状态同理。写一下转移方程：

$\begin{aligned} f_{i + j + 2, 0} &\gets f_{i, 0} (j + 2)(j + 1) (2i - 2)^{\overline{j}} \\ f_{i + j + 2, 0} &\gets f_{i, 1} (j + 1) (2i - 1)^{\overline{j}} \\ f_{i + j + 1, 1} &\gets f_{i, 0} (j + 1) (2i - 2)^{\overline{j}} \\ f_{i + j + 1, 1} &\gets f_{0, 1} (2i - 1)^{\overline{j}} \end{aligned}$

统计答案的时候还要考虑在最后一组红蓝区间前面的黑区间的贡献。这里的细节可以看代码。

现在是 $O(n^2)$。进一步优化需要半在线差卷积，分治 MTT。但是不如卡常直接能过。可能需要 Barrett Reduction。

提交记录。

Passport (Medium-Hard)

考虑 $X = 1$ 怎么做：设 $p_0 = n$，每次找最左的能到达 $p_{i - 1}$ 的点 $p_i$，直到 $p_i = 1$。

这启发我们从 $n$ 开始向左扩展，计算从每个点出发到 $n$ 的距离。从 $1$ 开始向右扩展同理。

具体地，对于 $x \in [L_i, R_i]$，可以用 $dis_x + 1$ 来更新 $dis_i$，同时建出 bfs 树。

现在我们有两棵 bfs 树，它们之间可能会有影响。

假设我们要先从 $X$ 到达 $n$，经过从 $X$ 到 $n$ 的反祖链上的点。简单推一下可以发现，在中途选一个不在反祖链上的点，一定不会优于先走到 $n$ 再选不在反祖链上的点。另一侧也同理。

于是只需要分别考虑先走到 $n$ 和先走到 $1$ 的两种情况。先走到其中一个端点，然后查询前缀 / 后缀向另一侧走的 $dis$ 最小值。

若 bfs 树有多种形态，要选择能向另一侧扩展的最远的。把 $dis$ 记成 pair 即可解决这个问题。

实现上，不需要树套树 / 序列分块，直接线段树优化建反图，然后 01bfs 就行了。

注意若 pair 的第一维相同，更新第二维时只能 push_back。因为后面可能有一个更优的值把 push_front 的复杂度卡爆。

Day 2

Council (Easy-Medium)

最后可以转化成给你 $n$ 个集合 $S_{1, 2, \dots n}$，每次询问一个 $T_i$，求 $\min\limits_{j \neq i} |S_j \cap T_i|$。

那么对于 $S_j$， 设 $X = S_j \backslash T$，答案就是 $|S_j| - |X|$。

考虑枚举 $X$，要求 $X \cap T_i = \varnothing$，再枚举任意一个 $X \sube S_j$，用 $|S_j| - |X|$ 更新答案。

这样并不能保证 $X = S_j \backslash T$。但由于答案要求最小，$|X|$ 要取到最大，这时一定能让 $X = S_j \backslash T$。

于是我们直接对每个 $X \sube S_j$ 更新权值 $g_X$ 为 $|S_j| - |X|$， 每次查询 $T_i \cap X = \varnothing$ 的 $\min g_X$。

实现上可以高维后缀 min 求 $g_X$，再高维前缀 min 预处理答案。由于查询时要保证 $j \neq i$，$g$ 上要记两个不同的 argmin 而不是最小值和次小值。

时间复杂度 $O(2^mm + nm)$。

Day 3

Tourism (Easy)

连通块大小就是直接按 dfn 排序计算两两距离再除以二。

用链表维护 dfn 序列，不插入莫队即可 $O(n\sqrt n)$。不想写了。

Day 4

Bitaro’s Travel (Easy-Medium)

一个经典结论是，转向次数是 $O(\log V)$ 的。证明很显然。

然后随便维护一下。

---

咕咕咕了。