数学
排列组合
错排问题：\(D_n=(n-1)(D_{n-1}+D_{n-2})\) \((D_1=0,D_2=1)\)
数据结构
栈
出栈序列数量 卡特兰数\(\displaystyle C_i=\frac{C^n_{2n}}{n+1}=\sum_{i=0}^{n} {C_i}{C_{n-i}}\)
树
一个结点的度为这个节点的子节点数，一棵树的度为所有节点的度数最大值
二叉树
- 二叉树中，编号为i的结点，父结点为\(\lfloor \frac{i}{2} \rfloor\)，子结点分别为\(2i\)和\(2i+1\)
- 第\(i\)层最多有\(2^{i-1}\)个结点，深度为\(k\)的树最多有\(2^k-1\)个结点
- \(N=N_0+N_1+N_2\)，\(N_2+1=N_0\)
图
有关定义
- 不存在重边与自环的图，叫做简单图
- 无向图中任意两个结点间都存在边相连，叫做无向完全图
- 有向图中任意两个结点间都存在互为相反的两条边相连，叫做有向完全图
- 结点的度：图中与结点相连的边的数目
- 入度：在有向图中，以这个结点为终点的有向边的数目
- 出度：在有向图中，以这个结点为起点的有向边的数目
- 在无向图中，如果两点间存在路径（不一定直接到达），则称两点连通
- 在有向图中，如果两点间可以互相到达，则称两点强联通
- 一个无向图，若每两个点都连通，则称此图为连通图
- 一个有向图，若每两个点都连通，则称此图为强连通图
性质
- \(图中所有结点的度的总和=边数 \times 2\)
- 有向完全图，共有\(n(n-1)\)条边
- 无向完全图，共有\(\frac{n(n-1)}{2}\)条边
- \(n\)个点的连通图，边的数量至少为\(n-1\)
- \(n\)个点的强连通图，边的数量至少为\(n\)
算法
排序
不稳定的排序：选择、希尔、快排、堆排
- \(O(n^2)\)：冒泡、选择、插入、快排最坏
- \(O(n\log{n})\)：归并、快排、堆排、希尔、sort
- \(O(n)\)：桶排、计数、基数
动态规划
最大子段和
⚠️子段必须连续⚠️
\(dp_i\)代表以\(a_i\)为结尾的最大子段和
状态转移方程：\(dp_i=max({dp_{i-1}+a_i},{a_i})\)
最长上升子序列
⚠️子序列可以断开⚠️
\(dp_i\)代表以\(a_i\)为结尾的最长上升子序列的长度
主要代码：
int ans=0;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}
最长公共子序列
\(dp_{i,j}\)代表以\(s1_{i}\)为\(s1\)的末尾，\(s2_j\)为\(s2\)的末尾时的最长公共子序列长度
\[状态转移方程：dp_{i,j} = \begin{cases} dp_{i-1,j-1}+1 &\text{if } s1_i=s2_j \\ max(dp_{i-1,j},dp_{i-1,j}) &\text{if } s1_i \ne s2_j \end{cases} \]01背包
\(f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])\)
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
完全背包
\(f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])\)
for(int i=1;i<=n;i++){
for(int j=v[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
多重背包
int cnt = 0;
for (int i = 1; i <= n; i ++ ){
int a, b, s;
int k = 1;
cin >> a >> b >> s;
while (k <= s){
cnt ++ ;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0){
cnt ++ ;
v[cnt] = a * s;
w[cnt] = b * s;
}
}//二进制优化操作
n = cnt;
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);