NOIP辅导骗分VIP专享VIP免费

NOIP 辅导.ppt 以下是该文档的文本预览效果，预览是为了您快捷查看，但可能丢失了某些格式或图片。 打印 | 下载 NOI 辅导 厦门大学: 林阳斌 问题1 有些题目太长，很难看懂，或者是看题花太长的时间。 面对很长的题目（处理规则复杂）的题目会丧失信心；且容易烦躁。 解答1 对于长的难于理解的题目,首先必须有耐心,还要有信心。可以告诉自己这题其实就是题目不好懂,其实看懂了就很简单。（事实也是如此） 当然也存在题目长且难的题目,例如NOIP 2007 年的第4 道题. 首先难题主要为第4 题 , 所以可以把第4 题放最后做,而前面的那些题无论如何也要把题目看懂. 问题2 如何分析题目的难度 解答2 首先要认真的审题，分析题目所有的条件，然后才开始思考。在想出算法后，务必要计算该算法的复杂度，估计下是否会超时。 一些经验： 1.对于N>=1000， 000 的情况 ，要思考O(N)的算法。 面对这一类问题，往往比较简单，算法为O(N)大多数情况都是具有某种性质的，或者用贪心、HASH 的方法就可以做出来。 例如： 给定n（ n>=1000000）个数ai 和一个数C (1 <= c <= n) 你可以选择任意个数，使他们的和可以整除C，问如何选择。（任意选择只要慢阻条件即可） 比如输入： 5 1 2 3 7 5 4 输出 3 5（表示第3 个数和第5 个数） 输入： 3 7 11 2 5 13 17 6 输出 2 3 4 2.对于10000 <= n <= 1000000,这类题目很有可能跟数据结构相结合，它有两种可能，一种是o(n*logn)的算法， 例如RMQ,线段树，平衡二叉树；另一种就是O(n)，或低于O(n*lgn)，例如：并查集，栈扫描。 这类题目的另一种可能就是二分。例如最长单调子序列。 这里顺便提一下：用二分算法解决问题之前一定要思考下，函数是否是单调的，如果不是单调的就无法二分。 3.500 <= n <= 1000， 这种问题的算法必须控制在O(n*n)，如果想不出O(n*n)的时候再考虑O(n*n*lgn)的算法，这一类题目往往也是最难的 100<= n <= 500 的情况太多，可能性太多，这里不做讨论。 4. 50 <= n <= 100， 这种问题只有可能两种情况，一种就是简单题，另一种就是搜索。 如果是后者，一定要注意减枝，因为很有可能会超时 5、 20 <= n <= 50， 这类问题基本就是简单题或者数学题。 6、 n <= 20, 这种题的复杂度往往是O(2^n)或者O(n!)，首先考虑使用DP 的方法，其次才是搜索和枚举，如果可以打表的话尽量打表。搜索的时候 问...