Acwing 算法基础课 c++模板整理（附python语法基础题）

这里写目录标题

#include 
using namespace std;
const int N = 100010;
int q[N];
void quick_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);
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第 $k$ 个数

#include 
using namespace std;
const int N = 100010;
int q[N];
int quick_sort(int q[], int l, int r, int k){
    if (l >= r) return q[l];
    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]);
    }
    if (j - l + 1 >= k) return quick_sort(q, l, j, k);
    else return quick_sort(q, j + 1, r, k - (j - l + 1));
}
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    cout << quick_sort(q, 0, n - 1, k) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

归并排序

#include 
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N];
void merge_sort(int q[], int l, int r){
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

逆序对数

#include 
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r){
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else{
            res += mid - i + 1;
            tmp[k ++ ] = q[j ++ ];
        }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    cout << merge_sort(a, 0, n - 1) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

数的范围

#include 
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    while (m -- ){
        int x;
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r){
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (q[l] != x) cout << "-1 -1" << endl;
        else{
            cout << l << ' ';
            int l = 0, r = n - 1;
            while (l < r){
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

三次方根

#include 
using namespace std;
int main(){
    double x;
    cin >> x;
    double l = -100, r = 100;
    while (r - l > 1e-8){
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%.6lf\n", l);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

高精加

#include 
#include 
using namespace std;
vector add(vector &A, vector &B){
    if (A.size() < B.size()) return add(B, A);
    vector 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;
}
int main(){
    string a, b;
    vector 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');
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

高精减

#include 
#include 
using namespace std;
bool cmp(vector &A, vector &B){
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i -- )
        if (A[i] != B[i])
            return A[i] > B[i];
    return true;
}
vector sub(vector &A, vector &B){
    vector 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;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main(){
    string a, b;
    vector 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 C;
    if (cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

高精乘

#include 
#include 
using namespace std;
vector mul(vector &A, int b){
    vector 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;
}
int main(){
    string a;
    int b;
    cin >> a >> b;
    vector A;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    auto C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

高精除

#include 
#include 
#include 
using namespace std;
vector div(vector &A, int b, int &r){
    vector 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;
}
int main(){
    string a;
    vector A;
    int B;
    cin >> a >> B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    int r;
    auto C = div(A, B, r);
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl << r << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

前缀和

#include 
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化
    while (m -- ){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]); // 区间和的计算
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

矩阵前缀和

#include 
using namespace std;
const int N = 1010;
int n, m, q;
int s[N][N];
int main(){
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &s[i][j]);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    while (q -- ){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

差分

#include 
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);
    while (m -- ){
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];
    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

差分矩阵

#include 
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main(){
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);
    while (q -- ){
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

最长连续不重复子序列

#include 
using namespace std;
const int N = 100010;
int n;
int q[N], s[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ ){
        s[q[i]] ++ ;
        while (j < i && s[q[i]] > 1) s[q[j ++ ]] -- ;
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

数组元素的目标和

#include 
using namespace std;
const int N = 1e5 + 10;
int n, m, x;
int a[N], b[N];
int main(){
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    for (int i = 0, j = m - 1; i < n; i ++ ){
        while (j >= 0 && a[i] + b[j] > x) j -- ;
        if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二进制中1的个数

#include 
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int x, s = 0;
        scanf("%d", &x);
        for (int i = x; i; i -= i & -i) s ++ ;
        printf("%d ", s);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

区间和离散化

#include 
#include 
#include 
using namespace std;
typedef pair PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector alls;
vector add, query;
int find(int 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;
}
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ){
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }
    for (int i = 0; i < m; i ++ ){
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    // 处理插入
    for (auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }
    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
    // 处理询问
    for (auto item : query){
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

区间合并

#include 
#include 
#include 
using namespace std;
typedef pair PII;
void merge(vector &segs){
    vector res;
    sort(segs.begin(), segs.end());
    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);
    if (st != -2e9) res.push_back({st, ed});
    segs = res;
}
int main(){
    int n;
    scanf("%d", &n);
    vector segs;
    for (int i = 0; i < n; i ++ ){
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

数据结构

单调栈

给定一个长度为 $N$ 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

#include
#include
using namespace std;
stack stk;
const int N = 100005;
int arr[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    for (int i = 0; i < n; i++) {
        while (!stk.empty()&&arr[i] <= stk.top())
            stk.pop();
        if (stk.empty())
            cout << -1 << " ";
        else cout << stk.top() << " ";
        stk.push(arr[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

滑动窗口

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

#include
#include
using namespace std;
deque dq;
const int N = 1000005;
int arr[N];
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    for (int i = 0; i < n; i++) {
        if (!dq.empty() && i - k + 1 > dq.front())
            dq.pop_front();
        while (!dq.empty() && arr[dq.back()] >= arr[i])
            dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1)
            cout << arr[dq.front()]<<" ";
    }
    dq.clear();
    cout << endl;
    for (int i = 0; i < n; i++) {
        if (!dq.empty() && i - k + 1 > dq.front())
            dq.pop_front();
        while (!dq.empty() && arr[dq.back()] <= arr[i])
            dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) 
            cout << arr[dq.front()] << " ";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

KMP

#include 
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main(){
    cin >> n >> p + 1 >> m >> s + 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;
    }
    for (int i = 1, j = 0; i <= m; i ++ ){
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n){
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}
/*下标从0开始
#include 
#include 
#include 
using namespace std;
const int N = 1000010;
int n, m;
char s[N], p[N];
int ne[N];
int main(){
    cin >> m >> p >> n >> s;
    ne[0] = -1;
    for (int i = 1, j = -1; i < m; i ++ ){
        while (j >= 0 && p[j + 1] != p[i]) j = ne[j];
        if (p[j + 1] == p[i]) j ++ ;
        ne[i] = j;
    }
    for (int i = 0, j = -1; i < n; i ++ ){
        while (j != -1 && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == m - 1){
            cout << i - j << ' ';
            j = ne[j];
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

Trie

#include 
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];
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 main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

最大异或对

#include 
#include 
using namespace std;
const int N = 100010, M = 3100010;
int n;
int a[N], son[M][2], idx;
void insert(int x){
    int p = 0;
    for (int i = 30; i >= 0; i -- ){
        int &s = son[p][x >> i & 1];
        if (!s) s = ++ idx;
        p = s;
    }
}
int search(int x){
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i -- ){
        int s = x >> i & 1;
        if (son[p][!s]){
            res += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));
    printf("%d\n", res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

并查集

#include 
using namespace std;
const int N = 100010;
int p[N];
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    while (m -- ){
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'M') p[find(a)] = find(b);
        else{
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

连通块中点的数量

#include 
using namespace std;
const int N = 100010;
int n, m;
int p[N], cnt[N];
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
        cnt[i] = 1;
    }
    while (m -- ){
        string op;
        int a, b;
        cin >> op;
        if (op == "C"){
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b){
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1"){
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else{
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

堆排序

#include 
#include 
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
void down(int u){
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t){
        swap(h[u], h[t]);
        down(t);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    cnt = n;
    for (int i = n / 2; i; i -- ) down(i);
    while (m -- ){
        printf("%d ", h[1]);
        h[1] = h[cnt -- ];
        down(1);
    }
    puts("");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

模拟堆

维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 $x$ ；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 $k$ 个插入的数；
C k x，修改第 $k$ 个插入的数，将其变为 $x$ ；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。

#include
#include
using namespace std;
const int N=1e5+10;
int h[N];   //堆
int ph[N];  //存放第k个插入点的下标
int hp[N];  //存放堆中点的插入次序
int cur_size;   //size 记录的是堆当前的数据多少
//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int u,int v){   
    swap(h[u],h[v]); 
     swap(hp[u],hp[v]);     
     swap(ph[hp[u]],ph[hp[v]]);            
}
void down(int u){
    int t=u;
    if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2;
    if(u*2+1<=cur_size&&h[t]>h[u*2+1])  t=u*2+1;
    if(u!=t){
        heap_swap(u,t);
        down(t);
    }
}
void up(int u){
    if(u/2>0&&h[u]>1);
    }
}
int main(){
    int n;
    cin>>n;
    int m=0;      //m用来记录插入的数的个数
                //注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少
                //对应上文 m即是hp中应该存的值
    while(n--){
        string op;
        int k,x;
        cin>>op;
        if(op=="I"){
            cin>>x;
            m++;
            h[++cur_size]=x;
            ph[m]=cur_size;
            hp[cur_size]=m;
            //down(size);
            up(cur_size);
        }
        else if(op=="PM")    cout<>k;
            int u=ph[k];//这里一定要用u=ph[k]保存第k个插入点的下标
            heap_swap(u,cur_size);//因为在此处heap_swap操作后ph[k]的值已经发生 
            cur_size--;//如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            up(u);
           down(u);
        }
        else if(op=="C"){
            cin>>k>>x;
            h[ph[k]]=x;//此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
            down(ph[k]);//所以可直接传入ph[k]作为参数
            up(ph[k]);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

字符串哈希

#include 
#include 
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
int n, m;
char str[N];
ULL h[N], p[N];
ULL get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main(){
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i ++ ){
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    while (m -- ){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

搜索与图论

全排列

#include 
using namespace std;
const int N = 10;
int n;
int path[N];
void dfs(int u, int state){
    if (u == n){
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);
        puts("");
        return;
    }
    for (int i = 0; i < n; i ++ )
        if (!(state >> i & 1)){
            path[u] = i + 1;
            dfs(u + 1, state + (1 << i));
        }
}
int main(){
    scanf("%d", &n);
    dfs(0, 0);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

组合型枚举

#include
#include
using namespace std;
bool chosen[30];
int n, m;
vector nums;
void dfs(int pos) {
    if (nums.size() > m || nums.size() + n - pos + 1 < m)
        return;
    if (nums.size() == m) {
        for (int i = 0; i < nums.size(); i++)
            cout << nums[i]<<" ";
        cout << endl;
        return;
    }
    nums.push_back(pos);
    dfs(pos + 1);
    nums.pop_back();
    dfs(pos + 1);
}
int main() {
    cin >> n >> m;
    dfs(1);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

八皇后

#include 
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u){
    if (u == n){
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
        return;
    }
    for (int i = 0; i < n; i ++ )
        if (!col[i] && !dg[u + i] && !udg[n - u + i]){
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}
int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';
    dfs(0);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

走迷宫

#include 
#include 
#include 
#include 
using namespace std;
typedef pair PII;
const int N = 110;
int n, m;
int g[N][N], d[N][N];
int bfs(){
    queue q;
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while (q.size()){
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i ++ ){
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
    return d[n - 1][m - 1];
}
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j];
    cout << bfs() << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

树的重心

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

#include
#include
#include
using namespace std;
const int N = 100005;
vector g[N];
int n;
int st[N];
int ans = N;
int dfs(int u) {
    st[u] = true;
    int sum = 1, res = 0;
    for (auto node : g[u]) {
        if (!st[node]) {
            int s = dfs(node);
            res = max(res, s);
            sum += s;
        }
    }
    res = max(res, n - sum);
    ans = min(ans, res);
    return sum;
}
int main() {
    cin >> n;
    for(int i=0;i> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1);
    cout << ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

拓扑排序

#include
#include
#include
using namespace std;
const int N = 100010;
int n, m;
vector graph[N];
vector path;
int ind[N];//入度
bool toposort() {
    int indnode = 0;
    queue q;
    for (int i = 1; i <= n; i++) {
        if (ind[i] == 0) {
            indnode = i;
            q.push(i);
        }
    }
    if (indnode == 0)
        return false;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        path.push_back(cur);
        for (auto node : graph[cur]) {
            ind[node]--;
            if (ind[node] == 0)
                q.push(node);
        }
    }
    for (int i = 1; i <= n; i++)
        if (ind[i] > 0)
            return false;
    return true;
}
int main() {
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        ind[y]++;
    }
    if (toposort()) {
        for (auto node : path)
            cout << node << " ";
    }
    else 
        cout << -1;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

八数码

#include
#include
#include
#include
using namespace std;
typedef pair > PIV;
priority_queue,greater > q;
map, string> path;
map, int> dist;
vector endst = { 1,2,3,4,5,6,7,8,0 };
int pred(vector state,int steps) {
    int res = 0;
    for (int i = 0; i < 9; i++)//这里1~8对应的下标为0~7
        if (state[i] != 0) {
            int t = state[i] - 1;//对应下标
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);//曼哈顿距离
        }
    return res+steps;//返回总曼哈顿距离
}
int mfind(vector state) {
    for (int i = 0; i < 9; i++)
        if (state[i] == 0)
            return i;
    return -1;
}
void bfs() {
    while (!q.empty()) {
        PIV cur = q.top();
        q.pop();
        if (cur.second ==endst) {
            cout << path[cur.second];
            return;
        }
        int pos = mfind(cur.second);
        if (pos / 3 == 0) {
            vector newc = cur.second;
            swap(newc[pos], newc[pos + 3]);
            if (path.count(newc) == 0||dist[newc]>dist[cur.second]+1) {
                path[newc] = path[cur.second] + "d";
                dist[newc] = dist[cur.second] + 1;
                q.push({pred(newc,dist[newc]),newc });
            }
        }
        if (pos / 3 == 1) {
            vector newc = cur.second;
            swap(newc[pos], newc[pos + 3]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "d";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
            newc = cur.second;
            swap(newc[pos], newc[pos - 3]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "u";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
        }
        if (pos / 3 == 2) {
            vector newc = cur.second;
            swap(newc[pos], newc[pos - 3]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "u";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
        }
        if (pos % 3 == 0) {
            vector newc = cur.second;
            swap(newc[pos], newc[pos + 1]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "r";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
        }
        if (pos % 3 == 1) {
            vector newc = cur.second;
            swap(newc[pos], newc[pos + 1]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "r";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
            newc = cur.second;
            swap(newc[pos], newc[pos - 1]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "l";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
        }
        if (pos % 3 == 2) {
            vector newc = cur.second;
            swap(newc[pos], newc[pos - 1]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "l";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
        }
    }


}
int nixu(vector state) {
    int res = 0;
    for (int i = 0; i < 9; i++) {
        for (int j = i; j < 9; j++)
            if (state[j] < state[i] && state[j] != 0)
                res++;
    }
    return res;
}
int main() {
    vector ch(9);
    for (int i = 0; i < 9; i++)
        cin >> ch[i];
    vector init(9);
    for (int i = 0; i < 9; i++) {
        if (ch[i] == 'x')
            init[i] = 0;
        else init[i] = ch[i] - '0';
    }
    if (nixu(init) % 2 == 0) {
        q.push({pred(init,0),init });
        dist[init] = 0;
        path[init] = "";
        bfs();
        return 0;
    }
    else {
        cout << "unsolvable";
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

解数独

#include 
#include 
#include 
using namespace std;
const int N = 9, M = 1 << N;
int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];
void init(){
    for (int i = 0; i < N; i ++ )
        row[i] = col[i] = (1 << N) - 1;
    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            cell[i][j] = (1 << N) - 1;
}
void draw(int x, int y, int t, bool is_set){
    if (is_set) str[x * N + y] = '1' + t;
    else str[x * N + y] = '.';
    int v = 1 << t;
    if (!is_set) v = -v;
    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}
int lowbit(int x){
    return x & -x;
}
int get(int x, int y){
    return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int cnt){
    if (!cnt) return true;
    int minv = 10;
    int x, y;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i * N + j] == '.'){
                int state = get(i, j);
                if (ones[state] < minv){
                    minv = ones[state];
                    x = i, y = j;
                }
            }
    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i)){
        int t = map[lowbit(i)];
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true;
        draw(x, y, t, false);
    }
    return false;
}
int main(){
    for (int i = 0; i < N; i ++ ) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++ )
        for (int j = 0; j < N; j ++ )
            ones[i] += i >> j & 1;
    while (cin >> str, str[0] != 'e'){
        init();
        int cnt = 0;
        for (int i = 0, k = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++, k ++ )
                if (str[k] != '.')
                {
                    int t = str[k] - '1';
                    draw(i, j, t, true);
                }
                else cnt ++ ;
        dfs(cnt);
        puts(str);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

堆优化Dijkstra

#include
#include
#include
#include
using namespace std;
int t,c,ts,te;
int ans=0;
typedef pair PII;
priority_queue,greater > q;
int st[2505];
int dist[2505];
vector g[2505];
void dijkstra(){
    memset(dist,0x3f3f3f3f,sizeof dist);
    dist[ts]=0;
    q.push({0,ts});
    while(!q.empty()){
        auto [d,cur]=q.top();
        q.pop();
        if (st[cur])
            continue;
        st[cur]=1;
        for(auto node:g[cur]){
            auto [d,next]=node;
            if (d+dist[cur]>t>>c>>ts>>te;
    for(int i=1;i<=c;i++){
        int rs,re,ci;
        cin>>rs>>re>>ci;
        g[rs].push_back({ci,re});
        g[re].push_back({ci,rs});
    }
    dijkstra();
    cout<

SPFA

#include
#include
#include
#include
using namespace std;
int n, m;
const int N = 100005;
int dist[N];
typedef  pair PII;//first表示指向点，second表示距离
vector graph[N];
void spfa() {
    dist[1] = 0;
    queue q;
    q.push(1);
    while (!q.empty()) {
        int curnode = q.front();
        q.pop();
        for (auto node : graph[curnode]) {
            if (dist[node.first] > dist[curnode] + node.second) {
                dist[node.first] = dist[curnode] + node.second;
                q.push(node.first);
            }
        }
    }
}
int main() {
    cin >> n >> m;
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        graph[x].push_back({ y,z });
    }
    memset(dist, 0x3f3f3f3f, sizeof dist);
    spfa();
    if (dist[n] > 0x3f3f3f3f / 2)
        cout << "impossible";
    else
        cout << dist[n];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

SPFA判负环

#include
#include
#include
using namespace std;
int n, m;
const int N = 100005;
int cnt[N];
int dist[N];
typedef  pair PII;//first表示指向点，second表示距离
vector graph[N];
bool spfa() {
    queue q;
    for(int i=1;i<=n;i++)
        q.push(i);
    while (!q.empty()) {
        int curnode = q.front();
        q.pop();
        for (auto node : graph[curnode]) {
            if (dist[node.first] > dist[curnode] + node.second) {
                dist[node.first] = dist[curnode] + node.second;
                cnt[node.first]=cnt[curnode]+1;
                if (cnt[node.first] >= n)
                    return true;
                q.push(node.first);
            }
        }
    }
    return false;
}
int main() {
    cin >> n >> m;
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        graph[x].push_back({ y,z });
    }
    if (spfa())
        cout << "Yes";
    else
        cout << "No";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

Bellman-Ford

#include
#include
using namespace std;
int n, m, k;
struct Edge {
    int x, y, z;
};
Edge edges[10005];
int dist[505];
int backup[505];
int main() {
    cin >> n >> m >> k;
    memset(dist, 0x3f3f3f3f, sizeof dist);
    memset(backup, 0x3f3f3f3f, sizeof backup);
    for(int i=0;i> x >> y >> z;
        edges[i] = { x,y,z };
    }
    dist[1] = 0;
    while (k--) {
        for (int i = 1; i <= n; i++)
            backup[i] = dist[i];
        for (int i = 0; i < m; i++) 
            dist[edges[i].y] = min( dist[edges[i].y],backup[edges[i].x] + edges[i].z );
    }
    if (dist[n] >= 0x3f3f3f3f / 2)
        cout << "impossible";
    else
        cout << dist[n];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Prim

#include
#include
using namespace std;
const int N = 505;
int graph[N][N];
int dist[N];
int s[N];
int n, m;
int res = 0;
void prim() {
    s[1] = true;
    dist[1] = 0;
    for (int i = 1; i <= n; i++)
        dist[i] = graph[1][i];
    for (int i = 1; i <= n; i++) {
        int curnode = 0;
        for (int j = 1; j <= n; j++) {
            if (!s[j] && (curnode==0||dist[j] < dist[curnode]))
                curnode = j;
        }
        if (curnode&&dist[curnode] == 0x3f3f3f3f) {
            res = 0x3f3f3f3f;
            return;
        }
        if (curnode) {
            s[curnode] = true;
            res += dist[curnode];
            for (int j = 1; j <= n; j++)
                if (!s[j] && dist[j] >  graph[curnode][j])
                    dist[j] =  graph[curnode][j];
        }
    }
}
int main() {
    cin >> n >> m;
    memset(graph, 0x3f3f3f3f, sizeof graph);
    memset(dist, 0x3f3f3f3f, sizeof dist);
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        if (z < graph[x][y])
            graph[x][y] =graph[y][x]= z;
    }

    for (int i = 0; i <= n; i++)
        graph[i][i] = 0;
    prim();
    if (res < 0x3f3f3f3f)
        cout << res;
    else
        cout << "impossible";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

Kruskal

#include
#include
using namespace std;
const int N = 1000005;
struct edge {
    int u, v, w;
    bool operator <(const edge& b) const {
        return w < b.w;
    }
};
int p[N];
edge edges[N];
int find(int a) {
    if (a!= p[a]) 
        p[a] = find(p[a]);
    else return p[a];
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u!=v)
            edges[i] = { u,v,w };
    }
    for (int i = 0; i <=n; i++)
        p[i] = i;
    sort(edges, edges + m);
    long long res = 0;
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        u = find(u);
        v = find(v);
        if (u != v) {
            res += w;
            cnt++;
            p[find(u)] =v;
        }
    }
    if (cnt < n - 1)
        cout << "impossible";
    else
        cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

染色法判定二分图

#include
#include
using namespace std;
const int N = 100005;
int color[N];
int res = true;
vector G[N];
void dfs(int i, int clr) {
    color[i] = clr;
    for (auto node : G[i]) {
        if(!color[node])
            dfs(node, 3 - clr);
        else if (color[node] == color[i]) {
            res = false;
            return;
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    while (m--){
        int u, v;
        cin >> u >> v;
        if (u != v) {
            G[u].push_back(v);
            G[v].push_back(u);
        }
    }
    for (int i = 1; i <= n; i++) {
        if(!color[i])
            dfs(i, 1);
    }
    if (res)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

匈牙利算法

#include
#include
#include
using namespace std;
const int N = 1005;
vector graph[N];
int match[N];
int st[N];
bool find(int x) {
    for (auto node : graph[x]) {
        if (!st[node]) {
            st[node] = true;
            if (!match[node] || find(match[node])) {
                match[node]=x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    int n1, n2, m;
    cin >> n1 >> n2 >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    int res = 0;
    for (int i = 1; i <= n1; i++) {
        memset(st, false, sizeof st);
        if (find(i))
            res++;
    }
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

数论

线性筛

#include 
#include 
using namespace std;
const int N= 1000010;
int primes[N], cnt;
bool st[N];
void get_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;
        }
    }
}
int main(){
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

分解质因数

#include 
#include 
using namespace std;
void divide(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;
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        int x;
        cin >> x;
        divide(x);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

试除法求约数

#include 
#include 
#include 
using namespace std;
vector get_divisors(int x){
    vector 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);
        }
    sort(res.begin(), res.end());
    return res;
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        int x;
        cin >> x;
        auto res = get_divisors(x);
        for (auto x : res) cout << x << ' ';
        cout << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

约数个数

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main(){
    int n;
    cin >> n;
    unordered_map 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;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

约数之和

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main(){
    int n;
    cin >> n;
    unordered_map 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;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

gcd

#include 
#include 
using namespace std;
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

欧拉函数

#include 
using namespace std;
int phi(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);
    return res;
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        int x;
        cin >> x;
        cout << phi(x) << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

筛法欧拉函数

#include 
using namespace std;
typedef long long LL;
const int N = 1000010;
int primes[N], cnt;
int euler[N];
bool st[N];
void get_eulers(int n){
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]){
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ ){
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0){
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}
int main(){
    int n;
    cin >> n;
    get_eulers(n);
    LL res = 0;
    for (int i = 1; i <= n; i ++ ) res += euler[i];
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

快速幂

#include 
#include 
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p){
    LL res = 1 % p;
    while (b){
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%lld\n", qmi(a, b, p));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

快速幂求逆元

#include 
#include 
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p){
    LL res = 1;
    while (b){
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

扩展欧几里得算法

给定 $n$ 对正整数 $a_i,b_i$ ，对于每对数，求出一组 $x_i,y_i$ ，使其满足 $a_i×x_i+b_i×y_i=gcd(a_i,b_i)$ 。

#include 
#include 
using namespace std;
int exgcd(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;
}
int main(){
    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);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

线性同余方程

给定 $n$ 组数据 $a_i,b_i,m_i$ ，对于每组数求出一个 $x_i$ ，使其满足 $a_i×x_i≡b_i(\mod m_i)$ ，如果无解则输出 impossible。

#include 
#include 
using namespace std;
typedef long long LL;
int exgcd(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;
}
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, b, m;
        scanf("%d%d%d", &a, &b, &m);
        int x, y;
        int d = exgcd(a, m, x, y);
        if (b % d) puts("impossible");
        else printf("%d\n", (LL)b / d * x % m);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

扩展中国剩余定理

表达整数的奇怪方式。给定 $2 n$ 个整数 $a_1,a_2,…,a_n$ 和 $m_1,m_2,…,m_n$ ，求一个最小的非负整数 $x$ ，满足 $i∈[1,n],x≡m_i(\mod a_i)$ 。

#include 
#include 
using namespace std;
typedef long long LL;
int n;
LL exgcd(LL a, LL b, LL &x, LL &y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
LL inline mod(LL a, LL b){
    return ((a % b) + b) % b;
}
int main(){
    scanf("%d", &n);
    LL a1, m1;
    scanf("%lld%lld", &a1, &m1);
    for(int i = 1; i < n; i++){
        LL a2, m2, k1, k2;
        scanf("%lld%lld", &a2, &m2);
        LL d = exgcd(a1, -a2, k1, k2);
        if((m2 - m1) % d){ puts("-1"); return 0; }
        k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));
        m1 = k1 * a1 + m1;
        a1 = abs(a1 / d * a2);
    }
    printf("%lld\n", m1);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

同余方程

关于 $x$ 的方程 $a x \equiv 1 (m o d b)$ 的最小正整数解

#include
typedef long long LL;
using namespace std;
LL exgcd(LL a,LL b,LL&x,LL&y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    LL a,b,x,y;
    cin>>a>>b;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

斐波那契(矩阵快速幂)

#include
typedef long long LL;
using namespace std;
LL n,m;
LL M[2][2]={
    {0,1},
    {1,1}
};
LL res[2]={1,0};
void mulrm(){
    LL ans[2]={0};
    for(LL i=0;i<2;i++)
        for(LL j=0;j<2;j++)
            ans[i]+=res[j]*M[i][j]%m;
    for(LL i=0;i<2;i++)
        res[i]=ans[i]%m;
}
void mulmm(){
    LL ans[2][2]={0};
    for(LL i=0;i<2;i++){
        for(LL j=0;j<2;j++){
            for(LL k=0;k<2;k++)
                ans[i][j]+=M[i][k]*M[k][j]%m;
        }
    }
    for(LL i=0;i<2;i++)
        for(LL j=0;j<2;j++)
            M[i][j]=ans[i][j]%m;
}
void qpow(LL n){
    while(n){
        if (n&1)
            mulrm();
        mulmm();
        n>>=1;
    }
}
int main(){
    cin>>n>>m;
    qpow(n+2);
    cout<

高斯消元

#include 
#include 
#include 
#include 
using namespace std;
const int N = 110;
const double eps = 1e-8;
int n;
double a[N][N];
int gauss(){  // 高斯消元，答案存于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)
                return 2; // 无解
        return 1; // 有无穷多组解
    }
    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];
    return 0; // 有唯一解
}
int main(){
    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");
    else if (t == 1) puts("Infinite group solutions");
    else{
        for (int i = 0; i < n; i ++ ){
            if (fabs(a[i][n]) < eps) a[i][n] = 0;  // 去掉输出 -0.00 的情况
            printf("%.2lf\n", a[i][n]);
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

组合数

#include 
#include 
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int c[N][N];
void init(){
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
int main(){
    int n;
    init();
    scanf("%d", &n);
    while (n -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", c[a][b]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include 
#include 
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int fact[N], infact[N];
int qmi(int a, int k, int p){
    int res = 1;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int main(){
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ ){
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

$C_a^b=C_{\frac ap}^{\frac bp}C_{a \mod p}^{b\mod p}(\mod p)$

#include 
#include 
using namespace std;
typedef long long LL;
int qmi(int a, int k, int p){
    int res = 1;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int C(int a, int b, int p){
    if (b > a) return 0;
    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- ){
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}
int lucas(LL a, LL b, int p){
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

卡特兰数

$\frac {C_{2n}^n}{n+1}\\ C_1=1,C_n=C_{n-1}*\frac{4n-2}{n+1}$

#include 
#include 
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int qmi(int a, int k, int p){
    int res = 1;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int main(){
    int n;
    cin >> n;
    int a = n * 2, b = n;
    int res = 1;
    for (int i = a; i > a - b; i -- ) res = (LL)res * i % mod;
    for (int i = 1; i <= b; i ++ ) res = (LL)res * qmi(i, mod - 2, mod) % mod;
    res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

能被整除的数

给定一个整数 $n$ 和 $m$ 个不同的质数 $p_1,p_2,…,p_m$ 。
请你求出 $1 \sim n$ 中能被 $p_1,p_2,…,p_m$ 中的至少一个数整除的整数有多少个。

#include 
#include 
using namespace std;
typedef long long LL;
const int N = 20;
int p[N];
int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) cin >> p[i];
    int res = 0;
    for (int i = 1; i < 1 << m; i ++ ){
        int t = 1, s = 0;
        for (int j = 0; j < m; j ++ )
            if (i >> j & 1){
                if ((LL)t * p[j] > n){
                    t = -1;
                    break;
                }
                t *= p[j];
                s ++ ;
            }
        if (t != -1){
            if (s % 2) res += n / t;
            else res -= n / t;
        }
    }
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

龟速乘法

#include
using namespace std;
typedef long long LL;
LL a,b,p;
LL qadd(LL a,LL b,LL p){
    LL res=0;
    while(b){
        if (b&1)
            res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return res;
}
int main(){
    cin>>a>>b>>p;
    cout<

DP

01背包

#include 
#include 
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[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 = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

完全背包

#include 
#include 
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[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 = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

多重背包

#include
#include
using namespace std;
int dp[10005];
int v[1005];
int w[1005];
int s[1005];
int vf[10005], wf[10005];
int N, V;
int main() {
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i]>>s[i];
    int idx = 0;
    for (int i = 1; i <= N; i++) {
        int cur = 1;
        int res = s[i];
        while (res>=cur) {
            res = res - cur;
            idx++;
            vf[idx] = cur * v[i];
            wf[idx] = cur * w[i];
            cur = cur * 2;
        }
        if (res>0) {
            idx++;
            vf[idx] = res * v[i];
            wf[idx] = res * w[i];
        }
    }
    for(int i=1;i<=idx;i++)
        for (int j = V; j >= vf[i]; j--) {
            dp[j] = max(dp[j], dp[j - vf[i]] + wf[i]);
        }
    cout << dp[V];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

分组背包问题

有 $N$ 组物品和一个容量是 $V$ 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$ ，价值是 $w_{ij}$ ，其中 $i$ 是组号, $j$ 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。

#include 
#include 
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k < s[i]; k ++ )
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

数字三角形

#include 
#include 
using namespace std;
const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][N];
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            scanf("%d", &a[i][j]);
    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i + 1; j ++ )
            f[i][j] = -INF;
    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
    int res = -INF;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    printf("%d\n", res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

石子合并

设有 $N$ 堆石子排成一排，其编号为 $1 ， 2 ， 3 ， \dots ， N$ 。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 $N$ 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

#include 
#include 
using namespace std;
const int N = 310;
int n;
int s[N];
int f[N][N];
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
    for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];
    for (int len = 2; len <= n; len ++ )
        for (int i = 1; i + len - 1 <= n; i ++ ){
            int l = i, r = i + len - 1;
            f[l][r] = 1e8;
            for (int k = l; k < r; k ++ )
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    printf("%d\n", f[1][n]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

lis

#include 
#include 
using namespace std;
const int N = 100010;
int n;
int a[N];
int q[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    int len = 0;
    for (int i = 0; i < n; i ++ ){
        int l = 0, r = len;
        while (l < r){
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    printf("%d\n", len);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

整数划分

一个正整数 $n$ 可以表示成若干个正整数之和，形如 $n=n_1+n_2+…+n_k$ ，其中 $n_1≥n_2≥…≥n_k,k≥1$ 。
我们将这样的一种表示称为正整数 $n$ 的一种划分。
现在给定一个正整数 $n$ ，请你求出 $n$ 共有多少种不同的划分方法。
完全背包解法
状态表示：
f[i][j]表示只从1~i中选，且总和等于j的方案数
状态转移方程:
f[i][j] = f[i - 1][j] + f[i][j - i];

#include 
#include 
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];
int main(){
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
            f[j] = (f[j] + f[j - i]) % mod;
    cout << f[n] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

其他算法
状态表示：
f[i][j]表示总和为i，总个数为j的方案数
状态转移方程：
f[i][j] = f[i - 1][j - 1] + f[i - j][j];

#include 
#include 
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];
int main(){
    cin >> n;
    f[1][1] = 1;
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod;
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1050. 鸣人的影分身

在火影忍者的世界里，令敌人捉摸不透是非常关键的。
我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。
针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
那么问题来了，假设鸣人的查克拉能量为 $M$ ，他影分身的个数最多为 $N$ ，那么制造影分身时有多少种不同的分配方法？
注意：
影分身可以分配 $0$ 点能量。
分配方案不考虑顺序，例如： $M = 7, N = 3$ ，那么 (2,2,3) 和 (2,3,2) 被视为同一种方案。

#include
#include
using namespace std;
int f[15][15];
int main(){
    int t;
    cin>>t;
    while(t--){
        int m,n;
        cin>>m>>n;
        memset(f,0,sizeof f);
        f[0][0]=1;
        //把m划分成n个数
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                f[i][j]+=f[i][j-1];
                if (i>=j)
                    f[i][j]+=f[i-j][j];
            }
        }
        cout<

将整数

n

分成

k

份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。