Featured image of post 「题解」Codeforces Round 1037 (Div.3)
题解

「题解」Codeforces Round 1037 (Div.3)

【并非】也许是打得最好的一次 Codeforces

比赛链接

周四偶遇 Codeforces，突然断电惊若神人，神秘路易精准押题。

最开心。

A. Only One Digit

给一个整数 $x$，求最小的整数 $y$ 与 $x$ 拥有共同数位相同。

显然 $y$ 是 $x$ 的数位中最小的那个。

代码

1
2
3
4
5
6
7
8

auto solve() {
    std::string s;
    std::cin >> s;
    char ch = '9';
    for (auto x : s)
        ch = std::min(ch, x);
    std::cout << ch << "\n";
}

B. No Casino in the Mountains

给定长度为 $n$ 由 $0$ 和 $1$ 组成的数组 $a$，如果当天下雨 $a_i=0$，否则 $a_i=1$；然后爬一座山需要连续 $k$ 天晴天，同时爬完之后需要 $1$ 天休息。问最多能爬几座山。

显然可以直接贪心：我们从前往后依次枚举每一个点 $i$，判断每一个 $[i,i+k)$ 的区间内是否有雨天，如果有那么 $i\gets i+1$，否则答案加一并且 $i\gets i+k+1$。为了加速判断区间内是否有雨天，我们可以直接做一个前缀和。

代码

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

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> pre(n + 1);
    for (int i = 0; i < n; i++)
        pre[i + 1] = pre[i] + a[i];
    int ans = 0;
    int nxt = 0;
    for (int i = 0; i + k <= n; i++) {
        if (i >= nxt and pre[i + k] - pre[i] == 0) {
            ans++;
            nxt = i + k + 1;
        }
    }
    cout << ans << "\n";
}

C. I Will Definitely Make It

给 $n$ 个塔，每个高 $h_i$，初始你在 $k$ 号塔上，水位为 $1$，每过一个单位时间，水位上升 $1$，如果水位大于塔高就会死亡。在第 $x$ 个时刻，可以耗费 $|h_i-h_j|$ 秒从塔楼 $i$ 传送到 $j$。问是否能在被水淹没前到达高度最大的塔楼。

首先显然有如果当前所在的塔楼高度就是最高的塔楼高度则一定可行，然后我们再来考虑其他的情况。

首先我们不难得出：如果我们只往更高的塔上跳，无论路径如何，我们的耗时一定是 $h’-h$，然后我们还要确保不被水淹，我们就要保证 $h’-h_k\le h$，则有 $h’\le h + h_k$，即我们最多跳到高度为 $h+h_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

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    int cur = h[k - 1];
    int mx = *max_element(h.begin(), h.end());
    if (cur == mx) {
        cout << "YES\n";
        return;
    }
    vector<int> a = h;
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    bool ok = false;
    int pos = cur;
    while (true) {
        if (pos >= mx) {
            ok = true;
            break;
        }
        int nxt = pos + cur;
        auto it = upper_bound(a.begin(), a.end(), nxt);
        if (it == a.begin())
            break;
        it--;
        if (*it <= pos)
            break;
        pos = *it;
    }
    if (ok)
        cout << "YES\n";
    else
        cout << "NO\n";
}

D. This Is the Last Time

给定 $n$ 个操作，每个操作为：$s.t\ x\in[l_i,r_i],x\gets \mathit{real}_i$，每个操作最多只能使用一次，给出初始的 $x$，问 $x$ 的最大值。

直接贪心即可。

首先我们选择一个操作当且仅当 $x\in[l_i,r_i],\mathit{real}_i\gt x$，然后我们期望 $\mathit{real}_i$ 尽可能大。于是我们可以先按 $l_i$ 从小到大排序，然后在所有 $l_i\le x$ 中按 $real_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

using i3 = array<int, 3>;
void solve() {
    int n, k;
    cin >> n >> k;
    vector<i3> a(n);
    for (auto &[l, r, real] : a)
        cin >> l >> r >> real;
    sort(a.begin(), a.end());
    priority_queue<pair<int, int>> pq;
    int x = k;
    int pos = 0;
    while (true) {
        while (pos < n and a[pos][0] <= x) {
            pq.emplace(a[pos][2], pos);
            pos++;
        }
        bool ok = false;
        while (not pq.empty()) {
            auto [v, i] = pq.top();
            pq.pop();
            if (a[i][1] < x or v <= x) {
                continue;
            }
            x = v;
            ok = true;
            break;
        }
        if (not ok)
            break;
    }
    cout << x << "\n";
}

E. G-C-D, Unlucky!

给定长度为 $n$ 的两个数组 $p$ 和 $s$，其中 $p$ 是数组 $a$ 的前缀 $\gcd$，$s$ 是 $a$ 的后缀 $\gcd$，问是否存在这样的数组 $a$。

因为 $p_i=\gcd(a_1,\ldots,a_i),s_i=\gcd(a_i,\ldots,a_n)$，因此有 $p_i\mid a_i,s_i\mid a_i$，为了使这个条件成立，我们可以令 $a_i\gets\text{lcm}(p_i,s_i)$。在此时，对于 $\forall j\lt i$，有 $p_j\mid a_j$，同时必然有 $p_j\ge p_i$，因此 $p_i\mid p_j\mid a_j$，则：

$$ \gcd(a_1,\ldots,a_i)\ge\gcd(p_i,\ldots,p_i)=p_i $$

又有 $\because a_i=\operatorname{lcm}(p_i,s_i)$，$\therefore$ 我们不会引入其他的公因子，因此 $\gcd(a_1,\ldots,a_i)\le p_i$，综合可得 $\gcd(a_1,\ldots,a_i)=p_i$

同理可得 $\gcd(a_i,\ldots,a_n)=s_i$

所以我们得出我们构造出的 $a$ 能恰好能复原 $p$ 和 $s$，我们验证 $a$ 和前后缀 $\gcd$ 是否分别是 $p$ 和 $s$ 即可。

代码

 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

#define int long long
void solve() {
    int n;
    cin >> n;
    vector<int> p(n), s(n);
    for (int i = 0; i < n; i++)
        cin >> p[i];
    for (int i = 0; i < n; i++)
        cin >> s[i];
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = p[i] / gcd(p[i], s[i]) * s[i];
    }
    if (a[0] != p[0] or a[n - 1] != s[n - 1]) {
        cout << "NO\n";
        return;
    }
    int lst = a[0];
    for (int i = 1; i < n; i++) {
        int cur = gcd(lst, a[i]);
        if (cur != p[i]) {
            cout << "NO\n";
            return;
        }
        lst = cur;
    }
    int nxt = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        int cur = gcd(nxt, a[i]);
        if (cur != s[i]) {
            cout << "NO\n";
            return;
        }
        nxt = cur;
    }
    cout << "YES\n";
}

F. 1-1-1, Free 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
62
63
64

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) std::println(std::cerr, "{}", x)

using i64 = long long;
void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), p(n + 1);
    vector<map<int, i64>> cnt(n + 1);
    map<pair<int, int>, int> w;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector adj(n + 1, vector<pair<int, int>>{});
    for (int i = 1; i < n; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
        w[{u, v}] = w[{v, u}] = c;
    }
    i64 ans = 0;
    [&](this auto &&self, int u) -> void {
        for (auto [v, w] : adj[u]) {
            if (v == p[u])
                continue;
            if (a[u] != a[v])
                ans += w;
            cnt[u][a[v]] += w;
            p[v] = u;
            self(v);
        }
    } (1);
    while (q--) {
        int v, x;
        cin >> v >> x;
        if (a[v] == x) {
            cout << ans << "\n";
            continue;
        }
        int cur = w[{v, p[v]}];
        if (p[v] and a[p[v]] == x)
            ans -= cur;
        else if (p[v] and a[v] == a[p[v]])
            ans += cur;
        cnt[p[v]][x] += cur;
        cnt[p[v]][a[v]] -= cur;
        ans += cnt[v][a[v]];
        ans -= cnt[v][x];
        a[v] = x;
        cout << ans << "\n";
    }
}

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

听说这道题有边定向的做法，但是鉴于我没听过这里就只写大部分人写的根号分治的做法了。

悲报：成功在 System Testing 中 MLE 了。

MLE 的做法

给定一颗有 $n$ 个顶点的树，每个顶点初始颜色为 $a_i$，每条边定义为 $(u_i,v_i,c_i)$，若 $u_i$ 和 $v_i$ 的颜色不相同，则该边的权值为 $c_i$，否则为 $0$。给定 $q$ 个查询，每个查询将顶点 $v$ 的颜色变成 $x$，求每次查询后树上所有边权值的总和。

首先我们不难想到，我们要求的答案就是该树所有 $c_i$ 的和减去所有相同颜色边的 $c_i$ 的和。前者为常数，我们要思考如何快速更新后者。

如果不使用任何优化，按一般方法操作，每次更新需要遍历 $v$ 的每一条边，复杂度是 $O(\deg(v))$，考虑度数特别大的情况可能会变成最坏的 $O(n)$ 的复杂度，若有 $q$ 次操作则会超时。

因此我们可以对度数分块：令块大小为 $\lceil \sqrt{2(n-1)} \rceil$，即度数低于此数值的直接用上面方法遍历，高于此值的，我们用 unordered_map 来维护该点每一种颜色的 $c_i$ 的和。同时我们还需要维护一个反向的邻接表 $adj^{-1}$ 来保存每一个点相邻的度数高的点，以便更新。

具体实现参考代码：

代码

 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

#define int long long
void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n), deg(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    auto adj = vector(n, vector<pair<int, int>>{});
    int s0 = 0;
    int s1 = 0;
    for (int i = 1; i < n; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
        deg[u]++, deg[v]++;
        s0 += c;
    }
    vector<bool> mark(n);
    int blk = sqrt(2 * (n - 1)) + 1;
    for (int i = 0; i < n; i++) {
        mark[i] = (deg[i] > blk);
    }
    for (int u = 0; u < n; u++) {
        for (auto [v, c] : adj[u]) {
            if (u < v and a[u] == a[v])
                s1 += c;
        }
    }
    vector<unordered_map<int, int>> vec(n);
    auto Tadj = vector(n, vector<pair<int, int>>{});
    for (int v = 0; v < n; v++) {
        for (auto [u, c] : adj[v]) {
            if (mark[u])
                Tadj[v].emplace_back(u, c);
        }
    }
    for (int v = 0; v < n; v++) {
        if (not mark[v])
            continue;
        for (auto [u, c] : adj[v]) {
            vec[v][a[u]] += c;
        }
    }
    while (q--) {
        int v, x;
        cin >> v >> x;
        v--;
        int y = a[v];
        int delta = 0;
        if (mark[v]) {
            delta -= vec[v][y];
            delta += vec[v][x];
        } else {
            for (auto [u, c] : adj[v]) {
                if (a[u] == y)
                    delta -= c;
                if (a[u] == x)
                    delta += c;
            }
        }
        for (auto [u, c] : Tadj[v]) {
            vec[u][y] -= c;
            vec[u][x] += c;
        }
        a[v] = x;
        s1 += delta;
        cout << s0 - s1 << "\n";
    }
}

G1. Big Wins! (easy version)

先枚举每个在数组中出现的 $m\le100$ 作为子数组的最小值，然后对所有大于 $m$ 的候选中位数 $M$ 倒序尝试。将数组中每个位置映射为

$$ f(i) = \begin{cases} +1 & \text{if } a_i \ge M \\ -1 & \text{if } a_i \lt M \end{cases} $$

并计算前缀和

$$ \text{pre}[k]=\sum_{i\lt k}f(i). $$

此时任意子数组 $[L..R]$ 满足

$$ \sum_{i=L}^R f(i)=\text{pre}[R+1]-\text{pre}[L]\ge0 $$

当且仅当其中位数 $\ge M$。为了确保子数组最小值正好为 $m$，把所有 $a_i<m$ 当作断点，将原数组分为若干段，每段内元素都 $\ge m$。在每段 $[L..R)$ 内枚举所有满足 $a_p=m$ 的下标 $p$，设基准值 $B=\text{pre}[L]$，并预处理后缀最大值

$$ \text{suf}[k]=\max_{i\in[L+k..R]}\text{pre}[i]. $$

如果存在 $p$ 使得

$$ \text{suf}[p-L+1]-B\ge0, $$

则说明有一个包含 $p$ 的子区间同时满足最小值 $m$、中位数 $\ge M$，称为可行。对每个 $m$ 取对应的最大可行差值 $M-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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> st = a;
    sort(st.begin(), st.end());
    st.erase(unique(st.begin(), st.end()), st.end());
    auto check = [&](int m, int M) -> bool {
        vector<int> pre(n + 1, 0);
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + (a[i] >= M ? 1 : -1);
        }
        for (int l = 0; l < n; l++) {
            while (l < n and a[l] < m)
                l++;
            if (l >= n)
                break;
            int r = l;
            while (r < n and a[r] >= m)
                r++;
            int mp = pre[l];
            vector<int> suf(r - l + 1);
            suf[r - l] = pre[r];
            for (int i = r - 1; i >= l; i--)
                suf[i - l] = max(pre[i], suf[i - l + 1]);
            for (int i = l; i < r; i++) {
                if (a[i] == m) {
                    if (suf[i - l + 1] - mp >= 0)
                        return true;
                }
                mp = min(mp, pre[i + 1]);
            }
            l = r;
        }
        return false;
    };
    int ans = 0;
    for (auto x : st) {
        for (auto it = st.rbegin(); it != st.rend() and *it > x; it++) {
            if (check(x, *it)) {
                ans = max(ans, *it - x);
                break;
            }
        }
    }
    cout << ans << "\n";
}

G2. Big Wins! (hard version)

我觉得代码能说明一切：

  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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

#include <bits/stdc++.h>

struct Kadane {
    int ans;     
    int mxpref;   
    int mxsuff;  
    int sum;     

    Kadane() : ans(0), mxpref(0), mxsuff(0), sum(0) {}
    Kadane(int val) : sum(val) {
        ans = mxpref = mxsuff = std::max(val, 0);
    }

    friend Kadane operator+(const Kadane& a, const Kadane& b) {
        Kadane res;
        res.sum = a.sum + b.sum;
        res.mxpref = std::max(a.mxpref, a.sum + b.mxpref);
        res.mxsuff = std::max(b.mxsuff, a.mxsuff + b.sum);
        res.ans = std::max({a.ans, b.ans, a.mxsuff + b.mxpref});
        return res;
    }
};

namespace Mohao {
template <class S>
struct SegTree {
    int n;
    std::vector<S> tree;

    void pull(int p) {
        tree[p] = tree[2 * p] + tree[2 * p + 1];
    }

    template <class T>
    void build(const std::vector<T> &v, int p, int l, int r) {
        if (l == r) {
            tree[p] = S(v[l]);
            return;
        }
        int mid = l + (r - l) / 2;
        build(v, 2 * p, l, mid);
        build(v, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    S query(int ql, int qr, int p, int l, int r) {
        if (ql > r or qr < l)
            return {};
        if (ql <= l and r <= qr)
            return tree[p];
        int mid = l + (r - l) / 2;
        return query(ql, qr, 2 * p, l, mid) + 
               query(ql, qr, 2 * p + 1, mid + 1, r);
    }

    void update(int pos, const S &val, int p, int l, int r) {
        if (l == r) {
            tree[p] = val;
            return;
        }
        int mid = l + (r - l) / 2;
        if (pos <= mid)
            update(pos, val, 2 * p, l, mid);
        else
            update(pos, val, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    SegTree() : n(0) {}
    SegTree(int _n) : n(_n), tree(4 * n, {}) {}
    template <class T>
    SegTree(const std::vector<T> &v) : n(v.size()) {
        tree.resize(4 * n);
        build(v, 1, 0, n - 1);
    }

    S Query(int l, int r) {
        return query(l, r, 1, 0, n - 1);
    }

    void Update(int p, const S &v) {
        update(p, v, 1, 0, n - 1);
    }
};
} 

void solve() {
    int n, m = 0;
    std::cin >> n;
    std::vector<int> a(n);
    if (n == 0) {
        std::cout << 0 << std::endl;
        return;
    }
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        m = std::max(m, a[i]);
    }

    std::vector<std::vector<int>> ind(m + 2);
    for (int i = 0; i < n; i++) {
        ind[a[i]].push_back(i);
    }

    std::vector<int> l(n), r(n);
    std::stack<int> s;
    for (int i = 0; i < n; i++) {
        while (not s.empty() and a[s.top()] >= a[i]) { s.pop(); }
        l[i] = s.empty() ? 0 : s.top() + 1;
        s.push(i);
    }
    s = std::stack<int>();
    for (int i = n - 1; i >= 0; i--) {
        while (not s.empty() and a[s.top()] >= a[i]) { s.pop(); }
        r[i] = s.empty() ? n - 1 : s.top() - 1;
        s.push(i);
    }

    std::vector<int> tmp(n, 1);
    Mohao::SegTree<Kadane> seg(tmp);
    
    int med = 1;
    int ans = 0;

    if (1 <= m) {
        for (int i : ind[1]) {
            seg.Update(i, Kadane(-1));
        }
    }

    for (int mn = 1; mn <= m; mn++) {
        if (!ind[mn].empty()) {
            for (int u : ind[mn]) {
                int lg = l[u], rg = r[u];
                
                while (med < m && (seg.Query(lg, u - 1).mxsuff + seg.Query(u + 1, rg).mxpref + (a[u] < med ? -1 : 1)) >= 0) {
                    med++; 
                    if (med <= m) {
                        for (int i : ind[med]) {
                            seg.Update(i, Kadane(-1));
                        }
                    }
                }
            }
        }

        ans = std::max(ans, med - mn);
    }
    std::cout << ans << std::endl;
}


signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    std::cin >> T;
    while (T--) 
        solve();        
    return 0;
}
Codeforces
Licensed under CC BY-NC-SA 4.0
最后更新于 Oct 03, 2025 19:23 +0800
© 2024 - 2025 Mohao's Nest
赣ICP备2024042422号
使用 Hugo 构建
主题 Stack 由 Jimmy 设计