Zelda_max的代码模板（持续更新）

Zelda_max · 2026-02-05 12:30:19 · 算法·理论

图

• kruskral

  • 通过不断枚举并添加点来解决最小生成树问题。

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N = 5000, M = 3000;
    const int INF = 0x3f3f3f3f;
    int p[N], n, m;
    int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
    }
    struct Edge {
    int a, b, w;
    bool operator<(const Edge &W) const {return w < W.w;}
    } edges[M];
    int kruskal() {
    sort(edges, edges + m);;
    for(int i = 1; i <= n; i++) p[i] = i;
    int res = 0, cnt = 0;
    for(int i = 0; i < m; i++) {
    int a = edges[i].a, b = edges[i].b, w = edges[i].w;
    a = find(a), b = find(b);
    if(a != b) {
        p[a] = b;
        res += w;
        cnt++;
    }
    }
    if(cnt < n - 1) return INF;
    return res;
    }
    signed main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    edges[i] = {u, v, w};
    }
    int  = kruskal();
    return 0;
    }

• prim

  • 作用和 kruskal 类似，通过枚举边并添加边解决最小生成树问题。

    #include<bits/stdc++.h>
    using namespace std;
    const int N = , INF = 0x3f3f3f3f;
    int n;
    int g[N][N], dist[N];
    bool st[N];
    int prim() {
    memset(dist, 0x3f, sizeof(dist));
    int res = 0;
    for(int i = 0; i < n; i++) {
    int t = -1;
    for(int j = 1; j <= n; j++) {
        if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
    }
    if(i != 0 && dist[t] == INF) return INF;
    if(i != 0) res += dist[t];
    st[t] = true;
    for(int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
    }
    return res;
    }
    int main() {
    int m;
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    for(int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u][v] = g[v][u] = min(g[u][v], w);
    }
    int  = prim();
    return 0;
    }

• dijkstra

  • 可以解决求一个点到其他点的最短路问题。

    #include<bits/stdc++.h>
    using namespace std;
    int n, m, s, t;
    double g[105][105], dist[105];
    bool st[105];
    void dijkstra(int start) {
    for(int i = 1; i <= n; i++) {
      dist[i] = g[start][i];
    }
    dist[start] = 0;
    st[start] = 1;
    for(int i = 1; i < n; i++) {
      int t = -1;
      for(int j = 1; j <= n; j++) {
          if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j; 
      }
      st[t] = 1;
      for(int j = 1; j <= n; j++) {
          if(!st[j] && dist[t] + g[t][j] < dist[j]) {
              dist[j] = dist[t] + g[t][j];
          }
      }
    }
    }
    int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= n; j++) {
          g[i][j] = 1e9;
      }
      g[i][i] = 0;
    }
    
    dijkstra(s);
    return 0;
    }

树

• 线段树

  • 通过将数组不断拆分成零散的区间来求解区间值或对区间操作问题。

    #include<bits/stdc++.h>
    using namespace std;
    int n, q;
    long long a[1000001];
    struct Segment_Tree {
    struct Node {
    int l, r;
    long long sum, lazy;
    };
    vector<Node> tr;
    Segment_Tree(int n) {
    tr.resize(n * 4);
    }
    void pushup(int x) {
    //线段树基本操作
    tr[x].sum = (tr[x * 2].sum + tr[x * 2 + 1].sum);
    }
    void build(int x, int l, int r) {
    //建树
    tr[x].l = l, tr[x].r = r;
    tr[x].lazy = 0;
    if(l == r) {
        tr[x].sum = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * x, l, mid);
    build(2 * x + 1, mid + 1, r);
    pushup(x);
    }
    void pushdown(int x) {
    //下发懒标记
    if(tr[x].lazy != 0) {
        int l = tr[x].l, r = tr[x].r;
        int mid = (l + r) / 2;
        long long lazy_val = tr[x].lazy;
        tr[2 * x].sum += (mid - l + 1) * lazy_val;
        tr[2 * x].lazy += lazy_val;
        tr[2 * x + 1].sum += (r - mid) * lazy_val;
        tr[2 * x + 1].lazy += lazy_val;
        tr[x].lazy = 0;
    }
    }
    void update(int x, int l, int r, int ul, int ur, long long val) {
    //更新函数
    if(ul <= l && ur >= r) {
        tr[x].sum += (r - l + 1) * val;
        tr[x].lazy += val;
        return;
    }
    pushdown(x);
    int mid = (l + r) / 2;
    if(ul <= mid) update(2 * x, l, mid, ul, ur, val);
    if(ur > mid) update(2 * x + 1, mid + 1, r, ul, ur, val);
    pushup(x);
    }
    long long query(int x, int l, int r, int ql, int qr) {
    //查询区间函数
    if(ql <= l && r <= qr) return tr[x].sum;
    pushdown(x);
    int mid = (l + r) / 2;
    long long res = 0;
    if(ql <= mid) res = (res + query(2 * x, l, mid, ql, qr));
    if(qr > mid) res = (res + query(2 * x + 1, mid + 1, r, ql, qr));
    return res;
    }
    };
    void solve();
    signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    }
    void solve() {
    scanf("%d%d", &n, &q);
    Segment_Tree seg(n * 4);
    seg.build(1, 1, n);
    for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    }
    while(q--) {
    int op, x, y;
    long long k;
    scanf("%d%d%d", &op, &x, &y);
    if(op == 1) {
        scanf("%lld", &k);
        seg.update(1, 1, n, x, y, k);
    } else {
        printf("%lld\n", seg.query(1, 1, n, x, y));
    }
    }
    exit(0);
    }

• 并查集

  • 也可以用于图。

    #include<bits/stdc++.h>
    using namespace std;
    struct DSU {
    std::vector<int> f, siz;
    DSU(int n) : f(n+1), siz(n+1, 1) {
    std::iota(f.begin(), f.end(), 0);
    }
    int leader(int x) {
    while(x != f[x]) x = f[x] = f[f[x]];
    return x;
    }
    bool same(int x, int y) {
    return leader(x) == leader(y);
    }
    bool merge(int x, int y) {
    x = leader(x);
    y = leader(y);
    if(x == y) return false;
    siz[x] += siz[y];
    f[y] = x;
    return true;
    }
    int size(int x) {
    return siz[leader(x)];
    }
    };
    int main() {
    int n;
    scanf("%d", &n);
    DSU dsu(n);
    return 0;
    }

    数据结构

数论

• 高精度加法（无负数）

  • 解决大整数加法。

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 5;
    long long n;
    int a[N], b[N], c[N], ans[N];
    int main() {
    string sa, sb;
    cin >> sa >> sb;
    reverse(sa.begin(), sa.end());
    reverse(sb.begin(), sb.end());
    int la = sa.size(), lb = sb.size();
    for(int i = 0; i < sa.length(); i++) a[i] = sa[i] - '0';
    for(int i = 0; i < sb.length(); i++) b[i] = sb[i] - '0';
    int l = max(la, lb);
    for(int i = 0; i < l; i++) {
    ans[i] += a[i] + b[i];
    if(ans[i] >= 10) {
        ans[i+1] = ans[i] / 10;
        ans[i] = ans[i] % 10;
    }
    }
    if(ans[l] != 0) l++;
    int cnt = l - 1;
    while(ans[cnt] == 0) cnt--;
    for(int i = cnt; i >= 0; i--) cout << ans[i];
    return 0;
    }

• 高精度减法（被减数减数不能同时为 0）

  • 大整数减法。

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 5;
    long long n;
    int a[N], b[N], c[N], ans[N];
    int main() {
    string sa, sc;
    cin >> sa >> sc;
    reverse(sa.begin(), sa.end());
    reverse(sc.begin(), sc.end());
    int la = sa.length();
    int lc = sc.length();
    if(la < lc || (la == lc && sa < sc)) {
    cout << '-';
    swap(sa, sc);
    }
    for(int i = 0; i < sa.length(); i++) a[i] = sa[i] - '0';
    for(int i = 0; i < sc.length(); i++) b[i] = sc[i] - '0';
    int l = max(la, lc);
    for(int i = 0 ; i < l; i++) {
    if(a[i] < b[i]) {
        a[i] += 10;
        a[i+1] -= 1;
    }
    a[i] -= b[i];
    }
    while(l > 0 && a[l] == 0) l--;
    for(int i = l; i >= 0; i--) cout << a[i];
    return 0;
    }

• 高精度乘法（无负数）

  • 大整数乘法。

    #include<bits/stdc++.h>
    using namespace std;
    vector<int> A, B;
    vector<int> mul(vector<int> &A, vector<int> &B) {
    vector<int> C(A.size() + B.size(), 0);
    for(int i = 0; i < A.size(); i++) {
    for(int j = 0; j < B.size(); j++) {
        C[i + j] += A[i] * B[j];
    }
    }
    int t = 0;
    for(int i = 0; i < C.size(); i++) {
    t += C[i];
    C[i] = t % 10;
    t /= 10;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
    }
    int main() {
    string a, b;
    cin >> a >> b;
    for(int i = a.size()-1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size()-1; i >= 0; i--) B.push_back(b[i] - '0');
    vector<int>C = mul(A, B);
    for(int i = C.size()-1; i >= 0; i--) cout << C[i];
    cout << endl;
    return 0;
    }

• 高精度除法（无负数）

  • 大整数除法。

    #include<bits/stdc++.h>
    using namespace std;
    bool cmp(vector <int> A, vector <int> B) {
    if(A.size() != B.size()) return A.size() > B.size();
    for(int i = 0; i < A.size(); i++) {
    if(A[i] == B[i]) continue;
    return A[i] > B[i];
    }
    return true;
    }
    vector <int> sub(vector<int> A, vector<int> B) {
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());
    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);
    t < 0 ? t = 1 : t = 0;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    reverse(C.begin(), C.end());
    return C;
    }
    vector <int> div(vector <int> A, vector <int> B, vector <int> &R) {
    vector <int> C;
    if(!cmp(A, B)) {
    C.push_back(0);
    R = A;
    return C;
    }
    int len_b = B.size();
    while(B.size() < A.size()) B.push_back(0);
    while(B.size() >= len_b) {
    int x = 0;
    while(cmp(A, B)) {
        A = sub(A, B);
        x++;
    }
    C.push_back(x);
    B.pop_back();
    }
    reverse(C.begin(), C.end());
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    reverse(C.begin(), C.end());
    R = A;
    return C;
    }
    int main() {
    vector <int> A, B, C, R;
    string a, b;
    cin >> a >> b;
    for(int i = 0; i < a.size(); i++) A.push_back(a[i] - '0');
    for(int i = 0; i < b.size(); i++) B.push_back(b[i] - '0');
    C = div(A, B, R);
    for(int i = 0; i < C.size(); i++) cout << C[i];
    cout << endl;
    for(int i = 0; i < R.size(); i++) cout << R[i];
    return 0;
    }

    快速计算 a^b\mod{p}。

    #include<bits/stdc++.h>
    using namespace std;
    long long qpow(int a, int b, int p) {
    long long res = 1 % p;
    a %= p;
    while(b) {
    if(b & 1) res = res * a % p;
    a = 1LL * a * a % p;
    b >>= 1;
    }
    return res % p;
    }
    int main() {
    int n, m, mod;
    cin >> n >> m >> mod;
    cout << qpow(n, m, mod);
    return 0;
    }

• 矩阵快速幂

  • 矩阵快速幂。

    #include<bits/stdc++.h>
    using namespace std;
    const int mod = 1000000007;
    struct Matrix {
    int n;
    vector<vector<long long>> data;
    Matrix(int size) : n(size), data(size, vector<long long>(size, 0)) {}
    Matrix operator*(const Matrix& other) const {
      Matrix res(n);
      for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) {
              for (int k = 0; k < n; k++) {
                  res.data[i][j] = (res.data[i][j] + data[i][k] * other.data[k][j]) % mod;
              }
          }
      }
      return res;
    }
    };
    Matrix pow(Matrix base, long long exp) {
    int n = base.n;
    Matrix res(n);
    for(int i = 0; i < n; i++) res.data[i][i] = 1;
    while(exp > 0) {
      if(exp & 1) res = res * base;
      base = base * base;
      exp >>= 1;
    }
    return res;
    }
    int main() {
    int n;
    long long k;
    cin >> n >> k;
    Matrix a(n);
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
          cin >> a.data[i][j];
          a.data[i][j] %= mod;
          if(a.data[i][j] < 0) a.data[i][j] += mod;
      }
    }
    Matrix res = pow(a, k);
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
          cout << res.data[i][j] % mod;
          if (j < n - 1) cout << ' ';
      }
      cout << "\n";
    }
    return 0;
    }

• Lucas 算法

  • 解决 C_{n+m}^{n}\mod{p} 的问题。

    
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    int a[200001], b[200001];
    int qpow(int x, int y, int p) {
    int res = 1;
    while(y > 0) {
      if(y & 1) res = res * x % p;
      x = x * x % p;
      y >>= 1;
    }
    return res;
    }
    int comb(int n, int k, int p) {
    if(k < 0 || k > n) return 0;
    if(k == 0 || k == n) return 1;
    if(n < p) {
      a[0] = 1;
      for(int i = 1; i <= n; i++) a[i] = a[i-1] * i % p;
      b[n] = qpow(a[n], p-2, p);
      for(int i = n-1; i >= 0; i--) b[i] = b[i+1] * (i+1) % p;
      return a[n] * b[k] % p * b[n-k] % p;
    }
    return comb(n/p, k/p, p) * comb(n%p, k%p, p) % p;
    }

  signed main() { int t; cin >> t; while(t--) { int n, m, p; cin >> n >> m >> p; cout << comb(n + m, m, p) << "\n"; } return 0; }

• 中国剩余定理

  • 解如下方程中 x 的最小整数解。 \begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll fast_mul(ll a, ll b, ll mod) {
    ll res = 0;
    a %= mod;
    if (b < 0) {
    a = -a;
    b = -b;
    }
    while (b > 0) {
    if (b & 1) res = (res + a) % mod;
    a = (a * 2) % mod;
    b >>= 1;
    }
    return res;
    }
    ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(!b) {
    x=1,y=0;
    return a;
    }
    ll d = exgcd(b,a%b,x,y);
    ll t = x;
    x = y;
    y = t - a/b*y;
    return d;
    }
    ll crt(int n, ll *ai, ll *mi) {
    ll m = 1, ans = 0;
    for(int i=1; i<=n; i++) m *= mi[i];
    for(int i=1; i<=n; i++) {
    ll Mi = m / mi[i], ti, y;
    exgcd(Mi, mi[i], ti, y);
    ans = (ans + ai[i] * Mi * ti % m) % m;
    }
    return (ans % m + m) % m;
    }
    int main() {
    int n;
    cin >> n;
    ll M, ans;
    cin >> M >> ans;
    for(int i = 1; i < n; i++) {
    ll m2, r2;
    cin >> m2 >> r2;
    ll c = r2 - ans, t, y;
    ll g = exgcd(M, m2, t, y);
    ll mod_for_t = m2 / g;
    t = fast_mul(t, c / g, mod_for_t);
    t = (t % mod_for_t + mod_for_t) % mod_for_t;
    ll M_old = M;
    M = M_old / g * m2;
    ans = ans + t * M_old;
    ans = (ans % M + M) % M;
    }
    cout << ans;
    return 0;
    }

• 扩展中国剩余定理

  • 同上，能解决更强数据。

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll fast_mul(ll a, ll b, ll mod) {
    ll res = 0;
    a %= mod;
    if (b < 0) {
    a = -a;
    b = -b;
    }
    while (b > 0) {
    if (b & 1) res = (res + a) % mod;
    a = (a * 2) % mod;
    b >>= 1;
    }
    return res;
    }
    ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(!b) {
    x=1,y=0;
    return a;
    }
    ll d = exgcd(b,a%b,x,y);
    ll t = x;
    x = y;
    y = t - a/b*y;
    return d;
    }
    ll crt(int n, ll *ai, ll *mi) {
    ll m = 1, ans = 0;
    for(int i=1; i<=n; i++) m *= mi[i];
    for(int i=1; i<=n; i++) {
    ll Mi = m / mi[i], ti, y;
    exgcd(Mi, mi[i], ti, y);
    ans = (ans + ai[i] * Mi * ti % m) % m;
    }
    return (ans % m + m) % m;
    }
    int main() {
    int n;
    cin >> n;
    ll M, ans;
    cin >> M >> ans;
    for(int i = 1; i < n; i++) {
    ll m2, r2;
    cin >> m2 >> r2;
    ll c = r2 - ans, t, y;
    ll g = exgcd(M, m2, t, y);
    ll mod_for_t = m2 / g;
    t = fast_mul(t, c / g, mod_for_t);
    t = (t % mod_for_t + mod_for_t) % mod_for_t;
    ll M_old = M;
    M = M_old / g * m2;
    ans = ans + t * M_old;
    ans = (ans % M + M) % M;
    }
    cout << ans;
    return 0;
    }

• 高斯消元法

  • 利用高斯消元法解如下的方程组的解。 \begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}

    #include<bits/stdc++.h>
    using namespace std;
    const double eps = 1e-6;
    int n;
    const int N = 110;
    double a[N][N + 1];
    int gauss() {
    int r = 0;
    for(int c = 0; c < n; c++) {
      int maxx = r;
      for(int i = r + 1; i < n; i++) {
          if(abs(a[i][c]) > abs(a[maxx][c])) {
              maxx = i;
          }
      }
      if(abs(a[maxx][c]) < eps) continue;
      for(int j = c; j <= n; j++) {
          swap(a[r][j], a[maxx][j]);
      }
      double div = a[r][c];
      for(int j = c; j <= n; j++) {
          a[r][j] /= div;
      }
      for(int i = 0; i < n; i++) {
          if(i == r) continue;
          if(abs(a[i][c]) > eps) {
              double cnt = a[i][c];
              for(int j = c; j <= n; j++) {
                  a[i][j] -= cnt * a[r][j];
              }
          }
      }
      r++;
    }
    for(int i = r; i < n; i++) {
    if(abs(a[i][n]) > eps) {
          return -1;
      }
    }
    if(r < n) return 0;
    return 1;
    }
    int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n + 1; j++) {
          cin >> a[i][j];
      }
    }
    int res = gauss();
    if(res == -1) {
      cout << "No Solution\n";
    } else if(res == 0) {
      cout << "No Solution\n";
    } else {
      for(int i = 0; i < n; i++) {
          printf("%.2lf\n", a[i][n]);
      }
    }
    return 0;
    }

动态规划

搜索

查找

• 树状数组 1

  • 区间查询，单点修改的树状数组。

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    int n;
    int a[1000001];
    int lowbit(int x) {
    return x & -x;
    }
    void add(int st, int val) {
    while(st <= n) {
    a[st] += val;
    st += lowbit(st);
    }
    }
    int sum(int st) {
    int x = 0;
    while(st > 0) {
    x += a[st];
    st -= lowbit(st);
    }
    return x;
    }
    void solve();
    signed main() {
    solve();
    }
    void solve() {
    int t;
    cin >> n >> t;
    for(int i = 1, x; i <= n; i++) {
    cin >> x;
    add(i, x);
    }
    while(t--) {
    int x, y, z;
    cin >> x >> y >> z;
    if(x == 1) {
        add(y, z);
    } else {
        cout << (sum(z) - sum(y-1)) << "\n";
    }
    }
    exit(0);
    }

• 树状数组 2

  • 单点查询，区间修改的树状数组。

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    int n;
    int a[1000001];
    int lowbit(int x) {
    return x & -x;
    }
    void add(int st, int val) {
    while(st <= n) {
    a[st] += val;
    st += lowbit(st);
    }
    }
    int sum(int st) {
    int x = 0;
    while(st > 0) {
    x += a[st];
    st -= lowbit(st);
    }
    return x;
    }
    void solve();
    signed main() {
    solve();
    }
    void solve() {
    int t;
    cin >> n >> t;
    for(int i = 1, x; i <= n; i++) {
    cin >> x;
    add(i, x);
    }
    while(t--) {
    int x, y, z;
    cin >> x >> y >> z;
    if(x == 1) {
        add(y, z);
    } else {
        cout << (sum(z) - sum(y-1)) << "\n";
    }
    }
    exit(0);
    }

• ST 表

  • 以 O(1) 的时间复杂度查询区间最大值。

    #include<bits/stdc++.h>
    //#define int long long
    using namespace std;
    int a[100001], b[100001], cnt[100001][18];
    void solve();
    signed main() {
    solve();
    }
    int q(int l, int r) {
    int i = b[r-l+1];
    int x = max(cnt[l][i], cnt[r-(1 << i)+1][i]);
    return x;
    }
    void solve() {
    int n, m;
    scanf("%d%d", &n, &m);
    b[1] = 0;
    b[2] = 1;
    for(int i = 3; i <= 100001; i++) {
    b[i] = b[i >> 1] + 1;
    }
    for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    cnt[i][0] = a[i];
    }
    for(int j = 1; (1 << j)-1 <= n; j++) {
    for(int i = 1; i + (1 << j) - 1 <= n; i++) {
        cnt[i][j] = max(cnt[i + (1 << (j-1))][j-1], cnt[i][j-1]);
    }
    }
    while(m--) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", q(l, r));
    }
    exit(0);
    }

    杂项