算法-数据结构-练习

发表于 更新于

目前共计 13 道题。

直方图中最大的矩形-单调栈

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 <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;

int n;
ll h[N];
ll s[N], w[N], p = 0; // 栈和指针对应矩形对应的宽度

int main()
{
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; i++)
            cin >> h[i];
        h[++n] = 0;
        ll res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (p == 0 || h[i] > s[p])
                s[++p] = h[i], w[p] = 1;
            else
            {
                ll width = 0;
                while (p != 0 && h[i] <= s[p])
                {
                    width += w[p];
                    res = max(res, width * s[p]);
                    p--;
                }
                s[++p] = h[i], w[p] = width + 1;
                res = max(res, w[p] * s[p]);
            }
        }
        cout << res << endl;
    }
}

最大子序和-单调队列

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 <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5 + 10;

int n, m;
int a[N];
ll p[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    deque<int> q;
    q.push_back(0);
    ll ans = -0x3f3f3f3f;
    for (int i = 1; i <= n; ++i)
    {
        while (q.size() && i - q.front() > m)
            q.pop_front();
        ans = max(ans, p[i] - p[q.front()]);
        while (q.size() && p[i] <= p[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    cout << ans << endl;
}

雪花雪花雪花-字符串哈希

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10, MOD = 99991;

int n;
ll head[N], snow[N][6], ne[N], tot = 0;

ll Hash(ll *a)
{
    ll sum = 0, mul = 1;
    for (int i = 0; i < 6; ++i)
    {
        sum = (sum + a[i]) % MOD;
        mul = (mul * a[i]) % MOD;
    }
    return (sum + mul) % MOD;
}

bool equal(ll *a, ll *b)
{
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 6; j++)
        {
            bool eq = 1;
            for (int k = 0; k < 6; k++)
                if (a[(i + k) % 6] != b[(j + k) % 6])
                    eq = 0;
            if (eq)
                return 1;
            eq = 1;
            for (int k = 0; k < 6; k++)
                if (a[(i + k) % 6] != b[(j - k + 6) % 6])
                    eq = 0;
            if (eq)
                return 1;
        }
    return 0;
}

bool insert(ll *a)
{
    ll val = Hash(a);
    for (int i = head[val]; i; i = ne[i])
    {
        if (equal(a, snow[i]))
            return 1;
    }
    ++tot;
    memcpy(snow[tot], a, 6 * sizeof(ll));
    ne[tot] = head[val];
    head[val] = tot;
    return 0;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        ll a[6];
        for (int j = 0; j < 6; j++)
            cin >> a[j];
        if (insert(a))
        {
            cout << "Twin snowflakes found." << endl;
            return 0;
        }
    }
    cout << "No two snowflakes are alike." << endl;
}

序列-堆

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
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 2010;

int m, n, a[N], b[N], c[N];
PII heap[N];
int tot = 0;

void up(int p)
{
    while (p > 1)
    {
        if (heap[p] < heap[p / 2])
        {
            swap(heap[p], heap[p / 2]);
            p /= 2;
        }
        else
            break;
    }
}

void insert(PII val)
{
    heap[++tot] = val;
    up(tot);
}

void down(int p)
{
    int s = 2 * p;
    while (s <= n)
    {
        if (s < n && heap[s + 1] < heap[s])
            s += 1;
        if (heap[p] > heap[s])
        {
            swap(heap[p], heap[s]);
            p = s, s = 2 * p;
        }
        else
            break;
    }
}

void extract()
{
    heap[1] = heap[tot--];
    down(1);
}

void merge()
{
    tot = 0;
    for (int i = 1; i <= n; i++)
        insert({a[1] + b[i], 1});
    for (int i = 1; i <= n; i++)
    {
        int s, p;
        tie(s, p) = heap[1];
        extract();
        c[i] = s;
        insert({s - a[p] + a[p + 1], p + 1});
    }
    for (int i = 1; i <= n; i++)
        a[i] = c[i];
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> m >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + 1 + n);
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j <= n; j++)
                cin >> b[j];
            merge();
        }
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
}

荷马史诗-Huffman树

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10, M = 2 * N;

struct Node
{
    ll val, depth;
    Node *next[10];

    bool operator<(Node b)
    {
        return this->val == b.val ? this->depth < b.depth : this->val < b.val;
    }
};

int n, m; // n 个单词， m 进制
Node *heap[N];
int tot = 0;

void up(int p)
{
    while (p > 1)
    {
        if (*heap[p] < *heap[p / 2])
        {
            swap(heap[p], heap[p / 2]);
            p /= 2;
        }
        else
            break;
    }
}

void down(int p)
{
    int s = 2 * p;
    while (s <= tot)
    {
        if (s < tot && *heap[s + 1] < *heap[s])
            s += 1;
        if (*heap[s] < *heap[p])
        {
            swap(heap[s], heap[p]);
            p = s, s = p * 2;
        }
        else
            break;
    }
}

void insert(Node *val)
{
    heap[++tot] = val;
    up(tot);
}

Node *extract()
{
    Node *ret = heap[1];
    heap[1] = heap[tot--];
    down(1);
    return ret;
}

ll len = 0, sum = 0;
void dfs(Node *t, ll d)
{
    if (t->next[0] == nullptr)
    { // 若为叶子节点
        sum += t->val * d;
        len = max(len, d);
    }
    else
    {
        for (int i = 0; i < m; i++)
            dfs(t->next[i], d + 1);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        Node *t = new Node();
        cin >> t->val;
        insert(t);
    }
    while (m > 2 && (n - 1) % (m - 1) != 0)
    {
        insert(new Node());
        n++;
    }
    while (tot > 1)
    {
        Node *t = new Node();
        for (int i = 0; i < m; i++)
        {
            t->next[i] = extract();
            t->val += t->next[i]->val;
            t->depth = max(t->depth, t->next[i]->depth);
        }
        t->depth++;
        insert(t);
    }
    dfs(heap[1], 0);
    cout << sum << endl
         << len << endl;
}

括号画家-栈

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 <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

unordered_map<char, char> p{
    {')', '('},
    {'}', '{'},
    {']', '['},
};

char str[N];
int stk[N]; // 标识位置
int top = -1;

int main()
{
    cin >> (str + 1);
    int len = strlen(str + 1);

    int res = 0;
    for (int i = 1; i <= len; i++)
    {
        char t = str[i];
        if (top != -1 && (t == ')' || t == '}' || t == ']') && str[stk[top]] == p[t])
        {
            top--;
            if (top == -1)
                res = max(res, i);
            else
                res = max(res, i - stk[top]);
        }
        else
            stk[++top] = i;
    }
    cout << 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
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

int n, m;
int grid[N][N]; // 在第 j 列，从第 i 行往上有多少连续的 F
int stk[N], w[N], top = -1;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char ch;
            cin >> ch;
            if (ch == 'F')
                grid[i][j] = 1;
        }
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            if (grid[i][j])
                grid[i][j] += grid[i + 1][j];
    int res = 0;
    for (int i = 1; i <= n; i++)
    { // 在第 i 行做单调栈
        int squ = 0;
        memset(w, 0, sizeof(w));
        top = -1;
        for (int j = 1; j <= m + 1; j++)
        {
            if (top == -1 || grid[i][j] > stk[top])
                stk[++top] = grid[i][j], w[top] = 1;
            else
            {
                int width = 0;
                while (top != -1 && grid[i][j] <= stk[top])
                {
                    width += w[top];
                    squ = max(squ, width * stk[top]);
                    top--;
                }
                stk[++top] = grid[i][j], w[top] = width + 1;
                squ = max(squ, stk[top] * w[top]);
            }
        }
        res = max(squ, res);
    }
    cout << 3 * res << endl;
}

程序自动分析-并查集

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
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 2e5 + 10;

unordered_map<int, int> disp;
int tot = 0;

vector<PII> contri;

int n;
int p[N];

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

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        memset(p, 0, sizeof(p));
        disp.clear();
        tot = 0;
        contri.clear();
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int a, b, e;
            cin >> a >> b >> e;
            if (disp.count(a) == 0)
                disp[a] = ++tot, p[tot] = tot;
            if (disp.count(b) == 0)
                disp[b] = ++tot, p[tot] = tot;
            a = disp[a], b = disp[b];
            if (e == 0)
                contri.push_back({a, b});
            else if (find(a) != find(b))
                p[find(a)] = find(b);
        }
        bool flag = true;
        for (auto p : contri)
        {
            int a, b;
            tie(a, b) = p;
            if (find(a) == find(b))
            {
                flag = false;
                break;
            }
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
}

银河英雄传说-带权并查集

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>
using namespace std;
const int N = 3e5 + 110;

int n = N - 10;
int p[N], l[N], d[N]; // 代表元、队列长度、到队首距离

int find(int x)
{
    if (x == p[x])
        return x;
    int root = find(p[x]); // 需要先递归地压缩父节点
    d[x] += d[p[x]];
    return p[x] = root;
}

void merge(int a, int b) // 把 a 加入到 b 的尾部，此时 a b 本身都是代表元
{
    d[a] = l[b];
    l[b] += l[a];
    p[a] = b;
}

int main()
{
    for (int i = 1; i <= n; i++)
        p[i] = i, l[i] = 1;
    int t;
    cin >> t;
    while (t--)
    {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'M')
        {
            a = find(a), b = find(b);
            if (a != b)
                merge(a, b);
        }
        else
        {
            if (find(a) != find(b))
                cout << -1 << endl;
            else if (a == b)
                cout << 0 << endl;
            else
                cout << abs(d[a] - d[b]) - 1 << endl;
        }
    }
}

楼兰图腾-树状数组

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 10;

int n;
LL a[N], lt[N], rt[N];
LL ll[N], rl[N], lg[N], rg[N];

LL ask(int x, LL *c)
{
    LL res = 0;
    for (; x; x -= x & -x)
        res += c[x];
    return res;
}

void add(int x, int val, LL *c)
{
    for (; x <= n; x += x & -x)
        c[x] += val;
}

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

    // 先求 i 之前，多少数比 a[i] 小，多少数比 a[i] 大
    for (int i = 1; i <= n; i++)
    {
        ll[i] = ask(a[i] - 1, lt);
        lg[i] = ask(n, lt) - ask(a[i], lt);
        add(a[i], 1, lt);
    }

    for (int i = n; i >= 1; i--)
    {
        rl[i] = ask(a[i] - 1, rt);
        rg[i] = ask(n, rt) - ask(a[i], rt);
        add(a[i], 1, rt);
    }

    LL res1 = 0, res2 = 0;
    for (int i = 1; i <= n; i++)
    {
        res1 += lg[i] * rg[i];
        res2 += ll[i] * rl[i];
    }
    cout << res1 << " " << res2;
}

你能回答这些问题吗-线段树

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 5e5 + 10;

int n, m;
int a[N];

struct SegTree
{
    int l, r;
    ll sum, lmax, rmax, max;
} t[4 * N];

ll max(ll a, ll b, ll c)
{
    if (b > a)
        a = b;
    if (c > a)
        a = c;
    return a;
}

void pushup(SegTree &p, SegTree &l, SegTree &r)
{
    p.sum = l.sum + r.sum;
    p.lmax = max(l.lmax, l.sum + r.lmax);
    p.rmax = max(r.rmax, r.sum + l.rmax);
    p.max = max(l.max, r.max, l.rmax + r.lmax);
}

void build(int p, int l, int r)
{
    if (l == r)
    {
        t[p] = {l, l, a[l], a[l], a[l], a[l]};
        return;
    }
    t[p].l = l, t[p].r = r;
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    pushup(t[p], t[p * 2], t[p * 2 + 1]);
}

void change(int p, int x, int v)
{
    if (t[p].l == t[p].r)
    {
        t[p] = {x, x, v, v, v, v};
        return;
    }
    int mid = (t[p].l + t[p].r) / 2;
    if (x <= mid)
        change(p * 2, x, v);
    if (x > mid)
        change(p * 2 + 1, x, v);
    pushup(t[p], t[p * 2], t[p * 2 + 1]);
}

SegTree query(int p, int l, int r)
{
    if (l <= t[p].l && r >= t[p].r)
        return t[p];
    int mid = (t[p].l + t[p].r) / 2;
    if (r <= mid)
        return query(p * 2, l, r);
    if (l > mid)
        return query(p * 2 + 1, l, r);
    SegTree a, b, c;
    a = query(2 * p, l, r);
    b = query(2 * p + 1, l, r);
    pushup(c, a, b);
    return c;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while (m--)
    {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1)
        {
            if (a > b)
                swap(a, b);
            cout << query(1, a, b).max << endl;
        }
        else
            change(1, a, b);
    }
}

Rorororobot-线段树

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;

struct SegTree
{
    int l, r;
    int val; // 最大值
} t[N * 4];

int n, m, q;
int h[N];

void build(int p, int l, int r)
{
    t[p].l = l, t[p].r = r;
    if (l == r)
    {
        t[p].val = h[l];
        return;
    }
    int mid = l + r >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p].val = max(t[p * 2].val, t[p * 2 + 1].val);
}

int query(int p, int l, int r)
{
    if (l <= t[p].l && r >= t[p].r)
        return t[p].val;
    int mid = t[p].l + t[p].r >> 1;
    int res = 0;
    if (l <= mid)
        res = query(p * 2, l, r);
    if (r > mid)
        res = max(res, query(p * 2 + 1, l, r));
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> h[i];
    build(1, 1, m);
    cin >> q;
    while (q--)
    {
        int xs, ys, xt, yt, k;
        cin >> xs >> ys >> xt >> yt >> k;
        if (ys > yt)
        {
            swap(ys, yt);
            swap(xs, xt);
        }
        if (abs(yt - ys) % k || abs(xt - xs) % k)
        {
            cout << "NO" << endl;
            continue;
        }
        int top = query(1, ys, yt);
        if (top < xs && top < xt)
        {
            cout << "YES" << endl;
            continue;
        }
        int t = (top - xs + k - 1) / k;
        int reach = xs + t * k;
        if (reach == top)
            reach += k;
        if (reach > n)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
}

奇偶游戏

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
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 2e4 + 10;

int n, m;
int p[N];
bool d[N];
unordered_map<int, int> ump;

int disc(int x)
{
    if (ump.count(x) == 0)
        ump[x] = ++n;
    return ump[x];
}

int find(int x)
{
    if (p[x] == x)
        return x;
    int r = find(p[x]);
    d[x] ^= d[p[x]];
    return p[x] = r;
}

int main()
{
    cin >> n >> m;
    n = 0;
    for (int i = 0; i < N; i++)
        p[i] = i, d[i] = 0;
    int res = m;
    for (int i = 1; i <= m; i++)
    {
        string str;
        int a, b;
        cin >> a >> b >> str;
        a = disc(a - 1), b = disc(b); // 能确定关系的是 a-1 和 b
        bool rel = str[0] == 'o';
        int pa = find(a), pb = find(b);
        if (pa == pb)
        {
            if ((d[a] ^ d[b]) != rel)
            {
                res = i - 1;
                break;
            }
        }
        else
        {
            d[pb] = d[a] ^ d[b] ^ rel;
            p[pb] = pa;
        }
    }
    cout << res << endl;
}

Minimum Possible Integer After at Most K Adjacent Swaps On Digits

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
class Solution
{
public:
    static const int N = 3e4 + 10;

    int n;
    int tr[N];

    void add(int x, int v) // 位置 x 加 v
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }

    int sum(int x) // 1~x 前缀和
    {
        int sum = 0;
        for (; x >= 1; x -= x & -x)
            sum += tr[x];
        return sum;
    }

    string minInteger(string num, int k)
    {
        n = num.length();
        num = " " + num;
        list<int> li[10]; // 保存了0~9的所有出现位置
        for (int i = 1; i <= n; i++)
            li[num[i] - '0'].push_back(i);

        string res = "";
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= 9; j++)
            {
                if (li[j].size() && li[j].front() + (sum(n) - sum(li[j].front())) - i <= k)
                {
                    k -= (li[j].front() + (sum(n) - sum(li[j].front())) - i);
                    add(li[j].front(), 1);
                    li[j].pop_front();
                    res.push_back(j + '0');
                    break;
                }
            }
        }
        return res;
    }
};