自动搬运

查看原文

来自洛谷，原作者为

	buowen123 生活将我反复捶打，我变成可可爱爱的年糕～ | 根据抽屉原理，必然存在关注 >= 粉丝的人，也存在关注 <= 粉丝的人 | 似乎是 INFP-T | 粉关比 >= 1 的都是大神

搬运于2025-08-24 23:04:16，当前版本为作者最后更新于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$，分三种可能：

1. $x$ 在 $P'$ 中，要求 $P'$ 的前缀与 $A$ 中，左括号与有括号的数量相等，于是 $P'$ 的前缀与 $A$ 都是合法的，与 $P',P$ 是优秀的矛盾；
2. $x$ 不在 $P'$ 中，显然与 $P'$ 是优秀的矛盾。

• 由此加解密过程都存在且合法。又因为结果唯一，于是每个 $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$ 不为极小集合。

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

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