「题解」2024 ICPC 上海区域赛

Mohao2025/8/28大约 5 分钟

「题解」2024 ICPC 上海区域赛

感觉再不发文章我就和似了一样

补题链接

唉唉，感觉区域赛好难。

去年的 $\texttt{Louisdlee}$ 太强。

C. Conquer the Multiples

这里就放新生赛的题解了。

题目描述

哈基詹与哈基君正在愉快地进行小游戏，规则如下：

选定一个正整数连续序列 $[l,r]$ 和一个正整数变量 $x\gets l$ 。
两名玩家轮流从序列中删除一个能被 $x$ 整除的数。哈基詹总是先手。每次操作后 $x \gets x + 1$ 。如果某位玩家当前无法删去这样的数，则该玩家输掉游戏。

显然哈基詹和哈基君都是绝顶聪明的，他们都会以最佳策略进行行动，你能判断出这场别样的数字大战的赢家是谁吗？

题解

首先不难想到对于 $x$ 我们在序列中可以删除的数为 $x,2x,3x,\ldots,nx$ ，同时有 $x$ 的初始值为 $l$ ，则当 $r \lt 2l$ 时，我们只能删除 $x$ 本身。这样游戏就变成了轮流取一个数问最后谁没取到的经典问题，有当序列长度为奇数时先手必赢，长度为偶数时先手必败的结论。

然后我们不难发现，若一个人拿到的第一个 $x$ 为偶数，那么此人往后只能选择偶数。而当 $x$ 为奇数时， $2x$ 为偶数，因此若一个人拿到的第一个 $x$ 为奇数，此人在一定条件下也能选择偶数。这样就导致了偶数数量的减少，使得只能选择偶数的那个人少了一个可以选择的数，当 $x \gt \frac{r}{2}$ 时，游戏转变为如上所述的轮流取数的问题，而偶数方因为必然选择的数已经被取走而陷入必败的局面。

因此当 $l$ 为奇数， $r \lt 2l$ 时，区间长度为奇数 Alice 赢，否则 Bob 赢； $r \ge 2l$ 时，则 Alice 一定赢（做法就是开局把 $2l$ 删除）。

当 $l$ 为偶数时，因为 $2l$ 也是偶数，如果开局能把 $2l$ 拿走，则后期必然导致无路可走，因此 Alice 开局只能拿 $l$ ，问题转换为在 Bob 视角下的以奇数开局：则当 $r\lt2(l+1)$ 时，问题取决于区间长度奇偶性（因为二人都无法拿走任何东西）； $r\ge2(l+1)$ 时则 Bob 必赢。

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        if (r < 2 * (l + !(l % 2))) { // 这里合并了 l 奇偶不同的判断，偶数则判断 2*(l+1)
            if ((r - l + 1) % 2) {
                cout << "Alice\n";
            } else {
                cout << "Bob\n";
            }
        } else {
            if (l % 2) {
                cout << "Alice\n";
            } else {
                cout << "Bob\n";
            }
        }
    }
    return 0;
}

I. In Search of the Ultimate Artifact

其实比上一题简单。

给定一个数组，每 $k$ 个元素可以合并成一个元素，其值等于这 $k$ 个元素的乘积，问最后数组中最大值是多少。

解法很显然，排序后从第一个元素开始合并往后 $k-1$ 个元素就行，如果有 $0$ 就特判一下，然后需要注意取模的问题……总而言之需要一些细节。

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

using i64 = long long;
const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<i64> p(n);
        for (int i = 0; i < n; i++) cin >> p[i];

        sort(p.begin(), p.end(), greater<>()); // 降序排列

        i64 cs = p[0] % MOD; // 当前最大值

        for (int i = 1; i + k - 2 < n; i += k - 1) {
            bool hasZero = false;
            i64 tms = 1;
            for (int j = 0; j < k - 1; j++) {
                if (p[i + j] == 0) {
                    hasZero = true;
                    break;
                }
                tms = (tms * (p[i + j] % MOD)) % MOD;
            }
            if (hasZero) break;
            cs = (cs * tms) % MOD;
        }

        cout << cs % MOD << "\n";
    }
    return 0;
}

B. Basic Graph Algorithm

感觉一点也不基础。

给定一个无向图和一个 DFS 顺序，问最少要加几条边才能达成此顺序。

我操，不保证不存在重边。

总而言之直接模拟这个 DFS 过程，如果接下来还有能走的点但不是按顺序的点的话就加边。

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> ans;
    vector adj(n + 1, vector<int>{});
    vector adv(n + 1, set<int>{});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
        adv[u].emplace(v);
        adv[v].emplace(u);
    }
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    int pos = 0;
    auto dfs = [&](this auto dfs, int u) -> void {
        for (auto v : adj[u])
            adv[v].erase(u);
        while (not adv[u].empty() and pos < n) {
            if (adv[u].contains(p[pos])) {
                adv[u].erase(p[pos]);
                dfs(p[pos++]);
            } else {
                ans.emplace_back(u, p[pos]);
                dfs(p[pos++]);
            }
        }
    };
    while (pos < n) {
        dfs(p[pos++]);
    }
    cout << ans.size() << "\n";
    for (auto [u, v] : ans)
        cout << u << " " << v << "\n";
    return 0;
}

D - Decrease and Swap

给定长度为 $n$ 的序列 $a$ ， $a_i$ 为 $0$ 或者 $10^{18}$ 。每次操作可以选一个 $1 \le i \le n-2$ ，然后 $a_i \gets a_i - 1$ ，交换 $a_{i+1}$ 和 $a_{i+2}$ 。问是否能把序列变成全 $0$ 。

首先我们可以明显地感觉出来如果最后两个东西是 $0$ 的话，我们一定可以完成该操作。

然后再手玩一下剩下的情况即可。（~~其实是不想写了~~)

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

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    if (s[n - 1] == s[n - 2] and s[n - 1] == '0') {
        cout << "Yes\n";
        return;
    }
    if (n == 3) {
        cout << "No\n";
        return;
    }
    // 神秘八岐大蛇变换
    // 其实本质上就是在摊大饼
    for (int l = 0, r = 1; l < n - 2; l++) {
        if (s[l] == '0')
            continue;
        r = l + 1;
        int cnt = 1;
        while (r < n - 2 and r - l + 1 <= cnt * 2)
            cnt += s[r++] == '1';
        for (int i = l; i < r; i++)
            s[i] = '0';
        int cost = 0;
        for (int i = l; i < r; i += 2)
            s[i] = '1', cost++;
        for (int i = r - 1; i >= l; i--) {
            if (s[i] == '1')
                continue;
            if (cost == cnt)
                break;
            s[i] = '1';
            cost += 1;
        }
        l = r - 1;
    }
    string ss = "";
    ss += s[n - 3];
    ss += s[n - 4];
    if (ss == "11")
        cout << "Yes\n";
    else if (ss == "00")
        cout << "No\n";
    else if (ss == "01") {
        if (s[n - 2] == '0' and s[n - 1] == '1')
            cout << "No\n";
        else
            cout << "Yes\n";
    } else if (n >= 5 and s[n - 5] == '1')
        cout << "Yes\n";
    else
        cout << "No\n";
}

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