Question

noip需要准备哪些方面的基础知识。复赛需要做哪些类型的题目（提高组）？

Answer 1

Noip算法（小超）
以下用n表示图的点数，m表示边数，k表示一个常数，log均以2为底数，存储边都采用边表。
【模拟】
高精度加、减、乘，除应该不需要
表达式求值（中缀转后缀，栈的操作）

【图论】
图的表示：邻接矩阵，邻接表，边表
单源最短路：dijkstra（O(n2)），bellman（spfa优化，O(km)）
传递闭包和floyd
最小生成树算法：prim（O(n2)），kruskal（O(m log m)）
拓扑排序（O(m)）
欧拉路（边一次）
汉密尔顿回路（点一次）

强连通分量
匹配算法（最大匹配，最小点覆盖，最小路径覆盖，最大独立集）
网络流算法（最大流dinic，最小费用流spfa）
差分约束系统

【树】
树的先序、中序、后序遍历
树中的最长路（两遍bfs）
特殊的树：二叉树
树形动态规划
并查集
字母树

【搜索】
深搜，一般需要剪枝，有可行性剪枝和最优性剪枝两种经常考。还有迭代深搜。
宽搜，双向广搜，估价函数。

【动态规划】
背包问题：01背包，无限背包，多重背包，有依赖的背包，二维费用背包。（参照背包九讲）
树形动态规划
状态压缩的动态规划
最长不下降子序列
最长公共子序列和最长公共子串
动态规划的优化（快速幂，改变状态，优化转移，单调性，四边形不等式）

【贪心】
也有一些经典的模型，如取线段的问题，一般从小规模数据找规律，再适当的有一些证明。

【排序】
选择排序、冒泡排序
快速排序（快排）、堆排序
插入排序
希尔排序
归并排序

【分治】
二分查找
二分答案（这个好像不是分治）

【串】
串的基本操作
Kmp（字串匹配）
Kmp扩展
AC自动机

【数论】
欧几里得算法，最大公约数和最小公倍数
判断质数（sqrt式与筛法求素数）
进制转换

同余定理
中国剩余定理
概率与期望
欧拉函数

【几何】
线段相交
凸包（水平序和极角序）
半平面交

【有序表】
顺序表、链表、块状链表
线段树及其基本操作
树状数组
平衡树（sbt、treap、splay）
后缀数组

【其他】
Hash
随机化算法
矩形切割（与线段树的比较）
Lca（最近公共祖先）与rmq（区间最值）
高斯消元

Answer 2

二、复赛内容与要求：
在初赛的内容上增加以下内容：
A．数据结构：
1．指针类型
2．多维数组
3．单链表及循环链表
4．二叉树
5．文件操作（从文本文件中读入数据，并输出到文本文件中）
B．程序设计
1．算法的实现能力
2．程序调试基本能力
3．设计测试数据的基本能力
4．程序的时间复杂度和空间复杂度的估计
C．算法处理
1．离散数学知识的应用（如排列组合、简单图论、数理逻辑）
2．分治思想
3．模拟法
4．贪心法
5．简单搜索算法（深度优先 广度优先）搜索中的剪枝
6．动态规划的思想及基本算法
评测环境
NOIP2010比赛环境规范依照使用Linux平台、统一编译器、提供多种集成开发环境选择的原则制定。
NOIP2010的比赛环境中，操作系统平台选择Linux；在固定的操作系统平台下，对应不同的语言，使用统一的编译器，消除编译器不同给选手带来的不利影响；对应每种语言，提供了多种集成开发环境，选手可以根据自己的习惯选择集成开发环境。
在全国评测时，评测环境保持与比赛环境的操作系统及编译器一致。也就是说全国评测时，使用与选手比赛时一致的平台对选手的程序进行评测，以消除平台不一致带来的不利影响。
以下是NOIP2010比赛环境要求的详细描述：
使用Linux操作系统平台：
（1）Linux操作系统必须使用NOI linux,基于ubuntu开发；
（2）Pascal语言，必须使用Free Pascal 2.0.4版本作为编译器；
（3）C语言，必须使用gcc 3.2.2作为编译器；
（4）C++语言，必须使用g++ 3.2.2作为编译器。

Answer 3

要准备noip复赛，做的题越多越好，最起码包括搜索、动态规划、高精度、基本图论、树、堆以及大量的相应练习题。