NOIP2012复习提纲(知识点)

在网上的复习提纲的基础上自己整理的。看了这么长时间书,感觉自己没有什么没听说过的了,大部分东西也已经搞明白,现在需要的就是复习、熟悉以及大量做题,融会贯通。

以下提纲按我认为的前两个是因为简单、实用、基础,所以排在前面,其余的是按照我认为的重要程度排序。

NOIP2012复习提纲

一、高精度计算

a) 高精度加法

b) 高精度减法

c) 高精度乘法

d) 高精度除以低精度

e) 压位高精

f) 二进制模拟高精度运算(见tyvj某模拟题第一题题解,用位运算)

二、排序

a) 选择排序

b) 冒泡排序

c) 插入排序

d) 希尔排序

e) 快速排序

f) 堆排序

g) 二叉树排序

h) 基数排序

i) 计数排序

j) C++ sort

三、搜索算法及典型例题

a) 深度优先搜索(+回溯、迭代加深搜索、)

b) 广度优先搜索

c) 双向广度优先搜索

d) A*算法

e) 分支定界

f) 常用剪枝技巧(可行性、最优性)

四、动态规划

a) 线性DP

b) 区间DP

c) 坐标DP

d) 背包DP

e) 树形DP

f) 集合 DP

g) 递推法

h) 记忆化搜索

i) 刷表法

五、贪心算法及典型例题

a) 最优装载、无限背包

b) 乘船问题

c) 选择区间、区间选点、区间覆盖

d) 哈夫曼树

 

六、图论算法

a) 图的表示

i. 邻接矩阵

ii. STL vector

iii. 邻接表

iv. 前向星

b) 最小生成树

i.Prim

ii. Kruskal

c) 最短路

i. Dijkstra

ii. Bellman-ford

iii. SPFA

iv. Floyd

v. Johnson

vi.(APSP)SPFA

d) 拓扑排序

e) 关键路径

f) 广度优先搜索

g) 深度优先搜索

h) 强联通分支

i) 二分图匹配

j) 网络流

七、树及相关算法

a) 树的表示

i. 数组

ii. 结构体+指针

iii. “动态化静态”,指向结构体数组元素的指针

b) 森林->二叉树,多叉树->二叉树(左孩子右兄弟)

c) 无根树转有根树

d) 哈夫曼树

e) 树的遍历

i. 先序

ii. 中序

iii. 后序

iv. 知二求一

f) 线段树

g) 树状数组,ST算法

h) 并查集(路径压缩,按秩优先)

i) 堆、堆排序

j) Trie树

八、数论算法

b) 素数判定,筛法——素数生成、单个或1~n欧拉函数

c) 最大公约数&最小公倍数

d) 扩展gcd解线性方程

e) 模运算、快速幂

f) 排列组合

h) 常见递推关系

g) 计算几何

九、线性表及相关算法

a) 栈

i. 手工栈

ii. STL stack

b) 队列

i.手工队列

i. STL queue

ii. 单调队列

iii. 优先队列, priority_queue

c) 链表

i. 单链表

ii. 双向链表

iii. 循环链表

十、分治算法及典型例题

a) 快速排序

b) 归并排序

c) 逆序对统计

d) 棋盘覆盖

e) 日程表安排

十一、优化

a) Hash优化(经典但有很大局限性的康托展开、可重字符串编解码,挂链法解决冲突)

b) 离散优化

c) STL bitset 用来做bool flag[]数组, 最大可以开到unsigned long long最大值那么大

d) STL map把字符串映射成数值

e) 二分答案,二分搜索,优化转判定(最大值最小化)

十二、 字符串匹配

a) 朴素

b) KMP

c) AC自动机

d) 后缀树

十三、 赛前准备及心态调整

a) 饮食

b) 睡觉

c) 练习准备

d) 赛时分配

e) 心态调整

本提纲修改自: http://tieba.baidu.com/p/1961121678

《NOIP2012复习提纲(知识点)》有9个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注