AT5802 [AGC043E] Topology

约瑟夫用脑玩 · 2021-09-03 18:59:49 · 题解

施工完毕！神仙题的详细且通俗易懂的题解（确信，长文警告！！！

Step1 读懂题面

虽然中文题面很劝退，但相信你英文题面也看不懂，我们还是可以从读入格式，输出格式和范围中获得如下信息：

（食用提醒：不出现超出初中理解范围的东西）

• 这是一张 2\times (N+1) 个格点的方格图，有两行，每行 N+1 个格点，规定所有格点的集合为 S=\{(x,y)|x\in[0,N],y\in\{0,1\}\}。
• 每个方格的中间有个点，称其为中间点，规定第 i 个中间点为 B_i=(i+0.5,0.5),i\in [0,n]。

良心笔者给了张手画的图：

• 题目有 2^N 组限制，每组限制为对于不重复的每一个集合 S，\forall x\in S,x\in[1,N]，给出一个整数 k_S。
• 我们需构造一个 封闭曲线 ，满足对于每个限制的集合 S 所对应的中间点集 D_S=\{B_x|x\in S\}，这个曲线可以 通过移动离开这个点集 当且仅当 k_S=1。

斜体的地方显然是我夹带了私货，你们这样看即可：

我们需构造一个 【数据删除】 ，满足对于每个限制的集合 S 所对应的中间点集 D_S=\{B_x|x\in S\}，这个曲线可以 【数据删除】 当且仅当 k_S=1。

好，这样肯定是没有出路的，我们需要寻求一种通俗的方式读懂【数据删除】。

首先我们将这个方格图升维，即在三维平面上考虑这个问题。

找不到什么好看的图凑合一下，只考虑中间点，先不管网格图，这张图的横杠代表的就是中间点。

良心笔者给出了将中间点加长，变成横杠的三维情况的过程：

此时图中间代表的是中间点都存在的情况，即 D_S 恰为全集的样子，我们来看一个更一般的情况：

我们现在要在上面绕绳子，绳子是悬空的，它的初始状态固定。

绳子就是我们要构造的东西。

接下来是通俗的描述限制：

设当前限制的集合为 S，对应中间点集为 E=D_S，B_x\in E 的中间点都存在，B_x\notin E 的中间点都不存在的，k_S=1当且仅当这根绳子在这种中间点的出现情况下能解开。

解开即能拿下来，使得绳子与这个云梯（一种健身器材）毫无关系，这里指实际三维空间概念上的完全分离。

这是绕上绳子的样子：

显然这张图是解不下来的。

这是另一种绕绳子的方式：

显然是解得下来的，而绿色的绳子就是解下来的样子，话说一根绳子解下来都是这个样子。

Step2 化简题目限制

考虑一个状态 S=01001,k_S=0，那么 k_{11001} 一定为 0，因为第一个中间点不加都解不下来，那么加了过后一定也解不下来。

建图，由 S 向 T 连边当且仅当 \exists i,S\&2^i=0\ \land\ S|2^i=T，即 S,T 相差一位。

那么这张图满足：对于任意上述的 S,T，满足 k_S=0,k_T=1 不同时成立。

那么最后的图一定长这样：

每个点代表一个状态，边为了体现方向由大的状态连向小的状态，其中在同一层的状态的 1 的个数相同，相邻层 1 的个数相差 1。

一定存在一条形如图中的红色分割线满足：分割线以下的蓝色部分的 k_s 均为 1，分割线以下的绿色部分的 k_s 均为 0。

考虑有边跨越分割线且 k_S=0 的状态，即图中的红色点，它们有一些巧妙的含义。

复述一下它们满足的条件，你或许会发现什么：设状态为 S，对应中间点集为 E=D_S，B_x\in E 的中间点都存在，B_x\notin E 的中间点都不存在时，这根绳子无法解开，即 k_S=0。

而去掉任意一个 B_x\in E 的中间点都会使得这根绳子能解开，因为去掉后就是另一个状态 U 必定在分割线另一侧，使得 k_U=1。

同时我们发现只要构造出的绳子满足分割线上的红色点都无法解开，那么绿色部分更内部的状态一定更无法解开。

蓝色部分同理，即分割线附近能解开，那么更下面的状态一定更能解开。

那么我们现在只用考虑把这些红色点即可，并且得到了很好的性质，达到了简化限制的目的。

Step3 构造

只剩下构造了，我们先只考虑一个红色点构造的绳子，所有红色点的构造是可以随便拼起来的，原因后面再讲。

一个红色点对应的状态假设是被圈出来的中间点，那么其他中间点我们可以忽略掉：

就像上图蓝色绕的绳子一样（乱画的），对于其他中间点我们可以全部走上面或是走下面，也即绳子完全绕不到它们身上去，跟它们毫无关系，直接忽略即可。

那么现在只剩下了一排 m 个点，我们要构造一种绳子的缠绕方式使得当前状态解不掉，但去掉任意一个点后都能解得掉！

实际上这个东西并不容易，不信你可以试着不看下面手推一下 n=2 的情况，保你推不出来。

提醒：强烈建议手玩一下 n=2 的情况，不管是看了归纳方法还是没看，不然你很难想象归纳进行的时候为什么能解开。

良心笔者的帮助，n=2 的效果图如下（画了两天都刻入 DNA 了），红色代表在黑色线的正上方，三维的怕你不好想象：

考虑归纳构造：

• 考虑边界 n=1，绕一圈即可：

但好像不方便扩展归纳，我们将左边解开，将所有的绳子都留一个口方便后面构造，容易发现把这个口接起来后还是一样的：

注意有以下性质：m' 个点构造出的绳子的（留的口的）两端一定一个从 m' 上面穿出，一个从 m' 下面穿出。

以下两端或上下端均指留了口的绳子的两端。

这个性质是构造过程中保证的，边界满足，后面构造也都满足，无需证明。

• 考虑 n>1，我们已经构造好了 n-1 的方案：

由于左边露了个口，补充一下：下文中“能解开”具体指能解成绿色绳子的样子，即与原本套住的点完全分离，第二个箭头表示往左边拖一点好看：

这里黑色的线仅代表一种方案将前 n-1 个点框住且满足少任意一个点都框不住，即能解开，我们并不关心具体方案，只用大概的一种形态表示即可。

想办法将 n 也框进来并且仍满足条件，我们再加一种方案（用颜色区分方案方案），红色方案与黑色方案有一定联系，过后再说：

我们用两个方案的下面一端将 n 框进来，剩下两端一上一下使得删掉 1\sim n-1 中任意一点后 1\sim n 都能解开。

即（假设 1\sim n-1 中的一个点被删掉了）：

我们是不是遗漏了什么？删掉 1\sim n-1 都能解开，那我们删 n 呢？显然我们可以利用红色方案和黑色方案之间的关系使得删 n 也能满足。

我们将黑色方案倒过来使得其可以倒着走回去，具体的，倒过来指：

对于某个点，黑色如果往下面走，红色回来的时候就跟着下面回来，而不走上面的绿色。

这样只要前面解开了就可以一步一步退回去，你也可以看作一条线往回缩，反正挨着回退构造即可。

这样利用的是一种方案从上端往下端走和从下端往回走都可以满足条件的性质：倒着走仍然能满足 n-1 前任删掉一个能把后面都解开，毕竟正着走和反着走本质一样，除了方向外基本算是一模一样。

这样我们就归纳构造出了方案。

Step4 整理思路

先找到分割线上的状态，顺便把无解都判掉。

这里补充一下为什么分别构造绳子是独立的：

首先包含了其他状态的状态肯定没用，然后两两状态互不包含，满足了一种限制的绳子在其他状态时肯定而会因为至少一个点而被解开。

注意这里解开是指从套了一些点解成了一个空套，还是那张图：

我们可以依次把除了恰好限制那种状态的其他限制的绳子的套都解完，如上上图红色绳子在黄色绳限制的状态处会因为左二而解开，蓝色也会因为左一的没有而被解开。

于是我们直接把红黄蓝这三种绳依次连接就能满足对应限制。

有多少的分割点的限制就在 (0,1) 或 (0,0) 处把绳子左端的口依次首尾相接即可。

注意亿些细节：

• 在构造时我们忽略了中间不在状态中的点，但在实际绕绳子的时候显然不能忽略，记得选择从上面或从下面全部绕过去。

• 构造时开了个口不仅方便了构造同时方便首尾连接，最后记得把口补上，自己搞的本来以为是小技巧结果还很有用。

• 不要相信网上那些有误导性错误还无法与博主对线的博客，更不要相信除了像我这样写包票无误以外的博客

  好吧耽误了点时间比较气，建议仅供参考，不过分相信还是有帮助的。

• 网上对复杂度上界完全闭口不谈（不包含官方，因为这种连英文题面都看不懂的题不敢看官方题解，其实网上的好像就是官方题解翻译），虽然上界很松还是要证明一下本做法在上界内：

  首先只取分割线的状态就只有 \binom 84=70 种状态了，满打满算最大的状态肯定是 N 个点排满，要用 T_N=2T_{N-1}+7 步。

代码是很有必要看一下的，比较构造题有许多细节容易挂。（雷我帮你都踩过一次了，不懂来问，当然自己踩雷更好，也就半天时间）