NOIP2010解题报1.doc

NOIP2010解题报告天津市南开中学 钱桥首先对这次比赛做一个总体分析。第一题我觉得没什么好说的，作为一道简单题还是挺简单的。第二题是动态规划，朴素的做法可以得到30-50分，如果发现了方程中的一个小优化并且稳稳当当地作对，可以拿到满分。第三题暴力有哪些信誉好的足球投注网站可以拿到30分。如果想得到满分，首先要想到二分答案，可能多数同学没有想到这个方向上，再验证是否是二分图，通过BFS实现，就可以拿到满分了。第三题还有一个并查集的方法也可以做。第四题确实较难，首先通过BFS判断“无解”的情况，可以拿到30分，而对于有解的情况，需要仔细分析，得出一个“重要结论”，之后用到BFS和Dp可以拿到满分。下面我将逐题进行分析第一题：（由于是NOIP，这道题的题解我就给个时间复杂度高一点但是好理解的吧，大牛们忽略此题题解）我们用一个a数组维护当前内存存储的单词，并且从1到m的位置就是单词进入内存的先后顺序。一开始内存是空的，所以所有位置上都是-1。我们顺序操作文章中的n个单词，对于每个单词，我们都查找它当前是否在内存中。若它在内存中，直接忽略过去；若它不在内存中，就需要把内存的2~m位置上的单词往前挪（挪到1~m-1处），并把新的这个单词放到m处，并把答案类加1。最后输出答案即可。第二题：我们的任务是用给定的卡片从1走到n，最终得分最大。动态规划的味道似乎挺浓的，于是尝试一下。动态规划首先要用变量来表示出状态。若要表示当前状态，需要用的变量是：当前位置、当前还剩余哪些卡片。当前位置很好记录，一个变量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）就可以表示出当前的状态了。我们另F[j1, j2, j3, j4]表示剩余j1张1卡片、剩余j2张2卡片、剩余j3张3卡片，剩余j4张4卡片，走到n的最大得???。而转移成子问题似乎也很显然：F[j1, j2, j3, j4] = a[n - j1+j2*2+j3*3+j4*4] + max（F[j1-1, j2, j3, j4]??????????????????????????????????????????????????? F[j1, j2-1, j3, j4]??????????????????????????????????????????????????? F[j1, j2, j3-1, j4]??????????????????????????????????????????????????? F[j1, j2, j3, j4-1]）边界F[0, 0, 0, 0]=a[n]。所求为F[m1, m2, m3, m4]。时间复杂度：O(p^4)?? 其中p为题目给定的每种卡片不超过40第三题：这道题是一个明显的“最大值最小”问题。解释一下，就是让你找出一个分配方案，使得所有冲突中的最大值尽量的小。“最大值最小”问题99%都可以用二分答案来做。再具体解释一下：? ?如果最后最小的最大冲突为ans。对于一个在区间[0, ans)的数k，一定不满足命题“所有冲突值都小于等于k”，而对于一个在区间[ans, 1000000000]的数k，一定满足命题“所有冲突值都小于等于k”。这就好比是一个猜价格的游戏，你猜一个价格，我告诉你高了还是低了，如果高了你就往低猜，如果低了你就往高猜。而这道题是你猜一个k，根据它满足命题还是不满足命题决定再大点还是再小点。当然，最快的方法就是在区间[0, 1000000000]上二分这个k。那接下来我们的任务就变成了，验证一个k，是否能满足命题“所有冲突都小于等于k”。而这个命题等价于“所有冲突值大于k的两个犯人必须被关押在不同的监狱”。那么通过BFS染色就可以判断。时间复杂度：O(M*log(10^9))对于另一做法，需要一个更高级的知识——并查集。这里简单说说。首先把所有冲突按照从大到小进行排序，然后进行操作。我们都检验，对于当前冲突的两个人是否能把他俩分开。直到遇到两个人，他俩不可能被分开（如果分开了就跟前面冲突了），那他俩的冲突度就是最后的答案了。而利用并查集可以维护已知的一些人的关系。时间复杂度：O(MlogM)第四题：这道题个人认为出的不错。首先判断是否有解。判断方法很简单：假设靠水库的所有城市（(1, 1)~(1, m)）都建造水泵，判断是否能覆盖所有靠沙漠的城市。如果无解就