自己敲模板还是有很多容易错的地方
写在注释里面了
LCA
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; const int N = 5e5 + 10; //以后MAXN改成N。因为MAXM和MAXN不容易区分 const int M = 20; struct Edge{ int to, next; } e[N << 1]; int head[N], tot, n, m, s; int d[N], f[N][M + 10]; //注意这里一定一定是M+10 void AddEdge(int from, int to) { e[tot] = Edge{to, head[from]}; head[from] = tot++; } void dfs(int u, int fa) //dfs的作用是初始化f数组和d数组 { for(int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if(v == fa) continue; d[v] = d[u] + 1; f[v][0] = u; dfs(v, u); } } void init() { f[s][0] = s; //注意这里一定是自己的父亲为自己 dfs(s, -1); _for(j, 1, M) //注意这里是到M，不是N _for(i, 1, n) f[i][j] = f[f[i][j-1]][j-1]; } int lca(int u, int v) { if(d[u] < d[v]) swap(u, v); //u和v不要写反 for(int j = M; j >= 0; j--) //逆序 if(d[f[u][j]] >= d[v]) //这里注意是深度的比较，u往上跳的深度和v本身的深度 u = f[u][j]; if(u == v) return u; for(int j = M; j >= 0; j--) if(f[u][j] != f[v][j]) u = f[u][j], v = f[v][j]; return f[u][0]; } int main() { memset(head, -1, sizeof(head)); tot = 0; scanf("%d%d%d", &n, &m, &s); REP(i, 1, n) { int u, v; scanf("%d%d", &u, &v); AddEdge(u, v); AddEdge(v, u); } init(); //主函数里面不要忘了写 _for(i, 1, m) { int u, v; scanf("%d%d", &u, &v); printf("%d ", lca(u, v)); } return 0; }
线段树
#include<bits/stdc++.h> #define ls (k << 1) #define rs (k << 1 | 1) #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; typedef long long ll; //根据题目 const int N = 2e5 + 10; struct Segment_Tree { int l, r; ll w, f; int m() { return (l + r) >> 1; } int len() { return r - l + 1; }; }t[N * 3]; int n, q; inline void deal(int k, ll p) { t[k].f += p; t[k].w += p * t[k].len(); } inline int up(int k) { t[k].w = t[ls].w + t[rs].w; } inline void down(int k) { deal(ls, t[k].f); deal(rs, t[k].f); t[k].f = 0; } void build(int k, int l, int r) { t[k] = Segment_Tree{l, r, 0, 0}; if(l == r) { scanf("%lld", &t[k].w); return; } int m = t[k].m(); build(ls, l, m); build(rs, m + 1, r); up(k); } void add(int k, int x, ll p) { if(t[k].l == t[k].r) //注意这里一定是这么写，不能写t[k].l == x，这是错的 { t[k].w += p; return; } if(t[k].f) down(k); int m = t[k].m(); if(x <= m) add(ls, x, p); else add(rs, x, p); up(k); } void change(int k, int L, int R, ll p) { if(L <= t[k].l && t[k].r <= R) { deal(k, p); return; } if(t[k].f) down(k); int m = t[k].m(); if(L <= m) change(ls, L, R, p); if(R > m) change(rs, L, R, p); up(k); } ll query(int k, int L, int R) { if(L <= t[k].l && t[k].r <= R) return t[k].w; if(t[k].f) down(k); int m = t[k].m(); ll res = 0; if(L <= m) res += query(ls, L, R); if(R > m) res += query(rs, L, R); return res; } int main() { scanf("%d", &n); build(1, 1, n); scanf("%d", &q); while(q--) { int op, x, y; ll z; scanf("%d", &op); if(op == 1) { scanf("%d%d%lld", &x, &y, &z); change(1, x, y, z); } else { scanf("%d%d", &x, &y); printf("%lld ", query(1, x, y)); } } return 0; }
KMP
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; const int N = 1e6 + 10; char a[N], b[N]; int next[N], lena, lenb; void get_next() { next[1] = 0; int j = 0; //注意这里从0开始。因为一开始匹配了0个 _for(i, 2, lenb) //这里的i从2开始 { while(j && b[j + 1] != b[i]) j = next[j]; if(b[j + 1] == b[i]) j++; next[i] = j; } } int main() { scanf("%s%s", a + 1, b + 1); lena = strlen(a + 1); lenb = strlen(b + 1); get_next(); int j = 0; _for(i, 1, lena) //这里的i从1开始 { while(j && b[j + 1] != a[i]) j = next[j]; if(b[j + 1] == a[i]) j++; if(j == lenb) { printf("%d %d ", i - lenb + 1, i); return 0; } } puts("NO"); return 0; }
同余方程
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; typedef long long ll;//如果考到数论题一定要开longlong！！！！！！！！ void exgcd(ll a, ll b, ll& d, ll& x, ll& y) { if(!b) { d = a; x = 1; y = 0; return; } else { exgcd(b, a % b, d, y, x); y -= x * (a / b); } } int main() { ll a, b, m; scanf("%lld%lld%lld", &a, &b, &m); ll A, B, K, d, x, y; A = a, B = -m, K = b; exgcd(A, B, d, x, y); if(K % d) { puts("no solution!"); return 0; } x *= K / d; int mod = abs(B / d); printf("%lld ", (x % mod + mod) % mod); return 0; }
同余方程组
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; typedef long long ll; void exgcd(ll a, ll b, ll& d, ll& x, ll& y) { if(!b) { d = a; x = 1; y = 0; return; } else { exgcd(b, a % b, d, y, x); y -= x * (a / b); } } int main() { int n; ll b1, b2, m1, m2; scanf("%d%lld%lld", &n, &b1, &m1); REP(i, 1, n) { scanf("%lld%lld", &b2, &m2); ll A, B, K, d, x, y; A = m1, B = -m2, K = b2 - b1; //推出什么写什么 exgcd(A, B, d, x, y); if(K % d) { puts("no solution!"); return 0; } x *= K / d; int mod = abs(B / d); //注意这里加abs x = (x % mod + mod) % mod; b1 = b1 + m1 * x; m1 = m1 * m2 / abs(d); //加abs } printf("%lld ", b1); return 0; }
欧拉函数
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; typedef long long ll; ll euler(ll x) { ll res = x; //注意区分res和x。x是用来取出因数的 for(int i = 2; i * i <= x; i++) if(x % i == 0) { res = res / i * (i - 1); //先除后乘比较保险，可以这么做是因为i是res的因数 while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res; } int main() { int n; scanf("%d", &n); _for(i, 1, n) { ll x; scanf("%lld", &x); printf("%lld ", euler(x)); } return 0; }
//线性求法 const int N = 1e6 + 10; int euler[N]; void get_euler() { REP(i, 1, N) euler[i] = i; REP(i, 2, N) //注意这里i从2开始。 if(euler[i] == i) for(int j = i; j < N; j += i) euler[j] = euler[j] / i * (i - 1); }
线性筛素数
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; const int N = 2e7 + 10; bool is_prime[N]; vector<int> prime; void get_prime() { memset(is_prime, true, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; REP(i, 2, N) //切记不能越界 { if(is_prime[i]) prime.push_back(i); REP(j, 0, prime.size()) { if(i * prime[j] >= N) break; //切记不能越界 is_prime[i * prime[j]] = false; if(i % prime[j] == 0) break; } } } int main() { get_prime(); int n; scanf("%d", &n); _for(i, 1, n) { int x; scanf("%d", &x); printf("%d ", prime[x-1]); } return 0; }
组合数
const int N = 1e3 + 10; int c[N][N]; void init() { REP(i, 0, N) //从0开始 { c[i][0] = 1; _for(j, 1, i) c[i][j] = c[i-1][j] + c[i-1][j-1]; } }
卡特兰数
f[1] = 1; REP(i, 2, N) f[i] = f[i-1] * (4 * i - 2) / (i + 1);