NOIP2015 - 知识点总结

最近没什么状态,一天什么事都干不了,直接开始联赛复习好了,权当调整状态。
其实不一定是NOIP范围内的,只是学过的,全都过一遍吧er…

算法 - Algorithm

排序 - Sort

基础的五种排序:选择排序/插入排序/快速排序/归并排序/冒泡排序
可能用到的排序:冒泡排序/快速排序
当需要稳定时,使用冒泡排序[Code 1],复杂度$O(n^{2})$
平时使用STL自带库函数sort(本质为随机快排),平均为$O(nlogn)$:
1.逆序或自定义比较方法可以自定义比较函数;
2.vector的排序使用sort(vector.begin(),vector.end());
3.结构体排序使用自定义函数或重载运算符:bool operator < (const struct a) const { … };
4.当需要将结构体指针给结构体定义大小(如哈弗曼编码),加入优先队列里,代码:[Code 2]
[BZOJ 4198] HNOI2015荷马史诗
[BZOJ 2457] 双端队列

深度优先搜索 - DFS

[BZOJ 3990] SDOI2015排序 题解

广度优先搜索- BFS

[BZOJ 1054] HAOI2008移动玩具

双向BFS - Duplex_BFS

代码:[Code 3]
[CodeVS 1225] 八数码难题

RMQ

不带修改的使用ST表,待修改的用线段树。
[POJ 2019] Confield 【二维RMQ[Code 4]

哈希 - Hash

至今觉得写得不错 >> 哈希专题总结
表现好的一些素数 >> Good Hash Table Primes
开放寻址代码:[Code 5]
[POJ 3504] Obfuscation 【无序字符串哈希/DP】

康托展开 - Cantor

康托展开及其逆运算代码:[Code 6]

数学相关 - Math

初等数论 - Elementary number theory

欧几里得算法&扩展欧几里得 - gcd&exgcd

[BZOJ 1477][BZOJ 1385][BZOJ 1407][BZOJ 1951]
代码:[Code 7]

中国剩余定理 - CRT

多用于大数取模运算,可以间接求解。

推论 mod x意义下模方程的解的个数等于所有mod pidi意义下解的个数的乘积,其中x=p1d1p1d2…pkdk,p为互不相通的质数。

代码:[Code 8]
[BZOJ 1951] 古代猪文
[BZOJ 3129] SDOI2013方程

欧拉定理 - Euler’s Theorem

$a^{φ(n)}≡1\ mod\ n$
$φ(n)$:欧拉函数,表示1~n中与n互质的数的个数。
计算公式:$$φ(x)=x\sum_{d|n}^{d\ is\ a\ prime}\frac{d-1}{d}$$

代码:[Code 9]
线性筛:[Code 10]
性质:$$\sum_{d|n}φ(\frac{n}{d})=n$$

推广:对于任意a,p有 $a^{n}≡a^{n\%φ(p)+φ(p)}\ mod\ p$
特殊情况:对于互质的a,p有 $a^{φ(p)}≡1\ mod\ p$
更特殊的情况:费马小定理。
[BZOJ 2818] GCD
[BZOJ 2190] SDOI2010仪仗队
[BZOJ 2705] Longge的问题

费马小定理 - Fermat’s Little Theorem

$gcd(a,p)=1\ \ =>\ \ a^{p-1}≡1\ mod\ p$
[BZOJ 1951] 古代猪文
[BZOJ 1451] HNOI2009有趣的数列

Lucas定理 - Lucas’ Theorem

${C(n,m) mod\ p≡C(n/p)(m/p)C(n\%p)(m\%p)\ mod\ p}$
代码:[Code 11]
[BZOJ 1951] 古代猪文

乘法逆元 - multiplication inverse

应用:模意义下,除以一个数等于乘上这个数关于模值的逆元。
求解:扩展欧几里得(求解二元二次方程)。

组合数学 - Combinatorial Mathematics

>> BZOJ组合数学题集

容斥原理 - Inclusion-exclusion Principle

|⋃i=1 to nAi|=∑k=1 to n[(-1)k-1I∈M(n,k)|⋂i∈IAi|]
错排问题:$ans=n!(1-\frac{1}{1!}+\frac{1}{2!}…±\frac{1}{n!})$

排列组合 -Permutation and Combination

  • 组合数公式

$C(n,k)=C(n,n-k)$

$C(n,m)=C(n-1,m-1)+C(n,m-1)$

$C(n,r)C(r,l)=C(n,l)C(n-l,r-l)$

$\sum_{i=0}^kC(n+i,i)=C(n+k+1,k)$

$\sum_{i=0}^nC(n,i)=2^n$

$\sum_{i=0}^n(-1)^iC(n,i)=0$

$\sum_{i=0}^kC(n,i)C(m,i-k)=C(n+m,k)$

$\sum_{i=0}^mC(n,i),C(m,i)=C(n+m,m)$

二项式定理 - Binomial Theorem

$$(a+b)^n=\sum_{i=0}^nC(n,i)a^{i}b^{n-i}$$

Catalan数 - Catalan Number

通项公式:$f(x)=\frac{C_{2n-2}^{n-1}}{n}$
递推公式:$f(x+1)=\frac{4n-6}{n}f(x)$

一一对应 - Bijection

prufer编码 - Prufer Array

戳 >> 非常详细的讲解+例题
[BZOJ 1430] 小猴打架
[BZOJ 1211] 树的计数
[BZOJ 1005] 明明的烦恼

莫比乌斯反演 - Möbius inversion formula

很久之前(大概3个月)之前搞过一次,当时觉得都会了,现在想起来真的是毛都不记得啊,实力复习一波。

概念

莫比乌斯函数
定义:

$$μ(n) =
\begin{cases}
1, & \text{n=1} \\
(-1)^k, & \text{n有k个质因子,且所有质因子次数都为1} \\
0, & \text{else} \\
\end{cases}
$$

性质:

$$\sum_{d|n}μ(d)=
\begin{cases}
1, &\text{n=1} \\
0, &\text{n>1} \\
\end{cases}
$$

莫比乌斯定理

内容:

$$F(n)=\sum^{d|n}f(n) =>f(n)=\sum^{d|n}μ(d)F(\frac{n}{d})$$

证明:

$$\sum^{d|n}μ(d)F(\frac{n}{d})=\sum^{d|n}μ(d)\sum^{k|\frac{n}{d}}f(k)=\sum^{d|n}f(k)\sum^{k|\frac{n}{d}}μ(d)=f(n)$$
其中最后一步转化用到了莫比乌斯函数的性质。

另一种表述

$$F(n)=\sum^{n|d}f(n) =>f(n)=\sum^{n|d}μ(\frac{d}{n})F(d)$$

技巧

线性筛莫比乌斯函数

代码:[Code 12]

下底函数分块

其实跟莫比乌斯并没有什么关系…只是有时候这两个东西一起考得比较多…
代码:[Code 13]

例题

[BZOJ 2440] 完全平方数
[BZOJ 2301] Problem b
[BZOJ 2820] YY的GCD
[BZOJ 3529] 数表

矩阵乘法

高斯消元

概率期望

置换

技巧

线性筛

素数
欧拉函数
莫比乌斯函数

n的约数个数

快速幂

质因数分解

单个欧拉函数求解

下底函数分块

组合数取模

字符串

MP

KMP

EXKMP

Manacher

[BZOJ 2342]

AC自动机

后缀数组

LCP


数据结构 - Data Structure

链表、栈和队列 - Chain Table, Stack and Queue

%一下 ->《链表、栈、队列》

链表 - Chain Table


· 单向链表
· 双向链表
[BZOJ 2288] 生日礼物
[BZOJ 1150] CTSC2007 Backup
[BZOJ 1098] 办公楼biu
· 循环链表
[BZOJ 2151] 种树
· 块状链表 —— TB说就是链表套链表
[BZOJ 1507] NOI2003 Editor
题解 >> 《链表小结》

栈 - Stack

遇到一个卡STL的题…于是手写了个栈:[Code 14]
[HDU 5357] Easy Sequence (注意它畸形的取模方式…)

单调栈 - Monotonous stack

[BZOJ 1012] JSOI2008 最大数
[BZOJ 1127] POI2008 KUP

队列- Queue

优先队列 - heap

[BZOJ 1150] 数据备份
[BZOJ 2151] 种数
[BZOJ 2288] 生日礼物

双端队列(单调) - Deque

[BZOJ 1047] HAOI2007 理想的正方形
[BZOJ 2096] POI2010 Pilots
[BZOJ 2276] POI2011 Temperature
[BZOJ 1122] POI2008 账本BBB
题解 >> 《栈和队列》

并查集 - Union-Find Sets

戳 >> 《并查集》
[BZOJ 2049][BZOJ 2079]
[BZOJ 1854][BZOJ 1116]
[BZOJ 1529][BZOJ 1202]
[BZOJ 2054][BZOJ 1050]
[BZOJ 1050][BZOJ 1015]
[BZOJ 2054][BZOJ 1370]
[BZOJ 4195] NOI2015 程序自动分析
Ural1003 奇偶性
NOIP2010 关押罪犯
NOI2002 银河英雄传说
NOI2002 食物链
POI 代码等式
POI 可爱的猴子
APOI2011 方格染色

图论 - Graph Theory

连通性 - Connectivity

基本都是时间戳的运用。

强连通分量 - Strongly Connected Component

Tarjan

代码:[Code 15]

缩点

[BZOJ 2208] JSOI2010 连通数
[BZOJ 1179] APIO2009 ATM
[BZOJ 1512] POI2006 Pro-Professor Szu
[BZOJ 1194] HNOI2006 潘多拉的盒子

Kosaraju

双连通分量 - Biconnected Component

割顶和桥 - ‘Cut’ and ‘Bridge’

求割顶:[Code 16]
同时可以把桥标记出来。
[BZOJ 1123] POI2008 BLO

2-SAT

BST

可并堆

Trie

Huffman

LCA

Tarjan
倍增

并查集

树状数组

线段树

[Codeforces Round #321 (Div. 2) E]

重心与直径

Prufer

树链剖分

平衡树

treap
splay

[BZOJ 2209]

LCT

[BZOJ 2759]

生成树

最小生成树

[BZOJ 1050]

最优比率生成树
曼哈顿生成树

最短路

Dijkstra(堆优化)
SPFA( 单调队列优化)

[BZOJ 1179] APIO2009 ATM

bellman-ford
Floyd
差分约束
k短路

拓扑排序

[BZOJ 1103]
[BZOJ 2208] JSOI2010 连通数
[BZOJ 1512] POI2006 Pro-Professor Szu

欧拉图

网络流

最大流与最小割
01分数规划
费用流
zkw费用流
二分图匹配

[BZOJ 4025]

匈牙利算法

技巧与思想

记忆化搜索

高精度

模拟

暴力

贪心

[BZOJ 2457] 双端队列
[BZOJ 2789]

分治

[BZOJ 3433]

离散化

莫队算法

[BZOJ 2120]
[BZOJ 2453]
[BZOJ 3052]

分块

[BZOJ 3433]

离线处理

动态规划

类型

线性递推

区间DP

树形DP

[BZOJ 2152]

DAG上的DP

[BZOJ 1512] POI2006 Pro-Professor Szu
[BZOJ 1123] POI2008 BLO

状压DP

[BZOJ 3195]

bitset

[BZOJ 2208]

概率期望DP

优化

单调栈优化

单调队列优化

斜率优化


附件 - 模板

[Code 1] 冒泡排序

1
2
3
4
5
void BubbleSort(int n){
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++)
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}

[Code 2] 结构体指针加入优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
struct structure{		//加入优先队列的结构体
...
}*s;
struct cmp{ //自定义比较的结构体
bool operator () (structure*a,structure*b){
return a->x<b->x || (a->x==b->x && a->y<b->y);
}
};
priority_queue<structure*,vector<structure*>,cmp> q; //优先队列的定义,默认大根堆

void push(structure str){
q.push(&str);
}

[Code 3] 双向BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
queue<int> q[2];
int step[2][maxn]; //状态为0~maxn-1
int Duplex_BFS(int s,int t){
if(s==t) return 0;
memset(step,-1,sizeof(step));
q[0].push(s),step[0][s]=0;
q[1].push(t),step[1][t]=0;
while(!q[0].empty() || !q[1].empty())
for(int k=0;k<2;k++) //轮流广搜
if(!q[k].empty()){
int u=q[k].front(); q[k].pop();
int v=nxt(u);
if(step[k][v]>=0) continue; //重复状态
if(step[k^1][v]>=0) return step[k][u]+step[k^1][v]+1; //搜到结果
q[k].push(v),step[k][v]=step[k][u]+1; //继续往前搜
}
}

[Code 4] 二维ST表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int matrix[maxn][maxn];
int rmq_min[2*maxn][maxl][2*maxn][maxl]; //开大一点可以直接忽略越界情况
int rmq_max[2*maxn][maxl][2*maxn][maxl]; //空间消耗非常大,切勿爆空间!
inline int len(int x){ return log2(x)+1; }
void RMQ(int n,int m){ //在n*m的矩阵中的RMQ
int len1=len(n),len2=len(m);
memset(rmq_min,127,sizeof(rmq_min));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
rmq_max[i][0][j][0]=rmq_min[i][0][j][0]=matrix[i][j];
for(int k=0;k<n;k++)
for(int j=1;j<len2;j++)
for(int i=0;i<m;i++){
rmq_max[k][0][i][j]=max(rmq_max[k][0][i][j-1],rmq_max[k][0][i+(1<<(j-1))][j-1]);
rmq_min[k][0][i][j]=min(rmq_min[k][0][i][j-1],rmq_min[k][0][i+(1<<(j-1))][j-1]);
}
for(int k=0;k<m;k++)
for(int j=1;j<len1;j++)
for(int i=0;i<n;i++){
rmq_max[i][j][k][0]=max(rmq_max[i][j-1][k][0],rmq_max[i+(1<<(j-1))][j-1][k][0]);
rmq_min[i][j][k][0]=min(rmq_min[i][j-1][k][0],rmq_min[i+(1<<(j-1))][j-1][k][0]);
}
for(int k=1;k<len1;k++)
for(int i=0;i<n;i++)
for(int l=1;l<len2;l++)
for(int j=0;j<m;j++){
if(!k && !l) continue;
int l1=1<<(k-1),l2=1<<(l-1);
rmq_max[i][k][j][l]=max(max(rmq_max[i][k-1][j][l-1],rmq_max[i+l1][k-1][j][l-1]),max(rmq_max[i][k-1][j+l2][l-1],rmq_max[i+l1][k-1][j+l2][l-1]));
rmq_min[i][k][j][l]=min(min(rmq_min[i][k-1][j][l-1],rmq_min[i+l1][k-1][j][l-1]),min(rmq_min[i][k-1][j+l2][l-1],rmq_min[i+l1][k-1][j+l2][l-1]));
}
}
int query_max(int x1,int y1,int x2,int y2){ //查询矩形的对角线为(x1,y1)-(x2,y2)
int len1=len(abs(x2-x1+1))-1,l1=1<<len1,len2=len(abs(y2-y1+1))-1,l2=1<<len2;
return max(max(rmq_max[x1][len1][y1][len2],rmq_max[x2-l1+1][len1][y1][len2]),max(rmq_max[x1][len1][y2-l2+1][len2],rmq_max[x2-l1+1][len1][y2-l2+1][len2]));
}
int query_min(int x1,int y1,int x2,int y2){
int len1=len(abs(x2-x1+1))-1,l1=1<<len1,len2=len(abs(y2-y1+1))-1,l2=1<<len2;
return min(min(rmq_min[x1][len1][y1][len2],rmq_min[x2-l1+1][len1][y1][len2]),min(rmq_min[x1][len1][y2-l2+1][len2],rmq_min[x2-l1+1][len1][y2-l2+1][len2]));
}

[Code 5] 开放寻址

1
2
3
4
5
6
7
const int mod=prime;
int HashTable[mod],num[mod];
void hash(int x){
int y=x%mod; y=y<0?y+mod:y;
while(HashTable[y] && num[y]!=x) y=(y+1)%mod;
HashTable[y]++;
}

[Code 6] 康托展开及其逆运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int maxn;
int fac[amxn],seq[maxn]; //fac[i]=i!
int Cantor(){
int res=0;
for(int i=0;i<maxn;i++){
int cnt=0;
for(int j=i+1;j<maxn;j++) if(seq[i]>seq[j]) cnt++;
res+=cnt*fac[maxn-i-1];
}
return res;
}
bool used[maxn];
void OppCantor(int x){
for(int i=0;i<maxn;i++) used[i]=0;
for(int i=0;i<maxn;i++){
seq[i]=x/fac[maxn-i-1]; x%=fac[maxn-i-1];
for(int j=0;j<=seq[i];j++) if(used[j]) seq[i]++;
used[seq[i]]=true;
}
}

[Code 7] 欧几里得算法&扩展欧几里得

1
2
3
4
inline void exgcd(int x,int y,int&d,int&a,int&b){
if(!y) d=x,a=1,b=0;
else{ exgcd(y,x%y,d,b,a); b-=a*(x/y); }
}

[Code 8] 中国剩余定理

1
2
3
4
5
6
7
8
9
10
11
12
const int mod;
int prime[],value[],cnt;
int CRT(int n){
divide_mod();
calc_value();
int res=0;
for(int i=0;i<cnt;i++){
int d,a,b; exgcd(mod/prime[i],prime[i],d,a,b);
res=(res+(ll)mod/prime[i]*a%mod*value[i]%mod)%mod;
}
return (res+mod)%mod;
}

[Code 9] sqrt求某个欧拉函数

1
2
3
4
5
6
7
8
9
inline int phi(int x){
int res=x;
for(int i=2,lim=sqrt(x)+1;i<lim;i++) if(!(x%i)){
res=res/i*(i-1);
while(!(x%i)) x/=i;
}
if(x>1) res=res/x*(x-1);
return res;
}

[Code 10] 线性筛欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool flag[maxn];
int prime[maxn],phi[maxn],cnt;
void MakePhiList(){
for(int i=2;i<maxn;i++){
if(!flag[i]) prime[cnt++]=i,phi[i]=i-1;
for(int j=0;j<cnt && i*prime[j]<maxn;j++){
flag[i*prime[j]]=true;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}

[Code 11] Lucas定理

1
2
3
4
5
6
7
8
9
10
inline int C(int n,int m,int mod){
if(!m) return 1; if(!n) return 0; if(n<m) return 0;
int cn=1,cm=1;
for(int i=0;i<m;i++) cn=cn*(n-i)%mod,cm=cm*(i+1)%mod;
return cn*power(cm,mod-2,mod)%mod;
}
inline int Lucas(int n,int m,int mod){
if(!m) return 1; if(!n) return 0; if(n<m) return 0;
return Lucas(n/mod,m/mod,mod)*C(n%mod,m%mod,mod)%mod;
}

[Code 12] 线性筛莫比乌斯函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int maxl;
bool form[maxl];
int prime[maxl],mu[maxl],cnt;
void MakeMuList(){
mu[1]=1;
for(int i=2;i<maxl;i++){
if(!form[i]) prime[cnt++]=i,mu[i]=-1;
for(int j=0;prime[j]*i<maxl;j++){
form[prime[j]*i]=true;
if(!(i%prime[j])){
mu[prime[j]*i]=0;
break;
}
else mu[prime[j]*i]=-mu[i];
}
}
}

[Code 13] 下底函数分块

1
2
3
4
5
6
7
8
9
int f(int n,int m,int k){
int ans=0;
if(n>m) swap(n,m);
for(int i=1,last;i<=n;i=last+1){
last=min(n/(n/i),m/(m/i));
ans+=(m/(i*k))*(n/(i*k));
}
return ans;
}

[Code 14] 非STL栈

1
2
3
4
5
6
7
8
struct Stack{
int a[maxn],p;
void init(){ p=0; }
int top(){ if(!p) exit(1); return a[p-1]; }
void push(int x){ if(p==n-1) exit(1); a[p++]=x; }
void pop(){ if(!p) exit(1); p--; }
bool empty(){ return p==0; }
}stack;

[Code 15] Tarjan求强连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int scc[maxn],cnter;

stack<int> st;
bool ins[maxn];
int dfn[maxn],low[maxn];
void Tarjan(int u){
static int num=0;
dfn[u]=low[u]=++num;
st.push(u),ins[u]=true;
for(int i=cur[u];i>=0;i=nxt[i]){
int v=to[i];
if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
while(true){
int x=st.top(); st.pop(),ins[x]=false;
scc[x]=cnter;
if(u==x) break;
}
cnter++;
}
}

[Code 16] 求割顶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool iscut[maxn];
int dfn[maxn],sze[maxn];
int Tarjan(int u,int fa){
static int counter=0;
sze[u]=1;
int lowu=dfn[u]=++counter;
for(int i=cur[u],now=0;i>=0;i=nxt[i]){
int v=to[i];
if(!dfn[v]){
int lowv=Tarjan(v,u);
lowu=min(lowu,lowv);
sze[u]+=sze[v];
if(lowv>=dfn[u]) iscut[u]=true;
}
else if(fa!=v) lowu=min(lowu,dfn[v]);
}
if(!u && sze[u]>1) iscut[u]=true;
return lowu;
}