GPLT L2 题解

发表于 更新于 分类于 阅读次数： 本文字数： 11k 阅读时长 ≈ 39 分钟
The very things that hold you down are going to lift you up. — Dumbo

L2-001 紧急救援

思路：

  • 首先，看到这个 \(n\) 的范围，我们要想到哪几种算法可以通过
  • 朴素版 \(dijkstra\) 和 \(Floyd\) 都可以通过，但本题使用 \(Floyd\) 不好处理，所以我们选用 \(dijstra\)
  • 然后我们跑一遍 \(dijkstra\) ，将所有到 \(S\) 的最短距离求出来
  • 然后我们 \(dfs\) 一遍，只要走到了 \(D\) 点，就个数加 \(1\)​，同时更新最大的人数和路径

时间复杂度：\(O(n^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
#include <bits/stdc++.h> 

using i64 = long long;

constexpr int inf = 0x3f3f3f3f;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M, S, D;
    std::cin >> N >> M >> S >> D;

    std::vector<int> a(N + 1);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }

    std::vector d(N + 1, std::vector<int>(N + 1));
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            if (i == j) {
                d[i][j] = 0;
            } else {
                d[i][j] = inf;
            }
        }
    }
    for (int i = 0; i < M; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;

        d[u][v] = w; d[v][u] = w;
    }

    std::vector<int> dist(N + 1), vis(N + 1);
    auto dijkstra = [&]() {
        for (int i = 0; i < N; i++) {
            dist[i] = d[S][i];
        }
        for (int i = 0; i < N; i++) {
            int min = inf;
            int t = -1;
            for (int j = 0; j < N; j++) {
                if (!vis[j] && (t == -1 || dist[t] > dist[j])) {
                    min = dist[j];
                    t = j;
                }
            }
            for (int j = 0; j < N; j++) {
                dist[j] = std::min(dist[j], dist[t] + d[t][j]);
            }
            vis[t] = true;
        }
    };
    dijkstra();
    
    int max = 0, cnt = 0;
    vis.assign(N + 1, 0);

    std::vector<int> path, ans;
    path.push_back(S);

    auto dfs = [&](auto self, int u, int v) -> void {
        if (u == D) {
            if (v > max) {
                max = v;
                ans = path;
            }
            cnt++;
            return ;
        }
        for (int i = 0; i < N; i++) {
            if (d[u][i] && !vis[i] && dist[i] == dist[u] + d[u][i]) { // 如果 S 到 i 的距离 == S 到 当前这个点的距离 + 当前这个点到 i 的距离
                vis[i] = true;
                path.push_back(i);
                self(self, i, v + a[i]);
                path.pop_back();
                vis[i] = false;
            }
        }
    };
    dfs(dfs, S, a[S]);
    
    std::cout << cnt << " " << max << "\n";
    for (int i = 0; i < ans.size(); i++) {
        std::cout << ans[i] << " \n"[i == ans.size() - 1];
    }

    return 0;
}

L2-002 链表去重

思路：

  • 用bfs把这个完整的链表建出来，然后我们去重进行重置前后的地址即可

时间复杂度：\(O(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
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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::string st;
    std::cin >> st >> N;

    std::map<std::string, std::pair<int, std::string>> mp; 
    for (int i = 0; i < N; i++) {
        int w;
        std::string x, y;
        std::cin >> x >> w >> y;
        mp[x] = {w, y};
    }

    std::vector<std::tuple<std::string, int, std::string>> a;
    std::queue<std::string> q;
    q.push(st);
    while (q.size()) {
        auto cur = q.front();
        q.pop();

        if (mp.count(cur)) {
            a.push_back({cur, mp[cur].first, mp[cur].second});
            q.push(mp[cur].second);
        }
    }

    std::map<int, int> cnt;
    std::vector<int> vis(a.size());
    for (int i = 0; i < a.size(); i++) {
        auto [x, y, z] = a[i];
        if (cnt[abs(y)]) {
            continue ;
        }
        cnt[abs(y)]++;
        vis[i] = true;
    }

    std::vector<std::tuple<std::string, int, std::string>> b;
    for (int i = 0; i < a.size(); i++) {
        if (vis[i]) {
            b.push_back(a[i]);
        }
    }

    for (int i = 0; i < b.size(); i++) {
        if (i + 1 < b.size()) {
            auto &[x1, y1, z1] = b[i];
            auto &[x2, y2, z2] = b[i + 1];
            if (z1 != x2) {
                z1 = x2;
            }
        } else {
            auto &[x1, y1, z1] = b[i];
            z1 = "-1";
        }
    }
    for (int i = 0; i < b.size(); i++) {
        auto [x, y, z] = b[i];
        std::cout << x << " " << y << " " << z << "\n";
    }
    b.clear();
    for (int i = 0; i < a.size(); i++) {
        if (!vis[i]) {
            b.push_back(a[i]);
        }
    }
    for (int i = 0; i < b.size(); i++) {
        if (i + 1 < b.size()) {
            auto &[x1, y1, z1] = b[i];
            auto &[x2, y2, z2] = b[i + 1];
            if (z1 != x2) {
                z1 = x2;
            }
        } else {
            auto &[x1, y1, z1] = b[i];
            z1 = "-1";
        }
    }
    for (int i = 0; i < b.size(); i++) {
        auto [x, y, z] = b[i];
        std::cout << x << " " << y << " " << z << "\n";
    }
    return 0;
}

L2-003 月饼

思路：

  • 贪心，我们存一下每个月饼的收益，然后从大到小排序即可
  • 然后逐个选取

时间复杂度：\(O(nlogn)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(2);

    int N, D;
    std::cin >> N >> D;

    std::vector<double> a(N), w(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }
    std::vector<double> rate(N);
    for (int i = 0; i < N; i++) {
        std::cin >> w[i];
        rate[i] = w[i] * 1.0 / a[i];
    }

    std::vector<int> p(N);
    std::iota(p.begin(), p.end(), 0);

    std::sort(p.begin(), p.end(), 
        [&](int i, int j) {
            if (rate[i] == rate[j]) return a[i] > a[j];
            return rate[i] > rate[j];
    });

    double ans = 0;
    for (int i = 0; i < N; i++) {
        if (a[p[i]] <= D) {
            D -= a[p[i]];
            ans += w[p[i]];
        } else {
            ans += D * 1.0 * w[p[i]] / a[p[i]];
            break;
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}

L2-004 这是二叉搜索树吗？

思路：

  • 首先我们假设这个树是非镜面二叉搜索树，一开始设ok为false，然后我们将其从先序转换为后序，假如发现这个转换后的后序数组长度不为n，那么就清空，将他按照镜面二叉搜索树的情况来求后续遍历
  • 只要以上两种情况中的任何一种合法，就直接输出，否则输出-1

时间复杂度：\(O(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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> pre(n);
    for (int i = 0; i < n; i++) {
        std::cin >> pre[i];
    }

    bool ok = false;
    std::vector<int> post;
    auto get = [&](auto self, int root, int tail) -> void {
        if (root > tail) return ;
        int i = root + 1, j = tail;
        if (!ok) {
            while (i <= tail && pre[root] > pre[i]) i++;
            while (j > root && pre[root] <= pre[j]) j--;
        } else {
            while (i <= tail && pre[root] <= pre[i]) i++;
            while (j > root && pre[root] > pre[j]) j--;
        }
        if (i - j != 1) return ;
        self(self, root + 1, j);
        self(self, i, tail);
        post.push_back(pre[root]);
    };

    get(get, 0, n - 1);
    if (post.size() != n) {
        ok = true;
        post.clear();
        get(get, 0, n - 1);
    }
    if (post.size() == n) {
        std::cout << "YES\n";
        for (int i = 0; i < post.size(); i++) {
            std::cout << post[i] << " \n"[i == post.size() - 1];
        }
    } else {
        std::cout << "NO\n";
    }
    
    return 0;
}

L2-005 集合相似度

题目大意：

  • 其中 \(N_c\) 是两个集合都有的不相等整数的个数：两个集合交集元素个数

  • \(N_t\) 是两个集合一共有的不相等整数的个数：两个集合的并集的元素个数

思路：

  • 用set直接进行集合去重和统计个数

时间复杂度：\(O(KlogM)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::vector<std::vector<int>> st(N);
    for (int i = 0; i < N; i++) {
        int n;
        std::cin >> n;
        std::set<int> a;
        for (int j = 0; j < n; j++) {
            int x;
            std::cin >> x;
            a.insert(x);
        }
        for (auto x : a) {
            st[i].push_back(x);
        }
    }

    int K;
    std::cin >> K;

    while (K--) {
        int a, b;
        std::cin >> a >> b;
        a--, b--;

        std::set<int> k;
        for (auto v : st[a]) {
            k.insert(v);
        }
        int ans = 0;
        for (auto v : st[b]) {
            if (k.count(v)) {
                ans++;
            }
        }
        for (auto v : st[b]) {
            k.insert(v);
        }
        printf("%.2lf%\n", ans * 100.0 / k.size());
    }

    return 0;
}

L2-006 树的遍历

思路：

  • 根据中序遍历和后序遍历建树，然后进行BFS即可

时间复杂度：\(O(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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> post(n), in(n);
    for (int i = 0; i < n; i++) {
        std::cin >> post[i];
    }

    std::unordered_map<int, int> pos, l, r;
    auto build = [&](auto self, int il, int ir, int pl, int pr) -> int {
        int root = post[pr]; // 后序遍历的最后一个节点即为根节点
        int k = pos[root]; // 在中序遍历中找到根节点的位置
        // k - il 为左子树的节点个数  
        if (il < k) l[root] = self(self, il, k - 1, pl, pl + k - 1 - il);
        if (ir > k) r[root] = self(self, k + 1, ir, pl + k - 1 - il + 1, pr - 1);
        return root;
    };
    for (int i = 0; i < n; i++) {
        std::cin >> in[i];
        pos[in[i]] = i; // 记录中序遍历中节点值与索引的映射关系
    }
    int root = build(build, 0, n - 1, 0, n - 1);

    std::queue<int> q;
    q.push(root);

    std::vector<int> ans;
    while (!q.empty()) {
        int t = q.front();
        q.pop();

        ans.push_back(t);
        if (l.count(t)) q.push(l[t]);
        if (r.count(t)) q.push(r[t]);
    }
    
    for (int i = 0; i < ans.size(); i++) {
        std::cout << ans[i] << " \n"[i == ans.size() - 1];
    }

    return 0;
}

L2-007 家庭房产

思路：

  • 将每一个家庭看作一个集合，然后用并查集来维护每一个家庭
  • 在合并的过程中，由于题目要求输出家庭里最小的那个编号，那么这个最小的编号就作为祖先节点
  • 然后我们遍历，求出每个家庭的信息，最后统计输出即可

时间复杂度：\(O(nlogn)\)

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
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (x > y) { // 保证小的那个是祖先
            f[x] = y;
        } else {
            f[y] = x;
        }
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

struct node1 {
    int id, fa, mo;
    int cnt, area;
    int c[5];
};

struct node2 {
    int id, peo;
    double num, area;
    bool ok = false;
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;  

    DSU f(10010);

    std::vector<node1> a(N);
    std::vector<int> vis(10010);
    for (int i = 0; i < N; i++) {
        int k;
        std::cin >> a[i].id >> a[i].fa >> a[i].mo >> k;
        vis[a[i].id] = true;
        if (a[i].fa != -1) {
            vis[a[i].fa] = true;
            f.merge(a[i].fa, a[i].id);
        }
        if (a[i].mo != -1) {
            vis[a[i].mo] = true;
            f.merge(a[i].mo, a[i].id);
        }
        for (int j = 0; j < k; j++) {
            std::cin >> a[i].c[j];
            vis[a[i].c[j]] = true;
            f.merge(a[i].c[j], a[i].id);
        }
        std::cin >> a[i].cnt >> a[i].area;
    }
    
    std::vector<node2> ans(10000);
    for (int i = 0; i < N; i++) {
        int pa = f.find(a[i].id);
        ans[pa].id = pa;
        ans[pa].num += a[i].cnt;
        ans[pa].area += a[i].area;
        ans[pa].ok = true;
    }
    int cnt = 0;
    for (int i = 0; i < 10000; i++) {
        if (vis[i]) {
            ans[f.find(i)].peo++;
        }
        if (ans[i].ok) {
            cnt++;
        }
    }
    for (int i = 0; i < 10000; i++) {
        if (ans[i].ok) {
            ans[i].num = (ans[i].num * 1.0 / ans[i].peo);
            ans[i].area = (ans[i].area * 1.0 / ans[i].peo);
        }
    }
    
    std::sort(ans.begin(), ans.end(), [&](auto i, auto j) {
        if (i.area != j.area) {
            return i.area > j.area;
        }
        return i.id < j.id;
    });
    printf("%d\n", cnt);
    for (int i = 0; i < cnt; i++) {
        printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].peo, ans[i].num, ans[i].area);
    }

    return 0;
}

L2-008 最长对称子串

思路：

  • 用字符串 \(hash\) 来判断回文串，然后枚举左右端点即可

本题也可以参考一下升级版智乃的前缀、后缀、回文的讲解

时间复杂度：\(O(n^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
struct Shash{
    const i64 base[2] = {29, 31};
    const i64 hashmod[2] = {(i64)1e9, 998244353};

    std::array<std::vector<i64>, 2> hsh, pwMod;
    void init(std::string &s) {
        int n = s.size(); 
        s = ' ' + s;
        hsh[0].resize(n + 1), hsh[1].resize(n + 1);
        pwMod[0].resize(n + 1), pwMod[1].resize(n + 1);
        for(int i = 0; i < 2; i++){
            pwMod[i][0] = 1;
            for(int j = 1; j <= n; j++){
                pwMod[i][j] = pwMod[i][j - 1] * base[i] % hashmod[i];
                hsh[i][j] = (hsh[i][j - 1] * base[i] + s[j]) % hashmod[i];
            }
        }
    }
    std::pair<i64, i64> get(int l, int r) {
        std::pair<i64, i64> ans;
        ans.first = (hsh[0][r] - hsh[0][l - 1] * pwMod[0][r - l + 1]) % hashmod[0];
        ans.second = (hsh[1][r] - hsh[1][l - 1] * pwMod[1][r - l + 1]) % hashmod[1];
        ans.first = (ans.first + hashmod[0]) % hashmod[0];
        ans.second = (ans.second + hashmod[1]) % hashmod[1];
        return ans;
    }
    bool same(int la, int ra, int lb, int rb){
        return get(la, ra) == get(lb, rb);
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::getline(std::cin, s);

    for (auto &i : s) {
        if (i == ' ') {
            i = 'a';
        }
    }

    std::string t = std::string(s.rbegin(), s.rend());

    Shash a, b;
    a.init(s); b.init(t);

    int n = s.size();   

    int ans = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (a.get(i, j) == b.get(n - j, n - i)) {
                ans = std::max(ans, j - i + 1);
            }
        }
    }
    std::cout << ans << "\n";

    
    return 0;
}

L2-009 抢红包

思路：

  • 直接模拟就行

时间复杂度：\(O(nlogn)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(2);

    int N;
    std::cin >> N;

    std::vector<std::tuple<double, int, int>> a(N + 1);
    for (int i = 0; i < N; i++) {
        auto &[x, y, z] = a[i + 1];
        y = i + 1;
        int k;
        std::cin >> k;
        double sum = 0;
        for (int j = 0; j < k; j++) {
            int id;
            double m;
            std::cin >> id >> m;
            auto &[x1, y1, z1] = a[id];
            x1 += m;
            y1 = id;
            z1++;
            sum += m;
        }
        x -= sum;
    }
    std::sort(a.begin() + 1, a.end(), [&](auto i, auto j) {
        auto [x1, y1, z1] = i;
        auto [x2, y2, z2] = j;
        if (x1 == x2) {
            if (z1 != z2) {
                return z1 > z2;
            } else {
                return y1 < y2;
            }
        }
        return x1 > x2;
        
    });
    for (int i = 1; i <= N; i++) {
        auto [x, y, z] = a[i];
        std::cout << y << " " << x / 100 << "\n";
    }
    
    return 0;
}

L2-010 排座位

思路：

  • 用并查集维护一下朋友关系
  • 然后用 set 维护一下敌对关系

时间复杂度：\(O(MlogN)\)

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
struct DSU {
    std::vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 0);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M, K;
    std::cin >> N >> M >> K;

    DSU f(N + 1);

    std::set<std::pair<int, int>> em;
    for (int i = 0; i < M; i++) {
        int x, y, op;
        std::cin >> x >> y >> op;

        if (op == -1) {
            em.insert({x, y});
            em.insert({y, x});
        } else {
            f.merge(x, y);
        }
    }

    for (int i = 0; i < K; i++) {
        int x, y;
        std::cin >> x >> y;

        if (!f.same(x, y) && !em.count({x, y})) {
            std::cout << "OK\n";
        } else if (f.same(x, y) && em.count({x, y})) {
            std::cout << "OK but...\n";
        } else if (em.count({x, y})) {
            std::cout << "No way\n";
        } else if (f.same(x, y)) {
            std::cout << "No problem\n";
        }
    }

    return 0;
}

L2-011 玩转二叉树

思路：

  • 按照规则构建一颗二叉树
  • 然后 bfs 的时候，将左右节点的输出顺序更换一下即可

时间复杂度：\(O(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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
struct Node {
    int val;
    Node *l;
    Node *r;
    Node(int x) : val(x), l(nullptr), r(nullptr) {}
};

class Solution {
public:
    Node* build(std::vector<int> &ino, std::vector<int> &pre) {
        std::unordered_map<int, int> mp;
        for (int i = 0; i < ino.size(); i++) {
            mp[ino[i]] = i;
        }
        return buildTree(ino, 0, ino.size() - 1, pre, 0, pre.size() - 1, mp);
    }
    Node* buildTree(auto &ino, int il, int ir, auto &pre, int pl, int pr, auto mp) {
        if (pl > pr) {
            return nullptr;
        }
        int root_val = pre[pl];
        Node *root = new Node(root_val);

        int tot = mp[root_val]; // 根节点的位置
        int ls = tot - il; // 左子树的大小

        root->l = buildTree(ino, il, tot - 1, pre, pl + 1, pl + ls, mp);
        root->r = buildTree(ino, tot + 1, ir, pre, pl + ls + 1, pr, mp);
        return root;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> ino(n), pre(n);
    for (int i = 0; i < n; i++) {
        std::cin >> ino[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> pre[i];
    }

      Solution s;
    Node* root = s.build(ino, pre);
    
    std::queue<Node*> q;
    q.push(root);

    std::vector<int> ans;
    while (!q.empty()) {
        auto t = q.front();
        q.pop();

        ans.push_back(t->val);
        if (t->r != nullptr) q.push(t->r);
        if (t->l != nullptr) q.push(t->l);
    }
    for (int i = 0; i < ans.size(); i++) {
        std::cout << ans[i] << " \n"[i == ans.size() - 1];
    }

    return 0;
}

L2-013 红色警报

思路：

  • 统计这个图的连通分量，然后每次摧毁一个城市，在求一次连通分量；
  • 如果摧毁后的连通分量大于摧毁前的连通分量数+1，那么，就说明，这个节点导致了这个图不连通了，那么我们就需要输出Red Alert: City k is lost!，否则输出City k is lost.
  • 如果K的数量等于N，那么就说明最后就摧毁完了，输出Game Over.

时间复杂度：\(O(K \times n^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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;

    std::vector<std::vector<int>> g(N, std::vector<int>(N));
    for (int i = 0; i < M; i++) {
        int u, v;
        std::cin >> u >> v;
        g[u][v] = g[v][u] = 1;
    }

    std::vector<int> vis(N);
    auto dfs = [&](auto self, int u) -> void {
        vis[u] = true;
        for (int i = 0; i < N; i++) {
            if (g[u][i] && !vis[i]) {
                self(self, i);
            }
        }
    };
    auto count = [&]() {
        int cnt = 0;
        vis.assign(N, 0);
        for (int i = 0; i < N; i++) {
            if (!vis[i]) {
                dfs(dfs, i);
                cnt++;
            }
        }
        return cnt;
    };
    int cnt = count();

    int K;
    std::cin >> K;

    for (int i = 0; i < K; i++) {
        int x;
        std::cin >> x;

        for (int j = 0; j < N; j++) {
            if (g[x][j]) {
                g[x][j] = 0;
                g[j][x] = 0;
            }
        }
        int t = count();
        if (t > cnt + 1) {
            std::cout << "Red Alert: City " << x << " is lost!\n";
        } else {
            std::cout << "City " << x << " is lost.\n";
        }
        cnt = t;
        if (i == N - 1) {
            std::cout << "Game Over.\n";
        }
    }

    return 0;
}

L2-014 列车调度

思路：

  • 每次将队列的第i个数与目前的最大值进行比较，只要出现一个比当前值小的数，我们就把比这个数大的数删掉，这样保证是从大到小的顺序，最后只需要输出这个有序队列的剩下元素的大小-1即可

时间复杂度：\(O(nlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;

    std::set<int> st;
    st.insert(0);
    for (int i = 0; i < N; i++) {
        int x;
        std::cin >> x;

        if (x < *st.rbegin()) {
            st.erase(*st.upper_bound(x));
        }
        st.insert(x);
    }

    std::cout << st.size() - 1 << "\n";

    return 0;
}

L2-015 互评成绩

思路：

  • 按照规则模拟

时间复杂度：\(O(n \times k)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(3);

    int N, k, M;
    std::cin >> N >> k >> M;

    std::vector<double> score;
    for (int i = 0; i < N; i++) {
        std::vector<double> a(k);
        for (int j = 0; j < k; j++) {
            std::cin >> a[j];
        }
        std::sort(a.begin(), a.end());
        double avg = std::accumulate(a.begin() + 1, a.end() - 1, 0.0) / (k - 2);
        score.push_back(avg);
    }

    std::sort(score.begin(), score.end());
    for (int i = N - M; i < N; i++) {
        std::cout << score[i] << " \n"[i == N - 1];
    }
    
    return 0;
}

L2-016 愿天下有情人都是失散多年的兄妹

思路：

  • 暴搜，统计 x 和 y 相差的代数

时间复杂度：\(O(n + kD)\)

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
struct node {
    char sex = '\0';
    int faid = -1, moid = -1;
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;
    
    std::vector<node> a(100000);
    for (int i = 0; i < N; i++) {
        int id;
        std::cin >> id;
        std::cin >> a[id].sex >> a[id].faid >> a[id].moid;
        if (a[id].faid != -1)
            a[a[id].faid].sex = 'M';
        if (a[id].moid != -1)
            a[a[id].moid].sex = 'F';
    }
    
    auto dfs = [&](auto self, int x, int y, int d) -> bool {
        if (!(x != -1 && y != -1)) {
            return true;
        }
        if (d > 5) return true;
        
        if (x == y) { 
            return false;
        } else {
            return self(self, a[x].faid, a[y].moid, d + 1) && self(self, a[x].faid, a[y].faid, d + 1)
            && self(self, a[x].moid, a[y].moid, d + 1) && self(self, a[x].moid, a[y].faid, d + 1);
        }
    };
    
    int K;
    std::cin >> K;

    while (K--) {
        int x, y;
        std::cin >> x >> y;

        if (a[x].sex == a[y].sex) {
            std::cout << "Never Mind\n";
        } else {
            if (dfs(dfs, x, y, 1)) {
                std::cout << "Yes\n";
            } else {
                std::cout << "No\n";
            }
        }
    }

    return 0;
}

L2-017 人以群分

思路：

  • 模拟即可

时间复杂度：\(O(nlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());

    int mid = N / 2;
    i64 sum1 = std::accumulate(a.begin(), a.begin() + mid, 0LL);
    i64 sum2 = std::accumulate(a.begin() + mid, a.end(), 0LL);
   
    printf("Outgoing #: %d\n", (N + 1) / 2);
    printf("Introverted #: %d\n", N / 2);
    printf("Diff = %lld\n", sum2 - sum1);
    
    return 0;
}

L2-019 悄悄关注

思路：

  • 直接模拟，判断在不在那个关注集合就行

时间复杂度：\(O(nlogn)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::set<std::string> st;
    for (int i = 0; i < N; i++) {
        std::string s;
        std::cin >> s;
        st.insert(s);
    }

    int M;
    std::cin >> M;

    double sum = 0;
    std::vector<std::pair<std::string, int>> a(M);
    for (int i = 0; i < M; i++) {
        std::cin >> a[i].first >> a[i].second;
        sum += a[i].second;
    }

    sum /= M;

    std::set<std::string> ans;
    for (int i = 0; i < M; i++) {
        if (!st.count(a[i].first) && a[i].second > sum) {
            ans.insert(a[i].first);
        }
    }
    if (ans.empty()) {
        std::cout << "Bing Mei You\n";
        return 0;
    }
    for (auto x : ans) {
        std::cout << x << "\n";
    }
    
    return 0;
}

L2-020 功夫传人

思路：

  • 直接 BFS 或者 DFS

时间复杂度：\(O(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
50
51
52
53
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    double Z, r;
    std::cin >> N >> Z >> r;

    std::map<int, i64> mp;
    std::vector<std::vector<int>> g(N);
    for (int i = 0; i < N; i++) {
        int k;
        std::cin >> k;

        if (k == 0) {
            i64 x;
            std::cin >> x;
            mp[i] = x;
        }
        for (int j = 0; j < k; j++) {
            int x;
            std::cin >> x;
            g[i].push_back(x);
        }
    }

    if (mp.count(0)) {
        std::cout << i64(Z * mp[0]) << "\n";
        return 0;
    }
    std::queue<std::tuple<int, double>> q;
    q.push({0, Z});


    double ans = 0;
    while (q.size()) {    
        auto [x, y] = q.front();
        q.pop();

        for (int v : g[x]) {
            if (mp.count(v)) {
                double t = mp[v] * y * (1 - r / 100);
                q.push({v, t});
                ans += t;
            } else {
                q.push({v, y * (1 - r / 100)});
            }
        }
    }
    std::cout << i64(ans) << "\n";

    return 0;
}

L2-021 点赞狂魔

思路：

  • 可以利用优先队列来存储答案，利用 map 和 set 来去重，然后按规则模拟即可

时间复杂度：\(O(nloglogn)\)

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
struct node {
    std::string s;
    int x;
    double avg;

    bool operator<(const node &t) const {
        if (x == t.x) {
            return avg > t.avg;
        }
        return x < t.x;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;
    std::map<std::string, double> avg;
    std::map<std::string, std::set<int>> mp;
    for (int i = 0; i < N; i++) {
        int K;
        std::string s;
        std::cin >> s >> K;
        for (int j = 0; j < K; j++) {
            int x;
            std::cin >> x;
            mp[s].insert(x);
        }
        avg[s] = K * 1.0 / int(mp[s].size());
    }

    std::priority_queue<node> q;
    for (auto [s, y] : mp) {
        q.push({s, y.size(), avg[s]});
    }   
    int cnt = 0;
    while (!q.empty()) {
        cnt++;
        if (cnt == 3) {
            std::cout << q.top().s;
            break;
        }
        std::cout << q.top().s << " ";
        q.pop();
    }
    if (cnt < 3) {
        for (int i = cnt; i < 3; i++) {
            std::cout << '-' << " \n"[i == 2];
        }
    }

    return 0;
}

L2-023 图着色问题

思路：

  • 数据范围较小，其实可以直接暴力枚举，然后 check 一下当前位置是否可行，不过我这里用了 BFS 来模拟这个 check 的过程
  • 如果个数不是 K 直接判定为 No

时间复杂度：\(O(V \times 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
50
51
52
53
54
55
56
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int V, E, K;
    std::cin >> V >> E >> K;

    std::vector<std::vector<int>> adj(V);
    for (int i = 0; i < E; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int N;
    std::cin >> N;

    while (N--) {
        std::set<int> st;
        std::vector<int> c(V);
        for (int i = 0; i < V; i++) {
            std::cin >> c[i];
            st.insert(c[i]);
        }

        std::vector<int> vis(V);
        auto bfs = [&](int u) -> bool {
            std::queue<int> q;
            vis[u] = true;
            q.push(u);

            while (!q.empty()) {
                int x = q.front();
                q.pop();

                for (int v : adj[x]) {
                    if (c[v] == c[x]) return false;
                    if (vis[v]) continue ;
                    vis[v] = true;
                    q.push(v);
                }
            }
            return true;
        };
        if (st.size() == K && bfs(0) && bfs(V - 1)) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
    }
    
    return 0;
}

L2-024 部落

思路：

  • 并查集，查询集合即可

时间复杂度：\(O(N \times K)\)

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
struct DSU {
    std::vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += y;
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    DSU f(10010);


    std::vector<int> vis(10010);
    for (int i = 0; i < N; i++) {
        int k, v;
        std::cin >> k >> v;
        vis[v] = true;
        int pa = f.find(v);
        for (int j = 1; j < k; j++) {
            int x;
            std::cin >> x;

            vis[x] = true;
            f.merge(x, pa);
        }
    }

    int cnt = 0;
    std::set<int> st;
    for (int i = 1; i <= 10000; i++) {
        if (!vis[i]) continue ;
        else {
            cnt++;
            st.insert(f.find(i));
        }
    }

    std::cout << cnt << " " << st.size() << "\n";

    int Q;
    std::cin >> Q;

    while (Q--) {
        int x, y;
        std::cin >> x >> y;

        if (f.same(x, y)) {
            std::cout << "Y\n";
        } else {
            std::cout << "N\n";
        }
    }

    return 0;
}

L2-025 分而治之

思路：

  • 直接记录每个点的度(deg)情况即可，然后每当删除一个点就把与这些点相连的点的度数都减 1，最后判断是否其他的点的度数为 0 即可，这样保证了度数为 0 的点是孤立的

时间复杂度：\(O(Q \times NlogN)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M;
    std::cin >> N >> M;

    std::vector<int> deg(N);
    std::vector<std::vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++, deg[v]++;
    }

    int Q;
    std::cin >> Q;

    while (Q--) {
        int Np;
        std::cin >> Np;

        auto tmp = deg;
        std::set<int> a;
        for (int i = 0; i < Np; i++) {
            int x;
            std::cin >> x;
            x--;
            a.insert(x);

            for (int v : adj[x]) {
                tmp[v]--;
            }
        }
        bool ok = false;
        for (int i = 0; i < N; i++) {
            if (a.count(i)) continue ;
            if (tmp[i] != 0) {
                ok = true;
                break;
            }
        }
        std::cout << (ok ? "NO\n": "YES\n");
    }
    
    return 0;
}

L2-026 小字辈

思路：

  • 两遍 dfs，第一遍先记录族谱树的最大深度，第二遍找到最大深度的所有节点，即为辈分最小的节点

时间复杂度：\(O(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
50
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::vector<int> a(N + 1);
    for (int i = 1; i <= N; i++) {
        std::cin >> a[i];
    }

    int u = 0;
    std::map<int, std::vector<int>> mp;
    for (int i = 1; i <= N; i++) {
        mp[a[i]].push_back(i);
        if (a[i] == -1) {
            u = i;
        }
    }

    int cnt = 0;
    auto dfs1 = [&](auto self, int x, int dep) -> void {
        cnt = std::max(cnt, dep);
        for (int v : mp[x]) {
            self(self, v, dep + 1);
        }
    };  
    dfs1(dfs1, u, 1);
    
    std::vector<int> ans;
    auto dfs2 = [&](auto self, int x, int dep) -> void {
        if (dep == cnt) {
            ans.push_back(x);
            return ;
        }
        for (int v : mp[x]) {
            self(self, v, dep + 1);
        }
    };  

    dfs2(dfs2, u, 1);

    std::cout << cnt << "\n";
    for (int i = 0; i < ans.size(); i++) {
        std::cout << ans[i] << " \n"[i == ans.size() - 1];
    }

    return 0;
}

L2-027 名人堂与代金券

思路：

  • 直接模拟即可，利用 map 和 set 处理所有的顺序

时间复杂度：\(O(kloglogn)\)

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
struct node {
    std::string s;
    int w;
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, G, K;
    std::cin >> N >> G >> K;

    std::vector<node> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i].s >> a[i].w;
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (a[i].w >= 60 && a[i].w < G) {
            ans += 20;
        } else if (a[i].w >= G && a[i].w <= 100) {
            ans += 50;
        }
    }

    std::map<int, std::set<std::string>, std::greater<int>> mp;
    for (auto [x, y] : a) {
        mp[y].insert(x);
    }

    std::cout << ans << "\n";
    int tot = 0, lst = 0;
    std::vector<std::pair<std::string, int>> res;
    for (auto [x, y] : mp) {
        tot += 1;
        for (auto s : y) {
            std::cout << tot + lst << " " << s << " " << x << "\n";
        }
        lst += y.size() - 1;
        if (lst + tot >= K) break;
    }

    return 0;
}

L2-029 特立独行的幸福

思路：

  • 模拟，用 set 记录一下是否依赖即可，然后记录幸福数的个数

时间复杂度：\(O(nlogx)\)

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
bool isprime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int A, B;
    std::cin >> A >> B;

    std::vector<int> cnt(100010), vis(100010);
    auto check = [&](int x) {
        std::set<int> st;
        int t = x;
        while (t != 1) {
            st.insert(t);
            int sum = 0;
            while (t) {
                int v = t % 10;
                t /= 10;
                sum += v * v;
            }
            cnt[x]++;
            vis[sum] = 1;
            t = sum;
            if (st.count(t)) return false;
        }
        return true;
    };

    std::vector<int> ans;
    for (int i = A; i <= B; i++) {
        if (check(i)) ans.push_back(i);    
    }
    bool ok = false;
    for (int i = 0; i < ans.size(); i++) {
        if (isprime(ans[i])) cnt[ans[i]] <<= 1;
        if (!vis[ans[i]]) {
            std::cout << ans[i] << " " << cnt[ans[i]] << "\n";
            ok = true;
        }
    }
    if (!ok) {
        std::cout << "SAD\n";
    }

    return 0;
}

L2-030 冰岛人

思路：

  • 利用 map 来存储维京男性和维京女性以及普通男性和普通女性的姓名
  • 然后利用暴力搜索出五代以内是否有公共祖先

时间复杂度：\(O(N \times logN)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::map<std::string, std::pair<int, std::string>> Record;
    for (int i = 0; i < N; i++) {
        std::string fname, sname;
        std::cin >> fname >> sname;
        if (sname.back() == 'n') { // 维京男性
            Record[fname] = {1, sname.substr(0, sname.size() - 4)};
        } else if (sname.back() == 'r') { // 维京女性
            Record[fname] = {0, sname.substr(0, sname.size() - 7)};	
        } else if (sname.back() == 'm') { // 普通男性
            Record[fname].first = 1;
        } else { // 普通女性
            Record[fname].first = 0;
        }
    }

    auto check = [&](std::string a, std::string b) {
        int cnt1 = 0, cnt2;
        while (a != "") {
            cnt2 = 0;
            std::string b2 = b;
            while (b2 != "") {
                if (a == b2 && (cnt1 < 4 || cnt2 < 4)) return "No\n";
                if (cnt1 >= 4 && cnt2 >= 4) return "Yes\n";
                b2 = Record[b2].second;
                cnt2++;
            }
            a = Record[a].second;
            cnt1++;
        }
        return "Yes\n";
    };

    int M;
    std::cin >> M;

    while (M--) {
        std::string fname, temp, sname;
        std::cin >> fname >> temp >> sname >> temp;
        if (!Record.count(fname) || !Record.count(sname)) {
            std::cout << "NA\n";
        } else if (Record[fname].first == Record[sname].first) {
            std::cout << "Whatever\n";
        } else {
            std::cout << check(fname, sname);
        }
    }
    
    return 0;
}

L2-031 深入虎穴

思路：

  • 首先找到那个唯一入口门的位置，然后进行 dfs 即可，可以类比一下L2-026 小字辈这题，几乎一模一样，唯一的区别就是有向树找根，有向树的根的入度为 0.

时间复杂度：\(O(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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::vector<int> deg(N);
    std::vector<std::vector<int>> adj(N);
    for (int i = 0; i < N; i++) {
        int K;
        std::cin >> K;

        for (int j = 0; j < K; j++) {
            int x;
            std::cin >> x;
            x--;
            adj[i].push_back(x);
            deg[x]++;
        }
    }

    int u = -1;
    for (int i = 0; i < N; i++) {
        if (!deg[i]) u = i;
    }

    int mx = 1;
    auto dfs1 = [&](auto self, int x, int dep) -> void {
        mx = std::max(mx, dep);
        for (int v : adj[x]) {
            self(self, v, dep + 1);
        }
    };
    dfs1(dfs1, u, 1);
       
       auto dfs2 = [&](auto self, int x, int dep) -> void {
           if (dep == mx) {
               std::cout << x + 1 << "\n";
               return ;
           }
           for (int v : adj[x]) {
            self(self, v, dep + 1);
        }
       };
    dfs2(dfs2, u, 1);

    return 0;
}

L2-032 彩虹瓶

思路：

  • 按照题目意思模拟，可以看出来就是考察的 stack 这个数据结构，只要发现存储的个数大于 M 或者无法按顺序排列，就不行

时间复杂度：\(O(KN)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M, K;
    std::cin >> N >> M >> K;

    for (int i = 0; i < K; i++) {
        std::vector<int> a(N);
        for (int j = 0; j < N; j++) {
            std::cin >> a[j];
        }

        std::stack<int> stk;
        std::vector<int> ans;
        int tot = 1, f = 0;
        for (int j = 0; j < N; j++) {
            if (a[j] == tot) {
                ans.push_back(tot);
                tot++;
            } else if (stk.size() && stk.top() == tot) {
                stk.pop();
                ans.push_back(tot);
                tot++;
                j--;
            } else {
                stk.push(a[j]);
            }
            if (stk.size() > M) f = true;
        }
        if (stk.size() > M || f) {
            std::cout << "NO\n";
            continue ;
        }
        while (stk.size()) {
            ans.push_back(stk.top());
            stk.pop();
        }
        if (std::is_sorted(ans.begin(), ans.end())) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
    
    return 0;
}

L2-033 简单计算器

思路：

  • 利用栈按照题意模拟

时间复杂度：\(O(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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::stack<int> num;
    for (int i = 0; i < N; i++) {
        int x;
        std::cin >> x;
        num.push(x);
    }

    std::stack<char> op;
    for (int i = 0; i + 1 < N; i++) {
        char c;
        std::cin >> c;
        op.push(c);
    }
    auto check = [&](int x, int y, char op) {
        if (op == '/' && y == 0) {
            return false;
        }
        return true;
    };
    
    auto cal = [&](int x, int y, char op) {
        if (op == '/') {
            return x / y;
        }
        if (op == '*') {
            return x * y;
        }
        if (op == '-') {
            return x - y;
        }
        if (op == '+') {
            return x + y;
        }
    };

    while (num.size() > 1) {
        int y = num.top();
        num.pop();
        int x = num.top();
        num.pop();

        char c = op.top();
        op.pop();
        if (check(x, y, c)) {
            num.push(cal(x, y, c));
        } else {
            std::cout << "ERROR: " << x << "/0" << "\n";
            return 0;
        }
        if (num.size() == 1) {
            std::cout << num.top() << "\n";
            break;
        }
    }

    return 0;
}

L2-034 口罩发放

思路：

  • 首先我们创建一个结构体 node 来存储每个人的个人有关信息，然后创建一个 map 来存储最后一次的记录的日期，通过 check 函数判断是否合法，然后按照题意模拟

时间复杂度：\(O(D \times TlogT)\)

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
struct node {
    std::string name, id, time;
    int ill, pos;
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int D, P;
    std::cin >> D >> P;

    std::vector<node> ill;
    std::map<std::string, int> mp;
    std::set<std::string> gotten;
    for (int t = 0; t < D; t++) {
        int T, S;
        std::cin >> T >> S;

        auto check = [&](std::string x) {
            if (x.size() != 18) return false;
            for (char c : x) {
                if (c < '0' || c > '9') return false;
            }
            return true;
        };

        std::vector<node> Record(T);
        for (int i = 0; i < T; i++) {
            std::cin >> Record[i].name >> Record[i].id >> Record[i].ill >> Record[i].time;
            Record[i].pos = i;
            if (!check(Record[i].id)) Record[i].name = "";
            else {
                if (!mp.count(Record[i].id)) mp[Record[i].id] = -30;
                if (Record[i].ill && !gotten.count(Record[i].id)) {
                    ill.push_back(Record[i]);
                    gotten.insert(Record[i].id);
                }
            }
        }
        std::sort(Record.begin(), Record.end(), [&](auto i, auto j) {
            if (i.time != j.time) return i.time < j.time;
            return i.pos < j.pos;
        });
        int sum = 0;
        for (int i = 0; i < T && sum < S; i++) {
            if (Record[i].name != "" && t - mp[Record[i].id] > P) {
                mp[Record[i].id] = t;
                sum++;
                std::cout << Record[i].name << " " << Record[i].id << "\n";
            }
        }
    }
    for (auto e : ill) {
        std::cout << e.name << " " << e.id << "\n";
    }

    return 0;
}

L2-035 完全二叉树的层序遍历

思路：

  • 可以发现，题目说这是一颗完全二叉树，那么可以知道，按照完全二叉树的遍历原理进行后序遍历，先进入左右子树（编号为index * 2 和 index * 2 + 1，即index右移1位，和index右移1位+1），cnt为后序遍历的位置标记，并将当前所在的后序遍历的元素，填入ans[index]内即可

时间复杂度：\(O(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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }

    int tot = 0;
    std::vector<int> ans(N + 1);
    std::function<void(int)> dfs = [&](int x) {
        if (x > N) return ;
        dfs(x << 1);
        dfs(x << 1 | 1);
        ans[x] = a[tot++];
    };

    dfs(1);
    for (int i = 1; i <= N; i++) {
        std::cout << ans[i] << " \n"[i == N];
    }

    return 0;
}

L2-037 包装机

思路：

  • 按照题目意思模拟，那个框其实就是一个栈，夹取物品就是出栈，按照意思模拟即可，只需要注意当队列为空，就不采取任何措施

时间复杂度：\(O(n \times m)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M, S;
    std::cin >> N >> M >> S;

    std::map<int, std::deque<char>> mp;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char c;
            std::cin >> c;
            mp[i + 1].push_back(c);
        }
    }

    int x;
    std::string ans = "";
    std::stack<char> stk;
    while (std::cin >> x && x != -1) {
        if (x != 0) {
            if (mp[x].empty()) continue ;
            if (stk.size() < S) {
                if (mp[x].size()) {
                    stk.push(mp[x].front());
                    mp[x].pop_front();
                }
            } else {
                char t = stk.top();
                stk.pop();
                ans += t;
                if (mp[x].size()) {
                    stk.push(mp[x].front());
                    mp[x].pop_front();
                }
            }
        } else {
            if (stk.size()) {
                char t = stk.top();
                ans += t;
                stk.pop();
            }
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}

L2-038 病毒溯源

思路：

  • 其实也可以用 dfs，求出深度最大的点即可，然后倒着找path

时间复杂度：\(O(n \times klogk)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::vector<int> deg(N), path(N);
    std::vector<std::vector<int>> adj(N);
    for (int i = 0; i < N; i++) {
        int k;
        std::cin >> k;

        for (int j = 0; j < k; j++) {
            int x;
            std::cin >> x;
            deg[x]++;
            path[x] = i;
            adj[i].push_back(x);
        }
        std::sort(adj[i].begin(), adj[i].end());
    }
    int u = 0;
    for (int i = 0; i < N; i++) {
        if (!deg[i]) u = i;
    }

    int ans = 0, mx = 0;
    // bfs or dfs
    // bfs version
    std::queue<std::pair<int, int>> q;
    q.push({u, 1});
    while (!q.empty()) {
        auto [x, dep] = q.front();
        q.pop();

        if (dep > mx) {
            mx = dep;
            ans = x;
        }
        for (int e : adj[x]) {
            q.push({e, dep + 1});
        }
    }
    /* dfs version
    auto dfs = [&](auto self, int u, int dep) -> void {
        if (dep > mx) {
            mx = dep;
            ans = u;
        }
        for (auto x : adj[u]) {
            self(self, x, dep + 1);
        }
    };
    dfs(dfs, u, 1);
    */
    std::cout << mx << "\n";
    std::vector<int> p;
    while (ans != u) {
        p.push_back(ans);
        ans = path[ans];
    }
    p.push_back(u);
    for (int i = 0; i < p.size(); i++) {
        std::cout << p[p.size() - i - 1] << " \n"[i == p.size() - 1];
    }
    
    return 0;
}

L2-039 清点代码库

思路：

  • 就是计算有多少个序列是重复的，直接用map维护即可

时间复杂度：\(O(n(logn + m))\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M;
    std::cin >> N >> M;

    std::map<std::vector<int>, int> mp;
    std::vector<std::vector<int>> a(N, std::vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            std::cin >> a[i][j];
        }
        mp[a[i]]++;
    }

    std::vector<std::pair<int, std::vector<int>>> ans;
    for (auto [x, y] : mp) {
        ans.push_back({y, x});
    }

    std::cout << ans.size() << "\n";
    std::sort(ans.begin(), ans.end(), [&](auto i, auto j) {
        if (i.first != j.first) {
            return i.first > j.first;
        }
        return i.second < j.second;
    });

    for (auto [x, y] : ans) {
        std::cout << x << " ";
        for (int i = 0; i < y.size(); i++) {
            std::cout << y[i] << " \n"[i == y.size() - 1];
        }
    }

    return 0;
}

L2-040 哲哲打游戏

思路：

  • 模拟即可，做一个结构体来存每次的存档情况，然后按照题目意思模拟

时间复杂度：\(O(n \times k)\)

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
struct node {
    int pos;
    std::vector<int> path;
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M;
    std::cin >> N >> M;

    std::vector<std::vector<int>> adj(N + 1);
    for (int i = 0; i < N; i++) {
        int K;
        std::cin >> K;
        for (int j = 0; j < K; j++) {
            int x;
            std::cin >> x;

            adj[i + 1].push_back(x);
        }
    }
    
    int now = 1;
    std::vector<int> tmp(1, 1);
    std::vector<node> save(105);
    for (int i = 0; i < M; i++) {
        int op, x;
        std::cin >> op >> x;

        if (op == 0) {
            tmp.push_back(adj[now][x - 1]);
            now = adj[now][x - 1];
        } else if (op == 1) {
            save[x].pos = now;
            save[x].path = tmp;
            std::cout << now << "\n";
        } else {
            now = save[x].pos;
            tmp = save[x].path;
        }
    }
    std::cout << tmp.back() << "\n";

    return 0;
}

L2-041 插松枝

思路：

  • tree[N]代表每一个松针数组，bot代表盒子，我们需要按照题目的意思模拟
  • 但需要特别注意的是，最后一定要把盒子清空，结束的时候，盒子里不能有任何松针

时间复杂度：\(O(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
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
constexpr int N = 1010;
std::vector<int> tree[N];

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M, K;
    std::cin >> N >> M >> K;

    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }

    int tot = 1;
    std::deque<int> bot;
    for (int i = 0; i < N; i++) {
        if (tree[tot].size() == K) {
            tot++;
        }
        if (bot.empty()) {
            if (tree[tot].empty()) {
                tree[tot].push_back(a[i]);
            } else if (tree[tot].back() >= a[i]) {
                tree[tot].push_back(a[i]);
            } else {
                bot.push_back(a[i]);
            }
        } else if (bot.size() < M) {
            if (tree[tot].empty()) {
                int tmp = bot.back();
                bot.pop_back();
                tree[tot].push_back(tmp);
                i--;
            } else if (bot.back() <= tree[tot].back()) {
                int tmp = bot.back();
                bot.pop_back();
                tree[tot].push_back(tmp);
                i--;
            } else if (bot.back() > tree[tot].back()) {
                if (a[i] <= tree[tot].back()) {
                    tree[tot].push_back(a[i]);
                } else {
                    bot.push_back(a[i]);
                }
            }
        } else if (bot.size() == M) {
            if (tree[tot].empty()) {
                int tmp = bot.back();
                bot.pop_back();
                tree[tot].push_back(tmp);
                i--;
            } else if (bot.back() <= tree[tot].back()) {
                int tmp = bot.back();
                bot.pop_back();
                tree[tot].push_back(tmp);
                i--;
            } else if (bot.back() > tree[tot].back()) {
                if (a[i] <= tree[tot].back()) {
                    tree[tot].push_back(a[i]);
                } else {
                    tot++;
                    i--;
                }
            }
        }
    }
    while (bot.size()) {
        if (tree[tot].empty() || bot.back() <= tree[tot].back()) {
            tree[tot].push_back(bot.back());
            bot.pop_back();
        } else {
            tot++;
        }
        if (tree[tot].size() == K) tot++;
    }
    for (int i = 1; i <= tot; i++) {
        if (tree[i].size()) {
            for (int j = 0; j < tree[i].size(); j++) {
                std::cout << tree[i][j] << " \n"[j == tree[i].size() - 1];
            }
        }
    }
    return 0;
}

L2-042 老板的作息表

思路：

  • 可以根据题意，设置起始时间 00:00:00 和终止时间 23:59:59，然后将题目所给的时间排序，然后开始匹配，当找到头部相等，就更新头部信息 \(\rightarrow\) 当前位置的结束时间，最后如果结束时间不等于这一天的最后时刻，就直接输出最后的时间到最后的时刻

时间复杂度：\(O(NlogN)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::string c;
    std::vector<std::pair<std::string, std::string>> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i].first >> c >> a[i].second;
    }

    std::sort(a.begin(), a.end(), [&](auto i, auto j) {
        return i.first < j.first;
    });
    std::string start = "00:00:00", end = "23:59:59";
    for (int i = 0; i < N; i++) {
        if (a[i].first == start) {
            start = a[i].second;
        } else {
            std::cout << start << " - " << a[i].first << "\n";
            start = a[i].second;
        }
    }
    if (start != end) {
        std::cout << start << " - " << end << "\n";
    }

    return 0;
}

L2-043 龙龙送外卖

思路：

  • 快递站是一颗树，我们求每一个节点到root节点的深度，然后当增加一个外卖站点(节点)，我们需要走的距离为计算从 \(x\) 到 \(x\) 所在的最远祖先(第一个被访问过的祖先)的路径长度 \(\Sigma_{i=0}^{M}node_{new} - node_{last} - max(node_{i})\)

时间复杂度：\(O(N + M \times Depth_{tree})\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M;
    std::cin >> N >> M;

    std::vector<int> p(N + 1);
    std::vector<std::vector<int>> adj(N + 1);
    for (int i = 1; i <= N; i++) {
        int x;
        std::cin >> x;

        if (x < 0) {
            p[0] = i;
        } else {
            adj[x].push_back(i);
        }
        p[i] = x;
    }
    // bfs or dfs
    std::vector<int> vis(N + 1), dist(N + 1);
    vis[p[0]] = 1;
    // bfs 
    std::queue<std::pair<int, int>> q;
    q.push({p[0], 0});
    while (!q.empty()) {
        auto [now, dep] = q.front();
        q.pop();

        dist[now] = dep;
        for (int x : adj[now]) {
            q.push({x, dep + 1});
        }
    }
    // dfs
    auto dfs = [&](auto self, int u, int dep) -> void {
        dist[u] = dep;
        for (auto x : adj[u]) {
            self(self, x, dep + 1);
        }
    };
    dfs(dfs, p[0], 0);

    int res = 0, lst = 0, max = 0;
    for (int i = 0; i < M; i++) {
        int x;
        std::cin >> x;

        lst = x;
        while (!vis[lst]) { // 访问所有点了的外卖至少一次
            vis[lst] = 1;
            lst = p[lst];
        }
        res += dist[x] - dist[lst];
        max = std::max(max, dist[x]);
        std::cout << res * 2 - max << "\n";
    }

    return 0;
}

L2-044 大众情人

思路：

  • 我们设 2 个集合，分别存男性和女性编号，然后用dist[i][Fri]来存储当前这个人i到朋友Fri之间的距离，然后可以使用 Floyd最短路来跑一遍，来计算每个人之间的最短距离
  • 由于题目中的“异性缘”的定义规则为：我们记一个人 \(i\) 在一个异性 \(j\) 眼中的距离感为 \(D_{ij}\)，将 \(i\) 的“异性缘”定义为 \(1/max_{j∈S(i)}\{D_{ij}\}\)，其中 \(S(i)\) 是相对于 \(i\)​ 的所有异性的集合。
  • 所以我们可以直接暴力枚举两个集合，然后求出当前异性缘最大的那个人的编号

时间复杂度：\(O(N^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
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
constexpr int inf = 1E9;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::vector<int> male, female;
    std::vector<std::vector<int>> dist(N + 1, std::vector<int>(N + 1, inf));
    for (int i = 1; i <= N; i++) {
        int K;
        char C;
        std::cin >> C >> K;
        if (C == 'F') {
            female.push_back(i);
        } else {
            male.push_back(i);
        }
        for (int j = 0; j < K; j++) {
            int Fri, d;
            std::cin >> Fri >> C >> d;
            dist[i][Fri] = d;
        }
    }

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dist[i][j] = std::min(dist[i][k] + dist[k][j], dist[i][j]);
            }
        }
    }

    auto get = [&](auto &find, auto &base, auto &target, int mark = 0) {
        for (int i = 0, score = 0; i < find.size(); i++, score = 0) {
            for (int j = 0; j < base.size(); j++) {
                score = std::max(score, dist[base[j]][find[i]]);
            }
            target[score].insert(find[i]);
        }
        for (auto x : target.begin()->second) {
            if (mark++) std::cout << " ";
            std::cout << x;
        }
    };
    
    std::map<int, std::set<int>> Fans, Mans;
    get(female, male, Fans);
    std::cout << "\n";
    get(male, female, Mans);
    
    return 0;
}

L2-045 堆宝塔

思路：

  • 用栈模拟圈的上下移动即可

时间复杂度：\(O(nlogn)\)

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
constexpr int N = 10010;
std::vector<int> v[N];
int a[N];

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

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

    std::stack<int> s;
    int p = 0;
    v[p].push_back(a[0]);
    for (int i = 1; i < n; i++) {
        if (v[p].size() && a[i] < v[p].back()) { // 如果比下面的那个圈小
            v[p].push_back(a[i]);
        } else if (v[p].size() && a[i] >= v[p].back()) { // 如果比下面那个圈大，
            if (s.empty() || (s.size() && a[i] > s.top())) s.push(a[i]); // 如果B柱子为空
            else if (s.size() && a[i] <= s.top()) {
                p++;
                while (s.size() && s.top() > a[i]) {
                    v[p].push_back(s.top());
                    s.pop();
                }
                v[p].push_back(a[i]);
            }
        }
    }
    if (s.size()) p++;
    std::cout << p + 1 << ' ';
    
    int mx = s.size();
    for (int i = 0; i <= p; i++) {
        mx = std::max(mx, (int)v[i].size());
    }

    std::cout << mx;
    return 0;
}

L2-046 天梯赛的赛场安排

思路：

  • 用 BFS 模拟，在优先队列(大根堆)里，先分配数量多的，然后分配数量少的

时间复杂度：\(O(NlogN)\)

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
constexpr int N = 250010;
int room[N];

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, C;
    std::cin >> N >> C;

    std::vector<std::string> s(N);
    std::priority_queue<std::pair<int, std::string>> q;
    for (int i = 0; i < N; i++) {
        int x;
        std::cin >> s[i] >> x;
        q.push({x, s[i]});
    }
    
    int tot = 0, ok = 0;
    std::map<std::string, int> mp;
    while (q.size()) {
        auto [cur, t] = q.top();
        q.pop();

        mp[t]++;
        if (cur >= C) {
            room[++tot] = 0;
            if (cur != C) {
                q.push({cur - C, t});
            }
        } else {
            ok = false;
            for (int i = 1; i <= tot; i++) {
                if (room[i] >= cur) {
                    room[i] -= cur;
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                room[++tot] = C - cur;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < N; i++) {
        std::cout << s[i] << " " << mp[s[i]] << "\n";
    }
    std::cout << tot << "\n";
    
    return 0;
}

L2-047 锦标赛

思路：

时间复杂度：\(O(k \times 2^k)\)

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
constexpr int N = 50, M = 1 << 20;
int id[N][M];

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int k;
    std::cin >> k;

    bool ok = true;
    std::vector<int> ans(M);
    std::vector<std::vector<int>> a(k + 1);
    for (int i = 1; i <= k; i++) {
        int n = 1 << (k - i);
        a[i].resize(n);
        for (int j = 0; j < n; j++) {
            std::cin >> a[i][j];
            if (i == 1) {
                ans[j << 1] = a[i][j];
                id[i][j] = (j << 1 | 1);
                continue ;
            }
            int max = std::max(a[i][j], std::max(a[i - 1][j << 1], a[i - 1][j << 1 | 1]));
            if (a[i][j] < a[i - 1][j << 1] && a[i][j] < a[i - 1][j << 1 | 1]) {
                ok = false;
                break;
            } else if (a[i][j] >= a[i - 1][j << 1]) {
                ans[id[i - 1][j << 1]] = a[i][j];
                id[i][j] = id[i - 1][j << 1 | 1];
            } else {
                ans[id[i - 1][j << 1 | 1]] = a[i][j];
                id[i][j] = id[i - 1][j << 1];
            }
            a[i][j] = max;
        }
    }

    int w;
    std::cin >> w;

    if (a[k][0] > w) {
        ok = false;
    } else {
        ans[id[k][0]] = w;
    }
    if (!ok) {
        std::cout << "No Solution\n";
    } else {
        for (int i = 0; i < (1 << k); i++) {
            std::cout << ans[i] << " \n"[i == (1 << k)];
        }
    }
    
    return 0;
}

L2-048 寻宝图

思路：

  • 直接 BFS 搜一下即可

时间复杂度：\(O(n \times m)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;    
    std::cin >> n >> m;

    std::vector<std::vector<char>> g(n, std::vector<char> (m, 0));
    std::vector<std::vector<int>> st(n, std::vector<int> (m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> g[i][j];
        }
    }

    bool flag = false;
    const int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
    auto bfs = [&] (int x, int y) {
        std::queue<std::pair<int, int>> q;
        q.push({x, y});
        st[x][y] = 1;

        while (q.size()) {
            auto t = q.front();
            q.pop();

            if (g[t.first][t.second] >= '2' && g[t.first][t.second] <= '9') flag = true;
            for (int i = 0; i < 4; i++) {
                int a = dx[i] + t.first, b = dy[i] + t.second;
                if (a < 0 || b < 0 || a >= n || b >= m || st[a][b]) continue;
                if (g[a][b] == '0') continue;
                st[a][b] = 1;
                q.push({a, b});
            }
        }
    };
    int ans = 0, res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!st[i][j] && g[i][j] != '0') {
                bfs(i, j);
                ans++;
                if (flag) {
                    res++;
                }
                flag = false;
            }
        }
    }
    std::cout << ans << ' ' << res << '\n';
    return 0;
}

L2-049 鱼与熊掌

思路：

  • 直接开m个set即可，假设x和y是询问的两个物品，那么我们只需要枚举集合x中的人员，与y中的相同的数量即可

时间复杂度：\(O(nlogn)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::set<int> st[m + 1];
    for (int i = 0; i < n; i++) {
        int k;
        std::cin >> k;

        for (int j = 0; j < k; j++) {
            int x;
            std::cin >> x;
            st[x].insert(i);
        }
    }

    int Q;
    std::cin >> Q;

    while (Q--) {
        int x, y;
        std::cin >> x >> y;

        int ans = 0;
        for (auto v : st[x]) {
            if (st[y].count(v)) {
                ans++;
            }
        }
        std::cout << ans << "\n";
    }

    return 0;
}

L2-050 懂蛇语

思路：

  • 如果按照题目意思模拟，不考虑一句话的前面是否存在空格，就会在第二个点出现格式错误，所以我们要先将前面的空格去除，然后存储的时候，需要把前面删除的空格给补回来

时间复杂度：\(O(nlogn)\)

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
signed main() {
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    getchar();

    std::map<std::string, std::vector<std::string>> mp;
    for (int i = 0; i < N; i++) {
        std::string s;
        std::getline(std::cin, s);

        int l = 0;
        while (s[l] == ' ') {
            l++;
        }
        s = s.substr(l);
        std::vector<std::string> vec;
        for (int j = 0; j < s.size(); j++) {
            int k = j, len = 0;
            while (k < s.size() && s[k] != ' ') {
                k++;
                len++;
            }
            while (s[k] == ' ') {
                k++;
            }
            std::string t = s.substr(j, len);
            vec.push_back(t);
            j = k - 1;
        }
        std::string tmp;
        for (int j = 0; j < vec.size(); j++) {
            tmp += vec[j][0];
        }
        if (l != 0) {
            while (l--) {
                s = ' ' + s;
            }
        }
        mp[tmp].push_back(s);
    }

    int M;
    std::cin >> M;

    getchar();

    for (int i = 0; i < M; i++) {
        std::string s;
        std::getline(std::cin, s);

        int l = 0;
        while (s[l] == ' ') {
            l++;
        }
        s = s.substr(l);
        std::vector<std::string> vec;
        for (int j = 0; j < s.size(); j++) {
            int k = j, len = 0;
            while (k < s.size() && s[k] != ' ') {
                k++;
                len++;
            }
            while (s[k] == ' ') {
                k++;
            }
            std::string t = s.substr(j, len);
            vec.push_back(t);
            j = k - 1;
        }
        std::string tmp;
        for (int j = 0; j < vec.size(); j++) {
            tmp += vec[j][0];
        }
        if (!mp.count(tmp)) {
            std::cout << s << "\n";
        } else {
            if (mp[tmp].size() == 1) {
                std::cout << mp[tmp][0] << "\n";
            } else {
                int tot = 0;
                std::sort(mp[tmp].begin(), mp[tmp].end());
                for (auto x : mp[tmp]) {
                    if (++tot != mp[tmp].size()) {
                        std::cout << x << "|";
                    } else {
                        std::cout << x << "\n";
                    }
                }
            }
        }
    }

    return 0;
}

L2-051 满树的遍历

思路：

  • 只需要知道一颗树怎么存以及树的前序遍历即可，没啥难的地方

时间复杂度：\(O(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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    int root = 0;
    std::vector<int> deg(n + 1);
    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;

        if (x == 0) {
            root = i;
        }

        adj[x].push_back(i);
        deg[x]++;
    }

    std::set<int> st;
    for (int i = 1; i <= n; i++) {
        st.insert(deg[i]);
    }
    if (st.size() == 2 || n == 1) {
        std::cout << *--st.end() << " " << "yes\n";
    } else {
        std::cout << *--st.end() << " " << "no\n";
    }

    int tot = 0;
    auto dfs = [&](auto self, int u) -> void {
        std::cout << u << " \n"[++tot == n];
        for (int x : adj[u]) {
            self(self, x);
        }
    };
    dfs(dfs, root);

    return 0;
}

L2-052 吉利矩阵

思路：

  • 我们将问题改变为存储每一行每一列的值，其中row[i]和col[i]分别表示第i行与第i列的和，然后我们开始暴搜

时间复杂度：\(O(N^L)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int L, N;
    std::cin >> L >> N;

    int ans = 0;
    std::vector<int> row(N + 1), col(N + 1);
    auto dfs = [&](auto self, int x, int y) {
        if (x == N + 1) {
            ans++;
            return ;
        }
        for (int i = 0; i <= L; i++) {
            row[x] += i;
            col[y] += i;
            if (row[x] <= L && col[y] <= L) {
                int v = 0; // 剪枝优化
                if (x == N) {
                    if (col[y] == L) {
                        v++;
                    }
                } else {
                    v++;
                }
                if (y == N) {
                    if (row[x] == L) {
                        v++;
                    }
                } else {
                    v++;
                }
                if (v == 2) {
                    self(self, x + (y / N), y % N + 1);
                }
            }
            col[y] -= i;
            row[x] -= i;
        }
    };
    dfs(dfs, 1, 1);

    std::cout << ans << "\n";

    return 0;
}