Contest Notes

Codeforces Hello 2025

比赛链接

Problems AC Note
A. MEX Table ○
B. Gorilla and the Exam ○
C. Trip to the Olympiad ○
D. Gifts Order ○ 线段树
E1. Another Exercise on Graphs (Easy Version) ⊕ 二分
E2. Another Exercise on Graphs (hard version) ⊕ 并查集
F. Formation
G. Secret Message
H. Coffee Break

A

Code
1
2
3
4
5
6
7
8
void solve() {
    int n = read();
    int m = read();

    int ans = 0;
    ans += max(n, m) + 1;
    cout << ans << '\n';
}

B

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
void solve() {
    int n = read();
    int k = read();

    vector<int> a(n);
    std::map<int, int> mp;
    for (auto &x : a) {
        x = read();
        mp[x]++;
    }

    vector<pii> b;
    for (auto [x, y] : mp) {
        b.eb(x, y);
    }
    std::sort(b.begin(), b.end(), [&](pii a, pii b) {
        return a.se > b.se;
    });
    int ans = b.size() - 1;
    while (ans >= 1LL and b[ans].se <= k and k >= 0LL) {
        k -= b[ans].se;
        ans--;
    }
    cout << ans + 1 << '\n';
}

C

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
void solve() {
    int l = read();
    int r = read();

    auto calc = [&](int x, int y, int z) {
        return (x ^ y) + (y ^ z) + (x ^ z);
    };

    int sum = 0; 
    int p = 30; 
    #define x (1LL << p)
    while (p >= 0) { 
        if ((l & x) == (r & x)) { 
            if (l & x) sum += x; 
        } else break; 
        --p; 
    } 
    if (r > sum + x) { 
        cout << sum + x - 1 << ' ' 
             << sum + x << ' ' 
             << sum + x + 1 << '\n'; 
    } else { 
        cout << sum + x - 2 << ' ' 
             << sum + x - 1 << ' ' 
             << sum + x << '\n'; 
    } 
}

D

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
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
template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
};

constexpr int inf = 1E9 + 1;
struct Info {
    int cnt;
    int minPre;
    int maxPre;
    int minSuf;
    int maxSuf;
    int mx = -inf;
};
Info get(int x) {
    return { 1, x + 1, x - 1, x + 1, x - 1, 0 };
}
Info operator+(const Info &a, const Info &b) {
    return { a.cnt + b.cnt, 
             min(a.minPre, a.cnt + b.minPre),
             max(a.maxPre, b.maxPre - a.cnt),
             min(b.minSuf, b.cnt + a.minSuf),
             max(b.maxSuf, a.maxSuf - b.cnt),
             max({a.mx, b.mx, 
                -a.minSuf + b.maxPre + 1,
                a.maxSuf - b.minPre + 1})
              };
}

void solve() {
    int n = read();
    int m = read();
    vector<int> a(n);
    for (auto &x : a) x = read();

    SegmentTree<Info> seg(n);
    for (int i = 0; i < n; i++) {
        seg.modify(i, get(a[i]));
    }
    // cerr << a << '\n';
    cout << seg.rangeQuery(0, n).mx << '\n';
    for (int i = 1; i <= m; i++) {
        int p = read() - 1, x = read();
        // a[p] = x;
        seg.modify(p, get(x));
        cout << seg.rangeQuery(0, n).mx << '\n';
    }
}

E1

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
64
void solve() {
    int n = read();
    int m = read();
    int q = read();

    vector<array<int, 3>> edges(m);
    vector dp(m + 1, vector(n, vector(n, INF)));

    for (auto &[u, v, w] : edges) {
        u = read() - 1;
        v = read() - 1;
        w = read();
    }
    std::ranges::sort(edges, [&](auto x, auto y) {
        return x[2] < y[2];
    });
    
    for (int i = 0; i < n; i++) { 
        dp[0][i][i] = 0;
    }
    for (auto [u, v, w] : edges) {
        dp[0][u][v] = dp[0][v][u] = 1;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[0][i][j] = min(dp[0][i][j], dp[0][i][k] + dp[0][k][j]);
            }
        }
    }
            
    for (int p = 1; p <= m; p++) {
        auto [u, v, _] = edges[p - 1];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[p][i][j] = min({
                    dp[p - 1][i][j],
                    dp[p - 1][i][u] + dp[p - 1][v][j],
                    dp[p - 1][i][v] + dp[p - 1][u][j]
                });
            }
        }
    }

    for (int _ = 1; _ <= q; _++) {
        int a = read() - 1;
        int b = read() - 1;
        int k = read();

        int ans = m - 1;
        for (int lo = 0, hi = m - 1; lo <= hi; ) {
            int mid = lo + hi >> 1;
            if (dp[mid + 1][a][b] < k) {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        cout << edges[ans][2] << " \n"[_ == q];
    }
}

E2

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
void solve() {
    int n = read();
    int m = read();
    int q = read();

    DSU dsu(n);

    vector<array<int, 3>> edges(m);
    vector dp(n, vector(n, vector(n, INF)));

    for (auto &[u, v, w] : edges) {
        u = read() - 1;
        v = read() - 1;
        w = read();
    }
    std::ranges::sort(edges, [&](auto x, auto y) {
        return x[2] < y[2];
    });
    
    for (int i = 0; i < n; i++) { 
        dp[0][i][i] = 0;
    }
    for (auto [u, v, w] : edges) {
        dp[0][u][v] = dp[0][v][u] = 1;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[0][i][j] = min(dp[0][i][j], dp[0][i][k] + dp[0][k][j]);
            }
        }
    }
            
    int id = 1;
    vector vals(n, 0);
    for (int p = 1; p <= m; p++) {
        auto [u, v, w] = edges[p - 1];

        if (dsu.same(u, v)) {
            continue;
        }

        dsu.merge(u, v);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[id][i][j] = min({
                    dp[id - 1][i][j],
                    dp[id - 1][i][u] + dp[id - 1][v][j],
                    dp[id - 1][i][v] + dp[id - 1][u][j]
                });
            }
        }

        vals[id] = w;
        id++;
    }

    for (int _ = 1; _ <= q; _++) {
        int a = read() - 1;
        int b = read() - 1;
        int k = read();

        int ans = m;
        for (int lo = 0, hi = n - 1; lo <= hi; ) {
            int mid = lo + hi >> 1;
            if (dp[mid][a][b] < k) {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        cout << vals[ans] << " \n"[_ == q];
    }
}

Codeforces Hello 2025

https://tosakaucw.github.io/codeforces-hello-2025/

Author

TosakaUCW

Posted on

2025-01-06

Updated on

2025-01-22

Licensed under

#

Comments

Catalogue

×