NOIP考前知识大总结_noip考前知识大总结

NOIP考前知识大总结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“noip考前知识大总结”。

数据类型

Type

Byte

Shortint

Smallint

Word

Integer

Cardinal

Longint

Longword

Int64

QWord

Real

Single

Double

Comp

Extended

算法思想:

1.搜索

2.归纳

3.分治

4.贪心

实现技巧: NOIP考前知识大总结 作者：于俊超 ID:MiniDragonXG2006年11月RangeSize in bytes0..2551-128..1271-32768..3276720..655352either smallint, longint or int64size 2,4 or 8either word, longword or qwordsize 2,4 or 8-2147483648..2***..42949672954-***5808..***580780..***70955161582.9E-39..1.7E3861.5E-45..3.4E3845.0E-324..1.7E3088-9.2E18..9.2E1883.4E-4932..1.1E493210(Search)枚举(穷举)/ 遍历 / 剪枝 / 产生式系统（估价函数）查找(字典)：折半查找(二分法)/ 树形查找(二叉排序树)/ Hash(To 数学方法)>递推式> DP(ex: 4 Hanoi Tower Problem)(Divided and Conquer)(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)=1fib(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)(ai0 & n>k)叫

k阶常系数线性齐次递推关系

可以利用矩阵性质和快速幂在O(logn)内求解

错位排列:F(1)=0F(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: 图Grapha: 图的遍历:

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/GetMinB: Binary Search Tree(BST)

C: 平衡二叉树......排序算法:

复杂度 思路 InsertChooseExchange O(n^2)直接插入排序 直接选择排序 冒泡排序(Inserting Sort)(Choosing Sort)(Bubble Sort)O(nlogn)希尔排序堆排序快速排序(Shell Sort)(Heap Sort)(Quick Sort)O(n)计数排序桶排序基数排序(Counting Sort)(Bucket Sort)(Radix Sort)归并(Merge 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完全 ……

∵九成不考 ∴略……

Copyright ©2006 By MiniDragonXG.All rights reserved.