常用数据结构模板 并查集 数组实现栈 数组实现队列 单调队列 单调栈 单链表 双链表 堆 一般哈希 并查集时间复杂度O(1) 朴素并查集1234567891011121314int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点int find(int x){ if (p[x] != x) p[x] = find(p[x]); return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的两个集合：p[find(a)] = find(b); 维护集合中点的数量1234567891011121314151617181920//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量int p[N], size[N];// 返回x的祖宗节点int find(int x){ if (p[x] != x) p[x] = find(p[x]); return p[x];}/ ...

贪心区间问题 区间选点 区间合并 区间分组 最大不相交区间数量 区间覆盖 区间选点给定N个闭区间[ai, bi]，选择尽量少的点使得每个区间内至少包含一个选出的点。输出选择的点的最小数量时间复杂度O(nlogn) 1234567891011121314151617181920212223242526272829303132333435363738#include <iostream>#include <algorithm>#define fi first#define se secondtypedef pair<int, int> PII;const int N = 100010;int n;PII a[N];int main(){ cin >> n; for (int i = 0; i < n; i ++ ) { int l, r; scanf("%d%d", &l, &r); a[i] = {r, l& ...

标题11# 标题1 标题21## 标题2 标题31### 标题3 标题41#### 标题4 标题51##### 标题5 标题61###### 标题6 代码块： 1#include <iostream> ```c++#include ``` 1print("Hello, world") ```pythonprint(“Hello, world”)``` 引用 1> 引用 有序列表: test1 test2 test3 1231. test12. test23. test3 无序列表： test1 test2 test3 123- test1- test2- test3 123* test1* test2* test3 数学公式：$$a = b + c$$ 123$$a = b + c$$ 表格 左”:”左对齐，右”:”右对齐，两个”:”居中对齐 姓名 年龄 成绩 张三 20 99 李四 19 98 ...

背包问题 01背包 分组背包 完全背包 01背包求方案 背包问题求方案数 多重背包 混合背包 有依赖的背包问题 01背包一维费用题目 朴素 123456789101112131415161718192021222324#include <iostream>using namespace std;const int N = 1010;int n, m, f[N][N], v[N], w[N];int main(){ cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) { f[i][j] = f[i - 1][j]; if (j >= v[i]) f[i][j] = max(f[i][j], f ...

数论基础算法模板 求组合数 exgcd 快速幂求逆元 欧拉函数 高斯消元 矩阵快速幂 扩展中国剩余定理excrt a^phi(n)^ ≡ 1 (mod n) 在gcd(a, n) = 1下成立 求组合数时间复杂度(O(n^2^))123456789int C[N][N];void init(){ for (int a = 0; a < N; a ++ ) for (int b = 0; b <= a; b ++ ) if (!b) C[a][b] = 1; else C[a][b] = C[a - 1][b - 1] + C[a - 1][b];} 时间复杂度(O(nlogn))12345678910111213141516171819202122232425262728293031323334353637383940414243444546//首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]//如果取模的数是质数，可以用费马小定理求逆元# ...