NOIP考前知识大总结
2006年11月
数据类型
Type Range Size in bytes
Byte 0 .. 255 1
Shortint -128 .. 127 1
Smallint -32768 .. 32767 2
Word 0 .. 65535 2
Integer either smallint, longint or int64 size 2,4 or 8
Cardinal either word, longword or qword size 2,4 or 8
Longint -2147483648 .. 2147483647 4
Longword 0..4294967295 4
Int64 -9223372036854775808 .. 9223372036854775807 8
QWord 0 .. 18446744073709551615 8
Real 2.9E-39 .. 1.7E38 6
Single 1.5E-45 .. 3.4E38 4
Double 5.0E-324 .. 1.7E308 8
Comp -9.2E18 .. 9.2E18 8
Extended 3.4E-4932 .. 1.1E4932 10
算法思想:
1.搜索 (Search) 枚举(穷举) / 遍历 / 剪枝 / 产生式系统（估价函数）
查找(字典)：折半查找(二分法) / 树形查找(二叉排序树) / Hash
2.归纳 (To 数学方法) > 递推式 > DP (ex: 4 Hanoi Tower Problem)
3.分治 (Divided and Conquer)
4.贪心 (Greedy) 5.模拟
实现技巧: 循环
递推(顺推/倒推) > 博弈 / 动态规划
递归(栈/DFS)
滚动数组
幂：
x ^ y = exp(y*ln(x))
x ^ (1/n) = exp(1/n*ln(x))
math单元里的Power
数学方法:
1.数论: 质数 / 因数 / 约数个数（种数）/ 最大公约数 / 最小公倍数 / 回文数....
2.进制转换 注意负进制
3.高精度运算 (int64...)
4.排列组合: 全排列
5.经典递推关系:
Fibonacci: fib(n)=fib(n-1)+fib(n-2)
fib(1)=1 fib(2)=1
通项： 设g5=sqrt(5) 则fib(n)=(1/g5)*( ((1+g5)/2)^n-((1-g5)/2)^n )
f(n)=a1*f(n-1)+a2*f(n-2)+....+ak*f(n-k) (ai<>0 & n>k)叫
k阶常系数线性齐次递推关系
可以利用矩阵性质和快速幂在O(logn)内求解
错位排列: F(1)=0 F(2)=1
Fn=(x-1) * (Fn-1 +Fn-2)
Catalan数: Catalan(n)=C(n,2*n)/(n+1)
第二类Stirling数 s(n,k)= { s(n-1,k-1)+k*s(n-1,k) } (n>k>=1)
6.高斯消元
数据结构(Data Structure):
1.物理结构:
I: 数组 > 二维平面/字符串(Ansistring)及其操作
II: 指针 > 链表 （单链表 / 双向链表 / 环状链表）
抽象数据类型(Abstract Data Type)
2.初级ADT:
I: 集合
II: 线性结构
A: 栈(stack)
(LIFO) operation: push/pop
a: 后缀表达式
b: 进出站序列问题(Catalan 枚举 > 归纳)
c: 栈优化最长不下降(上升)序列
B: 队列(queue) > 循环队列
(FIFO) operation: push/pop
a: 广度优先搜索
b: 求和广义线性表
C: 字典 Dictionary
III: 非线性结构
A: 树Tree (二叉树Binary Tree)
树的遍历：前序/中序/后序 (递归)
最优二叉树(哈夫曼树Huffman tree）（贪心）
树形DP
B: 图Graph
a: 图的遍历:
Depth first Search (DFS / 回溯 / 递归)
Breadth first Search (BFS / 队列 / FloodFill 种子染色法 )
b: 最小生成树：（贪心）
Prim: 边集密
Kruskal: 边集疏（排序 + 并查集）
c: 最短路径
Dijkstra（ 单源 O(n^2) BFS ）
Floyed（ 所有点间 O(n^3) ）
Bellman-Ford（负权环）
d: 拓扑序列
e: 关键路径（AOV网）
f: 无向图传递闭包
有向图强连通分量SCC
(Strong Connected Component)
g: 路与回路
欧拉路(Euler Route)所有边
哈密尔顿路(Hamilton Route)所有点
h: 割顶和桥
去除之后图变得不连通的顶点和边
3.高级ADT:
I: 集合型
A: 并查集(disjoint-set)
operation: Find/Union/Insert
II: 字典型
哈希表(Hash) 哈希函数
opertaion: Find/Insert
III: 树型
A: 二叉堆(Heap) > Treap
operation: Insert/Delete(Pop)/GetMax/GetMin
B: Binary Search Tree(BST)
C: 平衡二叉树......
排序算法:
复杂度 思路 Insert Choose Exchange
O(n^2) 直接插入排序 直接选择排序 冒泡排序
(Inserting Sort) (Choosing Sort) (Bubble Sort)
O(nlogn) 希尔排序 堆排序 快速排序 归并
(Shell Sort) (Heap Sort) (Quick Sort) (Merge Sort)
O(n) 计数排序 桶排序 基数排序
(Counting Sort) (Bucket Sort) (Radix Sort)
Quick Sort: 分治
Merge Sort: 分治
Bucket Sort: 哈希表
Heap Sort: 堆
还有二叉排序树..........
动态规划(Dynamic programming)
=记忆化搜索+用Table记录免去重复计算
（解决 满足具有最优子结构 且 无后效性）
1.状态转移方程+边界条件
2.合适的实现方法(To 实现技巧)
3.要掌握最经典的动规题目
a: 最长不下降(上升)序列
b: 最大子段和 & 最大M子段和
c: 最长公共子序列(LCS)
d: 石子合并（链，环）
e: 背包问题
01背包-可重复(DP)
01背包-不可重复(DP)
部分背包(贪心)
博弈问题：
1. 关键字：必胜态 / 必败态
2. 递推找规律
3. 归纳
计算几何
三角形面积 s=|x1y2+x2y3+x3y1-x3y2-x2y1-x1y3|
二维仿射变换 反射 / 镜像 / 旋转
计算二维凸包……这东西我直接听不懂……
网络流 & 匹配（二分图） & 线段树 & 树状数组 & NP完全 ……
∵九成不考 ∴略……
