https://www.noi.cn/upload/resources/file/2023/03/15/1fa58eac9c412e01ce3c89c761058a43.pdf
数据结构
- 线性结构
-
【 5 】双端栈
-
【 5 】双端队列
-
【 5 】单调队列
-
【 6 】优先队列
-
【 6 】ST 表（Sparse Table）
struct sparseTable
{
int g(int x, int y)
{
return std::max(x, y);
//需满足 g(x, x) = x
}
int f[maxn][maxk], log[maxn];
void init(int n, int a[])
{
for (int i = 1; i <= n; i++) log[i] = std::log2(i);
for (int i = 1; i <= n; i++) f[i][0] = a[i];
int K = std::log2(n);
for (int j = 1; j <= K; j++)
{
for (int i = 1; i <= n; i++)
{
if (i + (1 << (j - 1)) > n) f[i][j] = f[i][j - 1];
else f[i][j] = g(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r)
{
int t = log[r - l + 1];
return g(f[l][t], f[r - (1 << t) + 1][t]);
}
} ST;
- 集合与森林
- 【 6 】并查集
struct dsu
{
int fa[maxn], size[maxn];
void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i, size[i] = 1; }
int getFath(int u) { return fa[u] == u ? fa[u] : fa[u] = getFath(fa[u]); }
void follow(int u, int v)
{
int fu = getFath(u), fv = getFath(v);
if (size[fu] < size[fv]) fa[fu] = fv, size[fv] += size[fu];
else fa[fv] = fu, size[fu] += size[fv];
}
} D;
- 【 6 】树的孩子兄弟表示法
- 特殊树
-
【 6 】二叉堆
-
【 6 】树状数组
树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。
- 【 6 】线段树
struct segmentTree
{
struct node
{
int l, r;
long long sum, tag;
}
T[maxn * 4];
long long build(int p, int l, int r, long long a[])
{
T[p].l = l, T[p].r = r, T[p].tag = 0;
if (l == r) return T[p].sum = a[l];
else return T[p].sum = build(p << 1, l, (l + r) >> 1, a) + build((p << 1) + 1, ((l + r) >> 1) + 1, r, a);
}
void downData(int p)
{
T[p << 1].sum += T[p].tag * (T[p << 1].r - T[p << 1].l + 1), T[p << 1].tag += T[p].tag;
T[(p << 1) + 1].sum += T[p].tag * (T[(p << 1) + 1].r - T[(p << 1) + 1].l + 1), T[(p << 1) + 1].tag += T[p].tag;
T[p].tag = 0;
}
long long add(int p, int l, int r, long long k)
{
if (r < T[p].l || T[p].r < l) return T[p].sum;
else if (l <= T[p].l && T[p].r <= r) return T[p].tag += k, T[p].sum += k * (T[p].r - T[p].l + 1);
else return downData(p), T[p].sum = add(p << 1, l, r, k) + add((p << 1) + 1, l, r, k);
}
long long query(int p, int l, int r)
{
if (r < T[p].l || T[p].r < l) return 0;
else if (l <= T[p].l && T[p].r <= r) return T[p].sum;
else return downData(p), query(p << 1, l, r) + query((p << 1) + 1, l, r);
}
}
T;
- 【 6 】字典树（Trie 树）
struct trie
{
struct node
{
int val;
node *next[maxm];
node()
{
val = 0;
for (int i = 1; i <= 26; i++) next[i] = NULL;
}
};
node root;
void insert(char s[], int x)
{
node *p = &root;
int n = strlen(s + 1);
for (int i = 1; i <= n; i++)
{
int t = s[i] - 'a' + 1;
if (p -> next[t] == NULL) p -> next[t] = new node;
p = p -> next[t];
}
p -> val = x;
}
int find(char s[])
{
node *p = &root;
int n = strlen(s + 1);
for (int i = 1; i <= n; i++)
{
int t = s[i] - 'a' + 1;
if (p -> next[t] == NULL) return -1;
else p = p -> next[t];
}
if (p -> val == 0) return -1;
else return p -> val;
}
}
T;
- 【 7 】笛卡尔树
不会
- 【 8 】平衡树：AVL、treap、splay 等
不会
- 常见图
-
【 5 】稀疏图
-
【 6 】偶图（二分图）
struct Hungarian
{
int road[maxn], link[maxn], dfn;
bool dfs(int u)
{
for (int j = g.Last[u], v; j != 0; j = g.Next[j])
{
if (road[v = g.to[j]] == dfn) continue;
road[v] = dfn;
if (link[v] == -1 || dfs(link[v]))
{
link[v] = u;
return 1;
}
}
return 0;
}
int getMaxMatch(int n)
{
int ans = 0;
dfn = 0;
for (int i = 1; i <= n; i++) link[i] = road[i] = -1;
for (int i = 1; i <= n; i++)
{
dfn++;
ans += dfs(i);
}
return ans;
}
}
H;
-
【 6 】欧拉图
-
【 6 】有向无环图
-
【 7 】连通图与强连通图
-
【 7 】双连通图
- 哈希表
-
【 5 】数值哈希函数构造
-
【 6 】字符串哈希函数构造
-
【 6 】哈希冲突的常用处理方法
算法
- 复杂度分析
-
【 6 】时间复杂度分析
-
【 6 】空间复杂度分析
- 算法策略
- 【 6 】离散化
- 基础算法
- 【 6 】分治算法
- 排序算法
-
【 5 】归并排序
-
【 5 】快速排序
int a[maxn], b[maxn];
void qsort(int l, int r)
{
if (l >= r) return;
int x = a[(l + r) >> 1];
int i = l, j = r;
for (int k = l; k <= r; k++)
{
if (a[k] < x) b[i++] = a[k];
if (a[k] > x) b[j--] = a[k];
}
for (int k = l; k < i; k++) a[k] = b[k];
for (int k = i; k <= j; k++) a[k] = x;
for (int k = r; k > j; k--) a[k] = b[k];
qsort(l, i - 1), qsort(j + 1, r);
return;
}
-
【 6 】堆排序
-
【 5 】桶排序
-
【 6 】基数排序
- 字符串相关算法
- 【 5 】字符串匹配：KMP 算法
//不会
- 搜索算法
-
【 6 】搜索的剪枝优化
-
【 6 】记忆化搜索
-
【 7 】启发式搜索
-
【 7 】双向广度优先搜索
-
【 7 】迭代加深搜索
- 图论算法
-
【 6 】最小生成树：Prim 和 Kruskal 等算法
-
【 7 】次小生成树
//不会
- 【 6 】单源最短路：Bellman-Ford、Dijkstra、SPFA 等算法
bool mark[maxn];
long long dis[maxn];
void dijk(int n, int s)
{
std::priority_queue< std::pair<long long, int> > q;
for (int i = 1; i <= n; i++) mark[i] = 0;
for (int i = 1; i <= n; i++) dis[i] = 1LL << 60;
dis[1] = 0;
q.push(std::make_pair(0, 1));
while (!q.empty())
{
int u = q.top().second;
q.pop();
if (mark[u]) continue;
mark[u] = 1;
for (int j = g.Last[u]; j != 0; j = g.Next[j])
{
int v = g.to[j];
if (mark[v] == 1) continue;
if (dis[v] > dis[u] + g.w[j])
{
dis[v] = dis[u] + g.w[j];
q.push(std::make_pair(-dis[v], v));
}
}
}
return;
}
-
【 7 】单源次短路
-
【 6 】Floyd-Warshall 算法
-
【 6 】有向无环图的拓扑排序
-
【 6 】欧拉道路和欧拉回路
-
【 6 】二分图的判定
-
【 7 】强连通分量
struct Tarjan
{
int dfn[maxn], low[maxn];
int dfnCnt;
int scc[maxn], sccCnt;
int stack[maxn], top;
int mark[maxn];
void dfs(int u)
{
if (mark[u] == 1) return;
stack[++top] = u, mark[u] = 1;
dfn[u] = low[u] = ++dfnCnt;
for (int j = g.Last[u]; j != 0; j = g.Next[j])
{
int v = g.to[j];
if (dfn[v] == 0) dfs(v), low[u] = std::min(low[u], low[v]);
else if (mark[v]) low[u] = std::min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
sccCnt++;
int t;
do
{
t = stack[top--];
mark[t] = 0;
scc[t] = sccCnt;
}
while(t != u);
}
return;
}
void getScc(int n)
{
dfnCnt = sccCnt = top = 0;
for (int i = 1; i <= n; i++)
{
if (dfn[i] == 0)
{
dfnCnt = 0;
dfs(i);
}
}
}
}
T;
-
【 7 】割点、割边
-
【 6 】树的重心、直径、DFS 序与欧拉序
-
【 6 】树上差分、子树和与倍增
-
【 6 】最近公共祖先
struct LCA
{
int fa[maxn][maxk], depth[maxn];
int K;
void init(int n, int root)
{
K = std::log2(n);
dfs(root, 0);
for (int j = 1; j <= K; j++)
{
for (int i = 1; i <= n; i++)
{
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}
}
void dfs(int u, int fath)
{
fa[u][0] = fath, depth[u] = depth[fath] + 1;
for (int j = g.Last[u]; j != 0; j = g.Next[j])
{
int v = g.to[j];
if (v == fath) continue;
dfs(v, u);
}
}
int getLca(int u, int v)
{
if (depth[u] > depth[v]) std::swap(u, v);
for (int i = K; i >= 0; i--)
{
if (depth[fa[v][i]] >= depth[u]) v = fa[v][i];
}
if (u == v) return u;
for (int i = K; i >= 0; i--)
{
if (fa[u][i] != fa[v][i])
{
u = fa[u][i], v = fa[v][i];
}
}
return fa[u][0];
}
} L;
- 动态规划
-
【 6 】树型动态规划
-
【 7 】状态压缩动态规划
-
【 8 】动态规划的常用优化
数学及其他
- 初等数学
-
【 5 】代数（高中部分）
-
【 6 】几何（高中部分）
- 初等数论
-
【 5 】同余式
-
【 7 】欧拉定理和欧拉函数
-
【 7 】费马小定理
-
【 7 】威尔逊定理
-
【 7 】裴蜀定理
-
【 7 】模运算意义下的逆元
-
【 7 】扩展欧几里得算法
-
【 7 】中国剩余定理
- 离散与组合数学
-
【 6 】多重集合
-
【 6 】等价类
-
【 6 】多重集上的排列
-
【 6 】多重集上的组合
-
【 6 】错排列、圆排列
-
【 6 】鸽巢原理
-
【 6 】二项式定理
-
【 7 】容斥原理
-
【 7 】卡特兰（Catalan）数
- 线性代数
-
【 5 】向量与矩阵的概念
-
【 6 】向量的运算
-
【 6 】矩阵的初等变换
-
【 6 】矩阵的运算：加法、减法、乘法与转置
struct martix
{
int n, m;
long long mar[maxn][maxn];
martix(int _n, int _m)
{
n = _n, m = _m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
mar[i][j] = 0;
}
martix operator * (const martix &t) const
{
martix ans(n, t.m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= t.m; j++)
for (int k = 1; k <= m; k++)
ans.mar[i][j] = (ans.mar[i][j] + mar[i][k] * t.mar[k][j]) % mod;
return ans;
}
martix operator ^ (long long t) const
{
martix ans(n, m), x(n, m);
for (int i = 1; i <= n; i++)
ans.mar[i][i] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
x.mar[i][j] = mar[i][j];
while (t)
{
if (t & 1) ans = ans * x;
x = x * x;
t >>= 1;
}
return ans;
}
};
-
【 6 】特殊矩阵的概念：单位阵、三角阵、对称阵和稀疏矩阵
-
【 7 】高斯消元法