Codeforces Round 1004 + 1005 题解

发表于 2025-03-19 更新于 2025-04-09 分类于 Codeforces 阅读次数：本文字数： 9.5k

vp 然后补题都不知道时间怎么过这么快的。

Codeforces Round 1005 (Div. 2) 题解

A

题意

给定一个 01 串 $s$ 和空串 $t$，一次操作可以取一个位置，让这个位置之后的后缀转移给 $t$，求让 $s$ 全部是 0，$t$ 全部是 1 的最少操作次数。

题解

我们贪心地从前往后扫描，遇到 1 就把后缀转移给 $t$ ，此时字符串在 $t$，遇到 0 就把后缀转移给 $s$ 。其实就是遇到不同的情况就转移。

当然，$s$ 的开头不能为 1，需要特判。

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

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        if (s[i] != s[i - 1]) {
            ans++;
        }
    }
    ans += (s[1] == '1');
    cout << ans << "\n";
}

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

B

题意

给定一个数组，它的权值是数组的长度减去不同元素的数量。现在可以选择一个区间（也可以不选），消除区间内的所有元素，使得操作后权值最大且数组最短。

题解

减去一个数能够使得当前权值不变，当且仅当它是唯一存在的元素，否则权值一定会减少。那么我们找到最长的连续区间满足这个区间内的元素都是唯一的即可。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    int mxlen = 0;
    int ansl = 0;
    for (int i = 1; i <= n; i++) {
        if (mp[a[i]] == 1) {
            int len = 1;
            while (i + len <= n && mp[a[i + len]] == 1) {
                len++;
            }
            if (len > mxlen) {
                mxlen = len;
                ansl = i;
            }
            i = i + len - 1;
        }
    }
    if (ansl == 0) {
        cout << 0 << "\n";
    } else {
        cout << ansl << " " << ansl + mxlen - 1 << "\n";
    }
}

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

C

题意

给定一个数组，不断进行一下操作直到数组变为空：选择一个数，如果它是正数，那么将数组只保留下这个元素下一个位置的后缀，如果是负数就保留前一个元素结尾的前缀。每次操作都会加上选择的数绝对值大小的积分。求积分最大。

题解

显然对于最前面的数，我们尽可能删去正数，这样相当于只删去了一个数，而最后面的数，我们尽可能删去负数。那么我们维护前缀的正数和，后缀的负数绝对值之和，然后枚举位置 $i$，$i $ 之前的位置删去正数，$i$ 之后删去负数，求最大值即可。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> pre(n + 1), suf(n + 2);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + (a[i] > 0 ? a[i] : 0);
    }
    for (int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] + (a[i] < 0 ? -a[i] : 0);
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, pre[i] + suf[i + 1]);
    }
    cout << ans << "\n";
}

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

D

题意

给定一个数组 $w_i$ 和 $q$ 次询问，每次询问给定一个数 $x$ （每次询问独立），它会从数组的末尾开始，将自身变为 $x\oplus w_i$，直到 $x < w_i$ 或操作完所有数。回答每次询问的操作次数。

题解

遇到异或等问题一定要按位考虑，容易发现 $x, w_i$ 的最高位即 $\log_2(x), \log_2(w_i)$ 的比较分为三种情况：

$\log_2(x) > \log_2(w_i)$，该次操作一定成功，且不会改变 $\log_2(x)$。
$\log_2(x)= \log_2(w_i)$，需要判断 $x$ 与 $w_i$ 的大小，且操作成功后 $x$ 的最高位会变为 0 。
$\log_2(x) < \log_2(w_i)$，操作一定失败，这次询问的过程结束。

那么我们可以设 $f_{i,j}$ 表示区间 $[1, i]$ 的二进制第 $j$ 位离位置 $i$ 最近的位置，那么对于 $0\le j\le log_2(w_i)$，应该有 $f_{i,j} = i$，否则 $f_{i,j} = f_{i-1, j}$，这样在从右到左到转移过程中，我们可以快速找到 $\log_2(x)= \log_2(w_i)$ 的情况来比较，同时用前缀/后缀异或来快速求区间异或。由于每次进行第二种情况 $x$ 会变小，时间复杂度为 $O((n+q)\log x)$

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

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> w(n + 1), pre(n + 1), suf(n + 2);
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        pre[i] = pre[i - 1] ^ w[i];
    }
    for (int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] ^ w[i];
    }
    vector<array<int, 31>> f(n + 1);
    for (int i = 1; i <= n; i++) {
        int x = log2(w[i]);
        for (int j = 0; j <= x; j++) {
            f[i][j] = i;
        }
        for (int j = 30; j > x; j--) {
            f[i][j] = f[i - 1][j];
        }
    }
    while (q--) {
        int x;
        cin >> x;
        int p = n, b = log2(x);
        for (int j = b; j >= 0; j--) {
            if (x < (1ll << j)) {
                continue;
            }
            int nxt = f[p][j];
            x ^= suf[nxt + 1] ^ suf[p + 1];
            p = nxt;
            if (p == 0 || w[p] > x) {
                break;
            }
            x ^= w[p];
            p--;
        }
        cout << n - p << " \n"[q == 0];
    }
}

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

Codeforces Round 1004 (Div. 2) 题解

A

题意

给定两个数 $x, y$，函数 $S(n)$ 代表把 $n$ 十进制下个个数的位数加起来的值，判断是否存在一个数 $n$ 满足 $S(n) = x, S(n+1) = y$。

题解

一个数加 1，如果不进位的话需要 $y = x + 1$，如果产生进位，每进一位，总的位数和就会减少 9，所以应该有 $x + 1 - 9k = y$，即$(x+1)\pmod 9\equiv y\pmod9$，但是注意需要满足 $x \ge y$。

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

void solve() {
    int x, y;
    cin >> x >> y;
    if (x + 1 >= y && (x + 1) % 9 == y % 9) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

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

B

题意

给定两个包 A，B 和一个数组，初始时所有数都放在包 A 中，可以进行下面两种操作：

把一个数从 A 包拿到 B 包。
如果两个包都有相同的数，可以把 A 包的数加 1。

判断能否通过多次操作让两个包的数字相同。

题解

我们只能把一个数变大而不能变少，所以我们从小到大遍历的过程中，如果一个数只有一个，那么一定是不可能相同，否则我们可以让多出两个的数向上加，继续遍历。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 2);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (b[i] == 1) {
            cout << "No\n";
            return;
        }
        if (b[i] >= 2) {
            b[i] -= 2;
            b[i + 1] += b[i];
        }
    }
    cout << "Yes\n";
}

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

C

题意

给定一个数 $n$，你可以把这个数多次加上某类数，这个数要求必须是十进制下各位都是 9，求最少加的次数，使得十进制下这个数某一位含有“7”。

题解

首先对于 $n$ 加上的数一定是形如 $10^x - 1$，也就是个位先减去 1，然后把高位的某一位加上 1。不难看出，每次都加上同一个数是最优的（分配到不同高位是没有必要的，找一位离 7 最近的数加上即可）。我们也不需要考虑进位的情况，因为先把一位变成 0 之后加 7 次变成 7，还不如加一个很大的数，使得某一位从 0 直接到 7，因此答案的上界就是 7。我们通过枚举加的次数，寻找是否存在最优解即可，否则，7就是答案。（注意to_string()这个函数很好用，直接把整数转为十进制）

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

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i <= 6; i++) {
        string s = to_string(n - i);
        int sz = s.size();
        s = " " + s;
        for (int j = 1; j <= sz; j++) {
            if (s[j] <= '7') {
                if (s[j] + i >= '7') {// 注意这里是大于等于，因为减去 x 可能牵扯到其他位的退位，不一定是线性减少
                    cout << i << "\n";
                    return;
                }
            }
        }
    }
    cout << 7 << "\n";
}

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

D

题意

交互题。

有两个数组 $x,y$，只提供给你一个数组 $x$ （$1\le x_i\le n$），保证其中元素互不相同。程序有两种想法，只会想其中一种：

建一张有向图，从 $x_i$ 向 $y_i$ 连边
在平面坐标系下绘制点对 $(x_i,y_i)$

你需要通过至多两次询问判断程序在想哪一种。

每次询问，你需要提供两个下标 $i,j$，如果是第一种的话，程序会回答从 $i$ 到 $j$ 的最短路（注意不是 $x_i,y_j$ ），若不存在回答 0 ；如果是第二种的话，程序会回答$(x_i,y_i)$ 与 $(x_j,y_j)$ 的曼哈顿距离（$|x_i-x_j|+|y_i-y_j|$）。

题解

注意数组 $x$ 的各元素互不相同，所以回答的曼哈顿距离一定不是 0 ，那么我们可以往这个方面思考：如果程序回答 0 就可以判断了。

首先，如果 $x$ 中有没有覆盖到 $1$~$n$ 的元素，那么直接询问它即可，如果是第一种想法一定会回答 0 ，因为没有这个数有关的边。

否则，我们可以选择两个最远的数对应的下标，即 1 和 $n$ 分别对应的下标，如果是第二种想法，回答至少为 $n - 1$，否则是第一种想法。同时由于边数只有 $n$ 条，所以第一种想法的答案最大就是 $n - 1$。因此如果回答小于 $n - 1$ 的话，应该是第一种，大于 $n-1$ 的话应该是第二种，如果等于 $n-1$ 的话，我们只需要问反着问一次，由于是有向图，两次答案不同就是第一种，否则是第二种。

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

void solve() {
    auto query = [&](int i, int j) {
        cout << "? " << i << " " << j << endl;
        int d;
        cin >> d;
        return d;
    };
    int n;
    cin >> n;
    vector<int> x(n + 1);
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        mp[x[i]] = i;
    }
    if (mp.size() < n) {
        int empty = 0;
        for (int i = 1; i <= n; i++) {
            if (!mp[i]) {
                empty = i;
                break;
            }
        }
        int x = 1;
        while (x == empty) {
            x++;
        }
        int d = query(empty, x);
        if (d == 0) {
            cout << "! A" << endl;
        } else {
            cout << "! B" << endl;
        }
        return;
    }
    int d1 = query(mp[1], mp[n]);
    int d2 = query(mp[n], mp[1]);
    int d = max(d1, d2);
    if (d > n - 1) {
        cout << "! B" << endl;
    } else if (d < n - 1) {
        cout << "! A\n" << endl;
    } else {
        if (d1 != d2) {
            cout << "! A" << endl;
        } else {
            cout << "! B" << endl;
        }
    }
}

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

E

题意

给定一个数组，求它的一个最长子数组 $a$，满足对所有 $1\le i\le |a|$，有 $\min(a_1,...a_i)\ge \text{mex}(a_{i+1},...,a_{|a|})$。

题解

一个求 mex 的方式为：首先把集合中装入值域中所有元素，那么这个集合就代表不存在的元素了，然后依次把元素加入集合，加入钱判断一个数是否在集合内，在的话就清除这个元素。这样过后，集合的最小元素就是 mex 了。

通过观察可以注意到，一旦数组中没有 0，那么条件一定成立。如果有 0 的话，0最多有一个，否则就不成立（取最前面的 0，前面的 min 是 0，而后面的 mex 大于或等于 1）。那么我们肯定是贪心地取最前面的 0，因为这样的话它后面不是 0 的元素全部都可以取，然后贪心地判断前面的数能否加入答案即可。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] > n + 1) {
            a[i] = n + 1;
        }
        cin >> a[i];
    }
    set<int> st;
    for (int i = 1; i <= n + 1; i++) {
        st.insert(i);
    }
    int id = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) {
            id = i;
            break;
        }
    }
    if (id == 0) {
        cout << n << "\n";
        return;
    }
    int res = 0;
    for (int i = id + 1; i <= n; i++) {
        if (a[i] == 0) {
            continue;
        }
        res++;
        if (st.find(a[i]) != st.end()) {
            st.erase(a[i]);
        }
    }
    int ans = res + id - 1;
    res++;
    int mex = *st.begin();
    for (int i = id - 1; i >= 1; i--) {
        if (a[i] >= mex) {
            res++;
            if (st.find(a[i]) != st.end()) {
                st.erase(a[i]);
            }
            mex = *st.begin();
        }
    }
    cout << max(ans, res) << "\n";
}

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