IOI2024

可能有点胡言乱语。

本人较菜，部分题目借鉴 tiger2005 的题解。

D1T1 Nile

观察到 \(B_i<A_i\)，那么我们可以转化我们要解决的问题：

记 \(val_i=A_i-B_i\)。如果我们让 \(i\) 货物和 \(j\) 货物运到一起，我们会有 \(val_i+val_j\) 的收益。由于 \(val_i>0\)，所以选择尽可能多的货物同时运输是更优的。

我们将货物按照 \(W_i\) 从小到大排序，那么这样我们可以很好的根据 \(D\) 确定 \(i\) 能够匹配哪些货物。那么如果我们确定了是哪 \(2k\) 个货物，那么匹配的货物必然是第 \(2i-1\) 个和第 \(2i\) 个，\(i=1,2\dots k\)。

假设其中一对是 \(x,y(x<y)\)。

如果 \(y>x+2\)，就是有 \(W_y-W_x\le D\)，显然可以推出 \(W_y-W_{x+2}\le D\) 和 \(W_{x+1}-W_x\le D\)，那么如果匹配 \(x,x+1\) 和 \(x+2,y\)，那么会多出 \(val_{x+1}\) 和 \(val_{x+2}\) 的贡献。那么 \(x,y\) 移动不是最优匹配中的匹配。

所以有 \(y\le x+2\)。

那么我们就很容易能够设计出 DP 了，记 \(f_x\) 表示处理了前 \(i\) 个货物的匹配的最大收益，可以得到三种转移：

• \(f_x\gets f_{x-1}\)
• \(f_x\gets f_{x-2}+val_{x-1}+val_x\)，当 \(W_x-W_{x-1}\le D\) 时。
• \(f_x\gets f_{x-3}+val_{x-2}+val_x\)，当 \(W_x-W_{x-2}\le D\) 时。

显然，这个转移时容易写成 \((\max,+)\) 矩阵的，记 \(f'_x=f_x+val_{x+1}\)：
\(\begin{bmatrix}f_x&f'_{x-1}&f'_{x-2}\end{bmatrix}\begin{bmatrix}0&val_{x+1}&-\infty&\\A_x& -\infty&1\\B_x&-\infty&-\infty\end{bmatrix}=\begin{bmatrix}f_{x+1}&f'_x&f'_{x-1}\end{bmatrix}\)。

其中 \(A_x=\begin{cases}val_{x+1}&,W_{x+1}-W_x\le D\\ -\infty&,W_{x+1}-W_x>D\end{cases}\)，\(B_x=\begin{cases}val_{x+1}&,W_{x+1}-W_{x-1}\le D\\ -\infty&,W_{x+1}-W_{x-1}>D\end{cases}\)。

考虑将所有询问从小到大排序处理，那么 \(A\) 和 \(B\) 的变化次数总计只会有 \(2n\) 次，使用数据结构维护动态 DP 即可。

时间复杂度 \(O(n\log n)\)。

D1T2 message

会被 \(C\) 修改的所有位置没有办法传输任何有效的信息，所以能够传输的有效信息之后 \(66\times 16=1056\) 位。

考虑需要传输多少个信息才能传输 \(M\)，因为 \(M\) 的位数不确定，所以我们需要 \(1025\) 位才能够传输信息：得到一个长度为 \(1025\) 的信息 \(M'\)，将最后一个 \(1\) 记以后的零都删除之后得到 \(M\)。

那么我们剩下的位就只剩 \(1056-1025=31\) 位了，刚好就是单次传输的信息长度，也就是 \(C\) 的长度。

发现我们难以在 \(<2\) 次传输内传输 \(C\) 具体时多少。所以我们考虑实际传世的有效信息是一个 \(66\times 16\) 的矩阵，我们只需要在占用 \(31\) 个格子的情况下确定 \(C\)，然后挖掉这 \(31\) 个格子，剩下的格子按照顺序就是 \(M'\)。

考虑对于每一个不会被 \(C\) 修改的位置，我们确定一个 \(x\) 表示在循环移位的意义下向后移动 \(x\) 次可以刚好到达下一个不会被 \(C\) 修改的位置。

传输 \(x\) 的方式就是让前 \(x-1\) 位为 \(0\)，第 \(x\) 位为 \(1\)。考虑上会被 \(C\) 修改的位置，每一个位置都会指向另一个位置，形成一个内向基环森林。而 \(16\) 个不会被修改的位置会形成一个大小为 \(16\) 的环。

由于总共只有 \(31\) 个节点，所以大小为 \(16\) 的环是唯一的，找到这个环就可以确定所有有效的位置。

发现我们占用的格子数就是 \(\sum x\)，刚好环绕一遍整个环，总计 \(31\) 个。

D1T3 tree

首先考虑如何处理依次询问。

发现我们的策略必然是在叶子处有 \(C_i=L\)，非叶子有 \(C_i\le 0\)。考虑非叶子处我们减少的具体数量是不确定的，所以我们可以先预留出来它可以减少多少次，在后面需要减少的时候挑最优的减少。
对于每一棵子树，维护可重集合 \(\{w\}\)，每一个 \(w\) 表示一个可以用 \(w\) 的代价减 \(1\) 操作，那么操作就是：

1. 在树上合并所有的儿子的集合
2. 将所有 \(w>W_i\) 的 \(w\) 都替换成 \(W_i\)。
3. 按照 \(w\) 从小到大删除，直到 \(\sum cnt\le R\)。
4. 将当前集合中权值最大的 \(L\) 个的 \(w\) 变成 \(+\infty\)。

初始化为所有叶子节点集合为 \(L\) 个 \(W_i\)。

考虑将这个问题拓展到多组询问。

由于上面的处理，除了某些数会被只删掉 \(R\bmod L\) 个之外，其余的所有块都只会被 \(L\) 个同时删去或者不删去。发现整个操作和 \(L,R\) 的绝对大小没有很大的关系，我们只关注 \(L,R\) 的相对大小，也就是 \(\left\lfloor\dfrac{R}{L}\right\rfloor\) 的值。

我们可以维护出在 \(L=1,R=k+1\) 的时候不会被删去，在 \(L=1,R=k\) 的时候会删去的权值之和为 \(v_k\)。那么对于 \(k_0=\left\lfloor\dfrac{R}{L}\right\rfloor\)，最终答案为 \((\sum\limits_{k\ge k_0}v_k)L-v_{k_0}(R/bmod L)\)。

仍然尝试使用使用单次询问的方法去维护，默认 \(L=1\)，但是由于不确定 \(R\)，所以我们统一到最后去对应贡献，但是考虑到在过程之中可能会出现有一些数要被删除的情况。但是考虑到，在一个儿子内会被删除掉，那么在后面的所有节点它都会被删除掉，所以一定会被删除。

那么我们只需要在它被修改的时候对他会影响的位置进行差分即可。

对于一个某个节点的集合内的第 \(t\) 大，代价是 \(w\) 的点，如果它的父亲贡献是 \(W_i<w\)，那么 \(w\) 就会在父亲处变成 \(W_i\)，但是实际上在 \(R<t\) 的时候它应该用 \(w\) 的贡献，那么它会对 \(R<t\) 的所有询问做出 \(w-W_i\) 的贡献

那么对于一个节点 \(W_x\)，权值等于 \(W_x\) 元素都会在第一个 \(W_u<W_x\) 的祖先处被卡住，所以我们考虑找到这个节点，以及 \(x\) 对应的那个 \(u\) 的儿子 \(y\)，假设 \(x\) 的所有节点对应 \(y\) 中的第 \(l,r\) 大，那么就会对 \([l,r]\) 这一段加上 \(W_x-W_u\)。

由于每一个节点都必然会有一个权值为 \(+\infty\) 的点，所以我们初始将每一个点的 \(siz\) 设为 \(1\)。我们从大到小枚举 \(x\)，那么权值为 \(x\) 的节点数量 \(siz'\) 就是 \(x\) 的所有儿子当前的 \(siz\) 之和，同时如果 \(y\) 的 \(siz\) 就会增加 \(siz'\)。

而找 \(y\) 可以直接使用并查集维护，时间复杂度 \(O(n\log n)\)。

D2T1 hieroglyphs

省略了很多证明，详情可见这里。

首先我们考虑 UCS 的组成结构。

对于一个字符 \(x\)，如果其在 \(A\) 中出现了 \(a\) 次，在 \(B\) 中出现了 \(b\) 次，那么显然 \(A\) 和 \(B\) 有一个公共子序列为 \(\min(a,b)\) 个 \(x\)。

那么 UCS 就至少包含 \(\min(a,b)\) 个 \(x\)，如果有 \(a\le b\)，那么 \(A\) 中所有 \(x\) 位置都会被 UCS 选择，称 \(x\) 为 \(A\) 的关键字符；同理 \(a>b\) 的情况，\(B\) 中所有的 \(x\) 都会被 UCS 选择，称 \(x\) 为 \(B\) 的关键字符。我们成所有关键字符在对应序列中的位置为关键位置。

记 UCS 为序列 \(C\)，那么我们可以得到两个长度为 \(|C|\) 的序列 \(\{p_i\}\) 和 \(\{q_i\}\)，有 \(C_i=A_{p_i}=B_{q_i}\)，那么显然 \(p_i\) 和 \(q_i\) 中有且仅有一个是关键位置。

那么发现 UCS 的长度就是确定的，就是 \(\sum\min(a,b)\)。同时由于 \(A\) 和 \(B\) 的所有公共子序列都是 \(C\) 的公共子序列，所以 UCS 应为唯一确定的。

现在的做法就很明确了，找到唯一一个可能是 UCS 的序列 \(C\)，然后检验 \(C\) 是否满足 UCS 的限制。

对于第一步，为了不遗漏情况，我们使用子序列经典的贪心匹配法，维护两个指针 \(flA\) 和 \(flB\) 表示当前 UCS 匹配到了 \(A\) 和 \(B\) 的哪个位置。

记 \(flA\) 之后的 \(A\) 中的下一个关键位置在 \(tA\)，\(flB\) 之后 \(B\) 中的下一个关键位置在 \(tB\)，那么 \(C\) 的下一位必然在 \(A_{tA}\) 和 \(B_{tB}\) 中选择。

我们考虑如果 \(A_{tA}\) 能够被选择需要满足什么条件：

1. 存在 \(i\in(flB,tB)\) 使得 \(B_i=A_{tA}\)。
2. 在 \((tA,|A|]\) 中 \(B_{tB}\) 的数量不小于 \([tB,|B|]\) 中 \(B\) 的数量。

如果这两个条件满足，我们就认为 \(A_{tA}\) 可以被选择。同理可以判断 \(B_{tB}\)。

如果两个都不可行，显然无解；如果只有一个可行，那么只能选择这个；如果两个都可行，可以被证明，能够按照这个方法生成出来的 UCS，都能找到一个 \(A\) 和 \(B\) 的公共子序列，其不是 UCS 的子序列。

这样我们就得到了一个 UCS，现在我们要考虑检验它是否满足条件，也就是是否所有的 \(A\) 和 \(B\) 的公共子序列都是 \(C\) 的子序列。

考虑仍然使用子序列匹配的思想，分别记 \(flA,flB,flC\) 为在 \(A,B,C\) 中匹配到的位置。那么我们就是希望构造出来一个序列，使得匹配到某一位时，\(flA\) 和 \(flB\) 仍然能匹配，但是 \(flC\) 不行。

首先，显然有 \(flA\le p_{flC}\) 和 \(flB\le q_{flC}\)，因为显然存在通过 \(p\) 和 \(q\) 将 \(C\) 中的匹配映射到 \(A\) 和 \(B\) 的方式，使得 \(flA=p_{flC},flB=q_{flC}\)。而 \(A\) 和 \(B\) 中又可能存在其他的匹配方式，所以只可能更小。

同时，如果 \(flA<p_{flC}\) 且 \(flB<q_{flC}\)，我们可以选择依次匹配 \(C_{flC},C_{flC+1} \dots C_{|C|}\)，发现共会匹配 \(|C|-flC+1\) 位但是 \(flC\) 只能在往后匹配 \(|C|-flC\) 位了。这样就构造出了无解的情况。

我们考虑匹配过程中 \((flA,flB,flC)\) 的几种情况：

情况 \(1\)：\(flA=p_{flC}\) 且 \(flB=q_{flC}\)。我们假设下一个匹配的时 \(A\) 的一个关键字符 \(x\)，设 \(flC\) 变成了 \(flC'\)，显然有 \(flA'=p_{flC'}\)。假设 \(flB\) 也匹配到了 \(q_{flC'}\)，那么仍然是情况 \(1\)，否则会变成情况 \(2\)。

情况 \(2\)：\(flA=p_{flC}\) 和 \(flB=q_{flC}\) 值满足一个，不妨假设时 \(flA=p_{flC}\)，假设接下来要匹配的字符是 \(x\)，如果其不在 \((flB,q_{flC}]\) 中出现，那么 \(flB\) 的值变成 \(q_{flC}\) 也没有区别，可以被归类为情况 \(1\)；否则有 \(flB'<q_{flC}\)，考虑 \(flA\) 会匹配到什么位置，如果匹配的是 \(p\) 中存在的位置，可以通过讨论得到 \(flA'=p_{flC'}\)，仍然是情况 \(2\)；否则有 \(p_{flC}<flA'<p_{flC'}\)，归类为情况 \(3\)。

情况 \(3\)：\(flA<p_{flC}\) 且 \(flB<q_{flC}\)，这就是让 UCS 无解的情况。

发现情况 \(3\) 只能从情况 \(2\) 导出，而在情况而中我们有 \(flB'<flC<flA'\) 的推导，所以我们发现满足条件的 \(flA>p_{flC}\) 且 \(flB\le q_{flC}\) 情况必然有 \(\exists i,flB<q_i,p_i<flA\)。

而这个是很好处理的。我们只需要对于每一个不是 \(p\) 从存在位置的 \(flA\)，找到所有匹配到 \(flA\) 位置的序列中，最小的 \(flB\)，然后检验最大的 \(i\) 使 \(p_i<flA\) 是否满足 \(flB\le q_i\)。对于堆成情况是相同的。

而对于 \(flA\) 求 \(flB\)，是可以用单调栈处理的。

认为 \(n,m\) 同阶，则最终时间复杂度为 \(O(n\log n+|\Sigma|)\)。

D2T2 mosaic

如果 \((x,y)\) 为 \(1\)，那么 \((x+1,y),(x,y+1)\) 一定是 \(0\)，那么 \((x+1,y+1)\) 是 \(1\)，也就是最终会形成若干条 \(x-y=k\) 的斜线。

但是发现由于第一行和第一列被确定了，所以可能会出现一些奇怪结构，但是考虑向下拓展一层之后，不会出现相邻的 \(1\)，再往下拓展一层之后，不会出现相邻的长度超过 \(2\) 的 \(0\)。发现这种情况下，就会达到如下结构：

通过观察，发现我们可以维护出一个集合 \(S\)，对于所有 \(x>1,y>1\)，\((x,y)\) 为 \(1\) 当且仅当 \(x-y\in S\)。

将询问差分成 \(4\) 个 \(x\le X,y\le Y\) 的询问。这样，我们特殊处理 \(x\le 1\lor y\le 1\) 的部分，其余的部分可以直接 \(O(\log n)\) 计算贡献。

总时间复杂度 \(O(n\log n)\)。

D2T3 sphinx

首先考虑链的情况怎么做。我们可以选出一个独立集 \(S\)，然后将所有其余的点染成颜色 \(c\)。

如果 \(S\) 中没有颜色为 \(c\) 的点，那么答案应该是多少是可以确定的，具体等于 \(|S|\) 加上删掉独立集中的点之后图剩余的连通块数。

如果询问得到的结果不等于这个值，那么就说明 \(S\) 中有节点的颜色为 \(c\)。我们将 \(S\) 看作一个序列，那么我们就可以通过二分来找到 \(S\) 中第一个颜色为 \(c\) 的点，然后就可以将这个点删掉了。

这样，我们最劣通过 \(N+\sum\limits_{i=1}^{|S|}\left\lfloor\log_2i\right\rfloor\) 次询问就可以确定 \(S\) 内部所有点的颜色。

而对于链的情况，甚至对于任意二分图的情况，我们通过直接对二分图进行黑白染色将点集拆成两个独立集，然后分别处理。

但是很显然图不一定是二分图。

发现我们要求 \(S\) 是独立集的限制，一来要防止出现 \(S\) 内存在相邻的点对互相干扰，二来要保证 \(S\) 内每一个点至少和一个不在 \(S\) 中的点相邻。

对于第一点，我们发现，如果 \(S\) 中相邻的点如果颜色不相同，那么他们之间也不会互相干扰，所以如果能够将所有相邻且颜色相同的点缩成同一个点，然后再去处理，此时图中不存在相邻且颜色不同的点对，那么 \(S\) 有没有元素不相邻的限制了。

那么现在我们只需要关注第二点，这个是容易实现的，只需要在图中找到一个生成树然后黑白染色即可。

那么现在的问题就变成了如何将相邻且颜色相同的点缩在一起，也就是 \(50\%\) 的部分分。

考虑增量构造，依次将 \(0,1,\dots N-1\) 加入点集，每次加入 \(x\) 的时候，考虑已经在点集内且与 \(x\) 相邻的所有点，我们将除此之外的所有点染成 \(N\)，询问的点和 \(x\) 保留，\(x\) 不与任何相邻的点集颜色相同，那么答案也是可以提前计算的。如果询问得到的结果和预期的不一样，那么就说明 \(x\) 和之前的某一个点颜色相同，仍可以通过二分得到。

假设合并之后还剩 \(C\) 个点，那么这一部分需要的询问次数不大于 \(N+\sum\limits_{i=C+1}^N\left\lfloor\log_2i\right\rfloor\)。

那么最终询问次数不大于 \(3N+\sum\limits_{i=1}^N\left\lfloor\log2_i\right\rfloor\)，发现在 \(N=250\) 的时候是可以通过的。