数据结构作业题解09

数据结构作业题解09

exdoubled Lv4
  2025-11-24 17:00 2025-11-24 17:00 Created   2025-12-27 20:23:32 2025-12-27 20:23:32 Updated    7.4k Words  36 Mins  

A.SA. 01迷宫

说明

有一个仅由数字 \(0\) 与 \(1\) 组成的 \(n \times n\) 迷宫。若你位于一格 \(0\) 上，那么你可以移动到相邻 \(4\) 格中的某一格 \(1\) 上，同样若你位于一格 \(1\) 上，那么你可以移动到相邻 \(4\) 格中的某一格 \(0\) 上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入格式

第 \(1\) 行为两个正整数 \(n, m\)。

下面 \(n\) 行，每行 \(n\) 个字符，字符只可能是 \(0\) 或者 \(1\)，字符之间没有空格。

接下来 \(m\) 行，每行 \(2\) 个用空格分隔的正整数 \(i, j\)，对应了迷宫中第 \(i\) 行第 \(j\) 列的一个格子，询问从这一格开始能移动到多少格。

输出格式

\(m\) 行，对于每个询问输出相应答案。

样例

输入数据 1

1
2
3
4
5
2 2
01
10
1 1
2 2

输出数据 1

1
2
4
4

提示

所有格子互相可达。

对于 \(20\%\) 的数据，\(n \leq 10\)；

对于 \(40\%\) 的数据，\(n \leq 50\)；

对于 \(50\%\) 的数据，\(m \leq 5\)；

对于 \(100\%\) 的数据，\(n \leq 100, m \leq 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;
vector<string> s;
vector<vector<int>> g;
vector<int> ans;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

void buildg() {
    g.assign(n, vector<int>(n, -1));
    ans.clear();

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (g[i][j] != -1) continue;
            queue<pair<int, int>> q;
            q.emplace(i, j);
            g[i][j] = ans.size();
            int cnt = 1;

            while (!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                for (int dir = 0; dir < 4; ++dir) {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if (s[nx][ny] == s[x][y]) continue;
                    if (g[nx][ny] != -1) continue;
                    g[nx][ny] = g[i][j];
                    ++cnt;
                    q.emplace(nx, ny);

                }
            }
            ans.push_back(cnt);
        }
    }
}

int main() {
    int m;
    cin >> n >> m;
    s.resize(n);
    for (int i = 0; i < n; ++i) cin >> s[i];

    buildg();

    while (m--) {
        int i, j;
        cin >> i >> j;
        --i; --j;
        cout << ans[g[i][j]] << '\n';
    }

    return 0;
}

B. 妙妙米奇树

题目背景

\(Y\) 非常喜欢妙妙米树。于是他在自己家种植了一棵有 \(n\) 个节点的妙妙米树。

\(Y\) 还养了一条名为 布料 的狗，这条狗最爱吃着一棵子树根植于不同颜色的米。

已知树上每个节点最初颜色是 \(0\)，节点 \(1\) 为树根，布料只会进行 \(q\) 次染色操作，每次操作可以用两个数字 \(op, x, y\) 表示。

你需要对布料的 \(q\) 次操作进行管理。

  • 如果 \(op = 1\)，表示将以节点 \(x\) 为根的子树（即 \(x\) 和其所有子孙后代节点）全部染上颜色 \(y\)。
  • 如果 \(op = 2\)，表示将节点 \(x\) 到根节点 \(1\) 的路径上的所有节点（包含 \(x\) 和 \(1\) 自身）染成颜色 \(y\)。

你需要回答每个节点的颜色是什么。

输入格式

第一行两个整数 \(n, q\)，分别表示节点数量和操作次数。

第二行 \(n-1\) 个整数 \(p_2, p_3, \dots, p_n\)，依次表示第 \(i\) 节点的父节点。

接下来 \(q\) 行每行三个整数 \(op, x, y\)，表示这次 \(q\) 个操作。

输出格式

输出 \(n\) 行，每行两个数用空格分开表示每个节点的颜色。

样例

输入数据 1

1
2
3
4
5
6
7
5 5
1 1 2 2
1 2 3
2 5 1
1 2 5
2 3 3
2 4 1

输出数据 1

1
5 5 1 5 1

输入数据 2

1
2
3
4
5
6
7
8
9
10
11
7 9
1 2 1 4 4 2
2 7 9
1 4 2
1 2 5
2 6 7
1 1 8
2 3 1
2 5 3
1 3 4
2 1 6

输出数据 2

1
6 8 4 5 3 7 3

数据范围

\(1 \leq n, q \leq 10^5\), \(1 \leq p_i \leq i\), \(1 \leq op \leq 2\), \(1 \leq x \leq n\), \(1 \leq y \leq 10^9\)。

思路与题解

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
#include <iostream>
#include <vector>
#include <tuple>
#include <numeric>

using namespace std;

int n;
vector<int> pa;
vector<tuple<int, int, int>> query;
vector<vector<int>> child;
vector<int> color;

vector<int> tin, tout, order;
int cnt = 0;

void build(int u) {
    tin[u] = cnt;
    order[cnt++] = u;
    for (int v : child[u]) build(v);
    tout[u] = cnt;
}

struct DSU {
    vector<int> fa;
    DSU(int n = 0) { init(n); }
    void init(int n) { fa.resize(n); iota(fa.begin(), fa.end(), 0); }

    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

    void erase(int x, int nxt) { fa[x] = nxt; }
};

int main() {
    int q;
    cin >> n >> q;
    pa.assign(n,-1);
    child.resize(n);
    color.assign(n,0);
    for (int i = 1; i < n; ++i) {
        int p;
        cin >> p;
        p--;
        pa[i] = p;
        child[p].emplace_back(i);
    }
    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        x--;
        query.emplace_back(op, x, y);
    }

    tin.resize(n);
    tout.resize(n);
    order.resize(n);
    build(0);

    DSU euler(n + 1);
    DSU up(n + 1);
    auto parent_idx = [&](int x) { return pa[x] == -1 ? n : pa[x]; };
    auto remove_node = [&](int node) {
        int nxt_up = up.find(parent_idx(node));
        up.erase(node, nxt_up);
    };

    for (int i = n; i >= 0; --i) up.fa.push_back(i);
    up.init(n + 1);

    auto color_node = [&](int node, int val) {
        color[node] = val;
        remove_node(node);
    };

    for (int i = (int)query.size() - 1; i >= 0; --i) {
        auto [op, x, y] = query[i];
        if (op == 1) {
            int cur = euler.find(tin[x]);
            while (cur < tout[x]) {
                int node = order[cur];
                if (color[node] == 0) color_node(node, y);
                euler.erase(cur, euler.find(cur + 1));
                cur = euler.find(cur);
            }
        } else {
            int cur = up.find(x);
            while (cur != n) {
                if (color[cur] == 0) color_node(cur, y);
                cur = up.find(cur);
            }
        }
    }

    for (auto a : color) {
        cout << a  << ' ';
    }
    return 0;
}

C. 超疯狂插队

题目背景

现有一支训练中的 \(n\) 名同学组成的战队。每个人的潜力值为 \(a_i\)，最多可以使用“爆气”技能次数为 \(k\)。

由于 \(Y\) 不在，同学之间进行对战。开始时，训练场也是满座基本法，规则如下：

  1. 每个同学优先选择潜力值 恰好 同伴的侧面。
  2. 如果 \(A\) 的潜力值恰小于 \(B\) 且 \(A\) 可以站在 \(B\) 的侧面，否则不行；
  3. 每个同学可以使用 一次 “爆气”技能，潜在潜力值比他人高的同学；
  4. 使用“爆气”技能后，仍然可以遇到潜力值不大于其的同学侧面。

请问，在这种规则下，每个同学都从自身开始，能遇到的最前边的位置是什么（位置从 \(1\) 开始编号）。还需对每个人在比赛中能够使用“爆气”的次数。

形式化地说，本题图对每个 \(i\) (\(1 \leq i \leq n\)) 求解从第 \(i\) 个人往前数 \(k_i + 1\) 个潜力值大于 \(a_i\) 的人的位置 \(+1\)，如果不存在则输出 \(1\)。

输入格式

第一行一个整数 \(n\) 表示同学的数。

第二行 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)，用空格隔开表示每个同学的潜力值。

第三行 \(n\) 个整数 \(k_1, k_2, \dots, k_n\)，用空格隔开表示每个同学最多可以使用的爆气技能次数。

输出格式

一行 \(n\) 个数用空格隔开表示每个同学能到的最靠前的队的位置。

样例

输入数据 1

1
2
3
5
1 1 1 2 5
1 1 1 2 3

输出数据 1

1
1 1 1 1 2

输入数据 2

1
2
3
10
1 8 18 8 26 5 10 35 19 32 17
1 2 1 1 3 2 1 1 5

输出数据 2

1
1 1 1 1 1 1 3 8 1

数据范围

\(1 \leq n \leq 2 \times 10^5\)，\(1 \leq a_i, k_i \leq 30\)。

思路与题解

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 <vector>
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

int lowbit (int idx) { return idx & -idx; }

class Fenwick {
    int n;
    vector<int> bit;
public:
    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, int val) {
        for (++idx; idx <= n; idx += lowbit(idx)) bit[idx] += val;
    }

    int sum(int idx) const {
        int res = 0;
        for (++idx; idx > 0; idx -= lowbit(idx)) res += bit[idx];
        return res;
    }

    int kth(int k) const {
        int x = 0;
        int acc = 0;
        int step = 1;
        while (step << 1 <= n) step <<= 1;
        for (; step; step >>= 1) {
            int nxt = x + step;
            if (nxt <= n && acc + bit[nxt] < k) {
                acc += bit[nxt];
                x = nxt;
            }
        }
        return x;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> a(n), k(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> k[i];

    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);

    sort(idx.begin(), idx.end(), [&](int x, int y) {
        if (a[x] != a[y]) return a[x] > a[y];
        return x < y;
    });

    vector<int> ans(n, 1);
    Fenwick fw(n);
    int pos = 0;
    while (pos < n) {
        int start = pos;
        int val = a[idx[pos]];
        while (pos < n && a[idx[pos]] == val) {
            int i = idx[pos];
            int cnt = fw.sum(i - 1);
            int need = k[i] + 1;
            if (cnt >= need) {
                int target = cnt - k[i];
                int barrier = fw.kth(target);
                ans[i] = barrier + 2;
            } else {
                ans[i] = 1;
            }
            ++pos;
        }
        for (int j = start; j < pos; ++j) fw.add(idx[j], 1);
    }

    for (auto i : ans) cout << i << " ";
    return 0;
}

D. 本质不同子串计数

题目描述

哔啦啦，哗啦啦，天上掉落一条随机字符串。

萌哒哒，萌哒哒，兔兔数起本质不同子串数。

输入格式

输出一个小写字母字符串 \(s\)，保证 \(1 \leq |s| \leq 10^5\) 且每个字符在 \(26\) 个小写字符中随机。

输出格式

一个正整数，表示本质不同子串数。

样例

Sample1.in

1
ababa

Sample1.out

1
9

Sample2.in

1
decbcccedcbeecccdb

Sample2.out

1
107

数据范围

\(1 \leq |s| \leq 10^5\)

时间限制 \(1000\)ms，空间 \(512\)MB

思路与题解

后缀自动机模板

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

using namespace std;

struct State {
    int next[26];
    int link;
    int len;
    State() : link(-1), len(0) {
        memset(next, -1, sizeof(next));
    }
};

int main() {
    string s;
    cin >> s;
    int n = s.size();

    vector<State> st;
    st.reserve(2 * n);
    st.emplace_back();
    int last = 0;

    auto extend = [&](int c) {
        int cur = (int)st.size();
        st.emplace_back();
        st[cur].len = st[last].len + 1;

        int p = last;
        while (p != -1 && st[p].next[c] == -1) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                int clone = (int)st.size();
                st.push_back(st[q]);
                st[clone].len = st[p].len + 1;
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    };

    for (char ch : s) {
        int c = ch - 'a';
        extend(c);
    }

    long long ans = 0;
    for (long long i = 1; i < st.size(); ++i) {
        ans += st[i].len - st[st[i].link].len;
    }
    cout << ans;
    return 0;
}

E. 傻瓜和道路

Description

在伯兰兹这个国家，有 \(n\) 座城市，每座城市都通过道路联通，因此每两个城市之间只有一条简单路径。

（简单路径指的是一条路径上没有重复的城市）

不同城市之间的傻瓜们会参观其他城市，他们到另一座城市拜访只会走简单路径。

现在给出这个国家傻瓜们所在的城市和要去参观的城市，请计算每条路径有多少个傻瓜经过。

城市编号 \(1\) 到 \(n\)。

Format

Input

第一行包括一个整数 \(n\) 表示城市数量。

接下来 \(n-1\) 行表示 \(n-1\) 条道路，每行两个整数 \(u, v\)，表示城市 \(u\) 和城市 \(v\) 之间有道路相连。

接下来一个整数 \(k\)，表示傻瓜的个数。

接下来 \(k\) 行，每行两个整数 \(a, b\)，表示傻瓜要从城市 \(a\) 到城市 \(b\)。

Output

输出 \(n-1\) 个整数，第 \(i\) 个数表示第 \(i\) 条边有多少个傻瓜经过。

Samples

输入样例 1

1
2
3
4
5
6
7
8
9
5
1 2
1 3
2 4
3 5
3
2 5
4 5
3 2

输出样例 1

1
2 1 1 1

输入样例 2

1
2
3
4
5
6
7
8
9
5
4 1
4 2
4 3
4 5
3
1 2
3 5
1 3

输出样例 2

1
3 1 1 1

Limitation

\(n \leq 10^5, k \leq 10^5\)。

思路与题解

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 <iostream>
#include <vector>
#include <stack>

using namespace std;

int n,m;
int LOG = 1;
vector<vector<int>> up;
vector<vector<int>> grid; // node
vector<int> depth;
vector<int> order;
vector<pair<int, int>> edges;

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    int diff = depth[a] - depth[b];
    for (int k = 0; k < LOG; ++k)
        if (diff & (1 << k))
            a = up[k][a];
    if (a == b) return a;
    for (int k = LOG - 1; k >= 0; --k) {
        if (up[k][a] != up[k][b]) {
            a = up[k][a];
            b = up[k][b];
        }
    }
    return up[0][a];
}

int main() {
    cin >> n;
    grid.resize(n);
    for (int i = 0; i < n-1; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        grid[u].emplace_back(v);
        grid[v].emplace_back(u);
        edges.emplace_back(u, v);
    }
    while ((1 << LOG) <= n) ++LOG;
    vector<int> temp(n,-1);
    up.resize(LOG, temp);
    depth.resize(n,0);

    stack<pair<int,int>> st;
    st.emplace(0, -1);
    up[0][0] = 0;
    depth[0] = 0;


    while (!st.empty()) {
        auto [u, p] = st.top(); st.pop();
        order.emplace_back(u);
        for (auto v : grid[u]) {
            if (v == p) continue;
            up[0][v] = u;
            depth[v] = depth[u] + 1;
            st.emplace(v, u);
        }
    }

    for (int k = 1; k < LOG; ++k) {
        for (int v = 0; v < n; ++v) {
            int mid = up[k-1][v];
            up[k][v] = (mid == -1 ? -1 : up[k-1][mid]);
        }
    }

    int k;
    cin >> k;
    vector<long long> add(n, 0), sub(n, 0);
    while (k--) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        int c = lca(a, b);
        add[a]++; add[b]++; add[c]-=2;
    }

    sub = add;
    for (int i = order.size()-1; i >= 0; --i) {
        int u = order[i];
        if (up[0][u]) sub[up[0][u]] += sub[u];
    }

    vector<long long> ans(n-1);
    for (int i = 0; i < n-1; ++i) {
        int u = edges[i].first;
        int v = edges[i].second;
        if (up[0][u] == v) ans[i] = sub[u];
        else if (up[0][v] == u) ans[i] = sub[v];
        else ans[i] = 0;
    }
    for (auto i : ans) cout << i << ' ';

    return 0;
}

F. 郁闷的出租员

Description

OIER 家是一家专业化软件公司，有着数以万计的员工。作为一名出租员，我的任务之一是统计每位员工的工资。本是份不错的工作，但是令人郁闷的是，我们的老板没有手，经常调整员工的工资。如果他心情好，就可能把某个员工的工资提高一倍；如果心情不好，就可能把当前在公司所有员工的工资的中位数给所有员工，从这个数开始，以这个数为基准，向后连续一段的所有员工的工资都进行一次调整。

工资的调整策略让员工很烦，尤其是全体出租员工的薪酬。一位出租员工发现自己的工资已经低于公司规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界是预先给定的。每当一个人离开公司，我就要从电脑中给出的工资资料表上，删掉，每当公司给增加了一份员工，我就要给每份最新的一个工资表。

老板偶尔还做些关于员工的薪酬，他并不向全体员工的工资做出查询，而是向现在在岗员工 \(k\) 的最少工资 \(i\) 多少，每询问一次，他就会重新进行一次新的调整，即给 \(i\) 个员工每人增加 \(1\) 个工资。

好了，现在你手里其他的任务已经不少了。老板给你的报酬，我也给你一个工资统计程序，怎么写，不提供时间限制。

如果你手里的 \(i\) 的最少工资已经超过标准，那么将 \(i\) 个人的后面的工资全涨 \(1\)。

Format

Input

一行有 \(n\) 个数 \(n, \min, m\) 表示共有多少条命令，\(\min\) 表示工资下界。

接下来 \(n\) 行，每行一个数 \(a_i\)，表示一个整数 \(k\)，表示一条命令。命令可以由以下四者之一：

  • I K 薪酬：一个员工薪酬，即给出 \(k\) 为人，如果手里的 \(i\) 的最少工资 \(\geq \min\) 算作 \(1\) 个工资，他将立刻离开公司。
  • P K 岗位：给出 \(k\) 的工资下界 \(a_k\)。
  • Q K 把每位员工的工资调整 \(k\)。
  • R K 把前面 \(k\) 个的工资。

任凭说时，可以认为公司里一个员工也没有。

Output

对与 \(IK\) 命令，你只需要单独输出一行，仅包含一个整数，为当前工资 \(\leq\) 员工工资下界 \(a_k\) 的员工总数，如果 \(k\) 大于目前的员工数，则输出 \(1\)。

输出最后一条命令，为离开公司的员工的总数。

请注意，初始工资低于下界的员工不会离开公司。

Samples

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
9 10 20
1
2
3
5
10
9
15
3
1
R 1
P 2
I 1
Q 2
P 5
K 1
I 3
Q 3
P 4
I 2

输出样例

1
2
3
0
1
2

Limitation

\(n \leq 3 \times 10^5, \min \leq 10^9\)

每次工资调整不超过 \(10^9\)，新员工工资不超过 \(10^9\)

思路与题解

随机 treap

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

using namespace std;
using ll = long long;

struct Node {
    ll val;
    int pr;
    int sz;
    Node *l, *r;
    Node(ll v): val(v),pr((rand()<<16)^rand()),sz(1),l(nullptr),r(nullptr){}
};

int getsz(Node* t){ return t ? t->sz : 0; }

void pull(Node* t){ if(t) t->sz = 1 + getsz(t->l) + getsz(t->r); }

void split(Node* t, ll key, Node*& a, Node*& b) {
    if (!t) {
        a = b = nullptr;
        return;
    }
    if (t->val < key) {
        a = t;
        split(t->r, key, a->r, b);
        pull(a);
    } else {
        b = t;
        split(t->l, key, a, b->l);
        pull(b);
    }
}

Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->pr < b->pr) {
        a->r = merge(a->r, b);
        pull(a);
        return a;
    } else {
        b->l = merge(a, b->l);
        pull(b);
        return b;
    }
}

void insert(Node*& root, ll v) {
    Node *a, *b;
    split(root, v, a, b);
    root = merge(merge(a,new Node(v)),b);
}

Node* kth(Node* t, int k) {
    if (!t) return nullptr;
    int l = getsz(t->l);
    if (k == l+1) return t;
    if (k <= l) return kth(t->l, k);
    return kth(t->r, k-l-1);
}

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

    srand(time(nullptr));
    Node *root = nullptr;
    ll base = 0;
    ll leaveCnt = 0;


    while (n--) {
        char op;
        ll k;
        cin >> op >> k;
        if (op == 'I') {
            if (k >= m) insert(root, k - base);
        } else if (op == 'A') {
            base += k;
        } else if (op == 'S') {
            base -= k;
            ll t = m - base;
            Node *a, *b;
            split(root, t, a, b);
            leaveCnt += getsz(a);
            root = b;
        } else if (op == 'F') {
            int sz = getsz(root);
            if (k > sz) cout << -1 << "\n";
            else {
                int rank = sz - k + 1;
                Node* node = kth(root, rank);
                cout << (node->val + base) << "\n";
            }
        }
    }
    cout << leaveCnt << "\n";
    return 0;
}

G. 同步跑

题目背景

因为题目太难，同学们集体罢工不在考试，于是结伴跑到操场上去了。

\(hkhkhk\) 发现上次跑步同学们都做着自己的事，认为这样行为不安全对谁都不好，所以这次同学们都往前跑。

题目描述

操场是块空地，操场看成一个平面，建立平面直角坐标系。

同学们分成 \(n\) 组同时在跑。

  • 同学们分成了 \(n\) 组，每组 \(w_i\) 个同学。他们可同时启动并跑都是 \((0, w_i)\) (跑：向 \(y\) 轴方向以 \(w_i\) 速度跑动), 每个同学有一个残留距离 \(w_i\)。他会跑足，当跑到 \((x+w_i, y+w_i)\) 时，能够复位到 \((x, y)\) 刚起点 \((x+w_i, y+w_i)\) 这条线上段上的人。
  • 每一组同学都从原点在 \(y\) 轴上。位置在 \((0, p_i)\)。他们可同时启动并跑都是 \((v_i, 0)\) (跑：向 \(x\) 轴方向以 \(v_i\) 速度跑动), 每个同学有一个残留距离 \(w_i\)。他会跑足，当跑到位于坐标 \((r+w_i, y)\) 时，能够复位到 \((r, y)\) 刚起点 \((r+w_i, y)\) 这条线上段上的人
  • 同学们拥有一个 \(C_i\) 的出现时间有。可以随时发力，而不是间隔时间。这个同学会出现开启：退出位上，然后按照内的速度奔跑。
  • 同学们会在自己跑的时候，会在自己跑的范围内内寻找别的人。然后需要求出每位同学在自己跑的范围内理想。理想距离最少几个不同的人** (不包括自己的人)。 (跑的时候而已，一点都不关系**)

输入格式

第一行 \(n\) 表示同学的个数。

接下来 \(n\) 行，每行 \(4\) 个整数 \(v_i, p_i, w_i, C_i\) 分别表示每个同学的速度、起始位置、残留距离和出现时间。

\(p_i\) 是 y 轴上的位置，即 \((0, p_i)\) 或 \((p_i, 0)\)。 (根据题目描述推测 \(p_i\) 的意义)

输出格式

一个正整数，表示第一个人跑完以后和最后一个同学跑完的不的人数。

样例

样例 #1

输入：

1
2
3
2
2 1 1 1
1 2 2 1

样例 #1 输出：

1
1

样例 #2

输入：

1
2
3
4
5
6
5
3 3 5 1
5 5 1 2
3 2 1 1
3 2 2 1
5 5 2 2

样例 #2 输出：

1
2

提示

【数据范围】

对于 \(20\%\) 的数据，\(n \leq 1000\)

对于 \(50\%\) 的数据， \(v_i = v_j\)

对于 \(100\%\) 的数据，\(1 \leq n \leq 10^5, v_i, p_i, w_i, C_i \leq 10^9\)，\(a \in \{1, 2\}\)，保证同组的同学中，任意两个同学的 \(v_i, p_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
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 <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

struct G1 {
    int idx;
    ll a,t,p,w;
    ll E, L, R, T1v1, C;
    G1(int _i, ll _a, ll _t, ll _p, ll _w) { idx = _i; a = _a; t = _t; p = _p; w = _w; }
};

struct G2 {
    int idx;
    ll a,t,p,w;
    ll T2v2, A, D, F;
    G2(int _i, ll _a, ll _t, ll _p, ll _w) { idx = _i; a = _a; t = _t; p = _p; w = _w; }
};


int lowbit (int idx) {
    return idx & -idx;
}

class Fenwick {
    int n;
    vector<int> bit;
public:
    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, int val) {
        for (++idx; idx <= n; idx += lowbit(idx)) bit[idx] += val;
    }

    int sum(int idx) const {
        int res = 0;
        for (++idx; idx > 0; idx -= lowbit(idx)) res += bit[idx];
        return res;
    }

    int range(int l, int r) {
        return sum(r) - (l ? sum(l-1) : 0);
    }
};

int main() {
    int n;
    ll v1, v2;
    cin >> n >> v1 >> v2;
    vector<G1> g1;
    vector<G2> g2;

    for (int i = 0; i < n; ++i) {
        int a;
        ll t,p,w;
        cin >> a >> t >> p >> w;
        if(a==1) g1.emplace_back(i,a,t,p,w);
        else     g2.emplace_back(i,a,t,p,w);
    }

    for(auto &x: g1){
        x.E = v2*x.t - x.p;
        x.L = v1*x.p - v1*v2*x.t;
        x.R = x.w * v2 - v1*v2*x.t + v1*x.p;
        x.T1v1 = v1*x.t;
        x.C = v1*x.p - v1*v2*x.t;
    }
    for(auto &x: g2){
        x.T2v2 = v2*x.t;
        x.A = v2*x.p - v1*v2*x.t;
        x.D = v2*v1*x.t - v2*x.p;
        x.F = v1*x.t - x.p;
    }

    vector<ll> ans(n,0);
    {
        vector<ll> G;
        G.reserve(g2.size());
        for(auto &x: g2) G.push_back(x.A);
        sort(G.begin(), G.end());
        G.erase(unique(G.begin(), G.end()), G.end());

        sort(g2.begin(), g2.end(), [](const G2& a,const G2& b){ return a.T2v2 > b.T2v2; });
        vector<int> ord;
        ord.reserve(g1.size());
        for(int i=0;i<(int)g1.size();++i) ord.push_back(i);
        sort(ord.begin(), ord.end(), [&](int i,int j){ return g1[i].E > g1[j].E; });

        Fenwick bit((int)G.size());
        int ptr = 0;
        for(int qi: ord){
            auto &q = g1[qi];
            while(ptr<g2.size() && g2[ptr].T2v2 >= q.E){
                int id = int(lower_bound(G.begin(), G.end(), g2[ptr].A)-G.begin());
                bit.add(id,1);
                ++ptr;
            }
            int l = lower_bound(G.begin(), G.end(), q.L)-G.begin();
            int r = upper_bound(G.begin(), G.end(), q.R)-G.begin() - 1;
            if(l<=r) ans[q.idx] = bit.range(l,r);
        }
    }
    {
        vector<ll> G;
        G.reserve(g1.size());
        for(auto &x: g1) G.push_back(x.C);
        sort(G.begin(), G.end());
        G.erase(unique(G.begin(), G.end()), G.end());

        sort(g1.begin(), g1.end(), [](const G1& a,const G1& b){ return a.T1v1 > b.T1v1; });
        vector<int> ord;
        ord.reserve(g2.size());
        for(int i=0;i<(int)g2.size();++i) ord.push_back(i);
        sort(ord.begin(), ord.end(), [&](int i,int j){ return g2[i].F > g2[j].F; });

        Fenwick bit((int)G.size());
        int ptr = 0;
        for(int qj: ord){
            auto &q = g2[qj];
            while(ptr<g1.size() && g1[ptr].T1v1 >= q.F){
                int id = int(lower_bound(G.begin(), G.end(), g1[ptr].C)-G.begin());
                bit.add(id,1);
                ++ptr;
            }
            ll L = -q.D;
            ll R = q.w * v1 - q.D;
            int l = lower_bound(G.begin(), G.end(), L)-G.begin();
            int r = upper_bound(G.begin(), G.end(), R)-G.begin() - 1;
            if(l<=r) ans[q.idx] = bit.range(l,r);
        }
    }
    for(int i = 0; i < n; i++) cout << ans[i] << "\n";

    return 0;
}

SB. 小兔子的等式

传统题 1000ms 256MiB

题目背景

小兔子对进制十分感兴趣。在一个位制数字系统中，基数 \(b\) 表示了所使用的 digit 的数量（即，\(b\) 进制）。例如 \(10\) 进制系统中，我们用 \(10\) 种数字 \(0,1,\dots,9\) 来组成每个数。

广义来说，在一个 \(b\) 进制（\(b > 1\)）体系中，一个字符串 \(d_1\dots d_n\) 表示了整数 \(d_1b^{n-1}+d_2b^{n-2}+\dots+d_nb^0\)，其中 \(0 \leq d_i < b\)。

小兔子随意的写下了一个等式，他想知道，在哪些进制下这个等式是成立的。

题目描述

每个测试数据仅包含一行字符串，表示小兔子写下的等式。字符串的长度最多为 \(15\)。

等式的格式为：一个数字，一个运算符，一个数字，等号 =，然后再一个数字。形式化写作 [num1][op][num2]=[num3]，中间没有空格。

数字 num1, num2, num3 至少有 \(1\) 位，可以包含数字 \(0\) 到 \(9\) 或大写字母 \(A\) 到 \(F\)（表示十进制 \(10\) 到 \(15\)）。保证该数字是非负整数，即不包含小数点或负号。但数字可能包含前导零。

运算符 op 是基本的四则运算符之一，即加号 +、减号 -、乘号 * 或除号 /。保证除号后的数字不等于 \(0\)。请注意，这里的除法不是整数除法，而是实数意义的除法。例如，在十进制系统中，7/2=3 是不正确的。

输入格式

同题目描述。

输出格式

对于每个测试数据，在一行中输出一个整数 \(r\)（\(2 \leq r \leq 16\)），表示在基数为 \(r\) 的进制系统中等式是成立的。如果有多个答案，则输出最小的一个。

如果在 \(2\) 和 \(16\) 之间没有答案，则输出 \(-1\)。

样例 #1

样例输入 #1

1
1+1=10

样例输出 #1

1
2

样例输入 #2

1
18-9=9

样例输出 #2

1
10

样例输入 #3

1
AA*AA=70E4

样例输出 #3

1
16

样例输入 #4

1
7/2=3

样例输出 #4

1
-1

样例输入 #5

1
3221+1=3222

样例输出 #5

1
4

样例输入 #6

1
155178/233=666

样例输出 #6

1
10

样例输入 #7

1
0B+5C=6A

样例输出 #7

1
13

样例输入 #8

1
4294967296+0=0

样例输出 #8

1
-1

样例输入 #9

1
00F+0=000F

样例输出 #9

1
16

样例输入 #10

1
14*14=232

样例输出 #10

1
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
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
#include <bits/stdc++.h>


using namespace std;

unsigned long long num(char c){
    switch(c){
        case '0':return 0;
        case '1':return 1;
        case '2':return 2;
        case '3':return 3;
        case '4':return 4;
        case '5':return 5;
        case '6':return 6;
        case '7':return 7;
        case '8':return 8;
        case '9':return 9;
        case 'A':return 10;
        case 'B':return 11;
        case 'C':return 12;
        case 'D':return 13;
        case 'E':return 14;
        case 'F':return 15;
    }
}

int main(){
    string s;
    cin >> s;
    int n = s.size();
    bool key = false;

    string num1;
    string num2;
    string num3;
    int op = 0;
    int temp = 0;
    char max = '0';
    for(int i = 0; i < n; ++i){
        if(s[i] == '+'){
            op = 1;
            temp = i;
            break;
        } else if(s[i] == '-'){
            op = 2;
            temp = i;
            break;
        } else if(s[i] == '*'){
            op = 3;
            temp = i;
            break;
        } else if(s[i] == '/'){
            op = 4;
            temp = i;
            break;
        } else{
            num1.push_back(s[i]);
        }
        max = std::max(max, s[i]);
    }

    for(int i = temp + 1; i < n; ++i){
        if(s[i] == '='){
            temp = i;
            break;
        } else{
            num2.push_back(s[i]);
        }
        max = std::max(max, s[i]);
    }

    for(int i = temp + 1; i < n; ++i){
        num3.push_back(s[i]);
        max = std::max(max, s[i]);
    }

    temp = -1;
    for(int k = std::max(num(max) + 1, 2ull); k <= 16; ++k){
        unsigned long long n1, n2, n3;
        size_t pos = 0;
        stoull(num1, &pos ,k);
        n1 = stoull(num1, &pos ,k);
        n2 = stoull(num2, &pos ,k);
        n3 = stoull(num3, &pos ,k);
        if(op == 1){
            if(n1 + n2 == n3){
                key = true;
                temp = k;
                break;
            }
        } else if (op == 2){
            if(n1 - n2 == n3){
                key = true;
                temp = k;
                break;
            }
        } else if (op == 3){
            if(n1 * n2 == n3){
                key = true;
                temp = k;
                break;
            }
        } else if (op == 4){
            if(n1 == n2 * n3){
                key = true;
                temp = k;
                break;
            }
        }
    }

    cout << (key ? temp : -1);

    return 0;
}

SC. 数字游戏

传统题 1000ms 256MB

Description

一天早上，完全是偶然的，ZZR 在马路中间发现了一个正整数 \(N\)。因为 ZZR 喜欢数字 30，他想知道将 \(N\) 的各个数位上的数字进行重新调整后，可能得到的 30 最大倍数是多少。

请帮助我们的 ZZR 计算出这个数。

Format

Input

共一行，一个整数 \(N\)，最多不超过 \(10^5\) 个数位，也就是说这个数小于 \(10^{100000}\)。

Output

共一行，表示可以组成的 30 最大倍数，如果无法组成则输出 \(-1\)。

Samples

输入样例 1

1
120

输出样例 1

1
210

输入样例 2

1
45

输出样例 2

1
-1

输入样例 3

1
31776969937490818572

输出样例 3

1
99998877776654332110

Limitation

对于其中 20% 的数据，保证 \(N \leq 10^8\)；

对于 100% 的数据，保证 \(1 \leq N \leq 10^{100000}\)。

思路与题解

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

using namespace std;

int main(){
    string s;
    cin >> s;
    vector<int> num(10, 0);
    int ans = -1;
    int sum = 0;
    for(auto ch : s){
        int c = ch - '0';
        num[c]++;
        sum += c;
    }
    if(sum % 3 != 0 || num[0] == 0) {
        cout << -1;
        return 0;
    }
    for(int i = 9; i >= 0; --i){
        while(num[i]--) cout << i;
    }
    return 0;
}
  • Title: 数据结构作业题解09
  • Author: exdoubled
  • Created at : 2025-11-24 17:00:00
  • Updated at : 2025-12-27 20:23:32
  • Link: https://github.com/exdoubled/exdoubled.github.io.git/sjjg/homework09/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
数据结构作业题解09
  1. A.SA. 01迷宫
    1. 说明
    2. 输入格式
    3. 输出格式
    4. 样例
    5. 提示
    6. 思路与题解
  2. B. 妙妙米奇树
    1. 题目背景
    2. 输入格式
    3. 输出格式
    4. 样例
    5. 数据范围
    6. 思路与题解
  3. C. 超疯狂插队
    1. 题目背景
    2. 输入格式
    3. 输出格式
    4. 样例
    5. 数据范围
    6. 思路与题解
  4. D. 本质不同子串计数
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 样例
    5. 数据范围
    6. 思路与题解
  5. E. 傻瓜和道路
    1. Description
    2. Format
      1. Input
      2. Output
    3. Samples
    4. Limitation
    5. 思路与题解
  6. F. 郁闷的出租员
    1. Description
    2. Format
      1. Input
      2. Output
    3. Samples
    4. Limitation
    5. 思路与题解
  7. G. 同步跑
    1. 题目背景
    2. 题目描述
    3. 输入格式
    4. 输出格式
    5. 样例
    6. 提示
    7. 思路与题解
  8. SB. 小兔子的等式
    1. 题目背景
    2. 题目描述
    3. 输入格式
    4. 输出格式
    5. 样例 #1
    6. 思路与题解
  9. SC. 数字游戏
    1. Description
    2. Format
      1. Input
      2. Output
    3. Samples
    4. Limitation