AcWing 第2讲 数据结构

表达式计算

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
// 表达式求值，支持括号和 - = * /

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1000010;

bool is_number(string str) {
    for (char ch : str) {
        if (ch < '0' || ch > '9') return false;
    }
    return true;
}

int main() {
    string sten;
    cin >> sten;

    char op[N];
    int op_top = 0;

    string ans[N];
    int ans_top = 0;

    for (int i;i < sten.length();i++) {
        char ch = sten[i];
        switch (ch) {
        case '(':
            op[op_top++] = ch;
            break;
        case ')':
            while (op[op_top - 1] != '(') {
                ans[ans_top++] = op[--op_top];
            }
            op_top--;
            break;
        case '+': case '-':
            while (op[op_top - 1] != '(' && op_top > 0) {
                ans[ans_top++] = op[--op_top];
            }
            op[op_top++] = ch;
            break;
        case '*': case '/':
            while (op[op_top - 1] != '(' && op_top > 0
                && op[op_top - 1] != '+' && op[op_top - 1] != '-') {
                ans[ans_top++] = op[--op_top];
            }
            op[op_top++] = ch;
            break;
        default:
            int num = 0;
            while (ch >= '0' && ch <= '9') {
                num = 10 * num + ch - '0';
                ch = sten[++i];
            }
            i--;
            ans[ans_top++] = to_string(num);
        }
    }

    while (op_top > 0) {
        ans[ans_top++] = op[--op_top];
    }

    // for (int i=0;i < ans_top;i++)
    //     cout << ans[i] << endl;

    int ret[N], ret_top = 0;
    for (int ans_head = 0; ans_head < ans_top;ans_head++) {            // loop through ans array from head to tail.)
        if (is_number(ans[ans_head])) {
            ret[ret_top++] = stoi(ans[ans_head]);
        }
        else {
            char ch = ans[ans_head][0];
            int x = 0, y = 0;
            x = ret[--ret_top];
            y = ret[--ret_top];
            switch (ch) {
            case '+':
                ret[ret_top++] = x + y;
                break;
            case '-':
                ret[ret_top++] = y - x;
                break;
            case '*':
                ret[ret_top++] = y * x;
                break;
            case '/':
                ret[ret_top++] = y / x;
                break;
            }
        }
    }
    // for(int x : ret) cout << x << endl; 
    cout << ret[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
// 单调栈
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 100010;

int main() {
    int num, n, st[N], top = 0;
    cin >> n;

    while (n--) {
        cin >> num;
        while (top && st[top-1] >= num) top--;
        if (!top) {
            cout << "-1 ";
            st[top++] = num;
        }
        else{
            cout << st[top - 1] << " ";
            st[top++] = num;
        }
    }


    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 <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1000010;

int main() {
    int num[N], st[N];
    int n, m, head = 0, top = 0;
    cin >> n >> m;

    // 最小值
    for (int i = 0;i < n;i++) {
        cin >> num[i];
        if (i - m + 1 > st[head]) head++;
        while (head < top && num[i] <= num[st[top - 1]]) top--;
        st[top++] = i;
        if (i >= m-1) cout << num[st[head]] << " ";
    }

    cout << endl;

    head = 0, top = 0;
    for (int i = 0;i < n;i++) st[i] = 0;
    // 求最大值
    for (int i = 0;i < n;i++) {
        if (i - m + 1 > st[head]) head++;
        while (head < top && num[i] >= num[st[top - 1]]) top--;
        st[top++] = i;
        if (i >= m-1) cout << num[st[head]] << " ";
    }
    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
//单调队列接雨水 leetcode 42
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 100010;

int main() {
    int n;
    cin >> n;
    int st[N], num[N], ans=0, top = 0;
    for (int i = 0;i < n;i++) {
        cin >> num[i];
        while (top && num[i] > num[st[top - 1]]) {
            top--;
            int tmp = num[st[top]];
            int distence = i - st[top-1] - 1;
            int heignt = min(num[st[top - 1]], num[i]) - tmp;
            ans+=distence * heignt;
        }
        st[top++] = i;
    }

    cout << ans;

    return 0;
}

KMP算法

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 <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1000010;
int n, m, ne[N];
char s[N], p[N];

int main() {
    cin >> m >> p + 1 >> n >> s + 1;

    for (int i = 2, j = 0;i <= m;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 <= n;i++) {
        while(j && s[i]!= p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == m) {
            cout << i - m << " " << i-1;
            break;
        }
    }
    return 0;
}

trie树

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
// acw_835 trie树
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 100010;
int son[N][26], cnt[N], idx;
// son类似链式前向星，存储的是后继编号
// cnt相当于son[N][27]，跟在son[N]后面记录一个串出现的次数

void insert(char* s) {
    int j = 0;
    for (int i = 0; s[i]; i++) {
        int x = s[i] - 'a';
        if (!son[j][x]) son[j][x] = ++idx;
        j = son[j][x];
    }
    cnt[j]++;
}

int query(char* s) {
    int j = 0;
    for (int i = 0;s[i];i++) {
        int x = s[i] - 'a';
        if (!son[j][x]) return 0;
        j = son[j][x];
    }
    return cnt[j];
}

int main() {
    int n; cin >> n;
    char op[2], str[N];
    while (n--) {
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else cout << query(str) << 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 <bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long LL;

const int N = 3000010;

int son[N][2], idx;

void insert(int x) {
    int j = 0;
    for (int i = 30;~i;i--) {
        if (!son[j][x >> i & 1]) son[j][x >> i & 1] = ++idx;
        j = son[j][x >> i & 1];
    }
}

int search(int x) {
    int ans, p = 0;
    for (int i = 30;~i;i--) {
        int xt = x >> i & 1;
        if (son[p][!xt]) {
            p = son[p][!xt];
            ans = ans * 2 + 1;
        }
        else if (son[p][xt]) {
            p = son[p][xt];
            ans = ans * 2;
        }
    }
    return ans;
}

int main() {
    int n, a[N];
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        insert(a[i]);
    }

    int ans = 0;
    for (int i = 0;i < n;i++) {
        ans = max(ans, search(a[i]));
    }

    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
36
37
38
39
40
// 合并集合

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 100010;

int num[N];

int find(int x) {
    if (num[x] != x) num[x] = find(num[x]);
    return num[x];
}

int main() {
    int n, m, x, y;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) num[i] = i;
    for (int i = 1;i <= n;i++) cout << num[i] << " ";
    cout << endl;

    string op;
    while (m--) {
        cin >> op;
        cin >> x>>y;
        if (op == "M") {
            num[find(x)] = find(y);
        }
        else {
            if (find(x) == find(y)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    for (int i = 1;i <= n;i++) cout << num[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
36
37
38
39
40
41
42
43
// 连通块中点的数量

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 100010;

int num[N];
int siz[N];

int find(int x) {
    if (num[x] != x) num[x] = find(num[x]);
    return num[x];
}

int main() {
    int n, m, x, y;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) num[i] = i, siz[i] = 1;

    char op[3];
    while (m--) {
        scanf("%s", op);
        if (op[0] == 'C') {
            cin >> x >> y;
            if (find(num[x]) == find(num[y])) continue;
            siz[find(x)] += siz[find(y)];
            num[find(y)] = find(x);
        }
        else if (op[1] == '1') {
            cin >> x >> y;
            if (find(x) == find(y)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        else {
            cin >> x;
            cout << siz[find(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
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
// 食物链

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 100010;
int p[N], d[N];

int find(int x) {
    if (p[x] != x) {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

// 路径压缩
// 暂时不改变秩，再次查询的时候再改变

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1;i <= n;i++) p[i] = i;


    int t, x, y, res = 0;
    while (k--) {
        cin >> t >> x >> y;
        if (x > n || y > n) res++;
        else {
            int px = find(x), py = find(y);
            if (t == 1) {
                if (px == py && (d[x] - d[y]) % 3) res++;
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else {
                if (px == py && (d[x] - d[y] - 1) % 3) res++;
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] - d[x] + 1;
                }
            }
        }
    }

    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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
int n, m, num[N];

void down(int x) {
    int u = x;
    if (2 * x <= n && num[2 * x] < num[u]) u = 2 * x;
    if (2 * x + 1 <= n && num[2 * x + 1] < num[u]) u = 2 * x + 1;
    if (u != x) {
        swap(num[u], num[x]);
        down(u);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> num[i];

    for (int i = n / 2;i > 0;i--) down(i);
    while (m--) {
        cout << num[1] << " ";
        num[1] = num[n--];
        down(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
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
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

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)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n--)
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt++;
            m++;
            // ph[x]=y :第x个插入的数的位置为y
            // hp[x]=y :位置为x的数是第y个插入的
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt--;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt--;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }

    return 0;
}

模拟哈希-开放寻址法

哈希的参考资料：https://blog.csdn.net/raelum/article/details/128793474

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 <algorithm>
#include <iostream>
#include<string.h>
using namespace std;
typedef long long LL;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) {
        k++;
        if (k == N) k = 0;
    }
    return k;
}


int main() {
    int n;

    memset(h, 0x3f, sizeof(h));

    string op;
    int x;
    cin >> n;
    while (n--) {
        cin >> op >> x;
        if (op == "I") h[find(x)] = x;
        else h[find(x)] == null ? cout << "No\n" : cout << "Yes\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
// 字符串哈希

#include <algorithm>
#include <iostream>
#include<string.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N = 200003, P = 131;

ULL h[N], pre[N];

ULL get(int l, int r) {
    return h[r] - h[l - 1] * pre[r - l + 1];
}

int main() {
    int n, m;
    cin >> n >> m;
    char str[N];
    cin >> str + 1;

    pre[0] = 1;
    for (int i = 1; i <= n;i++) {
        h[i] = h[i - 1] * P + str[i];
        pre[i] = pre[i - 1] * P;
    }

    int a, b, c, d;
    while (m--) {
        cin >> a >> b >> c >> d;
        if (get(a, b) == get(c, d)) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

总结

这是 AcWing 算法基础课的第二讲，这几天一直在做这个，刷了大概有5天吧。题并不难，主要是效率实在太低了。以后如果疲了一定要及时休息，状态不好时的效率实在太低了。

然后就是一点收获吧。这章主要是数据结构，之前学的都是使用结构体加指针实现的，这里全部使用的数组模拟，或者说链式前向星，据说这样时间开销会降低很多。以后要习惯这一点，在具体写代码时要应用进去。

还有4讲，争取用小学期刷完？当然一定要兼顾别的事情。DP和图论可能会比较难，所以一定要提高时间利用率！！！

#AcWing #算法题 #数据结构
AcWing 第2讲 数据结构
https://asxjdb.github.io/2023/06/20/AcWing-ch2/
作者
Asxjdb
发布于
2023年6月20日
许可协议