三个月内如何突破noip

Question

NOIP
如何在三个月突破noip到省一等奖的水平?
有过c的语法基础，即将有两个月的c和c++魔鬼训练.每天学习时间大约15小时左右，还有三个月，如何在三个月内得到获得省一等奖的水平，没有老师教noip，两个月的培训是c和c++的，有一个优势，每天睡觉时间3小时左右，可以腾出5小时学习noip的时间。如何利用仅有的时间，得到一等奖的目标，是提高组，就是高中生参加的，之前没有noip任何基础，也没老师教，需要怎么做？不要说三个月不可能达到，李连杰的太太三个月都可以从abcd到考托福，人的潜能是无限的。我相信我也行。希望大家能说说学习什么东西，从从哪里学，如何学习，详细的学习清单及意见。急！！！

Answer 1

1.确定你的语言 NOIP接受Pascal、C、C++三种语言的参赛者，在学习的开始，务必确定自己使用的语言。 在中途变更自己学习的语言，对学习NOIP来说是非常大的困难。若是初学者，对C、C++没有基础，我个人建议学习Pascal。Pascal可读性高，对于初学者来说，比起C和C++，Pascal应该是更容易上手的。如果有较长时间的准备，不妨试试看学C或者C++，在以后的大学学习中也会有帮助，而且需要网上搜索题解时，C和C++的题解往往较多，更加方便阅读参考。 （本人使用Pascal语言，所以后文回答可能涉及到具体程序的大多是Pascal思维。）

2.从排序入手 排序是信息竞赛基础中的基础，值得我划出整整一块来为排序进行说明。 快速排序是必备本领，在信息竞赛中，若是不会快排，其他的知识就是空中阁楼，学习其他各种优化方法，排序却丢了时间，是万万不可的。学习快排最简单的方法是背。而C和C++应当是自带快排的，所以快速排序很是轻松。 而个人认为，快速排序以外，必须掌握的排序知识还有多关键字排序以及稳定的O(nlogn)排序。 多关键字排序来说，我个人是引入比较函数，在确定两个数字顺序时不单纯比大小，而使用函数处理判断先后。 而稳定排序，我学习了归并排序。它不仅是一个稳定排序，而且可以进行求逆序对等操作，对程序学习的帮助也非常大。

3.贪心和穷举以及模拟——最简单的程序 想要快速获奖，必须熟练掌握贪心和穷举以及模拟。它们虽然不能帮你得到满分，但是可以帮助你从得不到分变为得到30分甚至60分，或者说，它是你想不出更好算法时的救命稻草。 所谓贪心，就是通过局部最优来达成整体最优。每一步都获得当前能取得的最优值，最终也能获得最优值。虽然看似是非常正确的思路，但由于贪心算法所能够考虑因素往往具有局限性，得出的答案常常不会是最优解。但是，仍然需要强调的是，贪心在NOIP这一类比赛中，是能够得分的。 所谓穷举，就是列出所有可能的情况，然后从中寻找最优解。虽然看上去是非常简单的操作方法，但是实际应用时，通过穷举和剪枝（程序运行到一定程度由于能判断必定不是最优解而不再继续），可以达到意想不到的效果。 所谓模拟，常应用于给定步骤时。我们通过逐步进行操作、逐步判断来推断是否符合题目中所给出的情况。这种方法常常是非常耗费时间的，所以一般都不可能是最优解。但是，仍然是可以得到部分分数的一种简单而粗暴的方法。

4.用动态规划来训练思维 动态规划，我偶然跟母亲说到这个的时候，母亲想起了大学时的课程，然后一脸苦笑的样子现在都令我印象深刻（笑）。 动态规划是非常难的一个部分，虽然解题上有一定的规律，但是对于思维的周密程度和逻辑要求非常高。所以我会建议先通过动态规划来训练自己的思维。特别是在短时间内的学习的话，动态规划可以帮助你快速进入编程状态。并且，动态规划的思考也可能帮你发现题目背后可能隐藏的更简便的算法。 动态规划主要的思考规律应该是如下： 定义函数（动态转移方程中转移量的定义） 建立方程 确定初值和边界 由于没有具体的题目，我也不能详细说明动态规划。动态规划千变万化，题目类型多种多样，动态规划的种类也多种多样，难以一一赘述了。 需要提醒的是，在NOIP的考场上，千万不要因为想不到动态转移方程而放弃一道题目，尝试使用贪心等看似并不完全正确的做法来做，能够得到部分分数；也不要在动态规划写出后发现答案不正确后耗费太多的时间，经验表明要找出动态规划的错误点可能可以浪费你整场考试的时间。

5.学习简单的图论 我认为简单图论中包括的有：（单源或多源）最短路和（最小）生成树。 最短路中需要学习的有Dijkstra算法和Floyd算法。Dijkstra算法有点像图论中的动态规划，而Floyd则是图论中的穷举法。但是由于近年来图论的题目越来越困难，加入的其他知识越来越多，没有长时间准备的话，这两种算法掌握即可。如果想再深入一点的话，可以学习SPFA，SPFA也是非常实用的一种算法。 最小生成树就不得不提Prim算法和Kruskal算法。最小生成树的算法中，这两种某种意义上都可以算是贪心的算法。Prim算法更适用于稠密图，而Kruskal算法更适用于稀疏图。如果要学习最小生成树的话，两者都学习并且对比是一种很好的方法，能够看到两种算法的优点和不足。

6.常用的数据结构——让程序更快一点 数据结构中想说的NOIP常常能够用到的是：堆（优先队列）、并查集。更加深入学习还可以提到树状数组 堆，这种数据结构只关注“直系亲属”之间的关系，而不关注“旁系”。常常能够配合贪心使用。例如NOIP的经典题合并果子，虽然能够想出是贪心，但是如果不明白堆的话，程序也不能够得到满分。 并查集，能够快速判断两个元素是否有关联，增加了其他手法之后还能够判断元素之间关系。比如说上面提到的Kruskal，一种非常常见的写法中就运用到了并查集来判断两个点是否已经被连接。 树状数组，能够查询和修改操作复杂度比较平衡的一种算法，正因如此常用来解决同时需要查询和修改的问题。

7.不知道该放在哪里说的搜索——和枚举很像 老师每次被要求讲解搜索都会非常无奈，因为每次讲解完搜索，同学们都会以一种“啊，原来是这样”的眼神看着他，而几个月后还会再重复这样的场景（笑）。 搜索大题来说分为深度优先搜索和广度优先搜索。深度优先搜索就是一条路走到死，撞墙了再回头，而广度优先搜索则是每一步就将下一步所有的可能性放入队列中，然后按照队列顺序来探测。 初赛经常会考深度优先遍历或广度优先遍历后是什么顺序，而复赛的搜索题会加入许多复杂的因素，所以也请好好学习一下这一部分。

8.最后的最后，一定要学习的数学基础知识 简单列举一下： 快速幂 高精度 筛法选素数 扩展欧几里得定理（辗转相除法） 这些在考前一定要重新再看一遍，因为难度并不大但是NOIP考到的几率并不小（会隐藏在第一题中）。

Answer 2

（本人NOIP提高组2012一等）不管你有多自信，我还是要说，你数学好么，不好就别指望了，三个月没基础只能靠数学好。不过还是建议了解所有语法之后，从基本题一直练到难题，看书之余还要刷题，推荐http://www.vijos.org 在线题库，十分经典。章节练习：字符串处理、模拟题、搜索与剪枝、动态规划初步、图论基础、数据结构。注意几个必备算法：二分查找、线段树或者RMQ、最短路径、强连通分量、网络流、最小生成树、并查集、LCA、哈希。常考点：数据结构、动态规划、搜索、模拟

Answer 3

我也在准备考NOIP。我现在在看一个学校老师给我的PPT，我觉得对我挺有帮助的，我可以发给你。PPT上的知识你掌握后，就做真题。2004~2012的卷子和答案网上都有的，你肯定找得到。做完后，相信你的水平肯定突飞猛进。
（把邮箱留给我哦）

追问

2410665641

追答

好吧sorry，我看错了，还以为你是初中组的~不好意思啊

Answer 4

3个月时间可能是紧了些，能否达到可能因人而异。现在语言学完了，就要开始练习算法了。算法的书很多，你可以先看针对NOIP的，如果不够再看专门讲算法的，比如算法导论（Introduction to Algorithms）。书其实好坏影响并不大，关键是自己要理解并多练习。

追问

不是说算法导论太难了吗，不适合noip

追答

是的，但如果你能力太强了，觉得其它的都太简单了的话

Answer 5

学习 Scratch 和乐高只是在电脑上拼积木。但是不要灰心，因为学习这些东西其实可以让孩子更早接触到类似于循环、变量、运算符等知识，在学 C++ 的过程中其实也是一种帮助。

关于学习 Python 的事情，个人建议可以在 C++ 语法学习好了之后稍微看一下。C++ 和 python 的互通性实际上还是蛮大的。学好了 C++ 之后，想看懂 Python 并不是一个很难的事情。但是这两者中先接触到的语言可是会影响到孩子之后的代码风格什么的。在 Python 中，需要用 tab 表示循环，变量使用 var 进行定义，库需要使用 import，可以使用 range 表示一个区间，和 C++ 的大括号、多类型分开定义、使用 #include<> 进行引用是很不同的。所以，如果现在想学的话，还是建议 先学习 C++ 。朋友推荐龙之梦酷叮猫少儿编程