信息学noip2010提高组noip2010tg解题报告

1、NOIP2010 解题市中学 钱桥首先对这次比赛做一个总体分析。第一题我觉得没什么好说的，作为一道简单题还是挺简单的。第二题是动态规划，朴素的做法可以得到 30-50 分，如果发现了方程中的一个小优化并且稳稳当当地作对，可以拿搜索可以拿到 30 分。如果想得到到满分。第三题满分，首先要想到二分，可能多数同学没有想到这个方向上，再验证是否是二分图，通过 BFS 实现，就可以拿到满分了。第三题还有一个并查集的方法也可以做。第四题确实较难，首先通过 BFS 判断“无解”的情况，可以拿到 30 分，而对于有解的情况，需要仔细分析，得出一个“重要结论”，之后用到 BFS 和 Dp可以拿到满分。下面我将逐

2、题进行分析第一题：（由于是 NOIP，这道题的题解我就给个时间复杂度高一点但是好理解的吧，大牛们忽略此题题解）用一个 a 数组当前内存的单词，并且从1 到 m 的位置就是单词进入内存的先后顺序。一开始内存是空的，所以所有位置上都是-1。顺序操作文章中的 n 个单词，对于每个单词，我们都查找它当前是否在内存中。若它在内存中，直接忽略过去；若它不在内存中，就需要把内存的 2m 位置上的单词往前挪（挪到 1m-1 处），并把新的这个单词放到 m 处，并把类加 1。最后输出即可。第二题：的任务是用给定的卡片从 1 走到 n，最终得分最大。动态规划的味道似乎挺浓的，于是尝试一下。 动态规划首先要用变量来

3、表示出状态。若要表示当前状态，需要用的变量是：当前位置、当前余哪些，一个变量 i 即可。而“当卡片。当前位置很好前余哪些卡片”似乎并不好。但仔细观察数据规模就会发现，卡片上的数值只会是 1、2、3、4，并且每种不会超过40 张，这样可以用4 个变量j1、仔细观察就会发现，j2、j3、j4 也可以了。而这 5 个变量存在一个恒等式：i+j1+j2*2+j3*3+j4*4=n，也就是说其中一个可以通过另外四个推出来。于是我们只需要 4 个变量（j1, j2, j3, j4）就可以表示出当前另Fj1, j2, j3, j4表示剩余 j1 张 1 卡片、的状态了剩余 j2 张 2 卡片、剩余 j3 张

4、 3 卡片，剩余 j4 张 4 卡片，走到 n 的最大得分。而转移问题似乎也很显然：Fj1, j2, j3, j4 = an - j1+j2*2+j3*3+j4*4 + max（Fj1-1,j2, j3, j4Fj1, j2-1, j3, j4Fj1, j2, j3-1, j4Fj1, j2, j3, j4-1）边界 F0, 0, 0, 0=an。所求为 Fm1, m2, m3, m4。时间复杂度：O(p4)不超过 40其中 p 为题目给定的每种卡片第三题：这道题是一个明显的“最大值最小”问题。解释一下，就是让你找出一个分配方案，使得所有中的最大值尽量的小。“最大值最小”问题 99%都可以用二

5、分来做。再具体解释一下：为 ans。对于一个在区间0,如果最后最小的最大ans)的数 k，一定不满足命题“所有值都小于等于 k”，而对于一个在区间ans, 1000000000的数 k，一定满足命题“所有值都小于等于 k”。这就好比是一个猜价格的，你猜一个价格，我告诉你高了还是低了，如果高了你就往低猜，如果低了你就往高猜。而这道题是你猜一个 k，根据它满足命题还是不满足命题决定再大点还是再小点。当然，最快的方法就是在区间0, 1000000000上二分这个 k。的任务就变成了，验证一个 k，是否能那接下来满足命题“所有都小于等于 k”。而这个命题等价于“所有值大于 k 的两个犯人必须被关押在不

6、同”。那么通过 BFS 染色就可以判断。的时间复杂度：O(M*log(109)对于另一做法，需要一个更高级的知识并查集。这里简单说说。首先把所有按照从大到小进行排序，然后进行操作。都检验，对于当前的两个人是否能把他俩分开。直到遇到两个人，他俩不可能被分开（如果分开了就跟前面了），那他俩的度就是最后的系。了。而利用并查集可以已知的一些人的关时间复杂度：O(MlogM)第四题：这道题个人认为出的不错。首先判断是否有解。判断方法很简单：假设靠水库的所有城市（(1, 1)(1, m)）都建造水泵，判断是否能覆盖所有靠沙漠的城市。如果无解就顺便输出不能覆盖的个数。这些都能通过一次 BFS 实现，时间复杂

7、度 O(N*M)。接下来考虑有解的情况。我就顺着我考场上的思路说吧。我首先想到，能否通过一个预处理，求出：（1）对于单独在每个靠水库的城市(1, i)修建水泵，求出它能覆盖到的靠沙漠的城市的*Ai。然后再考虑：（2）通过最少个数的 Ai，使得它们的并集覆盖 1n。面对这两个问题，我同时进行思考，首先第一个问题 N3 可以解决，N2 似乎没有更好方法，但也勉强接受，毕竟够 90 分了。面对第二个问题，尝试往网络流方向想，试图构建最小割模型，可似乎没什么进展。此时我仔细看了下第二个问题，发现它是 NP 问题！道理很简单，把每个靠水库的城市当做一个 Boolean 型变量 Ri，建就是 TRUE，不

8、建就是 FALSE。把每个靠沙漠的城市当做一个表达式，如果这个城市出现在某几个水库的*中，例如 Ai、Aj、Ak、Ap、Aq中，那么这个表达式就是“Ri Or Rj Or Rk Or RpOr Rq”，的目的是满足所有表达式。显然这是一个多 sat 问题，而多 sat 问题是 NP 问题。（这段完全是思路，看不懂的就忽略过去）从而得出一个结论：这个图、这个问题肯定有它的特殊性！究竟是什么特殊性呢？经过观察，我大胆一个结论：如果某个靠水库的城市构建水泵，它能覆盖的 Ai 一定是连续的一段！（如果不是连续一段必然无解）道理很简单：|X例如，出现这样一个靠水库的城市“O”，它覆盖的不是连续一段区间，

9、即中间有一个或多个“X”。由于“O”到“X”的两条路海拔高度都是严格递降的（如箭头方向）。也就是说，在这个“环”上无法找到一个点到“X”的路径为单调递降的。那“X”位置就不可能被任意一个靠水库的城市覆盖。所以得出重要结论：在每一个靠水库的城市修建水泵，能覆盖的区间一定是连续的一段！那接下来问题有两个：（1）对于每个靠水库的城市 i，求出它能覆盖的靠沙漠的城市 STi和 EDi。（2）已知 m 条线段，每条线段是从 STi到 EDi，求最少的线段能覆盖 1-n。先说第二个问题，是一个经典的 Dp。（不怕大牛笑话就说个点但是易懂的方法吧）定义 Fi表示覆盖 1i 需要的最小线段数量。Fi = min(FSTj-1)+1j = i = EDj1=j=m 且必须满足 ST边界 F0 = 0，所求为 Fm。时间复杂度 O(M2)而对于第一个问题，O(N*M*M)的方法很简单，分别从(n, 1)(n, m)搜索 m 次即可。重点说说 O(N*M)的方法。由于 ST 和 ED 是对称问题，只说 ST先从(n, 1)开始往上面 BFS（只不过改如何求。成从低向高搜索），能够搜到的点就是“能够从这个点传递到(n, 1)的点”。显然这些点能够到达的底层最左端的点就是 1。然后再从(n, 2)往上 BFS，只不过对于(n, 1)之前搜到过的点就不必再重新搜索了（因为这次搜