「题解」2024 ICPC 网络赛第一场

A. World Cup

给出 32 个队伍的实力，然后按照小组赛 => 16 强 => 8 强 => 4 强 => 2 强 => 冠军的顺序判断中国队最好情况能取得的等次。对于小组赛而言，每一个小组的前两名才能出线，且出线后的 16 强赛是每一个小组的第一名和另一个小组的第二名对战。

本题主要难度在于理解题面。感觉是我挺好萌看少了。

不难发现 16 强出线的条件当且仅当有 2 个队伍比自己弱，然后考虑 8 强出线的条件就是某一个小组的第一名比自己弱，也就是额外有 4 个队伍比自己弱，总共 6 个队伍。然后考虑 4 强就需要有另外 7 个队伍比自己弱（考虑我们在 4 强赛上遇到的也是按照自己这个规则晋升上来的，加上这个人共有 7 个队伍）。然后这里我们从后往前推就比较麻烦了，我们考虑从前往后推。手玩一下不难发现想要进 2 强的话只需要至多有 4 个队比我们强就行（考虑这四个倒霉蛋全都分到一个组里去了）。最后不难想到当且仅当没人比我们强我们才能取得冠军。

Code

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        array<int, 32> a = {};
        for (int i = 0; i < 32; i++)
            cin >> a[i];
        int val = a[0];
        sort(a.begin(), a.end());
        auto k = a.end() - lower_bound(a.begin(), a.end(), val) - 1;
        // 我操，怎么还有小组赛
		if (k == 0) cout << 1 << '\n';
        else if (k <= 4) cout << 2 << '\n';
        else if (k <= 18) cout << 4 << '\n';
        else if (k <= 25) cout << 8 << '\n';
        else if (k <= 29) cout << 16 << '\n';
        else cout << 32 << '\n';
		
    }
    return 0;
}

M. Find the Easiest Problem

定义最简单的题目是最多队伍通过的题目。然后每一个队伍可能会有多个提交，每个提交可能是正确（accepted) 或者错误（rejected），问你最简单的题目是哪道。

简单用 map 模拟一下即可。

说句闲话：
2025 年的网络赛第一场也是一个关于 ICPC 题目的题目，但是那玩意比这个东西恶心一万倍。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

int main() {
   cin.tie(nullptr)->sync_with_stdio(false);
   int t;
   cin >> t;
   while (t--) {
       int n;
       cin >> n;
       map<string, int> ump;
       map<string, set<string>> mp;
       while (n--) {
           string name, problem, status;
           cin >> name >> problem >> status;
           if (status == "accepted") {
               if (ump.contains(problem) == false)
                   ump[problem] = 0;
               if (mp[name].contains(problem))
                   continue;
               ump[problem]++;
               mp[name].insert(problem);
           }
       }
       int val = -1;
       string ans;
       for (auto [k, v] : ump) {
           if (v > val) {
               ans = k;
               val = v;
           }
       }
       cout << ans << "\n";
   }
   return 0;
}

F. Make Max

实际上感觉是很有意思的一道题目。

这里采用的是题解的做法，我们就把它当作一道笛卡尔树例题吧。

给定一个长度为 $n$ 的数组 $a$，你可以选择一个元素不重的连续区间 $a[l..r]$ 然后把其每一个元素变成区间内的最大值。问最多的操作次数。

不难想到因为我们要操作次数最大，所以我们希望我们的区间尽可能小，于是我们发现我们每次只需要选择两个相邻的数操作即可，最后的答案是每个数的操作次数也就是这个数到根的路径上不同的数字个数。

然后我们建立一个笛卡尔树（坐标为 BIT，$a_i$ 为大根堆），根据笛卡尔树的特性我们不难发现我们对这个树进行中序遍历就能完成相邻合并的操作，然后还是根据笛卡尔树的特性我们发现判断不同树的个数只需要和父节点比较即可。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

#define int long long
void solve() {
    int n, ans = 0;
    cin >> n;

    vector<int> a(n + 1), l(n + 1), r(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    stack<int> stk;
    for (int i = 1; i <= n; ++i) {
        int lst = 0;
        while (not stk.empty() && a[stk.top()] < a[i]) {
            lst = stk.top();
            stk.pop();
        }

        if (lst != 0) {
            l[i] = lst;
        }

        if (!stk.empty()) {
            r[stk.top()] = i;
        }

        stk.push(i);
    }

    int root;
    while (not stk.empty())
        root = stk.top(), stk.pop();

    [&](this auto dfs, int u, int cnt, int fa) -> void {
        if (u == 0) {
            return;
        }

        int cur = cnt;
        if (a[u] != fa) {
            cur++;
        }

        ans += cur;

        dfs(l[u], cur, a[u]);
        dfs(r[u], cur, a[u]);
    }(root, 0, 0);

    std::cout << ans - n << std::endl;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}