信息学集训队作业董华星solution

1、IOI2003 中国国家集训队难题活动0083sucker解题湖南长郡中学【题目大意】给定 m 个集合，每个集合中包括若干 1.n 中的数，要你确定一种 1.n 的排列序列，使得这 m 个集合中，每个集合包含的元素分别都排列在连续的位置上，任意顺序都可以，只要排列在一起。比如 n=4，有两个集合1，2，4，2，3，4，那么 1，2，4 要排列在一起，2，3，4 要排列在一起。1，2，4，3 就是满足条件的排列。【解决情况】已得到基本的解题思路和一般的实现方法，实现的时间复杂度为 O(MNlogN )。【算法梗概】通过集合划分的方式，得到最后可行的。【收获与感谢】基本想法已知道了，但不知道该如何

2、进一步优化，而大家也好像没想过，所以暂无收获。【正文】这道题表面上看起来好像是道 NP 问题，但是实际上有多项式解法。先简单的考虑一下，如果开始只有一个集合，那么集合中元素可以看作一个整体，这个整体中的元素的位置可以互相交换，如果再加入一个集合，这个集合与原来的集合相交（不包含或不被包含），那么可以将与这两个集合的相关的元素看为连续的 3 个整体，每个整体中的元素的位置任意，但是个整体间是有序的。比如，两个集合为1, 2, 3和2，3，4，那么分为的 3 个整体分别为1,2，3,4而且这三个整体的顺序是确定的，不然集合中的元素就不会连续了，当然42，31也是可行的，但是这两种顺序是对称的，可以

3、选其中任一种。再继续，如果一个新的集合与现有的至少两个整体相交（所有整体中未出现的元素，可看作属于另一整体），那么有可以根据相交的情况，划分为更细的若干连续整体。这样如果当我们将所有的集合都考虑进去了，最后只要按整体的顺序，输出各整体中的元素（每个整体中元素可以任意顺序输出）就是一种。其实整体实际上就是一个集合，下面提到的包含或相交和集合间包含和相交是一样的。根据上面的想法，可推出一种解法：设当前已被划分的整体有 T 个，依次为 Z1,Z2ZT。选择一个至少与其中两个整体相交，但是不完全包含 Z1.ZL 的集合 Si，可由 Si 与 L 个整体的关系划分新的整体。这里可以分为三种情况：1假设

4、Si 只与 Z 中整体相交，不包含这些整体以外的元素。在这种情况中，如果与 Si 相交的最左的整体为 ZL,最右的整体为 ZR，那么 Si 必须包含Zl+1.ZR-1 中全部的元素，否则无解。2假设 Si 包含 T 个整体以外的元素，而且与左边的一些整体相交。同上，如果与 Si 相交的最右整体为 ZR，那么 Si 必须包含 Z1.ZR-1 中的元素。3刚好同第二种情况相反。如果找到了满足条件的 Si，就可以按上面的方法细化各整体，但是如果找不到呢？下面分三种情况：1 如果所有的集合都与整体都不相交。那么，其他一些集合的情况和当前处理的集合是不相干的，可以看为独立的两个部分，可以先直截输出先前这

5、些整体中的元素，然后再考虑剩下一些集合。2 如果所有剩下的集合都包含整体。T12345T123T12345T123L+1T12这种情况好处理，一开始不总是选集合 1 设为初始整体，而选元素最多的集合。那么，以后得到的各整体中总元素，不会比未处理的任一个集合中的元素少，就不会出现这种情况。3 如果，剩下的一些集合只与一个整体相交。这种情况实际是问题规模的减小，分开考虑每个整体，处理只与此整体相交的集合，可将此整体划分为更小的整体。现在这个算法架已经确定了，下面讲具体实现的框架。1 设当前所有元素被划分为的所有整体，集合 Z（包含 Z1,Z2.）。开始将所有的元素看为一个整体 Z1=1.n。2 选

6、择当前整体中包含其他集合的整体，设为 Zx。如果找不到，程序结束；否则，继续。3 先规定：Zx 中元素划分为的整体集设为 Z。最开始就选择一个被 Zx 包含的最大的集合，此集合中元素可看作一个整体 Z1，然后每次都找一个至少与当前两个 Z整体有交的集合 Si（Zx 中不被任何 Z整体包含的元素看作另一整体 Z0），按前面提到的方式，划分新的 Z整体。直到找不到合理的 Si 为止。那么，用得到的 Z0，Z1看作相应的整体集 Z 中的整体，用来代替原来的 Zx。4 继续执行 2。实现的细节及优化：算法中因为要加入和两个以上的整体相交的集合，为了判断方便，可以用 CI表示第 I 个集合和当前几个整体

7、相交，那么对于 CI1 的集合，就可加入进来。但是这样判断就漏掉了一种情况：一个集合和一个整体相交，并且包含所有整体中都不包含的元素，这样的集合同样可以加入进来。为了解决这个问题，可以设 BI表示当前所有整体中有多少元素被集合 I 包含，那么如果 Bi0，而且 Bi小于集合 i 的大小就可以判断这种情况了。而计算 Bi的复杂度最多为 O(MN)，即所有整体中每增加一个元素，就刷新一次 B 数组。那么现在很明显，如果能确定 C 数组，其他工作的复杂度就不会超过 O(MN )了。那么，C 数组的求解就是问题的关键了，关于 C 的一般算法的求解复杂度为 O(MN 2)，也就是每次得到一个新的整体，都

8、去刷新 C。但是这里显然很多可以优化的地方，首先看看整体是如何增加的，整体的增加只有两种情况：第一种情况：加入若干新的元素形成一个整体，如下图的整体 1。这种情况下刷新 C 的总复杂度为 O(NM)，没有优化的必要。第二种情况：一个整体被划分为两个整体，如上图中，整体 2 被划分为整体 3，4。这种情况的总复杂度可能达到 O(MN 2)，看来主要要优化这个部分。下面分析：假设被划分的整体为 x，被划分为 y，z 两个整体。而这个时候只需考虑计算被整体x 包含的集合的 C 值，计算其他的集合的 C 值没有意义（要么 C 值已经大于 1，要么与 x 不相交）。那么，对于包含的集合 i，如何算呢？会

9、判断，集合在 y 中是否有元素，在 z中是否有元素，那么这就需要将整个 x 中元素一遍，显然很浪费。那么如果已经知道了集合 i 在 y 中的元素数目，那么就可以直截算出集合包含 z 中元素的数目了，因为它们之和为 Bi，反之亦然。那么每次只需要其中一个整体就可以得到 Ci了，而要肯定包含元素少的那个整体了。那么通过这个优化，复杂度是否有改观呢？可以证明，再此优化下，计算 C 的总时间复杂度降为了 O(MNlogN)。为什么？因为假设每次将一整体分为两个都需要刷新 Ci，而每次计算 Ci只需两个分成整体中小的一个中的元素，这NlogN 个元素，所有的整体的大小都样将整体一直分割下去，可以证明最多只需只有 1 了。这个结论可通过归纳证明：fn aa logab log log( a *bN* 2 ) log（n *) lognfb blog bbfa alog aa图中每条线段表示一个整体，蓝色线段表示被的整体，fi 表示 i 长度的整体，在以后无论如何分解中，上述算法最多被的元素总数。看上图，假设将长度为 N 的整体划分为长度分别为 a, bT12345T123的整体，那么通过归纳可证明 f N 不大于 nlogn。综上，一个集