题解：P11990 [JOIST 2025] 大会 / Conference
luqyou
·
2026-07-21 20:54:49
·
题解
这题，太难了。
考虑这个相邻字符贡献的形式启发我们去考虑一个什么样的结构。我们发现，一个极大连续 \texttt{?} 段内的字符我们可以任意选定。首先显然可以先扔掉所有 \texttt{?} 后加入所有相邻不同字符的贡献，那么，为了最小化段内的贡献，我们肯定是将所有相同的字符排在一起，所以一个这样的段的贡献只会取决于：
具体地：
若这个段的左右两侧字符相同：
若只允许其填入这个段左右两侧的这种字符，则产生 0 的额外代价；
在此基础上，若额外允许填入一种（如 \texttt{AAAAABBBBA} ），产生 2 的额外代价；
若额外允许填入两种（如 \texttt{AABBBBBCCCA} ），产生 3 的额外代价。
若这个段的左右两侧字符不同：
若只允许其填入这个段左右两侧的这两种字符（如 \texttt{AAABBB} ），则产生 0 的额外代价；
若允许填入所有字符（如 \texttt{AAAAACCCCBB} ），则产生 1 的额外代价。
我们当然希望所有段的额外代价就是 0 ，即：对于某一个段，只允许填入在两端出现过的字符。但是这几乎是不可能做到的。于是我们定义一个“扩展”的操作，即允许该段填入更多种类的字符，但是也需要如上付出额外的代价。举个例子：
那么我们什么时候需要进行扩展呢？
经过观察可以发现，只有两种情况：要么是我们要求强制填某种字符的位置太多了，要么是能够填某种字符的位置太少了。我们记 L_c 代表强制填字符 c 的位置个数，R_c 代表能够填字符 c 的位置个数，那么有一个必要的有解条件是 L_{\texttt{A}} \le X \le R_{\texttt{A}} 且 L_{\texttt{B}} \le Y \le R_{\texttt{B}} 且 L_{\texttt{C}} \le Z \le R_{\texttt{C}} 。手玩一下发现这个条件似乎很强啊！事实上，这个条件是充分的。证明可以考虑对字符与段建立二分图，那么 Hall 定理给出的上下界就刚好是这六个不等式。
那么我们应该如何去考虑这个限制呢？下界只对应了一种段，而上界对应了很多个段，所以上界肯定是比下界要难考虑的，所以我们去考虑上界的满足情况，在此基础上去考虑下界。接下来有三种情况：
此时只需要考虑下界，每个字符的扩展是独立的。假设考虑 \texttt{A} ，那么一定是选择若干个最长的 \texttt{A} 段，花费 1 的代价将其扩展为 \texttt{AB} 段或 \texttt{AC} 段（这两种情况等价），对于 \texttt{B} 和 \texttt{C} 同理，因此只需要将所有段长降序排序后二分一下即可。
仅有 X > R_{\texttt{A}} 或仅有 Y > R_{\texttt{B}} 或仅有 Z > R_{\texttt{C}} 。
不妨设 X > R_{\texttt{A}} ，其余情况是对称的。
此时若 $\texttt{A}$ 的上界仍然不满足，那么现在就需要继续将一些 $\texttt{B}$ 段或 $\texttt{C}$ 段扩展为 $\texttt{AB}$ 段或 $\texttt{AC}$ 段，或者将一些 $\texttt{BC}$ 段扩展为 $\texttt{ABC}$ 段。问题转化为这样的形式：有若干个物品，每个物品有一个 $1$ 或者 $2$ 的代价以及一个收益，问达到某个收益的最少代价是多少。
这就是 [sale](https://www.luogu.com.cn/problem/P14636)，按照性价比排序后，优先选择性价比高的物品。若最后一个选择的物品代价为 $1$，那么不选它不可能用更少的代价达成目标；否则我们最后选择了一个代价为 $2$ 的物品，考虑其可能卡住的本来可以用更少代价达成目标的 $1$，或者删掉一个已经选了的 $1$ 即可。这一段细节特别多，写的时候小心一点。
- 仅有 $X \le R_{\texttt{A}}$ 或仅有 $Y \le R_{\texttt{B}}$ 或仅有 $Z \le R_{\texttt{C}}$。
不妨设 $X \le R_{\texttt{A}}$。
这个时候，记总共有 $K$ 个 $\texttt{?}$，则有 $K-L_{\texttt{A}} \le R_{\texttt{B}}+R_{\texttt{C}} < Y+Z$，而 $X=K-Y-Z$，因此一定有 $X < L_{\texttt{A}}$。所以我们必须要将某些 $\texttt{A}$ 段扩展为 $\texttt{AB}$ 段、$\texttt{AC}$ 段或 $\texttt{ABC}$ 段以满足限制。
首先要想满足 $\texttt{A}$ 的限制，我们仍然将段长排序后二分一个最少的段数使得其满足 $\texttt{A}$ 的下界，假设需要 $p$ 个。首先将它们全部扩展为 $\texttt{ABC}$ 肯定是能满足限制的，因此不需要额外的段来扩展。然后我们至少需要付出 $2p$ 的代价，因为每个 $\texttt{A}$ 段至少需要被扩展为一个 $\texttt{AB}$ 段或 $\texttt{AC}$ 段。
但是 $2p$ 的代价肯定是不一定够的，考虑若某一个段被扩展为 $\texttt{ABC}$ 会怎么样。我们一定是选择最长的段扩展，然后考虑两个段：一个 $\texttt{ABC}$ 段和一个 $\texttt{A}$ 段，需要被扩展为 $\texttt{AB}$ 段或 $\texttt{AC}$ 段。若需要放入的 $\texttt{B}$ 的个数小于 $\texttt{ABC}$ 的段数，那么我们将 $\texttt{A}$ 段扩展为 $\texttt{AC}$，因为 $\texttt{ABC}$ 段已经能容纳所有的 $\texttt{B}$ 了。此时其余位置均能填写 $\texttt{A}$ 或者 $\texttt{C}$，因此这种方案一定是合法的；否则将 $\texttt{A}$ 段扩展为 $\texttt{AB}$ 段，是同理的。这告诉我们，这两段在效果上等效于一个长度为它们长度之和的 $\texttt{ABC}$ 段！因此我们至多只需要扩展出一个 $\texttt{ABC}$ 段，就可以使用上述合并段的方法证明其一定合法。
所以最大代价至多是 $2p+1$，现在唯一的问题就是如何判定 $2p$ 是否可行了。分别考虑 $\texttt{B},\texttt{C}$ 对方案的限制，假设扩展为 $\texttt{AB}$ 的段长总和是 $x$，能够扩展的 $\texttt{A}$ 段总长为 $l$，那么对于字符 $\texttt{B}$，我们有 $x \ge Y-R_{\texttt{B}}$，同理有 $l-x \ge Z-R_{\texttt{C}}$。因此我们的 $x$ 必须满足 $Y-R_{\texttt{B}} \le x \le l-Z+R_{\texttt{C}}$。
这就是在问我们，在长度为 $p$ 的前缀中，是否存在一个子集和在某个区间 $[L,R]$ 中？
显然可以使用背包处理 $f_x$ 代表能凑出和 $x$ 的最短前缀，则只需要用 ST 表支持查询区间 $\text{min}$ 即可。暴力背包可以做到 $O(n^2)$，但是我们运用经典 trick，段的总长是不超过 $n$ 的，因此段长种类数是 $O(\sqrt n)$ 的。对每个段长转移，肯定用最长可凑出的总和转移最优，因此只需要对每个余数维护最后一个可达下标即可做到 $O(n)$ 转移，这部分总的复杂度为 $O(n \sqrt n)$。
现在我们将三种情况全部讨论完了，这样就解决了该题。总时间复杂度是 $O(n \sqrt n + q \log n)$。