集训队作业解题报告

1、IOI2010国家集训队冬令营自编试题 解题报告PAGE PAGE 10珠链分割 解题报告命题人: 南京师范大学附属中学 汪一宁antoniowyn目录： TOC o 1-2 h z u HYPERLINK l _Toc251182945 一、试题大意 PAGEREF _Toc251182945 h 1 HYPERLINK l _Toc251182946 二、命题思路与考察要点 PAGEREF _Toc251182946 h 1 HYPERLINK l _Toc251182947 三、算法讨论 PAGEREF _Toc251182947 h 2 HYPERLINK l _Toc25118294

2、8 1、搜索算法 PAGEREF _Toc251182948 h 2 HYPERLINK l _Toc251182949 2、初步算法 PAGEREF _Toc251182949 h 2 HYPERLINK l _Toc251182950 3、改进算法1 PAGEREF _Toc251182950 h 5 HYPERLINK l _Toc251182951 4、改进算法2 PAGEREF _Toc251182951 h 6 HYPERLINK l _Toc251182952 5、标准算法 PAGEREF _Toc251182952 h 8 HYPERLINK l _Toc251182953 四

3、、数据设计与参考程序 PAGEREF _Toc251182953 h 10 HYPERLINK l _Toc251182954 五、感谢 PAGEREF _Toc251182954 h 10试题大意 给出一个个节点和条边的顶点加权无向连通图（显然图中有且仅有一个环）。首先去掉若干条边将这个图分割成个互不相交的连通子图，然后选择其中的一个连通子图，将该子图中所有位于环上的顶点的权值平方。如果我们定义每一个连通子图的分数为该连通子图中所有顶点权值之和，试最大化这个连通分量分数的最小值，并返回该最大化的最小值。所有的顶点权值都是正的。命题思路与考察要点 本题受到NOI2003试题草莓的启发，并进行了

4、一定的加强（允许事后对特定的顶点的权值进行平方操作）。通过笔者的细致思考，成功地设计出了在环上进行判定计算的算法和算法，从而将问题的解决范围从原题中的树扩展到了基环外向树，并且不改变的算法复杂度。 事实上，就本题而言，对于更加广泛的一类图仙人掌图（i.e. 每一个顶点最多属于一个环），仍然可以设计出甚至的算法。但是由于这样的算法过于复杂，已经超过了NOI水平的难度，所以没有将这些算法在本题中展示出来。 解决本题的基础是掌握二分算法（参数搜索）的基本原理，并且对于本题的判定性命题，在树上和环上均能够设计出正确的贪心算法。但是，要想更好地解决本题，选手需要熟悉倍增思想并且将其熟练地运用至环上的计算

5、中。最后，完整地解决本题，需要深入挖掘隐藏在试题背后的若干性质，并巧妙地通过抽屉原理指出最佳算法的时间复杂度。算法讨论1、搜索算法时间复杂度：空间复杂度：期望得分：10算法介绍： 搜索算法直接模拟题意，首先枚举哪些边需要被删掉，然后通过DFS找出所有连通子图，然后将权值之和最小的那个连通子图的环上顶点的权值平方。枚举所有的方案，选择最佳方案。算法的时间复杂度过高，只能得到10分。2、初步算法时间复杂度：空间复杂度：期望得分：40算法介绍： 首先，我们可以二分答案，从而将原问题转化为其判定性问题：给出参数，最多能将原图划分成多少个互不相交的连通子图，使得在选择一个连通子图平方之后每一个连通子图的

6、顶点的权值之和都不小于。如果这个值不小于，则说明成立，反之说明不成立。 环上的问题比较复杂，我们先考虑解决树上的问题。那么我们需要解决的问题就是：给出一个根顶点是的树，最多能将这棵树划分成几个连通子图，使得每一个连通子图的顶点的权值之和都不小于。 为了方便表述，我们定义返回一个二元组，其中表示以为根的子树最多可以划分出多少个连通子图，表示在划分出的连通子图数量为的前提下，所余下的与相连的顶点的权值之和的最大可能值。设顶点的个孩子分别是，顶点的权值为，我们可以证明下列两式成立： (1) (2) 其中，证明：我们尝试使用归纳法证明上面两式。（归纳奠基）如果顶点没有孩子，则显然我们有，。（归纳递推）

7、对于顶点来说，根据归纳假设，对于以的任何孩子为根所构成的子树最多能且可以分割出个连通子图，因此必然有。如果以某一个孩子为根的子树所划分出的连通子图的数量不足，则此时以为根的子树划分出来的子树的数量不超过，而且要取到这一值必须将顶点独立成为一个连通子图，所以此时余下的权值和为0。不难发现此时取到它的下界，因此肯定无必要。故我们可以断言对于顶点的每一个孩子，以之为根的子树划分出来的连通子图个数必为。在此基础上，根据归纳假设，与顶点相连接的尚没有被划分入任何一个连通子图的顶点的权值和至多为而且此值可以取到。如果，则这些顶点不能够形成一个独立的连通子图。根据函数定义，显然有，。如果，根据函数定义，我们

8、需要把这一连通子图独立出来，而且我们只能够独立出一个连通子图（因为这些顶点必须要通过连接），故此时我们有，。 （证毕） 通过(1)，(2)两式，我们可以在的时间内完成树上的计算。现在我们回到“基环”上。根据题意，我们可以给环上的每一个顶点设置两个新的权值：， 。其中，代表顶点的不在环上的孩子。表示没有平方的连通子图中顶点实际构成的权值之和，表示进行平方的连通子图中顶点实际构成的权值之和。求出环上的最多可能连通子图的个数，再加上外向树中分离出来的所有连通子图，如果总数不低于则说明下限可以被达到，否则说明下限不能被达到。 我们枚举被平方的片段的起始位置，然后绕环进行统计。一旦发现当前顶点的权值之和

9、不小于，就立刻将这一段分离出来，构成一个独立的连通子图。换言之，如果我们用表示从起始顶点到顶点的这个片段上，最多可以划分出个连通子图，并且在划分出个连通子图的前提下，剩余的顶点权值之和最大为。假如顶点在环上的前驱顶点为，我们有如下两式成立： (3) (4) 其中，表示顶点实际产生的权值，即。我们将这个环从起始位置前面断开，将剩下的链看作一颗特殊的树，不难发现(3), (4)两式与(1), (2)两式是一致的。 根据(3), (4)两式，在给定起点的前提下我们可以在的时间内完成一次扫描。故一次判断的时间复杂度为，总时间复杂度为。 算法的框架如下所示： Algorithm 1: 初步算法（判定过程

10、） Input: 一个无向连通图G，顶点数与边数均为N 每个顶点的权值Vv 一个整数L，表示每个连通子图的权值之和的最小值。 Output: 一个整数，表示G最多可以划分成多少个连通子图，满足L的限制。 Time Complexity: O(N2) Space Complexity: O(N) Procedure:通过DFS或者BFS找出图中的基环。对于基环上的每一个顶点引出的外向树，通过(1)式和(2)式计算f(v)，并用其更新uv和sv。同时，记外向树中分离出来的子图的数量为bas当前最佳值Best = 0Foreach StV on the circle Do 遍历环，通过(3)式和(4

11、)式确定环上所有点的g(v)的值。 Best = MAX(Best,g(lastStV)End ForReturn Best+bas3、改进算法1时间复杂度：空间复杂度：期望得分：60算法介绍： 在初步算法中，我们在的时间内完成了树上的计算（如果下面不特别指出，均指判定问题），的时间内完成了环上的计算。可见，我们优化的重点在于环上。 仔细考察环上计算公式(2)和(3)，我们发现，如果我们事先对于每一个环上的顶点，都能够求出从这个顶点开始至少经过多少个顶点才能够形成一个连通子图，则问题的求解会非常方便。我们只需要枚举需要平方的片段的起点，然后按照预处理的结果一个一个连通子图走下去，直到长度之和超

12、过环的总长度终止。此时得到的片段总数就是最多可以得到的子图总数，一次扫描的时间复杂度降为。 假设分别表示在未平方、平方的情况下，从顶点出发，至少经过多少个后继顶点，才可以形成一个独立的连通子图。表示顶点的后继顶点，表示从开始需要多少个后继顶点才能到（包括），并设。这些信息都可以通过对环上顶点按照一个方向重编号预处理得到。 通过下述算法，我们可以在的时间内预处理出这两个值。 Algorithm 2: UL和SL的预处理过程 Input: 一个环G，以及环上顶点的实际权值uv和sv 一个整数L，表示每个连通子图的权值之和的最小值。 一个顶点StV，表示起始顶点。可以是环上的任意一个顶点。 Outp

13、ut: 两个数组，UL和SL，定义如上文所述。 Time Complexity: O(N) Space Complexity: O(N) Procedure:当前无平方和sum1 = uStV，有平方和sum2 = sStV当前指针p = StV, 无平方终止指针j1 = StV，有平方终止指针j2 = StVDo While sum1L Do j1 = lastj1; sum1 += uj1; While sum2L Do j2 = lastj2; sum2 += sj2; ULp = Dist(p, j1); SLp = Dist(p, j2); Sum1 -= up; sum2 -= s

14、p; p = lastp;End While (p != StV) 需要注意的是，一旦我们发现某一个片断需要的顶点个数超过环上顶点的总数，则立刻可以通过特殊判断退出本次判定过程，从而不至于使时间在这种特殊情况下恶化。 然后，我们可以在的时间内完成环上的计算。设环的总长度为，算法框架如下： Algorithm 3: 改进算法1中环上的计算。 Input: 一个环G 通过预处理得到的UL和SL Output: 一个整数，表示环G最多可以被划分成多少个连通子图。 Time Complexity: O(NK) Space Complexity: O(N) Procedure:当前最佳值Best = 0

15、Foreach v on the circle Do 当前长度NowLeng = SLv 当前连通子图个数Count = 1 当前顶点指针p = lastSLv+1v While NowLeng TotalLeng Then ULsvk = +infinity End ForEnd For 然后，对于询问“从一个顶点开始，走过多少个连通子图达到长度上限”，我们不再需要像改进算法1那样一个一个走过去，而是可以利用我们已经计算出来的ULs数组在时间内完成。具体的算法框架如下图所示： Algorithm 5: 改进算法2的环上的计算过程 Input: 一个环G 通过预处理得到的ULs数组 Outpu

16、t: 一个整数，表示环G最多可以被划分成多少个连通子图。 Time Complexity: O(NlogK) Space Complexity: O(NlogK) Procedure:当前最佳解Best = 0Foreach v on the circle Do 当前长度NowLeng = SLv 当前连通子图个数Count = 1 当前顶点指针p = lastSLv+1v For k log2K downto 0 Do If NowLeng + ULspk = TotalLeng Then NowLeng += ULspk Count += 2k p = lastULspk+1p End I

17、f End For Best = MAX(Best, Count)End ForReturn Best5、标准算法时间复杂度：空间复杂度：期望得分：100算法介绍： 为了更高效地解决本题，我们需要挖掘环上判定过程的一些性质。 对于给定的顶点权值和下限以及环来说，我们忽略平方的操作，并且任取一个环上的顶点进行一次扫描（下文中称这次扫描为粗扫描过程），并记录下这次扫描划分出来的连通子图的个数，以及扫描得到的方案。 Algorithm 6: 粗扫描过程 Input: 一个环G，及环上顶点的个数TotalLeng 由预处理得到的UL数组。 Output: 一个整数S，表示此次扫描过程划分出来的连通子图

18、的个数。 以及扫描得到的方案。 Time Complexity: O(S) Space Complexity: O(N) Procedure:分离出来的连通子图的个数Count = 0当前顶点指针p = StV当前长度NowLeng = 0While NowLeng = TotalLeng Do Count + NowLeng += ULp p = lastULp+1pEnd WhileReturn Count-1 此次扫描过程中，我们得到了一个答案。假设这个环的实际答案应该是，显然一定成立。那么，在和之间，究竟还存在什么微妙的联系呢？为此，我们需要深入分析问题中的一些性质。 性质1：对于至少

19、一个粗扫描过程中得到的连通子图，在最终的答案中这个连通子图的所有顶点分属至多3个不同的连通子图。证明：我们选择在初扫描过程中划分出来的权值和最小的连通子图，根据粗扫描过程的流程，这个连通子图中去掉任何一个顶点剩下顶点的权值和都不足。如果最终答案中这个连通子图的所有顶点分属4个不同的连通子图，则至少有两个新的不同的连通子图仅包含部分原来这个连通子图中的顶点，因此至少有两个新的不同的连通子图的顶点权值和小于。由于我们只能选择一个连通子图将其中的所有顶点权值平方，因此至少有一个连通子图的权值和小于，故这样的方案是不存在的。（证毕）性质2：证明：选择满足性质1的那个粗扫描过程中得到的连通子图，将这个连

20、通子图里面的所有的不同连通子图合并，则我们至多损失2个连通子图。合并之后的方案显然能够通过粗扫描过程得到，因此我们有，即。 （证毕）性质3：在粗扫描过程得到的个连通子图中，一定存在一个连通子图，使得该子图中顶点的个数不超过。证明：这实际上是抽屉原理的直接应用。如果原命题不成立，则这个连通子图的顶点总数将超过个，这显然是不可能的。 （证毕） 现在，根据上述三个性质，我们在执行过粗扫描过程的基础上设计另外一个扫描算法（细扫描过程），以得出最优解。首先，我们通过改进算法1中的预处理过程计算出数组。同时，使用同样的技术，我们也计算出数组，表示从顶点开始沿着向后走，形成一个没有进行平方的连通子图，至少需

21、要通过的顶点数。然后，我们尝试枚举第一个连通子图的第一个顶点。显然我们只需要枚举粗扫描过程中顶点个数最少的连通子图中的所有顶点即可。根据性质3，这样的顶点个数为。 通过下述算法，我们可以在的时间内确定某个解答（在最佳方案中连通子图的个数）是否可行。 Algorithm 7: 细扫描过程 Input: 一个环G 通过预处理得到的UL, SL, NL数组 第一个连通子图的开始顶点v 需要检查可行性的解答T Output: Yes/No，表示解答T是否可行。 Time Complexity: O(T) Space Complexity: O(N) Procedure:当前连通子图的个数Count =

22、 1当前总长度NowLeng = SLv当前顶点指针p = lastSLv+1vWhile Nowleng = TotalLeng Do If NowLeng + NLsT-Countnextv = TotalLeng Then Return Yes NowLeng += ULp Count + p = lastULp+1pEnd WhileReturn No 其中，表示从顶点开始走过个连通子图所需要的长度。由于始终是固定的，故这个数组可以在细扫描之前通过预处理轻易地得到。 根据性质2，我们只需要检查和这两种情况是否成立即可。故一次判定过程总的时间复杂度为，故算法总的时间复杂度为，可以得到100分，为本题的标程算法。数据设计与参考程序 本题的数据设计的原则是不针对任何一种非完美算法设计反制数据，但也不允许任何一种完美算法得到太高的分数甚至满分。基于此，我采用了随机数据为主、人为设置图的参数的方法生成数据。对于全部10个数据中顶点的权值均采用随机数据，而对于前5个用A模式输入的图的结构，我