「题解」Codeforces Round 993 (Div.4)

Mohao2024/12/16大约 3 分钟

A

给 Cube 一个整数 $n$ 。她想知道有多少对有序的正整数 $(a,b)$ 能使 $a=n-b$ 成对。由于 Cube 不擅长数学，请帮助她！

考虑到数据范围较小（ $2\le n \le 100$ ），暴力枚举即可。

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= 1000; i ++) {
        for (int j = 1; j <= 1000; j ++) {
            if (i + j == n)
                ans ++;
        }
    }
    cout << ans << "\n";

}

以上是为了拼手速尽快 A 题想出来的神秘解法，稍微分析一下就可以知道答案是 $n - 1$ 。

B

一家商店的玻璃橱窗上画着一串只有字符 "p"、"q "和 "w "的字符串。Ship 走过商店，站在玻璃橱窗正前方，观察到字符串 $a$ 。然后，小船走进商店，直视同一玻璃橱窗，观察到字符串 $b$ 。

飞船给出字符串 $a$ 。您的任务是找到并输出 $b$ 。

考虑到镜像的特点，倒序输出的同时把 p 和 q 互换即可。

void solve() {
    string s;
    string t = "";
    cin >> s;
    int ans = 0;
    for (int i = s.length() - 1; i >= 0; i --) {
        if (s[i] == 'p')
            t += 'q';
        if (s[i] == 'q')
            t += 'p';
        if (s[i] == 'w')
            t += s[i];
    }
    cout << t << "\n";

}

C

波尔是纸折大学的老师。他教室里的座位排成 $2$ 行，每行有 $m$ 个座位。

波尔正在给 $a + b + c$ 只猴子上课，他想给尽可能多的猴子分配座位。波尔知道 $a$ 只想坐在第 $1$ 排， $b$ 只想坐在第 $2$ 排， $c$ 没有任何偏好。每个座位只能坐一只猴子，而且每只猴子都必须按照自己的偏好入座。

波尔最多可以让多少只猴子坐下？

小学数学。

void solve() {
    int m, a, b, c;
    cin >> m >> a >> b >> c;
    int ans = 0;
    if (a <= m) {
        ans += a;
    } else {
        ans += m;
    }
    if (b <= m) {
        ans += b;
    } else {
        ans += m;
    }
    if (ans <= 2 * m) {
        if (c) {
            ans = min(2 * m, ans + c);
        }
    }
    cout << ans << "\n";
}

D

给定一个正整数序列，如果一个正整数出现的次数是任何一个正整数出现的最大次数，那么这个正整数就称为序列的模。例如， $[2,2,3]$ 的模是 $2$ 。 $9$ 、 $8$ 或 $7$ 中的任何一个都可视为序列 $[9,9,8,8,7,7]$ 的模。

你给了 UFO 一个长度为 $n$ 的数组 $a$ 。为了感谢你，UFO 决定再构造一个长度为 $n$ 的数组 $b$ ，使得 $a_i$ 是数列 $[b_1, b_2, \ldots, b_i]$ 中所有 $1 \leq i \leq n$ 的模式。

然而，UFO 不知道如何构造数组 $b$ ，所以你必须帮助她。请注意，在所有 $1 \leq i \leq n$ 中，你的数组 $1 \leq b_i \leq n$ 必须成立。

考虑到 $1\le a_i\le n$ 且 $1\le b_i\le n$ ，因此本题可以看作一个排列问题。在此基础上，我们可以发现 $1 \ldots n$ 的排列的众数是其本身（即每个数都只出现一次）。因此我们只需要根据 $a_i$ 调整 $b_i$ 的顺序即可。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> f(n + 1);
    for (int &v : a) {
    vector<int> f(n + 1);
    for (int &v : a) {
        cin >> v;
    }
    vector<int> b(n);
    for (int i = 0; i < n; i ++) {
        if (!f[a[i]]) {
            f[a[i]] ++;
            b[i] = a[i];
        }
    }
    int p = 0;
    for (int i = 0; i < n; i ++) {
        if (b[i] == 0) {
            for (int j = p + 1; j <= n; j ++) {
                if (f[j] == 0) {
                    p = j;
                    break;
                }
            }
            b[i] = p;

        }
        cout << b[i] << " ";
    }
    cout << "\n";
}

E

小波得到五个整数 $k$ ， $l_1$ ， $r_1$ ， $l_2$ 和 $r_2$ 。小波希望你帮她计算出满足以下所有条件的有序数对 $(x, y)$ 的个数：

$l_1 \leq x \leq r_1$ .
$l_2 \leq y \leq r_2$ .
存在一个非负整数 $n$ ，使得 $\frac{y}{x} = k^n$ .

提前计算好 $k^n$ ，约束 $x$ 的范围枚举即可。

void solve() {
    int k, l1, r1, l2, r2;
    cin >> k >> l1 >> r1 >> l2 >> r2;
    int ans = 0;
    vector<int> kn;

    int tmp = 1;
    while (tmp <= r2) {
        kn.push_back(tmp);
        if (tmp > r2 / k) break;
        tmp *= k;
    }

    for (int power : kn) {
        int x_min = max((l2 + power - 1) / power, l1);
        int x_max = min(r2 / power, r1);

        if (x_min <= x_max) {
            ans += (x_max - x_min + 1);
        }
    }
    cout << ans << "\n";
}