信息学国家集训队作业sgu

1、IOI2004 中国国家集训队第一轮训练泛做表格SGU请大家尽量仔细的填写下列表格。基本要求是自己越的题目应该写得越多。如果觉得没什么意思就只写算法大意（一两行即可）和时空性能。的题目不用太多，否则就没有比较意义了。加红的是我比较想得也不深入，可能会有错误的的题目，可以先看，不过由于看得并不是很仔细，或者漏掉好题，只是起到一个参考作用。请注意：如果题目没什么新意一定不要在程度里加五星。凡是有加五星的都代表有一定的闪光点。需要剪切的，这里提供一堆：）题目名称题目和简要算法描述时空性能程度题目评价106The equation问题简述：求方程 ax + by + c = 0 在 x1xx2，y1y

2、y2 范围内的整数解个数。算法：方法不难想到，小错误却很多。1、判断如下三种特例： a=0&b=0、a=0、b=0 2、保证 b0，如果 b0 与 a0两种情况，通过 y1、y2，对 x 的范围 x1x2 进一步缩小。3、把 a、b、c 的最大公约数约去，求 ax+c=0(mod b)在 x1x2 范围内的整数解个数即可。时间复杂度：O(1)空间复杂度：O(1)比较繁琐，很多特殊情况和情况需要考虑，还有精度误差需要处理。虽然了选手的细心程度，却未能体现任何算法技巧。107987654321problem问题简述：给定 n ， 求平方末尾为 987654321 的 n 位数个数。算法：用数学方法

3、或编程序可以算出 n=9 时有 8 个解，那数据量：1n106时间复杂度：O(n)空间复杂度：O(1)刚看题可能因为数据量之大，而感到盲目无从下手。仔细分析一下可以发么 n=10 时有 72(=89)个， n=11 时有 720 个，以后 n每增加 1，解数就乘以 10。现最后 9 位仅和原数的后 9位有关。108Self-numbers问题简述：定义 d(n)为 n 加上 n 的所有数位之和。如 d(37)= 37+ 3+7。如果一个数 x 不能通过 d(n)计算得出，那么称之为 Self-number。如 1、3、 5、7、9 都是Self-number。求区间范围1,N 内的第 s1.s

4、k 个Self-number。算法：很容易想到模拟的办法，用哈希表从 1.N 生成。对每一个数 i，将 hashd(i)置为true。那么剩下的false就是 Self-number。时间勉强保证了，但是空间占用实在太大。注意在给 定 数 据 范 围 内 ， d(n)-n100，因此可以用长度为 100 的数组进行循环滚动。数据量：1 N 107,1 K 5000时间复杂度：O(NlgN)空间复杂度：O(10lgN)至少本题在我使用算法的层面上，是没有任何新意的，一切都是基础的算法和 。不知道能否得到改进？109of David Copperfield II问题简述：给定 NN 的棋盘，所有格

5、子被依次1NN。初始时候，有一位观众把手指放在左上角的格子1 中。魔术师每次要求他任意移动 K（KN）步（每步走到相邻的 4 格之一，魔术师无法看到他实际的路线，只知道 K）。之后魔术师将若干的格子删去，并且确保观众指此时不在这些格子中。然后魔术师再提出 K（可能与上次不同），并且再删去一些格子最后，只剩下一个格子，并且观众指在上面。给定 N，求一个可行的魔术师的方案。数据量：1 N 2 时，先走 N 步，然后以副对角线(右上到左下)为分界线将右下部分去掉，以后每次走奇数步并且去掉最靠右下的那一斜行，最后只剩第一个格子。114ecastingSion问题简述：在一 轴上，存在 N个整点 X1X

6、N，每个点上有一定数量的居民。要求在 该 轴 上 建 立 一 个 TV-s ion，使得所有人到达 TV-s ion 的距离和尽可能小。算法：易证 TV-sion 一定设在城市中，并且一定在最中间一个人的所在城市。 这题的城市坐标为整数且上限才 50000，可以用计数排序 (hash sort) ，枚举 150000，即可找到人数的中点。数据量：0 N 15000,0 X 1 则必有一条路穿过该节点，所以问题解决了。反例只有一种，即图本身就是一个环且节点数为奇数，这样就无解了。122The book问题简述：N 个点组成无向图，每个点至少(N+1)/2条边，要求找到一个圈。 解的存在性：首先易

7、证图是连通的。 用贪心法找到一条极长路，设为a1,a2,ak。 因为是极长路，所以 a1 的邻节点，全部在 a1ak 中， ak 也是如此。易证存在 ai(1ik)使 ai 与 ak 相连且 ai+1 与 a1 相连，再连 a1-ai+1 与 ai-ak，使 ai与 ai+1 断开，则这条路变成了一个环。由于图是连通的，从这个环的某处断开必能找到一个更长的极长路，就这样反复找下去，最后那个最大的环就是该图的圈。因此，问题一定有解。算法：如果按照前面的方法构造，程序复杂度势必过大。这 里 可 以 采 用 类 似 ctsc2003-100book-Airport 的贪心策略，从节点 1 开始，每次

8、连找到一个度数最小的点与之相连。其正确性的证明可以使用反证法，也和Airport 类似，限于篇幅这里从略。数据量：2 N 1000时间复杂度：O(N2)空间复杂度：O(N2)如果在 OI 考场上遇到此题，贪心策略并不难想到，要大胆地使用。该贪心的证明过程不会简单，但是直觉效应很强，直观上能够给人以自信。本题真正严格完整的证明，估计是一篇优秀的学术 了。125Shtirlits问题简述：NN（N3）的每个格子里时间复杂度：O(99)可能因为 我未 将本题 的都有一个 19 的数（可能相 同 ） ， 称 之 为 A1.N1.N 数组。而 B1.N1.N 数组 了每一个格子周围比其大的数的个数。给定

9、 B 数组，求一个可行的 A 数组。算法：局部可以进行贪心（如 Bij=0，那么显然可以让 Aij取最大的数），但是最终难逃搜索的魔爪。 幸好 N 的限制较小，加上剪枝能力较大，因此简单的深度搜索即可胜任。空间复杂度：O(N2)注：实际效果非常好，程序速度非常快。条件完全利用，最终没能得到一个较好的解法。不知道能否利用不等式的知识，解出一 组 可 行解？126Boxes问题简述：有两个盒子，分别有 A 和 B 个球。每次只能从球数较多的盒子里，拿出与另一个盒子里相同数量的球，放入另一个盒子。给定 A,B，问最终能否将所有球放入一个盒子，如果可以，需要多少步。算法： 逆推分析0 168 812

10、4/6 1014 2/3 1311 57 915 1分析得出，每往下分一层，就会丢失一个因子 2。因此如果有解，在很少的次数内，就可以完成任务，模拟即可。进一步应该可以找出通式，我这里就没有找下去了。数据量：0A+B2147483648时间复杂度：O(log2N)空间复杂度：O(1)刚开始会被一种又一种的死循环状态困扰，算法不会脱离hash判重，或许那样程序也能实现。但是只要稍加思考，对问题进行逆向思考，眼前豁然开朗！以后要经常使用这样的克朗代克式思维。130Circle问题简述：圆上 2k 个点，连 k 条线，数据量：1 k 30题目的描述有些绕，会让每个点只能连一次，问将圆划分成最少部分的

11、方案总数。算法：显然最少把圆分成k+1 块。关键是对于方法数的计算。假设第 1 个点，连接第 b个点，那么圆被分成了两个子部分因此可以用递推实现。时间复杂度：O(k2)空间复杂度：O(k) 部分人陷入误区，真正的算法构造并不 。132Another Chocolate Maniac问题简述：MN 的棋盘上，有一些格子被挖去。在其中放置 12或 21 的小块，问最少需要放置多少个，才能保证剩下的图中不存在两个相邻的空位（不能再放） 算法状态表示： minijk 表示考虑前 i行，第 i-1 和第 i 行的覆盖情况分别为 j,k，此时最少的巧克力数量。（这里 j 和 k 是 02N-1 的数，用于

12、表示该位置是否被覆盖） 为了无后效性，这里应该保证 j 中没有相邻的两个未覆盖点，k 中允许存在，也允许存在j 和k 的同一列均不被覆盖的情况出现。这是因为处理第 i+1 行的 时候，有可能再把第 i 行的某些位置覆盖住。算法状态转移：每次计算 minijk进行转移时，首先通过子程序递归穷举第 i 行（状态 k）中，横过来的 12 的可能情况。接下来，k 中剩余的未覆盖点（却必须覆盖的点），只可能通过 21 和第 i-1 行进行覆盖，这里进行整体考虑很方便。数据量：1 M 70,1 N 7时间复杂度：O(M212N3)（21 是 Fib8）但因为剪枝效果强硬，实际复杂度远远不到。空间复杂度：O

13、(2N2) 度很有新意的题型，我第一次遇到的是NOI2001兵阵地。这类问题的特点是通过二进制数表示状态，进行递推或者动态规划。随着这一类问题的增多，新意全无，编程复杂度却节节攀升。要想完全做对这一道题，的确要花费一番功夫，还要有扎实的位操作功底。最后，找到所有可能情况，再穷举第 i-2 行（当然不满足的还要排除），即可进行转移。算法空间优化：循环滚动 min 数组可以优化一。134Centroid问题简述：给定一棵 N 个结点的树，求该树的所有重心。重心的定义如下：删掉某结点 i 后，若剩余 k个连通分量，那么定义 d(i)为这些连通分量中结点数的最大值。所谓重心，就是使得 d(i)最小的结

14、点 i。算法：树的基本操作。以结点 1 为根，计算出每个结点所在的 的结点数。枚举每一个结点，若将其删掉，那么考虑剩余的所有连通分量。1、它的 ，其结点数可以直接调用。2、它的上方 ，其结点数可通过 n-1 减去所有子树的结点数算出。这样，在其中选择 d(i)最小的即可。数据量：1 N 16 000时间复杂度：O(N)空间复杂度：O(N)思路比较简单，但是通过直接计算的办法，求出了上方 的结点数，避免了 tree dp 的双向扫描，的确很精妙！137Funny Strings问题简述：一个长度为 N 的序列 S1 S2 . SN，如果序列 S1+1 S2 S3 . SN-1 SN -1 可以由

15、前者旋转得到，那么称前者为 “Funny”字符串。求一个长度为 N ， 和为 K 的 “Funny”字符串。算法：首先容易想到只用 K div N 和 K div N + 1 填入该序列。那么显然可以把(N,K)数据量：2 N 1000,1 K 30000时间复杂度：O(N2)空间复杂度：O(N)算法的构造非常精致，可惜不是出来的，出自 OIBH。但是这道题目让我想了很多。在思路受阻时，要将已知的东西进行嵌套，擦出火花，达到的问题转化为(N,K mod N)。对于填入 K 个 1 的长度为 N 的序列，有没有办法进一步缩小呢？几经推敲后发现，(N,K)（KK 时， 可以使用后者，否则使用前者。

16、不难证明此时时间复杂度降为 O(N2)。活学活用的目的。本题中将构造过程，与转转相除等方法进行类比的 就尤为重要！138Gamesof Chess问题简述：N 个人进行比赛，从任意两个人开始，其中有一个胜者。第二轮比赛必须由胜者和另一人进行（可能还是第一轮败者），类似地第三场已知 N 个人每人的比赛场次，要求构造出一组可行方案。算法：很容易地，想到（ 0数据量：2 N 1001 比赛场数 M 10000时间复杂度：O(M)空间复杂度：O(M)贪心的使用是比较明显的，其它过程没有太点，一些小的情况要心细。其实最重要的是大胆 地贪心。代表任意一名选手）x 0 x 0 x 0y xy 0y 0z y

17、z 0这样的贪心策略。因此，只需要将若干参赛场数大于 1 的人，放置在第一列，剩下的任意安排，即可达到构造的目的。不难通过反证法证明该方案的正确性，也就是“参赛场数大于 1”的人数的足够性。140eger Sequen问题简述： 解模线性方程a1x1 + a2x2 + . + anxn b (mod p)算法：首先，求 a1.an 的最大公约数，如果其不是 b 的约数，那么无解。否则，设 g =(a1.,an-1)原方程可以看作： gX+anxn = b(mod p)这样一步一步逆推，一定可以推出一组可行解。数据量：1 N 1001 P 10 0000 B P-1时间复杂度：O(NlogN)空

18、间复杂度：O(N)我个人第一次遇到这样的数学问题，觉得这样递归的 确实很精妙，应该广泛运用。141JumJoe问题简述：已知 x1,x2,P,K解关于(P1,N1,P2,N2)的方程组P1x1-N1x1 + P2x2-N2x2= PP1 + N1 + P2 + N2 = K算法：解 ax+by=c 的不定方程 注意 a,b 的正负性，还有不仅可以通过 x+=b,y-=a 这样的方法来改变和，P1 和数据量：0 x1 , x2 40,000-40,000 P 40,0000 K 2109时间复杂度：O(logX)空间复杂度：O(1)对不定方程的自变量进行了限制，考察了选手的细心程度。不过选择的解

19、决算法是很显然的。N1（或者 P2 和N2）还是可以抵消的。有些，要留心！142Keyword问题简述：给定一个长度为 N 的只包含字母a、b的字符串 S，要求输出一个尽可能短的不被 S 包含的字符串。算法：从小到大枚举最短的长度，然后对该长度的所有子串进行Hash 统计，如果还有剩余，那么就找到了一个满足的字符串。具体统计过程可用“二进制数”表示字符串。易证，所求的字符串长度不会超过 log2N。数据量：1 N 500 000时间复杂度： O(Nlog2N) 空间复杂度： O(N)简单的统计题，本身并没新意，但是留给我们无限的思考空间。如果字符不仅仅是 ab呢？ 如果 串的长度增加呢？ 或许

20、 使用 哈希函 数能够解决一部分，但是有更好的方法吗？ 研究目前停止在了这里。144Meeting问题简述：两支队伍将分别在X 时Y时的某一时间点到达某处，每支队伍来了以后会等待 Z 分钟，求两支队伍相遇的可能性。算法：设 A=Y-X，Z/=60。如果第 1 支队，在 X 到达，此时 Y 有 Z/A 的可能性与他们相遇；如果第 1 支队，在 X+Z 到达，此时 Y 有 2Z/A 的可能性与他们相遇。在这之间，可能性是线性递增的！同样地考虑最后的 Z 小时，得到类似情况。而在 X+ZY-Z 之间，始终保持 2Z/A 的几率。综合化简即可。数据量：0 X Y 240 2，那么它的邻节点中存在 u：

21、、deg(u)=2、除 u 外的 v 的任两个邻节点间都有边相连。 求该图的环。 算法：不难从该图的特征中得出：该图由若干个链和若干个完全图组成，并且完全图上的每个结点，都连出一条链。若该图有 环，则任一个 x 个结点组成的完全图中，该环将严格通过 x条边。性质*不妨把任意一个完全图变成一个环，在新图中求欧拉回路，由性质*不难证得其存在性，与原图的哈密回路存在性互为充要条件。数据量：3 N 10000,M 100000时间复杂度：O(M)空间复杂度：O(M)唯一的难点在于对特殊图的分析。只有分析得细致准确，方可解决本题。任意图的哈密回路是 问题，但是在诸多特殊图中，该问题被数学界、信息学届得热

22、火朝天，希望将来我能致力这方面的研究157Patience问题简述：考虑 14 个格子，以及某种花色的 13，规定Ace210 时程序超时，因此我只能将 10、11、12 这三个数据 const 存入列表158Commuter Train问题简述：有一个长度为 L 的月台。月台上有 M 个人，每人与月台左端的距离为 Pi。另外有一辆 N 个门的火车，每个门和最左端门的距离为 Di。显然D1=0。已知每人会选择与自己距离最近的车门上车，求一个火车的停靠位置，使得所有人的移动距离和最长。算法：最优的状态一定至少有一个乘客正对着两个车门的正 ，或者列车停在月台的边缘。（否则易证一定可以让火车向某方向

23、移动，使得距离和增加）所以枚举乘客与车门即可。数据量：0 L 5000,0 M 300,0 ”, “/”,“/”,”,”=” 在内的一些运算符（详见英文原题），然后让 检查 K 个包含未知数的表达式，是否未知数取遍 H 中的所有元素，其结果均为 1。算法：题目限定|H|100，每个表达式的所有未知数取值的可能性总数106。这样最坏情况下对每个表达式要进行 106 次求值，可惜这个数字非常庞大。首先， 可以对 H 中的每个元素预先求值，并且将它们之间的所有运算预处理。其次， 需要建立表达式树，这样才容易对表达式计算，并且尽可能删除冗余。这样，我并没有使用任何高效优化，就通过了 sgu的数据，但

24、本题一定有更好的优化方法，譬如未知数的枚举顺序？数据量：无向图定点数 N 1 N 100无向图边数 M 0 M 50001 K 20时间复杂度：O(106K)虽然对表达式的计算存在不小的常数因子，但是删除冗余和预处理的过程将其大大降低。空间复杂度：O(N2)题意的理解是一关，其次就是表达式树的建立和处理。我个人觉得本题的算法没有过多新意，就是在程序的处理过程中会出现或大或小的不少麻烦。不知道有没有更简单易行 的 办 法呢？164Airlines问题简述：对于 N 个节点的无向完全图，所有的边被染色 1M。现要求选择其中不超过 (M+1) div 2)种颜色的边，使得这些边组成的图中，任意两个节

25、点的距离不超过 2。算法：任选一半颜色的边，若其不满足，设 A、B 两点距离超过 2，不妨设与 A 相数据量：1 N 200时间复杂度：O(N3)空间复杂度：O(N2)刚看到题，一定会觉得无从下手，本题有一定的数学技巧在其中。平时要多锻炼这类的数学技巧，多掌握一些图论知识，尤其是解决图论 问邻的点集为V1，与 B 相邻的 点 集 为 V2 ， 则 V1V2=，并且 V1 和 V2之间的任意两点没有边相连。选择先前未被选择的一半的边，则 A 将与所有的 V2相连，B 将与所有的 V1 相连，A、B 相意 V1、 V2 之间的点对相连，形象来说就是：ABAB| |V1V2V21对于不在 A+B+V

26、1+V2 中的点，一定同时连 A 和 B。不难证明，这一半的边一定满足条件。因此把图分成两半，至少有一半满足要求。题的方法，这对信息学是很有帮助的。165Basketball问题简述：给定 N 个人的身高 （1.95m2.05m），要求将他们排成一列，使得任意选取两个人，他们中间如果存在 K 个人，并且身高和为 S，那么 S 与 K2m的差的绝对值小于等于 0.1m。算法：首先将所有身高减去 2m。然后分成正的和负的，看当前的部分和。如果是0，就找一个0 的加上，否则找一个正的加上。不难证明，任意 ij 人身高的和100，这样显然满足要求。数据量：1 N 6000时间复杂度：O(N)空间复杂度

27、：O(N)构造并不是很难，费不了太多工夫，简单的天平添加砝码问题。这道题目的扩展就是 有一些砝码，从最大往最小填加，可以在一定程度上使得最后两边的差值较小。这是一个搜索顺序的问题， ctsc2003刘一鸣的解 题 中有很详细地阐述。167I-Country问题简述：在 NM 的地图上，每个格子有一个权值。要求在其中选择不超过 K 个格子，数据量：1 N,M 15,0 K N*M时间复杂度：较成功的动态规划题，对题目细致地分析后，将其使得这些格子的任意两个，都可仅通过上、下、左、右中的两种方向互达。要求这样选择的权值和最大。算法：仔细分析题意，不难得出问题所求的是一个“菱形”区域：.*.*.*.

28、*.*.*.*.之所以称之为“菱形”，是因为它的任意一面（上面、下面、左面、右面），都不会凹进去。具体来说，比如左面，所呈现的边界只能先向左，后向右（或者只向左、只向右）。注意每行只可能选择连续的一段区域。容易想到动态规划： optijkxyl表示满足如下条件的格子的最大权值前 i 行，并且第 i 行选取 jk 的格子，一共选取了 l个格子。x,y 用 0 或者 1 表示左边界和右边界的弯曲情况，比如如果左边界开始向右下伸展了，就不能再向左下。不难对 opt 数组其进行动态转移。O(N2M5)空间复杂度：O(N2M3)从本质上转化，同时也转化成了经典的题型。因为数据量非常小，我没有想着进行优化

29、。或许存在从本质上的改进吧，我想一定有更好的算法！171Sarov Zones问题简述：给定 N 名学生和 K 个赛场，第 i 个赛场最多有 Ni名学生参赛，N=N1+.+NK每个学生有一个能力值 P，每个赛场有一个等级值 Q。仅当一个学生的 P 值大于一个赛场的 Q 值，这名学生才能参加这个赛场的比赛。每个学生只能参加数据量：1 K 1000 N 16000时间复杂度： O(Nlog2N) 空间复杂度： O(N)没有新意的贪心题，这类问题是算法也容易想，证明也容易做。我觉得非常无聊。一个比赛。求参加的方案，使得参加比赛的人数尽可能多。算法：将所有学生按照P 值排序，显然最优方案中，选中的人可

30、以是P 值最大的几个。那么从最大的开始考虑，不妨将其放入他所能参加的，Q 值最大的考场。不难证明，这个贪心方案一定是最优的。另外从 P 值最小的人开始考虑，也是可行的。173Coins问题简述：给定长度为 K-1 的二进制数组 A，对 K 个排放好的硬币序列C，在其上定义 X操作：1、将 C 向左循环移动一格2、如果第 i（1 i s（顶点 n-1），容量无限大。（注，这里没有必要再设置 s-t，书上是错的）求 s到 t的最大流，如果能让所有 s出去的弧都满载，就有解。否则无解。如果有解，再利用 t-s 求最大流，将流量缩小。算法质疑：在附加网，以及流量缩小的地方，该算法容易被引起质疑：例如如

31、下情况，B-C 容量为 1，要求被满载。S-A-B-TO(N4)实际值不到 空间复杂度： O(N2)流算法的深入理解。有些算法我们不能仅仅 会用，就万事大吉。其实更重要的是深刻领悟一个算法：1、 为什么正确。2、 怎么被创造 出 来的。3、 引申扩展？这样不仅能锻炼在信息学赛场上的思维方式，还能够做到知己知彼，百战不殆。我做这道题目是非常成功的，虽然刚开始我有些轻信（书上算法）的正确性，但是后来我能够对问题有一个很深入地分析，并且将算法进行了适当改造。 定要将做这道题目的经验拓展开去！/ /C/如用上述方法，将得到最小流量为 0，也就是仅仅出现 A-B-C-A 一个环的情 况 ， 而 不 是

32、S-A-B-C-A-B-T 的流量为 1 的结果。但是要注意网络流的定义，其并没有说这种情况不能发生。对于本题，设定 S 制造速度为 0，一开始 ABC 中间就有物质在不停地运动（题目中没有说不可以）。流量缩小的过程并不尽如人意，比如：S-T/ /A/T-A 容量为 1 要求满载。那么在缩小流量的时候，会把 S-T-A-S 圈上的 S-T 删掉， 得 到流量-1为什么呢？因为在网络流的定义中，规定了不能有弧指向S，也不能有弧流出 T。须要再设定超级源和超级汇有没有简便的方法呢？算法改进不缩小流？很容易地，我们找到了许多反例。对前面“标准算法”的理解透彻，仔细思考后发现： t-s（也就是 N-1

33、）弧的流量，就是 s 点的制造速度。因此，只要在 t-s 的弧上设定费用为 1，对附加网求最小费用最大流就可以了。算法进一步简化事实上，进行两次最大流即可。第一次不添加 t-s 的弧，求最大流。第二次把这条弧填进去，再尝试把 s流出的弧都满载，进行一次最大流。不难证明正确性。我觉得方法适用于所有“上下界的最小流”问题，简单易行，时间复杂度平均意义上更低。177Square问题简述：有一张 NN 的 子纸，按顺序将 M 个矩形（与纸张边缘平行）范围内的格子染上黑色或白色，后染上的颜色可以覆盖先染上的颜色。求最后纸上有多少 子。算法初探：首先可以进行离散化（不一定有必要，因为坐标都是整点，在范围

34、1N 内）接下来逐个离散行处理，容易想到 N3 和用 heap 维护的 N2log2N 算法。而下面我将介绍的 N2 算法，基于一个非常简单的策略：算法简单策略：初始时候 hash1.N全为白色， covered1.N 均为 false。从最后一个矩形开始，譬如说要覆盖该行的 xy，那么对xiy，如果coveredi= false，那么将 hashi置为相应的颜色，coveredi也修改为 true。算法优化：上述算法是一个逐一染色的过程，考虑进行优化。初始时候设定 nexti = i+1，譬如覆盖 35，那么 covered3.5 和 hash3.5适当修改，并且 next3.5置为 6，接

35、下来如果覆盖数据量：1 N 1000,1 M 5000时间复杂度：O(N2)空间复杂度：O(N)这个问题的算法被得热火朝天，听说有 O(N(log2N)2)的算法，不过我未见其真面目。比较经典的算法还有一个是矩形的四分法，复杂度为 O(NM)。刚拿到这题，我陷在了对 heap 算法的 优化中，始终未能得到好的方法。而到了最后，我转移了视线，转移到了一个最简单的方法，反而从中使复杂度 发生质的飞跃。以后比赛时，要注意这种视线的大转移！27 ， 那 么 先 处 理 covered2和 hash2，这时候发现 covered3被覆盖，那么直接走到 next3=6，接着覆盖 67 。并且 next2,

36、next67也要修改为 8。这个过程有些类似于并查集，甚至还可以考虑“路径压缩”，可以证明时间复杂度为线性。178Golden Chain问题简述：有一根 N 个环连成的链，每天需要付一个环，可以通过“付出 4 个环，要回 3个环”这样类似的方式。问至少要打开多少个环，才能使 N 天内每天都能付一个环。题意分析：一定要理解清楚，如果打断一个环，不仅链子被分成了两段，而且还多出一个单个的环。算法：如果不打断任一个环，那么 N 最多到 1。如果打断一个环，首先有一个长度为 1 的链，可以坚持第 1 天；第二天，最多用长度为 2 的链；第三天可以度过；第四天最多用长度为 4 的链。如果打断两个环，首

37、先有 2个长度为 1 的链，可以坚持前两天；第三天最多用长度为 3 的链，坚持到第五天；第六天最多用长度为 6 的链，坚持到第 11天每次加入一个链，所有小于等于总长度的数，都可以被表示，而选择的链，是所有可选的链中最长数据量：1 N 1016时间复杂度：O(log2N)空间复杂度：O(1)对所求问题有正确的认识，加上严密仔细的分析，并不难得到最后的公式。我打听了一下比赛时没有通过这道题目的选手，他们都是因为没有想到 “ 打开一个环，多出一个长度为一的 链”这个重要条件。的。因此不难证明这种方法的最优性。进一步可以推出公式：如果打开 n 个环，最多可以坚持(n+1)2n+1 天。因此只需要枚举

38、打开的环的数量，检测给定的 N 是否在最多能表示的天数范围内即可。179Brackets light问题简述：给定一个合法的括号序列，要求输出与之长度相同的，字典排序下一个的合法括号序列。算法：仔细考虑一下，不难得知()()()是最大的序列()是最小的序列从后往前，找到第一个可以由(变成)的位置，将其改变，然后其后的所有位置，尽可能靠前地多填(，最后只能填)。数据量：不超过 10000 个字符时间复杂度： O(10000)空间复杂度：O(10000)计算下一个排列组合的基本算法的扩展，没有太多创意。182Openthe brackets问题简述：给定包含最多10 个 变量的表达式，其中包括“！

39、、|、&、=、#”操作和括号。要求把它脱去括号。输入不超过 2048 个字符，输出过 32768个字符。算法：最古老的想法，是一层一层脱括号，那样不仅不太现实，编程复杂，而且容易超过输出上限。一个很精妙的想法，是把所有变量的可能情况（最多 1024）种带入，求出原式的结果。如果仅当 a=0,b=1 或者 a=1,b=0 时原式为 1，那么可以这样输出：!a&b|a&!b时间复杂度：O(10242048)空间复杂度：O(2048) 个精妙的方法，使得我初二刚学信息学时，就百思不得其解的问题得到了非常好的解答。赛后我也没有能够独自解决这道题，归结起来，和 177 类似，我被困于“给人以虚假希望的绿

40、洲”！就是把所有可能的情况都带入，然后用|连接。注意无解的情况，可以找到一个出现过的变量，如 a，输出a&!a。对于原式的处理，可以通过 2 叉树，将其分解开来。183Paingthe balls问题简述：有 N 个白球排成一行，每个球有一个染色费用。现在要把其中的某些染黑色，使得任意连续 M 个球中至少有两个黑球。求最小的费用值。算法：简单地推理后，我否定了数学方法，那么只有动态规划可以奏效。 optij(ib-c-d a-e-f-d而如果第一次找到了a-b-f-d导致不存在第二条最短路径，那么就设置一些反向弧，使得第二次找到： a-e-fc-d因为 f (!x)x - (x) !x x算法

41、：比如样例，初始为 A，要求变成(AAB)。最终有三个块，第一个块放了 A 产品，因此必须进行 A-(A)BA 的变换（如果进行另一种变换，第一个块将放 B 产品）；接下来看第二个块，属于 B 公司，但是最终放置了 A 产品。因 此 ， 只 能 进 行 (A)BA-(AA)A 的操作。可见，如果问题有解，那么方案是唯一的。只要贪心即可。时间复杂度：O(N)空间复杂度：O(N)方法很容易想到。但是在比赛时，其得分率非常低，并不是因为有 的数据，而是因为大家都不敢大胆地理解题意。整 个 这 次 SSPC 的题目都有这种感觉192RGB问题简述：平面上有 N 条线段（顶点坐标范围在 032000），

42、这些线段都被染成 R、G、B三色之一。X 轴上的每一点，被染成了 Y 值与之相同的，最近的线段上的点数据量：0 N 300时间复杂度：O(N2log2N)空间复杂度：O(N2)难度不是很大，通过对数据算 分析，容易得出离散化和交换的方法。 N2log2N的的颜色。求X 轴上 R、G、 B 三种颜色的总长度。算法：把所有的端点、交点的 x坐标拎出来，离散并删除重复。对于每一个离散列，找到所有的线段，并找到距离坐标轴最近的一个。这是一种算法，时间复杂度为 O(N3)。从左到右依次处理每一个离散列，将线段按照当前列中的出现，从下至上排序。如果遇到一个交点，那么就交换两条线段的位置；遇到一个端点，就进

43、行 或删除。这样，总时间复杂度 O(N2)即可完成这个“顺序”的 ，对每个离散列，只需要选取最下面的一条线段的颜色即可。算法较难实现，我个人推荐N3 的方法，其在考场上更容易得到好的分数。193ChiGirls Amusement问题简述：N 个人围圈玩传球 ，开始时第一个人拿着球，每个人把球传给左手的第 K 个人。满足 1KN/2。求 K 的最大值，使得第一个人重新拿到球之前，每个人都拿过球。算法：显然，当且仅当 K 与 N 互质，才可满足条件。1、如果 n 是奇数，不难证明(n-1)/2 与 n 互质，即满足条件。2、当 n 是偶数， 先考虑 n/2-1。、若 n/2-1 是奇数，不难证明

44、，其与 n 的公因子最大只可能是 2。所以一定互质。、若 n/2-1 是偶数，不难证明，n/2-2 与 n 的公因数据量：3 N 102000时间复杂度：O(N)空间复杂度：O(N)很简单的数学分析就可以解决本题，没有太大新意。196MatrixMultiplication问题简述：给定N 个顶点M 条边的无向简单图，设定一个矩阵A=aij，其中第i 个顶点是第 j 条边的端点。设 AT表示将 A 的行列交换后的转置矩阵。求 ATA 所有元素的和。算法：设 B= AT，C=ATA子只可能是 1、2、4，而其为奇数，所以一定互质。注意高精度的处理，最高位有多余的 0 等情况。195NewYear

45、 Bonus Grant问题简述：给定 N 个职员的关系树，新年到了，要给某些职员发奖金。每个人可以自己的一个直接下属，让他的下属拿到奖金。每个人最多一个人，不可能同时拿到奖金且推荐别人。求所有员工最多能拿到多少奖金（每人次的奖金数额都是1000 元）。题意分析：求一棵树的边的最大独立集（选取最多的边，使得它们互相没有公共结点）。算法：树的动态规划，设 opti,j： j=1 表示 i 为根的，根结点的职员了奖金的最佳总奖金额。j=2 表示 i 为根的 ，根结点的职员没有 奖金的最佳总奖金额。很容易进行状态转移，但是不能用递归，否则会栈溢出。数据量：2 N 500 000时间复杂度：O(N)空

46、间复杂度：O(N)其实只是利用树的形式表达出动态规划的模型，而并不是真正的树的动态规划。比较简单，不存在太大新意。不难得出问题所求，就是 A 矩阵的每一行的数的和的平方和。197Nice Patterns Strike Back问题简述：NM 的格子纸，每个格子被填上黑色或者白色。求没有任何一个 22 的格子同色的染色方案总数 mod P。算法：每行最多 32(=2M)种状态，任两种状态是否可组成相邻行，可以用一个 3232的矩阵表示。显然的，这个矩阵的 n 次方，所有的元素的和，就是问题的 。数据量：1 N 101001 M 5时间复杂度：O(23Mlog2N)空间复杂度：O(2Mlog2N

47、)兵阵地一类 hash dp 题目的矩阵式扩展。当长度更长，宽度更小时，这类问题都可以考虑矩阵乘法来操作。当然这种算法的复杂度，随着 M 的上升而急剧上升。200Cracking RSA问题简述：给定 M 个数，它们的质因子 T 个质数范围内。求这M 个数组成集合的满足如下条件的非空子集个数：子集中所有数的积为完全平方数。算法：首先将读入的 M 个数，分解质因数，并对每个质因数出现次数的奇偶性进行。设 xi=0 或 1 代表是否使用第 i 个数。可以列出一个关于 xi(1=i单峰”这一过程（ 事先我并没有这方面的知识）。这种 可以广泛运用到各类求极值的问题中去。之为 V1(x)， 还可以算出第

48、二次起跳的初速度函数 V2(x)，不难发现 V2 有 4个类似的极值点。要求的是V(x)=maxV1(x), V2(x)的最大值。前面的 8 个极值点，把 V 函数分为 9 段。容易知道，任意一段都是单调或者单峰函数。因此， 只需要把 8 个极值点检查一遍，9 个区间通过 2 分找到极值，在所有的数值中选择最优的，就得到了问题的解。算法注意：别高兴得太早，这样的算法还会在 sgu 上 wa，这一切都是精度误差惹的祸。因此， 每每得到 V(x)是一个极值时，还需要进行抖动，检查 x 附近的位置。205zation Problem问题简述：针对样例阐明问题所求：38 8 19有 n=3 个数 8

49、8 19另外有一个矩阵(m*s)：2 45 10第一个数 ，在第一行（从第一行开始）找到 10 与之匹配，差值为 2。10 出现的位置为第 2 列，而(2-1) mod m + 1 = 2，接下来到第二行。第二个数8，选择其对应7，差值为 1。还是通过(2-1) mod m + 1 = 2，停在第二行。第三个数19，令其对应17，差值为 2。到这里就结束数据量：1 n 10001 m 128 m s 128时间复杂度：O(nms)空间复杂度：O(nm)最基本的动态规划题，不需要技巧。了，总差值为 5。（如果要继续走的话，接下来到(4-1) mod m+ 1=2，第二行）求总差值最小的方案。算法

50、：动态规划。opti,j代表第 in 的数，其中第 i 个数选择第 j 行与之匹配，总差值的最小值。O(nms)的简单转移即可206Roads问题简述：给定 N 个城市和 M 条道路，其中前 N-1 条道路是大路，其它都是小路，并保证大路可 N 个城市的生成树。第 i 条路费用为 ci，要求你谎报费用（设第 i 条 报的费用为 di），使得对费用数组 d 来说，N-1 条大路恰为 最 小 生 成 树 ， 并 且 sum|ci-di|尽可能小。问题转化：显然，大路只可能把费用报得更低，小路只可能报得更高。设1i1，考虑这个 0 所在的两个 2 之间的区间，如果剩下的都是 1（没有 0），那么把区

51、间最左边的 2 进位。2)、是 1，那么 1-0，向前一位进 1，如果前一位变成 2，注意前一位的前面的区间是否全部都是 1，如果那样也要和 1)一样修改。 如果前一位原来就是 2，那么跳转 3)数据量：1 N 10001 M 10000时间复杂度：O(N2)实际值远不到。空间复杂度： O(N)虽 然最终 得到的方法非常简单，但是要想思考出来并非易事，思考量非常大。做这类题目，需要有一个正确的思考方向。如果多个 2 连在一起，将会比较“”，容易超过 4 次的限额，怎么避免？ 让它们之间存在一个 0，这样就缓解了压力。这一种直观、化的 思考过程是非常 值得在 考场上借鉴的，因为它不需要大规模的证

52、明，确能给人以无比的3)、是 2，那么 2-1，再将其前面一位加 1 即可。自信。212Data Transmis问题简述：N 个节点被分为 L 层，每条弧从第 i 层指向 i+1 层，共 M 条弧，第一层和第 L曾只有一个节点：源和汇，要求找到一个“较大流”，使得不考虑后向弧，该图不存在增广路径。算法：听说有 O(sqrt(V)*E) 的求最大流的算法，我尚不清楚。我在 同学的帮助下使用了贪心+增广的办法。算法步骤 1 贪心： 贪心的目的是寻找一个较优的可行流来加快程序速度。基本过程是这样的： 1、正向检索在 每 个 节 点 处 有 一 个 inflowi 入 流 量 和 ouflowi出流量，初始时