跳至主要內容

「题解」Codeforces Round 1046 (Div. 2)

Mohao2025/9/1大约 6 分钟题解Codeforces

感觉太久没有训了，手速都变慢了……

赛时 A～C，D 交互太久没做憋不出来。赛后补了 D～E。

比赛链接

A. In the Dream

CF Better 的翻译把重要线索吞了……还得我自己看一遍。

给定足球比赛上半场和终局比分，已知同一支球队在同一半场不会连续进三个球，问比分是否合法。

假设极端情况：AABAABAAB...\texttt{AABAABAAB...}，也就是说为了不连续进三个球每连续进两个球另一队就必须进一个球，因此保证两场 max⁡>2×(min⁡+1)\max \gt 2 \times (\min + 1) 即可。

同时还需要注意下半场场的比分是终局比分减去上半场的比分。

void solve() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    c -= a;
    d -= b;
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);

    if (b > 2 * (a + 1) or d > 2 * (c + 1)) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

B. Like the Bitset

给定一个长度为 nn 的二进制字符串 ss 和一个长度为 kk 的整数，要求构造一个排列 pp 使得：当 si=1s_i=1 时，每一个长度至少为 kk 包含 ii 的区间内，pip_i 不是最大值。

首先我们不难看出如果存在连续至少 kk 个 si=1s_i=1 的话，那么不存在这样的排列。

然后考虑我们构造的是排列，没有重复的数字，所以我们可以把每一个 si=1s_i=1 的地方塞上比较小的数字，然后 si=0s_i=0 的地方塞上较大的数字。这样只要保证任意符合 si=0,sj=1s_i=0, s_j=1 的 (i,j)(i,j)，满足 pi>pjp_i \gt p_j 即可。反正不可能存在 kk 个连续的 si=1s_i=1。

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int l = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            l++;
            if (l >= k) {
                cout << "NO\n";
                return;
            }
        } else {
            l = 0;
        }
    }
    cout << "YES\n";
    int cur = n;
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        if (s[i] == '0')
            ans[i] = cur--;
    }
    for (int i = 0; i < n; i++) {
        if (ans[i] == 0)
            ans[i] = cur--;
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
}

C. Against the Difference

怎么 DP 贬值到 1100 了，太恐怖。

定义 block\mathrm{block} 是满足 ∀ai∈a,ai=length⁡(a)\forall a_i \in a, a_i=\operatorname{length}(a) 的数组。给定一个长度为 nn 的数组 aa，最大化全部由 block\mathrm{block} 组成的子序列长度。

首先我们可以知道这个子序列是由若干个 block\mathrm{block} 组成的，因此问题就是选择若干个 block\mathrm{block} 使得其总和长度最大。我们可以从前往后扫一遍数组，记录每一个数值出现的位置。当遍历到第 ii 个元素时，若 aia_i 及之前出现的元素个数为 aia_i，则可以在这里选择这个块。如果选择这个块的话，则当前状态改变为 aia_i 的首位置前一个位置的状态加上 aia_i。若 aia_i 位置的个数大于 aia_i 则更新 aia_i 的首位置为首位置的下一个位置。

详见代码

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector pos(n + 1, queue<int>{});
    vector<int> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        pos[a[i]].emplace(i);
        if (pos[a[i]].size() > a[i])
            pos[a[i]].pop();
        if (pos[a[i]].size() == a[i])
            dp[i] = max(dp[i], dp[pos[a[i]].front() - 1] + a[i]);
    }
    cout << dp[n] << "\n";
}

D. For the Champion

感觉太久没做交互题，不会做了。

交互题。

给定 nn 个点和一个你不知道的初始位置 (x,y)(x, y) 和 1010 次移动操作，每次操作可以选择朝上下左右某一个方向移动 kk 个单位距离（0≤k≤1090 \le k \le 10^9），然后告诉你当前位置距离之前存在的点的最小曼哈顿距离。求初始位置。

我们假设我们能走到一个充分远的地方，使得移动后的坐标 (x′,y′)(x',y') 满足 x′>x0, y′<y0x' \gt x_0,\ y' < y_0，这里的 (x0,y0)(x_0,y_0) 是任意上述点的坐标。

然后有我们的回报 res=x′−x1+y1−y′\mathrm{res}=x'-x_1+y_1-y'，这里 y1−x1y_1-x_1 为点坐标差中的最小值，然后我们让 y′<yy'<y，这样 res′=x′′−x2+y−y2′′\mathrm{res}'=x''-x_2+y-y_2''，这里 x2+y2x_2+y_2 为点坐标和的最大值。然后所有量均已知，我们不难通过求出原始坐标。

using i64 = long long;
i64 ask(char op, i64 k) {
    cout << "? " << op << " " << k << endl;
    i64 res;
    cin >> res;
    if (res == -1)
        exit(0);
    return res;
}

void solve() {
    i64 n;
    cin >> n;
    i64 mn1 = LLONG_MAX;
    i64 mx2 = -LLONG_MAX;
    for (int i = 0; i < n; i++) {
        i64 x, y;
        cin >> x >> y;
        mn1 = min(mn1, y - x);
        mx2 = max(mx2, y + x);
    }
    i64 s = 1e9;
    ask('R', s);
    ask('R', s);
    ask('D', s);
    i64 res = ask('D', s);
    i64 res1 = mn1 - res + 4 * s;
    ask('U', s);
    ask('U', s);
    ask('U', s);
    res = ask('U', s);
    i64 res2 = mx2 + res - 4 * s;
    cout << "! " << (res2 - res1) / 2 << " " << (res2 + res1) / 2 << "\n";
}

E. By the Assignment

Update on 2 Sep.
我能把数据结构和算法课翘了吗

问题：给定一个有 nn 个节点和 mm 条边的无向图和一个正整数 VV，要求对于任意的 (p,q)(p,q)，pp 和 qq 之间的简单路径上节点权值的异或和相等。在给定一个长度为 nn 的数组，其中第 ii 个元素代表第 ii 个节点的权值，如果是 −1-1 的话代表这里的权值是任意的。问有多少种权值方案使得这个玩意合法。

首先不难看出如果我们有一个环，环上的每一个节点的权值是相等的。顺便考虑一下奇偶性，显然如果是奇环的话，两个节点路径长度不相等，所以权值只能是 00，如果是偶环的话，权值可以为任意值。

然后考虑一下多个环叠加的情况，我们不难得出这种性质具有传递性，所以我们发现这玩意就是一个边双连通分量。然后我们用 Tarjan 求一下就可以了，求玩之后用二分图染色判断一下即可。

代码：

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

constexpr int modn = 998'244'353;
constexpr int maxn = 2e5 + 5;
void solve() {
    int n, m, V;
    cin >> n >> m >> V;
    vector<int> a(n + 1), dfn(n + 1), low(n + 1), s(n + 1), p(n + 1);
    int id = 0, tp = 0, cnt = 0;
    vector g(n + 1, vector<int>{});
    vector dcc(n + 1, vector<int>{});
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    // 使用 Tarjan 求解边双连通分量
    // 此时任意亮点都在一个简单环上
    // 如果有奇环的话 => 每个点权重必须相等且为0
    // 否则可以选 V 种
    auto tarjan = [&](this auto tarjan, int u, int f = 0) -> void {
        dfn[u] = low[u] = ++id;
        s[++tp] = u;
        for (int v : g[u]) {
            if (v == f)
                continue;
            if (!dfn[v]) {
                tarjan(v, u);
                low[u] = min(low[u], low[v]);
            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            cnt++;
            int x;
            do {
                x = s[tp--];
                p[x] = cnt;
                dcc[cnt].push_back(x);
            } while (x != u);
        }
    };
    for (int i = 1; i <= n; i++) {
        if (not dfn[i])
            tarjan(i);
    }
    int ans = 1;
    // 处理边双连通分量
    vector<int> col(n + 1, -1);
    auto check = [&](int s) -> bool {
        queue<int> q;
        q.push(s);
        col[s] = 0;
        while (not q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : g[u]) {
                // 显然得要是同一个部分的
                if (p[v] != p[u])
                    continue;
                if (col[v] == -1) {
                    col[v] = col[u] ^ 1;
                    q.push(v);
                } else if (col[v] == col[u]) {
                    return false;
                }
            }
        }
        return true;
    };

    for (int i = 1; i <= cnt; i++) {
        int x = -1;
        bool flag = true;
        for (int u : dcc[i]) {
            if (a[u] == -1)
                continue;
            if (x == -1)
                x = a[u];
            else if (x != a[u]) {
                flag = false;
                break;
            }
        }
        if (not flag) {
            ans = 0;
            break;
        }
        // 在这里检查一下是否是二分图
        if (not check(dcc[i][0])) {
            if (x > 0) {
                ans = 0;
                break;
            }
        } else {
            if (x == -1) {
                ans = 1ll * ans * V % modn;
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
最近更新
赣ICP备2024042422号
Copyright © 2025 Mohao CC BY-NC-SA 4.0 Licensed