JOISC 2024 记录

感觉我太滞后了

Day1 T1 Fish 3

我们可以做的操作是单点加 \(D\) 和后缀加 \(1\)，考虑把这个操作放在差分数组上，则操作变成了：

1. 单点加 \(1\)。
2. \(i\) 处加 \(D\)，\(i+1\) 处 \(-D\)。

需要最小化第二种操作的使用次数，发现只有对于所有差分数组中的负数是不得不用第二种操作的，而对于其他的，都可以用第 \(1\) 中操作补齐。

\(B_i:=C_i-C_i-1\)，则对于 \(B_i<0\)，我们需要对其进行若干次二操作，使得先变成一个 \(\le B_i\) 的数，然后用一操作补齐。而从它这个地方向前移出去的 \(D\) 都需要有其他的 \(B_i\) 承接。

我们至少需要对其进行 \(\left\lceil\dfrac{-B_i}{D}\right\rceil\) 次而操作，

由此，我们可以将题意转化成：对于 \(B_i<0\) 的位置，我们有 \(\left\lceil\dfrac{-B_i}{D}\right\rceil\) 个右括号；对于 \(B_i\ge 0\) 的位置，我们有 \(\left\lfloor\dfrac{B_i}{D}\right\rfloor\) 个左括号，我们需要进行括号匹配，匹配第 \(i\) 个位置的左括号和第 \(j\) 个位置的右括号的代价是 \(j-i\)，问最小的代价。

通过调整法可知，如果出现匹配 \(i_1,j_1\) 和 \(i_2,j_2\) 有 \(i_1<i_2<j_1<j_2\)，我们将其调整成 \(i_1\) 和 \(j_2\) 匹配，\(i_2\) 和 \(j_1\) 匹配不劣。也就是，我们就是进行贪心的括号匹配。因此，我们在询问一个区间的时候，除了差分数组的第一位，其余的都是原差分数组的子区间，可以发现所有的匹配不会变化。因此，我们初始的时候使用栈模拟匹配，可以得到 \(O(n)\) 对这样的匹配三元组 \((i,j,cnt)\)。

而我们想要查询一个子区间的代价，就是需要知道有那些在这个区域内的左右括号自己匹配了，以及有多少个右括号匹配的左括号不在选择的区间内。

具体的，记 \(v1=\sum\limits_{(i,j,cnt)} [L< i\land j\le R]cnt(j-i),v2=\sum\limits_{(i,j,cnt)} [i\le L<j\le R]cnt,v3=\sum\limits_{(i,j,cnt)} [i\le L<j\le R]cntj\)。

如果 \(C_L\ge D\times v2\)，则有解，最优解为 \(v3-v2\times L+v1\)。
否则，无解。

发现 \(v1,v2,v3\) 都是二维数点，可以使用主席树做到 \(O(n\log n)\)。

Day1 T2 Ski 2

我们先考虑 \(\max H_i\) 是 \(O(N)\) 的怎么做

首先考察几个贪心的结论，我们将所有的地点按照双关键字 \((H_i,C_i)\) 从小到大排序之后，所有 \(C_i\) 的前缀最小值对应的点是不会被移动的，容易通过调整法证明其不优。这也就意味着，我们知道要在某一个高度 \(H\) 上添加一个向前的连边，代价是可以 \(O(1)\) 的得到的。

对于一组确定的解，海拔更高的一层能够容纳的不需要额外修建连接设施的点是非严格递增的，下面给出一张图，可以用于感性理解：

其中橙色点为前缀最小值点，绿色边为原有连接设施连接的边，红色边为额外修建连接设施链接的边。

由此，我们可以设计出 DP 状态 \(f_{i,j,k}\)，表示当前要处理海拔 \(i\)，这一行可以接纳 \(j\) 个点，海拔 \(<i\) 的还有 \(k\) 个点没有填入的最小代价 \(f_{i,j,k}\)。

则可以有转移：\(f_{i,j+1,k}\gets f_{i,j,k}+\min\{C_x|H_x\le i\}\)，记 \(cnt_i=\#\{x|H_x=i\}\) \(f_{i+1,j,\max(k+cnt_i-j,0)}\gets f_{i,j,k}+K*(k+cnt_i)\)。

这样的时间复杂度是 \(O(n^2\max H_i)\) 的。

考虑 \(\max H_i\) 是 \(10^9\) 量级时，实际有操作意义的只有 \(H_i\) 和 \(H_i+1\) 这样的海拔，其他的海拔高度只影响第二种转移的权值计算，但是这个权值计算可以做到 \(O(1)\)。所以最终时间复杂度为 \(O(n^3)\)。

Day1 T3 Spy 3

很厉害的题目，首先考虑 \(q=1\) 怎么做。

我们找到一条从 \(0\) 到 \(T_0\) 的最短路，如果一个节点可以从多个节点走来，我们钦定从编号最小的走（为了唯一确定路径）。

在这条路径上，肯能会经过若干条边权 Bitaro 未知的边，我们将这些边标记为 1，其他边标记为 0。传输一个长度为 k 的字符串。

那么 Bitaro 将被标记了的边边权设置成 \(1\)，其余边设置成 \(+\infty\)。我们可以证明 Bitaro 选择出来的最短路径和 Aoi 的一致。

具体的，一条路劲的贡献可以被拆成两个部分，每一条边原来的权值-经过的未知边权值减小的量，发现 Aoi 选择的路径在第一个值中取到了最小值，在第二个值中取到了最大值，所以它一定是最优的。

考虑将这个做法拓展到 \(q>1\) 上。

这就意味着我们需要构造的不是最短路了，而是一个类似最短路树的结构。我们考虑依次处理 \(T_0,T_1\dots T_q\)。在处理 \(T_i\) 之前我们已经得到了 \(T_0\sim T_{i-1}\) 的最短路构成并了。如果我们知道 \(T_i\) 的最短路在什么时候和前面的最短路有交了，我们就可以从那个点开始，进行 \(q=1\) 的最短路了，因为这样每一条未知边最多只会被一个点的最短路覆盖，我们对于每一条未知边维护这个信息，就可以做到 \(k\log_2(q+1)+q\log_2n\)。更宽松的，我们可以将这个起始点向上移动到第一个未知边的下面，这样我们维护这个起始点就只需要 \(q\log_2(k+1)\)。考虑到 \(q+1=17\)，用 \(5\) 位维护太浪费了，所以压缩一下，即可通过。

Day2 T1 Board Game

我们首先分析一下 \(2\sim k\) 用处，因为要让 \(1\) 到达的时刻尽可能早，所以 \(2\sim k\) 需要走尽可能短的路径。考虑一个点走到了某一个终止点之后，它下一轮最多只需要走两步：\(u\to v\to u\)。所以除了第一轮，后面每一轮都最多走 \(2\) 步，代价可以被写成 \(2t+h\) 的形式。考虑走一步的时候，就是它在两个相邻的终止点之间横跳，假设我们可以在 \(a\) 轮，消耗 \(b\) 的时间走到一个这样的点，则它对应的代价就是 \((t-a)+b=t+(b-a)\)。可以证明在 \(t<a\) 的时候这个式子比 \(2t+h\) 劣，所以我们直接维护 \(b-a\) 即可。

而 \(h\) 和 \(b-a\) 的维护都是可以用 bfs 或者 01bfs 得到的。

因此，如果 \(1\) 每多走一轮，它就会至少多 \(k-1\) 的代价，也就意味相较于最早到达每一个点的轮数，最优的到达轮数至多比它对 \(\dfrac{n}{k-1}\)，我们可以建一个 \(O(\dfrac{n}{k-1})\) 层的分成图来求解，bfs 即可。看到对于 \(k\) 很大我们有了解决方案，就会联想到阈值分治。也就意味着我们有了 \(k>B\) 时 \(O(\dfrac{n^2}{B})\) 的做法。

考虑到 \(k\) 很小的时候，因为其他点的代价可以写成 \(kt+h\) 的形式，这也就意味着，最优的情况会形成一个下凸壳。我们对于每一种不同的斜率 \(k\)，钦定多走一轮的代价为 \(t\)，加上偏移量之后，一定只有在 \(t\) 属于对应斜率的区间才是最优的，所以可以直接跑 k 次 Dijk 来求解答案，时间复杂度 \(O(nB\log n)\)。

平衡之后复杂度为 \(O(n\sqrt{n}\log n)\)。

Day2 T2 Growing Vegetables is Fun 5

假设我们确定了每一种颜色的花盆对应的区间，我们可以通过调整法知道，必然是将 \(A\) 和 \(B\) 从小到大排序之后依次匹配。

由于 \([1,l)\cup [l+N,2N]\) 的处理可以认为是将所有的数取反了之后得到的结果，所以我们现在只考虑用 \(A[l,l+N-1],l\in [1,N]\) 去对应 \(B\) 的情况。

我们希望最大值最小，所以考虑二分答案 \(t\)。则对于每一个 \(A_i\)，我们知道它可以和一个区间的 \(B\) 匹配，具体的，就是 \([L,R)\)，其中 \(B_{L-1}< A_i-t\le B_L\)，\(B_{R-1}\le A_i+t<B_R\)。

由于 \(A\) 序列有极其特殊的结构，所以我们考察 \(A_i\) 的 \(l\in[1,N]\) 时，它会对应哪一个 \(B_j\)。

· 对于 \(i\in[1,N]\)，每一次移动区间会删去一个小于 \(A_i\) 的数，加入一个前若干次大于 \(A_i\) 后若干次小于等于 \(A_i\) 的数。对应的 \(B_j\) 中的 \(j\) 是一段斜率为 \(-1\) 的一次函数拼上一个常函数。
· 对于 \(i\in [N+1,2N]\)，每一次移动区间会加入一个小于 \(A_i\) 的数，删去一个前若干次小于等于 \(A_i\) 后若干次大于 \(A_i\) 的数。对应的 \(B_j\) 中的 \(j\) 是一段常函数拼上一个斜率为 \(1\) 的一次函数。

我们只需要计算出衔接的关键点，在配合上 \(A_i\) 能够匹配的 \(B\) 区间 \([L,R)\)，我们就可以 \(O(1)\) 计算出某一个区间的 \(l\)，对于这个 \(A_i\) 数满足条件的。我们利用差分前缀和就可以知道哪一些区间左端点 \(l\) 对于 \(N\) 个 \(A_i\) 满足条件了。

而计算关键点都是形如 \(\le A_i\) 的 \(x\) 最大的 \(A_x\) 之类的问题，可以通过指针扫一遍维护，单词 check 的时间复杂度为 \(O(n)\)。

所以最终时间复杂度为 \(O(n(\log n+\log \max A))\)。