常用算法模板

发表于 分类于 ， Waline：
本文字数： 28k 阅读时长 ≈ 25 分钟
常用算法模板：线性、树、图、搜索、数论、动态规划

序

  • 说明
    1. 用C库中的输入输出更快。
    2. 1s的时间复杂度限制大约可以进行 \(10^7\) 的运算，再根据输入数据的规模可以猜到应该使用什么复杂度的算法。
    3. 要用到的空间用类似于constexpr int N = 1e5的方法进行静态开辟。
    4. 同样根据数据规模确定int会不会溢出
    5. 命名规则都比较简洁，用自己喜欢的风格就行。

单链表

用两个数组，e， ne，头h，个数idx，第k个插入的数在k-1

  • e[N]：数组元素。ne[N]下一个元素的数组下标。
  • 不添加额外的头节点，h：第一个节点的数组下标。
  • 数组中的元素个数为idx，也是下一个可以用来存放新元素的数组下标

单链表

注意题中的k是插入的第k个而不是从前向后遍历到的第k个。所以这里的k-1正好就是对应元素的数组下标

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
#include <iostream>
using namespace std;

constexpr int N=1e5;
int e[N], ne[N], h, idx;

void Init(){
    h = -1; // 第一个节点
    idx = 0; // 下一个存储位
}

void Head(int x){
    e[idx] = x;
    ne[idx] = h;
    h = idx++;
}

void Insert(int k, int x){
    k--;
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

void Delete(int k){
    k--;
    ne[k] = ne[ne[k]];
}

int main(){
    int M;
    char op;
    int k, x;
    cin >> M;
    Init();
    while(M--){
        cin >> op;
        switch(op){
            case 'H':
                cin >> x;
                Head(x);
                break;
            case 'D':
                cin >> k;
                if(k == 0){
                    h = ne[h]; // 删除头部
                }else{
                    Delete(k);
                }
                break;
            case 'I':
                cin >> k >> x;
                Insert(k, x);
                break;
        }
    }
    
    for(int i = h; i != -1; i = ne[i]){ // h开始，-1结束
        printf("%d ", e[i]);
    }
    
    return 0;
}

双链表

双链表

  • e：数组元素，l：左边的下标，r：右边的下标。加入额外的头节点0和尾节点1。第k个插入的数在k+1。
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
#include <iostream>
#include <string>

using namespace std;

constexpr int N = 1e5;

int l[N], r[N], e[N], idx;

void Init(){
    r[0] = 1; // 头->尾
    l[1] = 0; // 尾->头
    idx = 2; // 下一个存储位
}

void InsertL(int x){ // 头插
    e[idx] = x; // 存储
    l[idx] = 0; // 左指向头
    r[idx] = r[0]; // 右指向第一个
    r[0] = idx;
    l[r[idx]] = idx;
    idx++;
}

void InsertR(int x){ // 尾插
    e[idx] = x;
    l[idx] = l[1]; // 左指向最后一个
    r[idx] = 1; // 右指向尾
    r[l[idx]] = idx;
    l[1] = idx;
    idx++;
}

void Delete(int k){
    k++;
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

void InsertKL(int k, int x){
    k++;
    e[idx] = x;
    l[idx] = l[k];
    r[idx] = k;
    r[l[idx]] = idx;
    l[k] = idx++;
}

void InsertKR(int k, int x){
    k++;
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[idx]] = idx;
    r[k] = idx++;
}

int main(){
    int M, k, x;
    string s;
    cin >> M;
    Init();
    while(M--){
        cin >> s;
        if(s == "L"){
            cin >> x;
            InsertL(x);
        }else if(s == "R"){
            cin >> x;
            InsertR(x);
        }else if(s == "D"){
            cin >> k;
            Delete(k);
        }else if(s == "IL"){
            cin >> k >> x;
            InsertKL(k, x);
        }else{
            cin >> k >> x;
            InsertKR(k, x);
        }
    }
    for(int i = r[0]; i != 1; i = r[i]){ // r[0]开始，1结束
        printf("%d ", e[i]);
    }
    
    return 0;
}

栈和队列

  • stk：栈。 e：栈中元素在原序列中的下标。 tt：栈顶元素下标，0号不存。
  • q：队列。hh：队头。 tt：队尾。

单调栈

从后向前扫描，比较栈顶，如果大则就是后面最靠近的大数，否则一直出栈，如果空，则表明后面没有大的数，结果为0（结果保存在数组q中，要逆序输出）

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 <iostream>

using namespace std;

constexpr int N = 3000000 + 10;

int stk[N], e[N], tt, a[N], q[N], qq;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    for (int i = n; i > 0; i--) {
        while (tt && stk[tt] <= a[i]) { // 将小的都出栈
            tt--;
        }
        if (tt == 0) { // 栈空，没有大的
            q[qq++] = 0; // 结果为0
        }
        else {
            q[qq++] = e[tt]; // 否则就是 对应元素的下标
        }
        stk[++tt] = a[i]; // 将这个元素也入栈
        e[tt] = i; // 同时保存其原下标
    }
    for (int i = qq - 1; i >= 0; i--) { // 逆序输出
        printf("%d ", q[i]);
    }
    return 0;
}

树

Trie字符统计

p[N][27]：保存下一个节点在数组中的下标，根为p[0]，每个节点可以保存26个字母，从而保存一系列字符串，对应字符串最后一节点加标记。cnt[N]记录每个节点对应字符串出现次数。

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 <iostream>

using namespace std;

constexpr int N = 1e5 + 10;

int p[N][27], cnt[N], idx = 1; // idx为下一个可存储节点的数组下标
char s[N]; // 输入的字符串

void Add(char* s) {
    int j = 0;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (p[j][u] == 0) { // 没有存储这个字符
            p[j][u] = idx++; // “开辟新节点”以表示存储(u对应存到idx)
        }
        j = p[j][u]; // 进入到下一个节点
    }
    cnt[j]++; // 到最后一个字符节点之后添加标记
}

int Find(char* s) {
    int j = 0;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (p[j][u] == 0) { // 字符串中这个字符未被存储
            return 0; // 就不存在这个字符串
        }
        j = p[j][u];
    }
    return cnt[j]; // 返回标记值（累积存储字符串次数）
}

int main() {
    int n;
    char op[2];
    scanf("%d", &n);
    while (n--) {
        scanf("%s%s", op, s); // op中有'\0'所以要%s而不是%c
        if (op[0] == 'I') {
            Add(s);
        }
        else {
            printf("%d\n", Find(s));
        }
    }

    return 0;
}

非递归DFS并保存路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void getPath(TreeNode *root, TreeNode *end, vector<TreeNode*>& path) {
        stack<TreeNode*> stk;
        TreeNode *p = root, *prev = nullptr;
        while (p || !stk.empty()) {
            while (p) { // 向左下走到头
                stk.push(p);
                path.push_back(p);
                if (p == end) return;
                p = p->left;
            }
            p = stk.top(); // 访问最坐下最近的节点
            if (!p->right || p->right == prev) { // 没有右子节点，需要退回父节点
                path.pop_back();
                stk.pop();
                prev = p;
                p = nullptr;
            } else { // 向右下走一步
                p = p->right;
            }
        }
    }
}

排序

快速排序模板

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 <iostream>
#include <cstdio>

using namespace std;

constexpr int N = 1e5 + 10;

int arr[N];

void QuickSort(int l, int r)
{
    if(l >= r) return;
    int x = arr[l+((r-l)>>1)], i = l-1, j = r+1;
    while(i < j){
        do i++; while(arr[i] < x); // 不会越界，因为最多到达x，会因为相等而停下
        do j--; while(arr[j] > x);
        if(i < j) swap(arr[i], arr[j]);
    }
    QuickSort(l, j);
    QuickSort(j+1, r);
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", arr+i);
    }
    QuickSort(0, n-1);
    for(int i = 0; i < n; i++){
        printf("%d ", arr[i]);
    }
}

通常还是用<algorithm>中的std::sort()，如果要从大到小排：

1
2
3
4
5
bool cmp(int a, int b){
    return a > b;
}
...
sort(arr, arr+n, cmp);

前缀和

扫描一遍并保存在S中之后，快速求指定范围的和

递归公式：（0号下标保持为0，这样不会溢出）

  • 一维数组递推：\[ S_i=S_{i-1}+a_i \]

    快速求指定范围数组和：\[ Sum_{i,j}=S_j-S_{i-1} \]

  • 二维数组递推：\[ S_{i,j}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{i,j} \]

    快速求指定两点之间形成的矩形：\[Sum_{(x,y),(i,j)}=S_{i,j}-S_{x-1,j}-S_{i,y-1}+S_{x-1,y-1}\]

    边界部分要根据题意取舍

注意：如果要求的范围超出原数组，则结果是整个数组的和

为了优化空间，实际Sum和S共用一个数组

激光炸弹

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 <iostream>
#include <cstdio>

using namespace std;

constexpr int N = 5000+10;

int f[N][N];

int main(){
    int n, r;
    cin >> n >> r;
    while(n--){
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        f[x+1][y+1] += w; // 0号不存
    }
    for(int i = 1; i < N; i++){
        for(int j = 1; j < N; j++){ // 求前缀和
            f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + f[i][j];
        }
    }
    int ans = 0;
    if(r >= N){ // 涵盖原数组
        ans = f[N-1][N-1];
    }else{
        for(int i = r; i < N; i++){ // 从r开始遍历，1.防越界，2.避免不必要的搜索
            for(int j = r; j < N; j++){
                // x=i-r+1，画图易得
                ans = max(ans, f[i][j] - f[i-r][j] - f[i][j-r] + f[i-r][j-r]);
            }
        }
    }
    cout << ans;
    return 0;
}

差分

相邻两项之差（0号下标恒为0）

递推：\[b_i=a_i-a_{i-1}\]

用于快速将指定范围内的数加上同一个数c：\[b_l += c; b_{r+1} -= c\]

(\[b_l=a_l-a_{l-1}, b_{l+1}=a_{l+1}-a_l...b_{r+1}=a_{r+1}-a_{r}\]刚好中间的都消掉了，只需要改变首尾)

改变之后的原数组元素：\[a_i=\sum_{1}^{i}b_i\]，用一个数累加即可。

差分

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
#include <iostream>
#include <cstdio>

using namespace std;

constexpr int N = 1e5+10;

int b[N];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        scanf("%d", b+i);
    }
    for(int i = n; i >= 2; i--){
        b[i] -= b[i-1];
    }
    while(m--){
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        b[l] += c;
        b[r+1] -= c;
    }
    for(int i = 1, a = 0; i <= n; i++){
        a += b[i];
        printf("%d ", a);
    }
    
    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
int Find1(int* arr, int l, int r, int t) { // 第一个t
    if (l > r) {
        return -1;
    }
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (arr[mid] < t) l = mid + 1;
        else r = mid;
    }
    return l;
}

int Find2(int* arr, int l, int r, int t) { // 最后一个t
    if (l > r) {
        return -1;
    }
    while (l < r) {
        int mid = l + ((r - l) >> 1) + 1;
        if (arr[mid] > t) r = mid - 1;
        else l = mid;
    }
    return l;
}
...
int arr[] = { 1, 2 ,3 ,4, 4, 4 ,5 };
cout << Find1(arr, 0, 6, 4) << endl; // 3 第一个在3
cout << Find2(arr, 0, 6, 4) << endl; // 5 最后一个在5

其他应用

  • 解立方根

数的三次方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>

using namespace std;

int main(){
    double n;
    cin >> n;
    double l = -10000, r = 10000;
    while(r-l > 1e-7){ // 1e-6精度不足
        double mid = (l + r) / 2;
        if(mid * mid * mid < n) l = mid;
        else r = mid;
    }
    
    printf("%.6f", l);
    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 <cstdio>
#include <iostream>

const int N = 100005;
int cows[N]; double sum[N];
int n, m;

bool check(double avg) {
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + (cows[i] - avg); //计算前缀和(与均值之差)
    }

    double minv = 0; //设置最小值(圈地范围前面的)
    for (int i = 0, j = m; j <= n; j++, i++) { // 圈地为i+1~j(共m块)
        minv = std::min(minv, sum[i]); //找最优极小值(与均值之差的累积)
        if(sum[j] - minv >= 0) return true; //进行判断(从最小值那里到j区间中的均值>=avg)
        								 // 	avg小了
    } return false; //如果所有的都不满足，那么这个平均数就一定不满足(avg大了)
}

int main() {
    scanf("%d %d", &n, &m); // 共n块地，至少围m块地
    double l = 0, r = 0;
    for (int i = 1; i <= n; i++) { //最小左区间 最大右区间
        scanf("%d", &cows[i]); 
        r = std::max(r, (double)cows[i]);
    }

    while(r - l > 1e-5) { //开始二分 因为是实数所以这里还搞个精度
        double mid = (l + r) / 2; // 不是>>1 这里是实数
        if(check(mid)) l = mid; //将问题转变为判定问题
        else r = mid;
    }
    printf("%d\n", (int)(r * 1000)); //因为我们找的极大值 所以要右端点*1000 否则可能会出错
    return 0; 
}

二进制运算

位运算

&, |, ^, ~, <<, >>

  1. 第k位(最低位为第0位)：x >> k & 1
  2. 从右向左第一个1：x & -x

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
// a^b % p
int f(int a, int b, int p){
    int res = 1;
    while(b){
        if(b & 1){
            res = (long long)res * a % p;
        }
        b >>= 1;
        a = (long long)a * a %p;
    }
    return res;
}

并查集

快速判断集合合并以及判断两元素是否属于同一集合。用一个数组实现（保存其所在集合中的父），类似一棵树。

如果是二维则通过换算坐标转换成一维数组。

如果要统计集合中的总数，另设一个数组，合并时合并集合中的总个数

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
#include <iostream>
#include <cstdio>

using namespace std;

constexpr int N = 1e5 + 10;

int p[N];

int find(int a){
    if(a != p[a]) p[a] = find(p[a]); // 路径压缩
    return p[a];
}

int main(){
    int m, n;
    cin >> 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[0] == 'M'){
            if(find(a) != find(b)){
                p[find(a)] = find(b); // 集合合并(合并根)
            }
        }else{
            if(find(a) == find(b)){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }
    }
    return 0;
}

DFS & BFS

DFS，栈或递归，回溯

n皇后

n-皇后问题

不能同行，同列，同斜线

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 <iostream>
#include <cstdio>

using namespace std;

constexpr int N = 10;
char mp[N][N]; // 棋盘
int n;
bool col[N], g[2*N], ug[2*N]; // 判断同列，同斜线(2N条!)，同反斜线（由于按行遍历，不需要增加行的）

void dfs(int u){ // 枚举到第u行(共0~n-1行)
    if(n == u){ // 一个完整的方案
        for(int i = 0; i < n; i++){
            printf("%s\n", mp[i]); // 有0，所以可当字符串输出
        }
        printf("\n");
    }
    for(int i = 0 ;i < n; i++){ // 当前行u，遍历可能的列（0~n-1）
        if(col[i] || g[i+u] || ug[n+u-i]){ // 以左上角建坐标，同斜线的x+y相同
            continue;					 // 同反斜线的x-y相同(防止负数，统一加n)
        }
        col[i] = g[i+u] = ug[n+u-i] = true; // 标记
        mp[u][i] = 'Q';
        dfs(u+1); // 放下一行
        col[i] = g[i+u] = ug[n+u-i] = false; // 回溯
        mp[u][i] = '.';
    }
}

int main(){
    cin >> n;
    for(int i= 0; i < n; i++){
        for(int j = 0; j < n ; j++){
            mp[i][j] = '.'; // 初始化
        }
    }
    dfs(0);
    return 0;
}

BFS

队列，最短路径(权值相同)

迷宫问题

n*m的二维数组，0可走，1不可走。从左上角(0,0)开始，可以按上下左右移动，到达(n-1,m-1)最少需要移动多少次？((0,0)和(n-1,m-1)处数字必为0，且至少有一条路，数据规模1~100)

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
#include <iostream>
#include <cstdio>

using namespace std;

constexpr int N = 110;

int qx[N*N], qy[N*N]; // 队列
int n, m, dd, tt=-1; // dd, tt为队头队尾

int mp[N][N], d[N][N]; // 地图，距离（-1为没有走过）

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int bfs(){
    qx[++tt] = 0; qy[tt] = 0; // 入队
    d[0][0] = 0;
    while(dd <= tt){ // 队列非空
        int x = qx[dd], y = qy[dd++]; // 出队
        for(int i = 0; i< 4;i++){
            int ix=x+dx[i], iy=y+dy[i];
            // 越界，走过，不可走
            if(ix<0||iy<0|| ix>=n||iy>=m || d[ix][iy]!=-1 || mp[ix][iy]==1){
                continue;
            }
            qx[++tt]=ix; qy[tt]=iy; // 入队
            d[ix][iy]=d[x][y]+1; // 到起点的距离（步数）
            if(ix==n-1&&iy==m-1){ // 已到达终点，那么这就是最小值！
                return d[ix][iy]; // 广度搜索，之后的路径距离更大
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n;i++){
        for(int j=0;j < m;j++){
            scanf("%d", mp[i]+j);
        }
    }
    memset(d, -1, sizeof d); // 初始化为没有走过（距离-1）
    					   // 只能初始化字节相同的int，如0，-1，0x3f3f3f3f,0x7f7f7f7f
    cout << bfs();
    return 0;
}

其中队列可以用STL的push,front,pop,size,empty

1
2
3
4
5
typedef struct{
    int x, y;
}Node;

q.push({1, 1}); // 临时结构体

八数码

八数码

保存网格状态：用string

网格状态对应交换的次数：用map<string, int>，map.count判断状态不重复

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
#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <unordered_map>

using namespace std;

string start;// 初始状态
unordered_map<string, int> d; // 用map会超时

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

int bfs() {
    queue<string> q;
    q.push(start); // 初始入队
    d[start] = 0; // 移动了0步
    while (!q.empty()) {
        string t = q.front(); // 取出一个状态
        q.pop();
        int x, y; // 此状态中'x'坐标
        int id = d[t]; // 此状态已经交换的次数
        for (int i = 0; i < 9; i++) {
            if (t[i] == 'x') {
                x = i / 3;
                y = i % 3;
                break;
            }
        }
        for (int i = 0; i < 4; i++) { // 尝试四个方向
            int ix = x + dx[i], iy = y + dy[i];
            if (ix < 0 || ix>2 || iy < 0 || iy>2) { // 越界
                continue;
            }
            swap(t[x * 3 + y], t[ix * 3 + iy]); // 将x与下一步的格子交换，进入下一个状态
            if (d.count(t)) { // 状态存在过
                swap(t[x * 3 + y], t[ix * 3 + iy]);
                continue;
            }
            q.push(t); // 入队
            d[t] = id + 1; // 计算距离
            if (t == "12345678x") { // 已结束
                return d[t];
            }
            swap(t[x * 3 + y], t[ix * 3 + iy]); // 因为四个方向的尝试共用一个string，要记得恢复
        }
    }
    return -1; // 没有路径
}

int main() {
    char ch;
    for (int i = 0; i < 9; i++) {
        scanf("%c ", &ch); // 输入有空格
        start += ch;
    }
    cout << bfs() << endl;
    return 0;
}

如果不能使用unordered_map，使用map会超时,需要手动哈希

手动映射-康托展开

对于全排列的哈希，可以使用康托展开

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
int fac[] = {1,1,2,6,24,120,720,5040,40320,362880};
//         0!1!2!3! 4! 5!  6!  7!   8!    9!
// 将一个全排列映射到其在所有排列中的次序
int cantor(int s[]){
    int sum = 0;
    for(int i = 0; i < 9; i++){
        int cnt = 0; // 小于当前位的个数
        for(int j = i + 1; j < 9; j++){
            if(s[j] < s[i]) cnt++;
        }
        sum += (cnt * fac[9-i-1]);
    }
    return sum+1;
}

void decantor(int x, int n)
{
    vector<int> v;  // 存放当前可选数
    vector<int> a;  // 所求排列组合
    for(int i=1;i<=n;i++)
        v.push_back(i);
    for(int i=n;i>=1;i--)
    {
        int r = x % FAC[i-1];
        int t = x / FAC[i-1];
        x = r;
        sort(v.begin(),v.end());// 从小到大排序
        a.push_back(v[t]);      // 剩余数里第t+1个数为当前位
        v.erase(v.begin()+t);   // 移除选做当前位的数
    }
}

另一种理解是变进制数，也就是转换成十进制时，i位的权值为i!

9位字符串排列共9!个，而 \[ 1\times1!+2\times2!+...+8\times8! \\ = 1+1\times1!+2\times2!+...+8\times8!-1 \\ = 2!+2\times2!+3\times3!+...+8\times8!-1 \\ =... = 9!-1 \] 所以变进制数恰好可以映射所有的字符串排列

首先用数组d统计每个数字前比其大的数字个数，分别对应权值0!~8!加权求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int f[10];
void Init(){
    f[1] = 1;
    for(int i = 2; i <= 9; i++){
        f[i] = f[i-1] * i;
    }
}
int Hash(string s){
    int sum = 0;
    for(int i = 0; i < 9; i++){
        int col = 0;
        for(int j = 0; j < i; j++){
            if(s[j] > s[i]) col++;
        }
        sum += f[i] * col; // f[i] = i!
    }
    return sum;
}

将字符串映射到int之后就可以用大小为9!=362880的数组保存对应状态的距离值，从而代替unordered_map

树与图的搜索

图

用邻接表（多个单链表）：h[N]是各个头节点，e[N]为元素，ne,idx与单链表定义相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int h[N], e[N*2], ne[N*2], idx;
bool st[N]; // 遍历过

void add(int a, int b) { // 添加一条边a->b
    e[idx] = b, ne[idx] = h[a], h[a] = idx++; // 将这条边头插入a的邻接链表
}

void dfs(int u) { // u当前节点，遍历其邻接链表
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (st[j]) continue;
        st[j] = true;
        dfs(j);
        st[j] = false;
    }
}

树的重心

一棵树，n个节点（1~n），n-1条无向边，树的重心为：删除这个节点后，剩余各个连通块中节点数的最大值最小。找到其重心并输出删除重心之后剩余各个连通块中节点数的最大值。

输入n和n-1条边

遍历树，逐个尝试删除每个节点，其删除后的连通块为左子树、右子树和其余的，其中其余的可以通过n-左子树-右子树-1来算出。

这里的树可以看成是只有无向边的图，左右孩子就是其两个邻接节点。

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
int n; // 总节点数
int g[N]; // 其余连通分支的节点最大数

int dfs(int u) { // u当前节点，遍历其邻接链表，这里是左右孩子
    int sum = 1; // 当前节点及其子树节点数
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (st[j]) continue;
        //st[j] = true; // 因为遍历的是树，没有环，不会重复遍历节点
        int col = dfs(j); // col 累积左右孩子节点数
        if (col > g[u]) g[u] = col;
        sum += col;
        //st[j] = false;
    }
    if (g[u] < n - sum) g[u] = n - sum; // 剩余节点数
    return sum;
}

int main(){
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) { // n-1条边
        int a, b;
        cin >> a >> b;
        add(a, b); // 为了在邻接表中存储无向边，同时保存两有向边即可
        add(b, a);
    }
    st[1] = true;
    dfs(1);
    int Min = 0x3f3f3f3f;
    // 遍历g，得到Min
    return 0;
}

优化：改用一个Min全局记录，省去g数组。

拓扑排序

有向无环图，BFS计算每个节点的入度。每去掉一个节点，就将其指向的每个节点的入度--，然后将其下入度为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
int d[N]; // 每个节点的入度
int q[N], dd, tt; // 队列，队头，队尾

int main(){
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int b;
        while (cin >> b && b) {
            add(i, b);
            d[b]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0) q[++tt] = i;
    }
    while (dd <= tt) {
        int t = q[dd++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j]--;
            if (d[j] == 0) q[++tt] = j;
        }
    }
    for (int i = 0; i < n; i++) { // 输出队列
        cout << q[i] << ' ';
    }
    return 0;
}

图论

无负权边

Dijkstra

普通版

Dijkstra求最短路

在还没有确定最短距离的点中选择dist最小的点，用它更新相邻且未确定的点的dist

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
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

constexpr int N = 510;

int n, m;
int g[N][N], dist[N]; // g为邻接矩阵，dist为距离起点的最短距离
bool st[N]; //是否已经确定

int Dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n; i++) {
        int t = n + 1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && dist[t] > dist[j]) t = j; // 找到未确定且距离最小的
        }
        st[t] = true;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && dist[t] + g[t][j] < dist[j]) dist[j] = dist[t] + g[t][j]; // 更新剩余点
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1; // 路径不存在
    return dist[n];
}

int main() {
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        if (g[x][y] > z) g[x][y] = z; // 因为输入可能有重边，临界矩阵只保存最短的
    }
    cout << Dijkstra() << endl;
    return 0;
}

用邻接表更快

堆优化

Dijkstra求最短路II

改用优先队列作为小顶堆，同时由于数据过大，不能用邻接矩阵，只能用邻接表存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <queue>

#define PII pair<int, int>
...
// 初始
priority_queue<PII, vector<PII>, greater<PII> >Heap; // 小顶堆，按照pair第一个元素排，注意写成>>可能编译错误
Heap.push({ 0,1 }); // {dist, id}

// 之后取dist最小元素操作
PII t = Heap.top();
Heap.pop();
int id = t.second, d = t.first;

// 更新距离操作
dist[k] = d + w[j]; // 为了方便遍历，仍需要dist数组
Heap.push({dist[k], k}); // 而原来的pair会因为dist较大而沉下（不需要删掉）

有负权边

Bellman-ford

只有当含有负权边并且题中指定了固定步数k时才可以使用

只保存图中的边，还需要备份dist的backup数组，与Dijkstra不同之处在于更新操作使用的是backup数组，

有边数限制的最短路

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 <iostream>
#include <cstring>

using namespace std;

int dist[550], bak[550], n, m, k;

struct N {
    int a, b, c;
}Ns[10010];

void bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {
        memcpy(bak, dist, sizeof dist);
        for (int j = 0; j < m; j++) {
            int a = Ns[j].a, b = Ns[j].b, c = Ns[j].c;
            if (bak[a] + c < dist[b]) dist[b] = bak[a] + c; // 使用bak更新
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible";
    else cout << dist[n];
}

int main() {

    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        Ns[i] = { a,b,c };
    }
    bellman_ford();

    return 0;
}

SPFA

类似于BFS，起点入队，一个点的dist被更新时，如果没有在队列里，则入队列。

spfa求最短路

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

constexpr int N = 2e5 + 5;
int n, m, e[N], ne[N], h[N], w[N], idx, dist[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b; ne[idx] = h[a];
    w[idx] = c; h[a] = idx++; 
}

void spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int>q;
    q.push(1);
    st[1] = true;
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) { // 更新t的相邻点
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true; // 在队列中
                }
            }
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible";
    else cout << dist[n];
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    spfa();

    return 0;
}

判断是否有负权回路

1
2
3
4
5
6
7
8
9
10
11
12
13
int cnt[N];
...
    // 开始时将所有点入队列
    for(int i = 0; i <= n; i++){
        q.push(i);
        st[i] = true;
    }
    if (dist[j] > dist[t] + w[i]) {
        dist[j] = dist[t] + w[i];
        cnt[j] = cnt[t] + 1;
        if (cnt[j] > n - 1) { // 存在负权回路

    	}

多源点

Floyd

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

constexpr int N = 2e2 + 5, INF = 0x3f3f3f3f;
int g[N][N], n, m, k;

int main(){
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) g[i][j] = 0;
            else g[i]][j] = INF;
        }
    }
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (g[a][b] > c) {
            g[a][b] = c;
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (g[i][j] > g[i][k] + g[k][j]) {
                    g[i][j] = g[i][k] + g[k][j];
                }
            }
        }
    }
    while (k--) {
        int x, y;
        cin >> x >> y;
        if (g[x][y] > INF / 2) cout << "impossible" << endl;
        else cout << g[x][y] << endl;
    }

    return 0;
}

最小生成树

Prim

适用于点远少于边，找到集合外dist最小的，更新其他点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Prim() {
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (dist[t] > dist[j] || t == -1)) {
                t = j;
            }
        }
        st[t] = true;
        if (i) {
            res += dist[t];
        }
        if (i && dist[t] == 0x3f3f3f3f) {
            cout << "impossible";
            return;
        }
        for (int j = 1; j <= n; j++) {
            if (dist[j] > g[t][j]) dist[j] = g[t][j];
        }
    }
    cout << res << endl;
}

Kruskal

保存每条边，按照权值从小到大排序，连通用到并查集

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 <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

constexpr int N = 2e2 + 5, INF = 0x3f3f3f3f;
int g[N][N], n, m, k;

constexpr int N = 1e2 + 5,
constexpr int M = 2e2 + 5;
int p[M], n, m, res, cnt; // p为并查集
struct Node {
    int a, b, c;
}Ns[M];

bool cmp(Node a, Node b) {
    return a.c < b.c;
}

int find(int a) {
    if (p[a] != a) {
        p[a] = find(p[a]);
    }
    return p[a];
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        p[i] = i; //并查集初始化
    }
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        Ns[i] = { a,b,c };
    }
    sort(Ns, Ns + m, cmp); // 边排序
    for (int i = 0; i < m; i++) {
        int a = Ns[i].a, b = Ns[i].b, c = Ns[i].c;
        if (find(a) != find(b)) {
            p[find(a)] = find(b);
            res += c;
        }
    }
    if (cnt != n - 1) {
        cout << "impossible";
    }
    cout << res;

    return 0;
}

数论

质数

判断n是否为质数

1
2
3
4
5
6
7
8
9
10
11
12
// 试除法判断n是否为质数
bool f(int n) {
    if (n < 2) {
        return false;
    }
    for (int i = 2, up = sqrt(n); i <= up; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

筛选出1~n的质数

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
// 埃式筛1~n的质数 O(nloglogn)
void f() {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            prime[cnt++] = i;
            for (int j = i + i; j <= n; j += i) { // i的倍数肯定都不是质数
                st[j] = true;
            }
        }
    }
}

// 线性筛质数O(n) (按照每一个数的最小质因数来筛，每个数都只会筛一次)
void f() {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            prime[cnt++] = i;
        }
        for (int j = 0, up = n / i; prime[j] <= up; j++) { // 枚举之前选的质数
            st[prime[j] * i] = true; // 两个质数乘积prime[j]*i肯定不是质数
            if (i % prime[j] == 0) { // prime[j]是i的质因数?，不需要再重复筛
                break;
            }
        }
    }
}

对n分解质因数

\[n=P_1^{a_1}{\times}P_2^{a_2}\times...{\times}P_n^{a_n}\]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void f(int n) {
    for (int i = 2, up = sqrt(n); i <= up; i++) {
        if (n % i == 0) { // 只要满足则i一定是质数(因为如果i不是质数，则前面就已经把n中i的质因子除掉了)
            int cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            cout << i << ' ' << cnt << endl; // 一个因子i^cnt
        }
    }
    if (n != 1) {
        cout << n << ' ' << 1 << endl;
    }
}

约数

求约数

数字n可能很大，数组静态开辟不能太大，可以改用std::vector

1
2
3
4
5
6
7
8
9
10
void f() {
    for (int i = 1, up = sqrt(n); i <= up; i++) {
        if (n % i == 0) {
            q[cnt++] = i; 
            if (i != n / i) {
                q[cnt++] = n / i; // 对称的另一个
            }
        }
    }
}

约数个数

先分解质因数\[n=P_1^{a_1}{\times}P_2^{a_2}\times...{\times}P_n^{a_n}\]，约数个数为\[(a_1+1){\times}(a_2+1){\times}...{\times}(a_n+1)\]。注意是相乘。

例：给定n个正数ai，输出这些数的乘积的约数个数，答案对1e9+7取模。

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 <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

constexpr int MOD = 1e9 + 7;
unordered_map<int, int> h; // 保存质因数的底和指数

int main(){
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;
        for (int i = 2; i <= a / i; i++) {
            if (a % i == 0) {
                while (a % i == 0) {
                    a /= i;
                    h[i]++;
                }
            }
        }
        if (a != 1) {
            h[a]++; // a没有被除完?
        }
    }
    long long res = 1;
    for (const auto i : h) {
        int b = i.second;
        res = res * (b + 1) % MOD; // 约数个数公式
    }
    cout << res;

    return 0;
}

约数和

先分解质因数\[n=P_1^{a_1}{\times}P_2^{a_2}\times...{\times}P_n^{a_n}\]，约数和为\[\sum_0^{a_1}P_1^i{\times}...{\times}\sum_0^{a_n}P^i\]，注意也是相乘。

每一部分都可以使用等比数列求和公式进行快速计算，而且还可以使用快速幂。

例：给定n个正数ai，输出这些数的乘积的约数个数，答案对1e9+7取模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fastpow(int a, int b, int p){
    int res = 1;
    while(b){
        if(b & 1){
            res = (long long)res * a % p;
        }
        b >>= 1;
        a = (long long)a * a %p;
    }
    return res;
}
// 基本同上，不同之处
int a = i.first, b = i.second;
res = (res * ((1-fastpow(a, b+1, MOD)) / (1 - a))) % MOD;

最大公约数

b != 0，(a, b) = (b, a%b)

1
2
3
4
5
6
7
8
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

// 最小公倍数
int lcm(int a, int b){
    return a * b / gcd(a, b);
}

欧拉函数

函数值为为小于等于n的正整数中与n互质的数的个数。

先分解质因数\[n=P_1^{a_1}{\times}P_2^{a_2}\times...{\times}P_n^{a_n}\]

则\[\phi(n)=n{\times}(1-\frac{1}{P_1})\times(1-\frac{1}{P_2})\times...\times(1-\frac{1}{P_n})\]

其实展开就是\[n-\frac{n}{P_1}-...-\frac{n}{P_n}+\frac{n}{P_1P_2}+...+\frac{n}{P_{n-1}P_{n}}-\frac{n}{P_1P_2P_3}-...\]

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
// O(n)
int Euler(int n){
    int ans = n;
    for(int i = 2; i <= n; i++){
        if(n%i == 0){
            ans = ans / i * (i-1);
            while(n%i==0){
                n /= i;
            }
        }
    }
    return ans;
}

// O(n^0.5)
int Euler(int n){
    int ans = n;
    for(int i = 2; i * i <= n; i++){
        if(n%i == 0){
            ans = ans / i * (i-1); 
            while(n%i == 0){
                n /= i;
            }
        }
    }
    if(n > 1){
        ans = ans / n * (n-1);
    }
    return ans;
}

性质

\[\phi(m{\times}n)=\phi(m)\times\phi(n)\]，其中m和n互质。

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 在线性筛素数基础上添加
int euler[N]; // 保存对应的欧拉函数值
void f() {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            prime[cnt++] = i;
            euler[i] = i-1;
        }
        for (int j = 0, up = n / i; prime[j] <= up; j++) {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) {
                euler[i*prime[j]] = euler[i] * prime[j];
                break;
            }
            euler[i*prime[j]] = euler[i] * euler[prime[j]]; // 欧拉函数性质
        }
    }
}

动态规划

某个问题可以转换成N个子问题，并且子问题还可以转换，而且存在着重复。

流程：反推、正推-状态表示-分类讨论-状态方程-优化

背包

N个物品，每个物品都有自己的价值v[i]和重量w[i]，背包最大载重量为W，需要在不超过载重量的情况下获得最大价值。动态规划dp[i][j]表示子问题：前i件物品在背包最大载重量为j时可以获得的最大价值

  1. 01背包 每个物品要么不放，要么就完整地放入，而且只能放一次，当j >= w[i]时dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i])，也就是说在填二维表的时候，每行都只跟上一行有关，于是可以改为使用一维的数组，而且因为转为一维了，j < w[i]的时候数组值不变，这种情况也就不需要考虑了。这里还需要注意逆向遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    vector<int> dp(W + 1, 0);
    for(int i = 1; i <= N; i++){ // 遍历物品i
        int w = weights[i-1], v = values[i-1]; // 当前物品i的重量和价值
        // 因为对应二维的时候是用上一行的j-w，所以一维的时候要逆向遍历，不然就覆盖掉了之前的结果
        for(int j = W; j >= w; j--){ // 对于能放下当前物品的背包载重量j，更新最大价值
            dp[j] = max(dp[j], dp[j-w] + v); // 不放：最大价值不变
            							   //   放：对应此物品原来的重量部分就是空的，等价于原背包载重量为j-w的情况，然后加上当前价值v
        }
    }

  2. 完全背包

    每个物品也是完整地放入，但是可以重复放多次，转移方程中的唯一变化就是dp[i-1][j-w[i]]改为dp[i][j-w[i]]，因为之后还可以继续放物品i。当j >= w[i]时转移方程是dp[i][j]=max(dp[i-1][j], dp[i][j-w[i]] + v[i])。同样要注意正向遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    vector<int> dp(W + 1, 0);
    for(int i = 1; i <= N; i++){ // 遍历物品i
        int w = weights[i-1], v = values[i-1]; // 当前物品i的重量和价值
        // 因为对应二维的时候就是用同一行的j-w，所以一维的时候也正向遍历，就是要更新j给后面的用
        for(int j = W; j >= w; j--){ // 对于能放下当前物品的背包载重量j，更新最大价值
            dp[j] = max(dp[j], dp[j-w] + v); // 不放：最大价值不变
            							   //   放：对应此物品原来的重量部分就是空的，等价于原背包载重量为j-w的情况，然后加上当前价值v
        }
    }

  3. 背包恰好装满

    用-INF表示不能恰好装满的无效状态，初始化只有dp[0]=0，其它都是-INF，因为初始只有容量为0的时候什么都不装才算装满背包，之后的遍历过程更原来基本一样，只是要加一句if(dp[j] < 0) dp[j] = -INF;。

其他

闰年

1
2
3
bool isLeapYear(int y){
    return y%400==0 || (y%100!=0 && y%4==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
// 读整数
inline bool scan_d(int &num)  
{
        char in; bool IsN=false;
        in=getchar();
        if(in==EOF) return false;
        while(in!='-'&&(in<'0'||in>'9')) in=getchar();
        if(in=='-'){ IsN=true;num=0;}
        else num=in-'0';
        while(in=getchar(),in>='0'&&in<='9'){
                num*=10,num+=in-'0';
        }
        if(IsN) num=-num;
        return true;
}

// 读实数
inline bool scan_lf(double &num)  
{
        char in; double Dec=0.1;
        bool IsN=false, IsD=false;
        in=getchar();
        if(in==EOF) return false;
        while(in!='-'&&in!='.'&&(in<'0'||in>'9'))
        	in=getchar();
        if(in=='-'){IsN=true;num=0;}
        else if(in=='.'){IsD=true;num=0;}
        else num=in-'0';
        if(!IsD){
            while(in=getchar(),in>='0'&&in<='9'){
                num*=10;num+=in-'0';}
        }
        if(in!='.'){
            if(IsN) num=-num;
            return true;
        }else{
            while(in=getchar(),in>='0'&&in<='9'){
                num+=Dec*(in-'0');Dec*=0.1;
            }
        }
        if(IsN) num=-num;
        return true;
}
相关文章