voidquick_sort(int q[], int l, int r) { if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); }
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用: intbsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用: intbsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }
浮点数二分
1 2 3 4 5 6 7 8 9 10 11 12 13
boolcheck(double x){/* ... */} // 检查x是否满足某种性质
doublebsearch_3(double l, double r) { constdouble eps = 1e-6; // eps 表示精度,取决于题目对精度的要求 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }
高精度
高精度加法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
// C = A + B, A >= 0, B >= 0 vector<int> add(vector<int> &A, vector<int> &B) { if (A.size() < B.size()) returnadd(B, A);
vector<int> C; int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; }
if (t) C.push_back(t); return C; }
高精度减法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// C = A - B, 满足A >= B, A >= 0, B >= 0 vector<int> sub(vector<int> &A, vector<int> &B) { vector<int> C; for (int i = 0, t = 0; i < A.size(); i ++ ) { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0; }
// C = A * b, A >= 0, b >= 0 vector<int> mul(vector<int> &A, int b) { vector<int> C;
int t = 0; for (int i = 0; i < A.size() || t; i ++ ) { if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; }
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C; }
高精度除以低精度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// A / b = C ... r, A >= 0, b > 0 vector<int> div(vector<int> &A, int b, int &r) { vector<int> C; r = 0; for (int i = A.size() - 1; i >= 0; i -- ) { r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
// 二分求出x对应的离散化的值 intfind(int x)// 找到第一个大于等于x的位置 { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; // 映射到1, 2, ...n }
int st = -2e9, ed = -2e9; for (auto seg : segs) if (ed < seg.first) { if (st != -2e9) res.push_back({st, ed}); st = seg.first, ed = seg.second; } else ed = max(ed, seg.second);
int son[N][26], cnt[N], idx; // 0号点既是根节点,又是空节点 // son[][]存储树中每个节点的子节点 // cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串 voidinsert(char *str) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) son[p][u] = ++ idx; p = son[p][u]; } cnt[p] ++ ; }
// 查询字符串出现的次数 intquery(char *str) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) return0; p = son[p][u]; } return cnt[p]; }
// 交换两个点,及其映射关系 voidheap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); }
voiddown(int u) { int t = u; if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t) { heap_swap(u, t); down(t); } }
voidup(int u) { while (u / 2 && h[u] < h[u / 2]) { heap_swap(u, u / 2); u >>= 1; } }
// 任取一点x,找到距离x最远点y,距离y最远距离即为树的直径 constint N = 1e5 + 10;
int h[N], e[2 * N], ne[2 * N], w[2 * N], idx; int dist[N]; //某点到其余各点距离 int n;
voidadd(int a, int b, int c) { e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++; }
voiddfs(int u, int father, int distance)//传入父节点,防止树向上遍历回去 { dist[u] = distance; for (int i = h[u]; i != -1; i = ne[i]) { if (e[i] != father) dfs(e[i], u, distance + w[i]); } }
intmain() { memset(h, -1, sizeof h); scanf("%d", &n); for (int i = 0; i < n - 1; i++)//树有n-1条边 { int a, b, c; scanf("%d %d %d", &a, &b, &c); add(a, b, c); add(b, a, c); } dfs(1, -1, 0); int mres = 1; //与1点距离最远点的编号 for (int i = 0; i <= n; i++) if (dist[i] > dist[mres]) mres = i; dfs(mres, -1, 0); for (int i = 0; i <= n; i++) if (dist[i] > dist[mres]) mres = i; int res = dist[mres]; printf("%lld", res * 10 + ((longlong)res + 1) * res / 2); return0; }
深搜
1 2 3 4 5 6 7 8 9 10
intdfs(int u) { st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); } }
for (int i = 0; i < n - 1; i ++ ) { int t = -1; // 在还未确定最短路的点中,寻找距离最小的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
structEdge { int a; int b; int w; } e[M];//把每个边保存下来即可 int dist[N]; int back[N];//备份数组防止串联 int n, m, k;//k代表最短路径最多包涵k条边
intbellman_ford(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < k; i++) {//k次循环 memcpy(back, dist, sizeof dist); for (int j = 0; j < m; j++) {//遍历所有边 int a = e[j].a, b = e[j].b, w = e[j].w; dist[b] = min(dist[b], back[a] + w); //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来 } } if (dist[n] > 0x3f3f3f3f / 2) return-1; elsereturn dist[n];
}
intmain(){ scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < m; i++) { int a, b, w; scanf("%d%d%d", &a, &b, &w); e[i] = {a, b, w}; } int res = bellman_ford(); if (res == -1) puts("impossible"); else cout << res;
queue<int> q; for (int i = 1; i <= n; i ++ ) { q.push(i); st[i] = true; }
while (q.size()) { auto t = q.front(); q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) returntrue; // 如果从1号点到x的最短路中包含至少n个点(不包括自己),则说明存在环 if (!st[j]) { q.push(j); st[j] = true; } } } }
returnfalse; }
floyd
多源最短路 O(n3)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
初始化: for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF;
// 算法结束后,d[a][b]表示a到b的最短距离 voidfloyd() { for (int k = 1; k <= n; k ++ ) for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }
int n; // n表示点数 int h[N], e[M], ne[M], idx; // 邻接表存储图 int color[N]; // 表示每个点的颜色,-1表示未染色,0表示白色,1表示黑色
// 参数:u表示当前节点,c表示当前点的颜色 booldfs(int u, int c) { color[u] = c; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (color[j] == -1) { if (!dfs(j, !c)) returnfalse; } elseif (color[j] == c) returnfalse; }
returntrue; }
boolcheck() { memset(color, -1, sizeof color); bool flag = true; for (int i = 1; i <= n; i ++ ) if (color[i] == -1) if (!dfs(i, 0)) { flag = false; break; } return flag; }
求二分图的最大匹配(匈牙利算法)
二分图的匹配:给定一个二分图 G,在 G 的一个子图 M 中,M 的边集 {E}中的任意两条边都不依附于同一个顶点,则称 M 是一个匹配。
int n1, n2; // n1表示第一个集合中的点数,n2表示第二个集合中的点数 int h[N], e[M], ne[M], idx; // 邻接表存储所有边,匈牙利算法中只会用到从第一个集合指向第二个集合的边,所以这里只用存一个方向的边 int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个 bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过
boolfind(int x) { for (int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; if (match[j] == 0 || find(match[j])) { match[j] = x; returntrue; } } }
returnfalse; }
// 求最大匹配数,依次枚举第一个集合中的每个点能否匹配第二个集合中的点 int res = 0; for (int i = 1; i <= n1; i ++ ) { memset(st, false, sizeof st); if (find(i)) res ++ ; }
数学知识
试除法判定是否为质数
1 2 3 4 5 6 7 8
boolis_prime(int x) { if (x < 2) returnfalse; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) returnfalse; returntrue; }
分解质因数
按照从小到大的顺序输出其分解质因数后,每个质因数的底数和指数,每个底数和指数占一行。
1 2 3 4 5 6 7 8 9 10 11 12
voiddivide(int x) { for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } if (x > 1) cout << x << ' ' << 1 << endl; cout << endl; }
vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); //如果i是x的约数那么x/i也一定是 } sort(res.begin(), res.end()); return res; }
intmain() { int n; cin >> n; unordered_map<int, int> primes; while (n -- ) { int x; cin >> x; for (int i = 2; i <= x / i; i ++ ) //套用分解质因数的那个模版 while (x % i == 0) { x /= i; primes[i] ++ ; } if (x > 1) primes[x] ++ ; } LL res = 1; for (auto p : primes) res = res * (p.second + 1) % mod; cout << res << endl; return0; } //约数之和 #include<iostream> #include<algorithm> #include<unordered_map> #include<vector>
usingnamespace std;
typedeflonglong LL;
constint N = 110, mod = 1e9 + 7;
intmain() { int n; cin >> n;
unordered_map<int, int> primes;
while (n -- ) { int x; cin >> x;
for (int i = 2; i <= x / i; i ++ ) while (x % i == 0) { x /= i; primes[i] ++ ; }
if (x > 1) primes[x] ++ ; }
LL res = 1; for (auto p : primes) { LL a = p.first, b = p.second; LL t = 1; while (b -- ) t = (t * a + 1) % mod; res = res * t % mod; }
cout << res << endl;
return0; }
辗转相除求最大公因数
1 2 3 4 5
intgcd(int a, int b) { return b ? gcd(b, a % b) : a; } // 最小公倍数 = a*b / gcd(a, b)
欧拉函数
1 2 3 4 5 6 7 8 9 10 11 12 13
intphi(int x) { int res = x; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { res = res / i * (i - 1); //先除再乘避免溢出 while (x % i == 0) x /= i; } if (x > 1) res = res / x * (x - 1);
usingnamespace std; intexgcd(int a, int b, int &x, int &y) { if (!b) { x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; }
intmain() { int n; scanf("%d", &n);
while (n -- ) { int a, b; scanf("%d%d", &a, &b); int x, y; exgcd(a, b, x, y); printf("%d %d\n", x, y); }
intgauss()// 高斯消元,答案存于a[i][n]中,0 <= i < n { int c, r; for (c = 0, r = 0; c < n; c ++ ) { int t = r; for (int i = r; i < n; i ++ ) // 找绝对值最大的行 if (fabs(a[i][c]) > fabs(a[t][c])) t = i;
if (fabs(a[t][c]) < eps) continue;
for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端 for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前行的首位变成1 for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0 if (fabs(a[i][c]) > eps) for (int j = n; j >= c; j -- ) a[i][j] -= a[r][j] * a[i][c];
r ++ ; }
if (r < n) { for (int i = r; i < n; i ++ ) if (fabs(a[i][n]) > eps) return2; // 无解 return1; // 有无穷多组解 }
for (int i = n - 1; i >= 0; i -- ) for (int j = i + 1; j < n; j ++ ) a[i][n] -= a[i][j] * a[j][n];
return0; // 有唯一解 }
intmain() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) for (int j = 0; j < n + 1; j ++ ) scanf("%lf", &a[i][j]);
int t = gauss(); if (t == 2) puts("No solution"); elseif (t == 1) puts("Infinite group solutions"); else { for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]); }
所有的区间dp问题枚举时,第一维通常是枚举区间长度,并且一般 len = 1 时用来初始化,枚举从 len = 2 开始;第二维枚举起点 i (右端点 j 自动获得,j = i + len - 1)
1 2 3 4 5 6 7 8 9 10 11 12 13
for (int len = 1; len <= n; len++) { // 区间长度 for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点 int j = i + len - 1; // 区间终点 if (len == 1) { dp[i][j] = 初始值 continue; }
for (int k = i; k < j; k++) { // 枚举分割点,构造状态转移方程 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]); } } }