信息学集训队作业poi.xiii sol

1、XIII Polish Olympiad in Informatics 2005/2006 SolutionsStage I2The Disks (kra)2Periods of Words (okr)3Professor Szu (pro)3Tetris 3D (tet)4(zab)5Stage II5Schools (szk)5Warehouse (mag)6Subway (met)7The Inva(naj)8Thetman (lis)8Ploughing (ork)9Stage III10Aesthetic Text (est)10Crystal (kry)11Palindromes

2、(pal)11Dancing in Circles (tan)12Sophie (zos)12Teddies (mis)13Stage IThe Disks (kra)Description翻译简述有一个各高度半径不同的空心 Tube，依次扔一些实心圆盘，求每个圆盘在何处停止。Solution解法一：首先需要明确一个事实，那就是：如果一个盘在在第 i 层的时候被卡住了，那么它就不会掉到第 i+1 层。这个看起来很显然的事实为的解题提供了条件。设开始时每个圆柱的半径分别为 R1 至 Rn，则 NewRi=minRj|ji。对于第一个扔下的盘子，设它的半径为 R0 它最后停住的位置一定是一个最大的

3、 k，同时满足 NewRkR0，这一步可以通过简单的二分查找完成。而对于以后的盘子，因为它们停住的位置必须比上一个盘子的位置高，因此只需用上一个盘子停住的位置作为二分查找的半径就可以了。综上，解法二：只需进行 M 次二分查找就可以解决这道问题，时间复杂度为 O(MlogN)。tube 凸出来的部分是没用的，所以可以直接切掉（就是如果比上面那个还长，就让它和上面的一样长）。于是每次放东西的时候从后向前扫描就行了。时间复杂度：O(n + m)。Periods of Words (okr)Description翻译简述给一个串，求它的所有前缀的最长重复子串长度之和。Solution如果 Q 是 A

4、的适当前缀（不为空也不为 A）且 A 是的前缀（不需要适当），则称 Q是 A 的 period。这等价于 A 除去前面的 Q（得到 A 的某个后缀）恰好是 A 的前缀，也就是这个后缀与 A 的最长公共前缀就是它本身。回到原题，首先求出从每个后缀和原串的最长公共前缀（扩展 KMP 算法），然后枚举 A（题目要求出这个字符串的所有前缀 A 的最长 period 的长度和），这个 A 的最长 period 长度就是最大的满足的 lcpi+1+i|A|的 i。从前到后枚举 A，在求解的过程中用栈以了。时间复杂度：O(k)。lcpi就可Professor Szu (pro)Description翻译简述

5、给有向图，可能有重边和自环。其中一个点是主楼，其他点是别墅。选一个别墅使得它到主楼的不同道路个数尽量多。一个点可以经过多次（包括主楼）。如果有多解输出全部。如果解超过 36500 则认为是无穷大。Solution先求强连通分量，如果有的话输出”zawsze”，输出所有能到这个分量的点（包括分量内的点）。如果没有，就是简单的动态规划。可以考虑这样一个问题：你最少需要把图遍历几遍？用什么样的求 SCC 的方法？时间复杂度：O(n+m)。Tetris 3D (tet)Description翻译简述模拟一些长方体的下落，计算最后的高度。Solution这是一道数据结构题。经过简单分析后不难发现，题目要

6、求够高效的完成下列两种操作：查询一个矩形区域中的最大值。将一个矩形区域中所有元素的值设为 k。设计一种数据结构，能这两种操作正是线段树的强项，因此，首先会想到使用线段树。不妨先来看看一维时的情况。一维的时候比较简单，对于线段树上的每个节点，纪录一个变量 same 和一个整数 key，表示这段中的每个点的值是否都相同和如果都相同时每个点的值。同时还需要max 表示这段中所有点的最大值。具体的操作过程比较简单，这里不再多说，可以参考各种有关选段树的资料。二维时，首先将行二分，得到 2N 个行线段，每个行线段对应一个 k*N 的矩形。而这些行线段中每个都着一颗一维的线段树，当然，这是通过对列二分得到

7、的。如果没有第二个操作，这样的线段树就足以满足要求了。但是，加上第二个操作应该怎么办呢？在一维时，为了能够满足要求，加上了 same 和 key 这两个变量。而现在，只需要对每个行线段再加上一颗一维线段树 C 即可。C 中样就可以了。的是完整覆盖 该行线段中的最大值。这显然，每次操作的时间复杂度都是 O(logd*logs)，因此，总的时间复杂度是 O(q*logd*logs)。 (zab)Description翻译简述在田里放一些吓唬青蛙的 scarefrog，给青蛙计算一条从 A 到 B 的路径，使得离最近的scarefrog 尽量远。Solution先求出所有点的 scare dista

8、ne （ 到距它最近的 scarefrog 的距离）， 就可以在O(wxwylog(wxwy)或 O(wx2+wy )的时间内求出2法，后者是由类似 prim 算法的桶实现达到的）。hold distance 了（二分或者类似 prim 的算如何预处理所有的点的 scare distance 呢？其实只需要一行一行扫描就可以了。在处理每行的时候，每列上其实只有一个 scarefrog 在起作用。所以要考虑的 scare frog 至多 wy 个。这些 scare frog 的作用范围是单调的，所以只要一个决策序列就可以了。所以求解每行的时间为 O(wy)。求解完一行要求解下一行的时候，更新最近

9、的 scare frog 也是 O(wy)的。所以这一步总的时间复杂度是 O(wxwy)。时间复杂度：O(wxwylog(wxwy)或 O(wx2+wy )。2Stage IISchools (szk)Description翻译简述给出 n 个 1n 之间的整数，把它变成 1n 的排列。每个新数 mi必须在区间ai bi内，改变费用为 ki|mi-mi|，其中 mi 为第 i 个数原来的值。Solution二分图最小权匹配，可以用 KM 算法。时间复杂度：O(n3)。Warehouse (mag)Description翻译简述网格上有n 个shop，每个 shop 需要经过ti 次。寻找一个

10、warehouse 使得总路程尽量小。只能沿着网格走。Solution首先可以证明 max|a|, |b| = (|a + b| + |a - b|) / 2. 于是有：|xi + yi x y| + |xi yi x + y| y| =max|x x|, |yii2xi + yix + yxi yix y= | + |2222求出(xi+yi)/2 和(xi-yi)/2 的中位数,分别作为(x+y)/2 和(x-y)/2。但为了保证 x 和 y 都是整数，必须保证它们的奇偶性一致。如果奇偶性不同，那么只要对其中的一个加 1 或减 1 就行了，找使得总距离增加最小的一种改变方案。时间复杂度:：

11、O(n)。Subway (met)Description翻译简述给一棵树，用 L 条无公共点的路径覆盖尽量多的结点。Solution解法一：首先证明，这些轨道了一颗树。如果两个轨道没有公共点，那么可以找一条路连接这两个轨道，然后交换两部分，就得到了两条新轨道，并且覆盖的点数都经过那条路）。那么什么样的树对应有可行解？是所有拥有不超过 2l 个叶子节点的树。因为可以选 2l 个点配对组成 l 条轨道，然后通过上面的调整得到这棵树。然后可以证明，存在一个包含任意一条最长链的端点的最优解。任何最优解一定和最长链有公共点。考虑最长链上最末端的未被覆盖的部分。显然，可以把一条轨道的末端交换到这里，解不会

12、变坏。于是就证明了结论。这样，将任意一条最长链的某个端点作为根，问题转化为：求出从根出发的不超过 2l-1条路，使得经过的总点数最多。很容易设计出这个问题的贪心算法：每次找一条最深的路径，然后将其收缩。正确性的证明也很容易。这个方法是 O(n + l*log n)的。其实还有更好的方法，并且本该在想到刚才的方法之前想到：每次删去一条最短的叶链。正确性证明比刚才的还要直接。用桶来时间复杂度为 O(n)。叶链，就可以做到 O(n+n-2l)。解法二：这道题目要求用 L 条链去覆盖尽量多的点。如果 L=1 时显然是求树上的最长链。但是，如果 L1 时应该怎么办呢？首先求出树中所有的叶子节点，然后将它

13、们全部删除，得到一颗新树T1，再将新树中的叶子节点全部删除，得到树 T2如此重复下去，直到第 k 次得到的树 Tk 中只有 1 个或 2 个节点，此时停止。因为只有 L 条链，所以在每层最多只能选 2L 个点。这样，我们只需要统计每层删去的叶子节点的个数，并与 2L 求最小值，最后在求一次和就可以了。整个算法的时间复杂度为 O(N)。The Inva (naj)Description翻译简述在 n 个顶点中选出三个组成三角形，使得三角形内的 factory 权和尽量大。每个 factory可负。的Solution设 si, j为多边形上从 i 到j 的部分和线段 ij 围成的这部分内的点的权和

14、，则-minsi, j+sj, k+sk, i。为total求si时，可以先把所有的点按照极角排序，然后扫描。这样做的总时间复杂度是O(nmlog m+n3)的。其实可以做的更好：对每个点，只要知道它会被计入哪些 si, j即可。枚举 i，用 j来扫描，这是可以做到 O(nm)的。时间复杂度：O(nm+n3)。The tman (lis)Description翻译简述给有向图，求一条从 1 开始到 1 结束的告不存在。回路，包含一些给定的连续顶点序列，或报Solution首先将序列合并，之后，对于一条v1，v2，vk 的序列，其中所有的边删去，并添加一条新边 v1- vk，并在新图上求回路，最

15、后将边展开即可。实现的时候也可以每条边的后续边，如果某条边有后续边，就必须沿后继边继续走下去，这也巧妙解决了路径部分重复。Ploughing (ork)Description翻译简述给一个 n*m 网格，每个格子有个非负整数。每次切下一个宽度为 1 的 slice，里面的数之和不得超过 k。每次切完后剩下的部分仍应是个矩形。要求切成尽量少的 slice。Solution容易发现, 最小化条数就是最大化最后一条的长度. 不妨假设最后一条是横向的.解法一：思路是这样的，枚举这个最后一条的左边界后，它的右边界最右可以到哪里呢？是，得保证棋盘上左右边界之间的部分只用横着切就能切完。但这样还是可能导致解

16、不合法。因为可能会中途遇到这种情况，从左边切到左边界了，也不能从上面、下面、右边切了。（当然，这个时候肯定没有从右边切到右边界）。所以，还必须可以通过从上面，下面，右边切的方法切到右边界。由于可以只从上面，下面切切完左右边界之间的部分，所以一定必须可以从上面、下面、右边切，切掉左边界到最右边的部分。同理，也必须可以从上面、下面、左边切，切掉最左边到右边界之间的部分。显然，这三个条件同时满足时，这一定是个合法方案。于是算法分两步：求出左右边界的取值范围，再在这个范围内求出最长的合法解。第一步是比较难以描述的队列、栈，要注意到切割时的特点。复杂度是 O(nm)的。第二部比较容易，就是简单的队列，复

17、杂度也是 O(nm)。最后一条是纵向的时候，用类似的方法也可求出。时间复杂度：O(nm)。解法二：枚举左边界，然后开始切，切的时候从左边切不能竖着切过左边界，然后如果能从上面、下面、左面切就切、再从右边切。时间复杂度：O(n+m)2)。Stage IIIAesthetic Text (est)Description翻译简述把 n 个单词分成若干行，每行的各个单词由一个空格隔开，要求相邻两行长度差的绝对值之和 sum|Li-Li+1|尽量小。其中 Li 为第 i 行的长度（即所有单词长度和加上单词的个数减 1）。Solution本题可以用单调性来解决，但是思考数小的算法：都十分麻烦，这里介绍一个

18、复杂度相同，常很明显此题是 DP，可以用 fij表示最后一行为第单词 i 到 j 时的最小值。但是由于绝对值的存在，以及优化的必要，还需要gtij和 ltij，分别表示前 j 个单词，最后一行第一个单词下标不大于/不小于 i 的最小值。这样，在按照 i 从小到大的顺序求 fij的时候，当前行长度 len 在不断减小（可以根据事先求出的前缀和数组 s得出），一个指针 k，使得单词 k 到 i-1 的长度大于 len，单词 k+1 到i-1 的长度不大于 len，分别用 gtki-1和 ltk+1i-1更新 fij。于是得到了个很方便实现的 O(n2)的算法。Crystal (kry)Descri

19、ption翻译简述Solution考虑最（假设是第 s 位）。如果有些数的这一位是 1，那么这些数两个选择，这一位变还是不变。如果这一位变，那么它后面的部分就可以任意取了。由于要保证 xor 为0，所以只能有偶数个不变。下面的均在这个前提下。假k0 个变了，这样的方案个数是可以直接求出来的。因为只要其它的数后面的部分任意取，这 k 个数中前 k-1 个数任意取，那么第 k 个数恰有一种取值可以让 xor 为 0。如果设 sumxy为前 y 个数中选了 x 个不变（包括第 s 位为 0 的），这 x 个不变的数的后面部分任意选取的方案数。那么有 k 个改变的方案个数就是sumn-kn*2(k-1

20、)(s-1)*sum 可以在 O(n2)时间内求出，枚举所有的合法的 k，就可以求出有数改变的情况下解的个数。其实可以只分奇偶性而不分选出的不变的个数，就可以做到 O(n)，只不过由于可能超出整数范围，所以实现上不够方便。假如都不变，就可以忽略这一位，处理它的子问题。时间复杂度为 O(nb)或 O(n2b)。Palindromes (pal)Description翻译简述给 n 个回文词，两两拼接的方法有 n2 种。其中有多少种的拼接结果也是回文词？Solution求出每个串的循环节（用 KMP 算法）。当且仅当两个串的循环节相同时它们的连接才会成为回文串。于是给所有的循环节排序（用 trie

21、 或别的方法）就可以了。使用 trie 时注意空间限制，要合理分配 trie 的分支数，另外注意，如果申请 127MB 内存，实际上会使用 132MB（这就 MLE 了），可能是程序为了内存管理使用了附加空间。最好的方法是排序而不是用 trie，虽然 trie 理论复杂度为 O(n)看上去更优，其实 trie 不但容易 MLE，TLE 也是瞬间的事情。排序实际效果非常不错。Dancing in Circles (tan)Description翻译简述SolutionSophie (zos)Description翻译简述Solution独立集的补集是点覆盖，因此求出最大独立集就是要求出最小点覆盖。假设 X 为一个最小点覆盖集，则它的补集 Y 为一个最大独立集。考虑每次从原图中随意取一条边，将这个边的两个端点加入集合 X，再删去所有与这两个点关联的边，重