联赛知识点总结_物理竞赛知识点总结

联赛知识点总结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“物理竞赛知识点总结”。

联赛知识点

算法思想:

1.搜索(Search)枚举(穷举)/遍历/剪枝/产生式系统

搜索（深搜、广搜）

 不会太简单的试题，能搜出来，就好，优化是一种功底。

 搜索编程复杂度高些。

 程序往简单方向写。

 搜索，尤其要增量调试式编程。

2.归纳(To 数学方法)

3.分治(Divided and Conquer)

4.贪心

5.模拟

实现方法:循环/递推/递归

数学方法:

1.数论:质数/因数/公约数/公倍数/回文数....2.高精度运算(int64...)

3.排列组合（全排列）、概率、向量

4.经典递推关系:

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(x)=(x-1)*[f(x-1)+f(x-2)]

f(1)=0f(2)=1

(好像记得f(n)=a1*f(n-1)+a2*f(n-2)+....+ak*f(n-k)(ai0 & n>k)叫什么k阶常系数线性齐次递推关系)

Catalan数:catalan(x)=C(n,2*n)/(n+1)

第二类Stirling数 f[n,m] = f[n-1,m-1] + m*f[n-1,m]

5.高斯消元

数据结构(Data Structure):

1.物理结构:

I: 数组>二维平面/字符串(Ansistring)及其操作

II: 指针>链表

Ⅲ.串（要注意KMP算法）>串类试题基本是模拟的细心题如，PKU1677 girls’s day

要练练

自己调试时，要出一些小的弱智数据

如判断C中的注释时，/*…*/

最简单的弱智数据/，这个不是注释

不能只以首字母来判断某串字符，是否相同，或出现过

要全面考虑问题

抽象数据类型(Abstract Data Type)

2.初级ADT:

I: 集合II: 线性表

A: 栈(stack)

(LIFO)operation: push/pop

a: 后缀表达式

b: 进出站序列问题(Catalan 枚举 > 归纳)

c: 栈优化最长不下降序列

B: 队列(queue)>循环队列

(FIFO)operation: push/pop

a: 广度优先搜索

III: 树Tree(二叉树Binary Tree)

树的遍历：前序/中序/后序(递归)

哈夫曼树（贪心）

IV: 图Graph

A: 图的遍历: DFS(回溯/递归)/BFS(队列/FloodFill)

B: 最小生成树：（贪心）

Prim: 边集密

Kruskal:边集疏（快排 + 并查集）

C: 最短路径

Dijkstra（单源 O(n^2)）

SPFA(用队列)

Floyed（所有点间 O(n^3)）

Bellman-Ford（负权环）

D: 拓扑序列

E: 关键路径（AOV网）

F: 无向图传递闭包

有向图强连通分量SCC

(Strong Connected Component)

G: 路与回路

a: 欧拉路(Euler Route)所有边

b: 哈密尔顿路(Hamilton Route)所有点

H: 割点和桥

3.高级ADT:

I: 集合型

A: 并查集(disjoint-set)

operation: Find/Union/Insert

II: 树型

A: 二叉堆(Heap)>Treap

operation: Insert/Delete(Pop)/GotMax/Min

B: Binary Search Tree(BST)

C: 平衡二叉树......III: 字典型

哈希表(Hash)哈希函数

排序算法:

复杂度 思路 InsertChooseExchange

O(n^2)直接插入排序 直接选择排序 冒泡排序

(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: 堆

还有二叉排序树(BST)..........，不要怕，真的不行，可以不用考虑平衡化处理。

动态规划(Dynamic programming):

不多说了：肯定最重要的:

1.状态转移方程+边界条件

2.合适的实现方法

3.要掌握最经典的动规题目

a: 最长不下降序列

b: 最大子段和(包括子矩形)

c: 最长公共子序列(LCS)

d: 石子合并（链，环）

e: 背包问题(参考01背包9讲)

f:判定性背包问题

g:资源型动态规划

01背包-可重复(DP)

01背包-不可重复(DP)

部分背包(贪心)