基础算法模板 (CSP-J/S必备)

voidquickSort(int a[], int l, int r){    if (l >= r) return;    int i = l - 1, j = r + 1, x = a[l + r >> 1];    while (i < j) {        do i++; while (a[i] < x);        do j--; while (a[j] > x);        if (i < j) swap(a[i], a[j]);    }    quickSort(a, l, j);    quickSort(a, j + 1, r);}

int tmp[N];longlongmergeSort(int a[], int l, int r) {    if (l >= r) return 0;    int mid = l + r >> 1;    long long res = mergeSort(a, l, mid) + mergeSort(a, mid + 1, r);    int i = l, j = mid + 1, k = 0;    while (i <= mid && j <= r) {        if (a[i] <= a[j]) tmp[k++] = a[i++];        else {            tmp[k++] = a[j++];            res += mid - i + 1;   // 统计逆序对        }    }    while (i <= mid) tmp[k++] = a[i++];    while (j <= r) tmp[k++] = a[j++];    for (i = l, k = 0; i <= r; i++, k++) a[i] = tmp[k];    return res;}

// 整数二分：在升序数组中找到第一个 >= x 的位置intlower_bound(int a[], int n, int x) {    int l = 0, r = n - 1, ans = n;    while (l <= r) {        int mid = l + r >> 1;        if (a[mid] >= x) ans = mid, r = mid - 1;        else l = mid + 1;    }    return ans;}// 实数二分：求 sqrt(2) 的近似值doublesqrt2() {    double l = 1, r = 2;    for (int i = 0; i < 100; i++) {        // 循环固定次数        double mid = (l + r) / 2;        if (mid * mid > 2) r = mid;        else l = mid;    }    return l;}

vector<int> add(vector<int> &A, vector<int> &B){    vector<int> C;    int t = 0;    for (int i = 0; i < A.size() || i < B.size() || t; i++) {        if (i < A.size()) t += A[i];        if (i < B.size()) t += B[i];        C.push_back(t % 10);        t /= 10;    }    return C;}

int n, path[N];bool st[N];voiddfs(int u) {    if (u == n) {        for (int i = 0; i < n; i++) cout << path[i] << ' ';        cout << '\n';        return;    }    for (int i = 1; i <= n; i++) {        if (!st[i]) {            path[u] = i;            st[i] = true;            dfs(u + 1);            st[i] = false;        }    }}

int g[N][N], dist[N][N];int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};intbfs(int sx, int sy, int tx, int ty){    memset(dist, -1, sizeof dist);    queue<pair<int,int>> q;    q.push({sx, sy});    dist[sx][sy] = 0;    while (q.size()) {        auto [x, y] = q.front(); q.pop();        if (x == tx && y == ty) return dist[x][y];        for (int i = 0; i < 4; i++) {            int nx = x + dx[i], ny = y + dy[i];            if (nx>=0 && nx<n && ny>=0 && ny<n && g[nx][ny]==0 && dist[nx][ny]==-1) {                dist[nx][ny] = dist[x][y] + 1;                q.push({nx, ny});            }        }    }    return -1;}

// 一维前缀和int a[N], s[N];for (int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];// 查询 [l, r] 的和：s[r] - s[l-1]// 一维差分（区间加）int d[N];voidadd(int l, int r, int c) {    d[l] += c;    d[r+1] -= c;}// 最后求前缀和得到原数组for (int i = 1; i <= n; i++) d[i] += d[i-1];

int dp[M];for (int i = 1; i <= n; i++) {    int v, w; cin >> v >> w;    for (int j = m; j >= v; j--)        dp[j] = max(dp[j], dp[j - v] + w);}cout << dp[m];

char a[N], b[N];int f[N][N];for (int i = 1; i <= n; i++)    for (int j = 1; j <= m; j++)        if (a[i] == b[j]) f[i][j] = f[i-1][j-1] + 1;        else f[i][j] = max(f[i-1][j], f[i][j-1]);

typedef pair<int,int> PII;vector<PII> g[N];int dist[N];bool vis[N];voiddijkstra(int s){    memset(dist, 0x3f, sizeof dist);    priority_queue<PII, vector<PII>, greater<PII>> pq;    dist[s] = 0;    pq.push({0, s});    while (pq.size()) {        auto [d, u] = pq.top(); pq.pop();        if (vis[u]) continue;        vis[u] = true;        for (auto [v, w] : g[u]) {            if (dist[v] > dist[u] + w) {                dist[v] = dist[u] + w;                pq.push({dist[v], v});            }        }    }}

int dist[N], cnt[N];bool inq[N];bool spfa(int n, int s) { // 返回true表示有负环    memset(dist, 0x3f, sizeof dist);    queue<int> q;    dist[s] = 0; q.push(s); inq[s] = true;    while (q.size()) {        int u = q.front(); q.pop(); inq[u] = false;        for (auto [v, w] : g[u]) {            if (dist[v] > dist[u] + w) {                dist[v] = dist[u] + w;                cnt[v] = cnt[u] + 1;                if (cnt[v] >= n) return true; // 有负环                if (!inq[v]) q.push(v), inq[v] = true;            }        }    }    return false;}

struct Edge { int u, v, w; } e[M];int fa[N];int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }int kruskal(int n, int m) {    sort(e, e + m, [](Edge a, Edge b){ return a.w < b.w; });    for (int i = 1; i <= n; i++) fa[i] = i;    int res = 0, cnt = 0;    for (int i = 0; i < m; i++) {        int fu = find(e[i].u), fv = find(e[i].v);        if (fu != fv) {            fa[fu] = fv;            res += e[i].w;            cnt++;        }        if (cnt == n - 1) break;    }    return cnt == n - 1 ? res : -1; // -1表示不连通}

int dfn[N], low[N], idx, stk[N], top;bool ins[N];int scc[N], scnt;voidtarjan(int u) {    dfn[u] = low[u] = ++idx;    stk[++top] = u; ins[u] = true;    for (int v : g[u]) {        if (!dfn[v]) {            tarjan(v);            low[u] = min(low[u], low[v]);        } else if (ins[v])            low[u] = min(low[u], dfn[v]);    }    if (dfn[u] == low[u]) {        scnt++;        int y;        do {            y = stk[top--];            ins[y] = false;            scc[y] = scnt;        } while (y != u);    }}

int fa[N], sz[N];voidinit(int n){    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;}intfind(int x){ return x == fa[x] ? x : fa[x] = find(fa[x]); }voidunite(int a, int b){    a = find(a); b = find(b);    if (a == b) return;    if (sz[a] < sz[b]) swap(a, b);    fa[b] = a;    sz[a] += sz[b];}

int tr[N];int n;int lowbit(int x) { return x & -x; }void add(int x, int v) {    for (; x <= n; x += lowbit(x)) tr[x] += v;}int sum(int x) {    int res = 0;    for (; x > 0; x -= lowbit(x)) res += tr[x];    return res;}int range_sum(int l, int r) { return sum(r) - sum(l-1); }

struct SegTree {    int l, r;    long long sum, add;} tr[N * 4];voidbuild(int u, int l, int r) {    tr[u] = {l, r, 0, 0};    if (l == r) return;    int mid = l + r >> 1;    build(u<<1, l, mid);    build(u<<1|1, mid+1, r);}voidpushup(int u) {    tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;}voidpushdown(int u) {    if (tr[u].add) {        auto &root = tr[u], &left = tr[u<<1], &right = tr[u<<1|1];        left.add += root.add;        left.sum += (left.r - left.l + 1) * root.add;        right.add += root.add;        right.sum += (right.r - right.l + 1) * root.add;        root.add = 0;    }}voidmodify(int u, int l, int r, int v) {    if (tr[u].l >= l && tr[u].r <= r) {        tr[u].sum += (tr[u].r - tr[u].l + 1) * v;        tr[u].add += v;        return;    }    pushdown(u);    int mid = tr[u].l + tr[u].r >> 1;    if (l <= mid) modify(u<<1, l, r, v);    if (r > mid) modify(u<<1|1, l, r, v);    pushup(u);}longlongquery(int u, int l, int r) {    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;    pushdown(u);    int mid = tr[u].l + tr[u].r >> 1;    long long res = 0;    if (l <= mid) res += query(u<<1, l, r);    if (r > mid) res += query(u<<1|1, l, r);    return res;}

long long qpow(longlong a, longlong b, longlong p) {    long long res = 1;    while (b) {        if (b & 1) res = res * a % p;        a = a * a % p;        b >>= 1;    }    return res;}

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;}// 返回gcd，且x,y满足 a*x + b*y = gcd(a,b)

int primes[N], cnt;bool st[N];voidget_primes(int n) {    for (int i = 2; i <= n; i++) {        if (!st[i]) primes[cnt++] = i;        for (int j = 0; primes[j] <= n / i; j++) {            st[primes[j] * i] = true;            if (i % primes[j] == 0) break;        }    }}

char s[N], p[N];int ne[N];voidbuild_next(){    int n = strlen(p + 1);    for (int i = 2, j = 0; i <= n; i++) {        while (j && p[i] != p[j+1]) j = ne[j];        if (p[i] == p[j+1]) j++;        ne[i] = j;    }}voidkmp(){    int n = strlen(s + 1), m = strlen(p + 1);    for (int i = 1, j = 0; i <= n; i++) {        while (j && s[i] != p[j+1]) j = ne[j];        if (s[i] == p[j+1]) j++;        if (j == m) {            // 匹配成功，位置 i-m+1            j = ne[j];        }    }}

int son[N][26], cnt[N], idx;void insert(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]++;}int query(char *str) {    int p = 0;    for (int i = 0; str[i]; i++) {        int u = str[i] - 'a';        if (!son[p][u]) return 0;        p = son[p][u];    }    return cnt[p];}

int depth[N], fa[N][20];vector<int> g[N];voidbfs(int root){    memset(depth, 0x3f, sizeof depth);    depth[0] = 0; depth[root] = 1;    queue<int> q; q.push(root);    while (q.size()) {        int u = q.front(); q.pop();        for (int v : g[u]) {            if (depth[v] > depth[u] + 1) {                depth[v] = depth[u] + 1;                q.push(v);                fa[v][0] = u;                for (int k = 1; k <= 19; k++)                    fa[v][k] = fa[fa[v][k-1]][k-1];            }        }    }}intlca(int a, int b){    if (depth[a] < depth[b]) swap(a, b);    for (int k = 19; k >= 0; k--)        if (depth[fa[a][k]] >= depth[b])            a = fa[a][k];    if (a == b) return a;    for (int k = 19; k >= 0; k--)        if (fa[a][k] != fa[b][k])            a = fa[a][k], b = fa[b][k];    return fa[a][0];}