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

周四偶遇 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\leftarrow i+1$，否则答案加一并且 $i\leftarrow 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\leftarrow real_i$，每个操作最多只能使用一次，给出初始的 $x$，问 $x$ 的最大值。

直接贪心即可。

首先我们选择一个操作当且仅当 $x\in[l_i,r_i],real_i>x$，然后我们期望 $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,…,a_i),s_i=\gcd(a_i,…,a_n)$，因此有 $p_i|a_i,s_i|a_i$，为了使这个条件成立，我们可以令 $a_i\leftarrow\text{lcm}(p_i,s_i)$。在此时，对于 $\forall j<i$，有 $p_j|a_j$，同时必然有 $p_j\ge p_i$，因此 $p_i|p_j|a_j$，则：

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

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

同理可得 $\gcd(a_i,…,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!

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

悲报：成功在 System Testing 中 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 < 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)

不会喵～在补喵～