题解：P11105 [ROI 2023 Day 1] 解密（数据有误）

buowen123 · 2024-12-13 17:34:58 · 题解

2024-12-13：交题解。
New update 2024-12-20：修改了原本有误的证明（T 不一定合法）；增添、修改了部分其他证明。

心路历程

我：令 R=\{x+1|x\in T\}，也就是将所有数加一。
出题人：不行，T=\{1,2,3\}。
我：将连续的数视为整体，这里令 R=\{4,5,6\}。
出题人：不行，T=\{1,2,4,6\}。
我：将所有数视为整体，有空位就往后拓展。这里令 R=\{3,5,7,8\}。
出题人：不行，T=\{1,2,4,6,12\}。
我：将 T 拆分为若干个集合，比如 T 拆分为 \{1,2,4,6\} 与 \{12\}，分别加密取并集。这里令 R=\{3,5,7,8,13\}。
出题人：不行，n=12。
我：将值域视作环形，令 12 的后继为 1。R=\{3,5,7,8,9\}。
出题人：……

正确解法

具体地，我们记一个 c 表示待拓展的数的个数，初始 c=0。从小到大遍历每一个数，每次将 c 增加 1 并尝试往后拓展，每拓展一个数 c 减去 1，直到遇到已出现的数或 c 变为 0 为止。

这样的话，每次 c 变为 0 等价于我们完成了一次拆分与加密。

解密就是往前拓展，不过你可以将每个 a_i 变为 n+1-a_i 然后和加密一样做。

一个细节：形如 n=10,T=\{1,10\} 一类的集合，如果你从小到大遍历，先划分出 \{1\} 并在 R 中加入 2，遍历到 10 时，需要跳过 1 和 2 直接在 R 中加入 3。具体见代码。

结论证明（过程极为繁琐）

如何证明加解密的正确性？我们具体考虑“往后拓展”的本质。以下探讨的 S \subseteq T 都是 T 中相邻的数构成的子集。

考虑我们划分出的 m 个数构成的数集 S，设 S 中的最小值为 t。
则会将 S 往后拓展为 K=[t,t+2m)\setminus S（自己手模一下）。
称 S \subseteq T 符合条件，当且仅当上述方法得到的 K 满足 K \cap T = \emptyset。
每次遍历一个数 a_i 时，会找出一个最小的 j，满足 S=\{x|x=a_o,i\le o\le j\} 符合条件（为了方便，不考虑值域环形）。称这样遍历出来的集合为极小集合。显然，所有极小集合的并为 T。
考虑将 T 视作括号序列：若 x \in T，则令 a_x=\texttt{(}，反之认为 a_x=\texttt{)}。于是操作变为：找出最短的以 t 开头的合法括号序列前缀。
对于加密，一个经典的 trick 是令 \texttt{(}=1,\texttt{)}=-1，考虑 f(y)=\sum_{i=t}^ya_i。由于 f(t)=1 且 f(t-1)\le 0（值域环形），由零点存在定理（假设函数图像为折线图）知存在一个 y 满足 f(y)=0，于是极小集合存在。将极小集合去除之后，只考虑剩下的未被使用过的 n-2m 个数，相当于规模由 (n,k) 变为 (n-2m,k-m)。 由于 n-2m\ge 2(k-m)\Leftrightarrow n\ge 2k 成立，故而对 (n,k) 归纳即可证明。这样的括号序列还满足不存在合法且不为 P 本身的前缀，称这样的括号序列是优秀的。
对于解密，由于合法括号序列的翻转仍然为合法括号序列，若解密过程不能正确还原 S，说明 K（翻转意义下）不是极小集合（还有更小的）。等价于原括号序列 P（未翻转）存在不为 P 本身的合法后缀。故说明 P 存在合法前缀，这与 P 是优秀的矛盾。的因此可知解密过程的存在性与正确性。
最后是一个特殊情况：上文中提到的细节是否影响正确性？同样从括号序列考虑，本质上是在一个优秀括号序列 P 中插入另一个优秀括号序列 P'（被跨越的部分）得到 Q（原本正确的部分），要求证明 Q 是优秀的。设 P=A+B,Q=A+P'+B。若不然，考虑合法前缀的结尾 x，分三种可能：
由此加解密过程都存在且合法。又因为结果唯一，于是每个 T 对应唯一的 R，每个 R 对应唯一的 T。证毕！

代码实现

代码细节很多；为了防止 xxs，本人的代码按照 QOJ 上的输入输出格式编写。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 3;
int a[maxn], b[maxn], n, k;
map <int, int> mp;
int main() {
    int id, T; cin >> id >> T;
    while (T--) {
        cin >> n >> k;
        for (int i = 1; i <= k; i++) cin >> a[i];
        if (id == 2) for (int i = 1; i <= k; i++) a[i] = n + 1 - a[i];
        sort(a + 1, a + k + 1);
        for (int i = 1; i <= k; i++) mp[a[i]] = 1;
        for (int i = 1, c = 0, j; i <= k; i++) {
            c++, j = a[i] + 1;
            mp[a[i]] = 3;
            if (j == n + 1) j = 1;
            while (mp[j] != 1 && c) { 
                if (!mp[j]) mp[j] = 2, c--;
                j++;
                if (j == n + 1) j = 1;
            }
            // j 在 map 里出现过，有两种可能：
            // 第一种可能：mp[j]==1，意味着碰到了另一个 T 中的数
            // 第二种可能：mp[j]==2或3，值域为环形，在例子中 n==10,T=={1,10} 的情况
            // 如 mp[1]=3 表示这个数时 T 中的数要 continue
            // mp[2]=2 表示这个数时 R 中的数要 continue
            // 注意不会遇到 需要break不需要continue 的 R 中的数
        }
        int tot = 0;
        for (auto p : mp) {
            if (p.second == 2) {
                if (id == 1) b[++tot] = p.first;
                else b[++tot] = n + 1 - p.first;
            }
        }
        sort(b + 1, b + tot + 1);
        for (int i = 1; i <= tot; i++) cout << b[i] << ' ';
        cout << '\n';
        mp.clear();
    } 
}

以下是一个真伪未知的证明（证明所有极小集合满足 t+2m-1\notin S）。在此求助大家，该证明过程是否正确？

若不然，则考虑对 S'=S\setminus \{t+2m-1\} 在忽略 t+2m-1 \in T 的前提下加密，不难证明加密出的结果 K' 仍满足 t+2m-1 \notin K'。即 S' 符合条件。由于在遍历到 S 前会遍历到 S'，于是 S 不为极小集合。

最后，如果本文有不足之处，或者各位有更简洁的证明方法，可以在评论区指出！

“所以你写这么多为啥不感性理解呢？”
“还不是被某道名字是吻秋的题撤一堆题解给吓的。”