官方题解｜巅峰赛#18

アイドル

2025-03-02 22:11:31

发布于：浙江

584阅读

13回复

14点赞

ACGO 巅峰赛#18 题解

本场巅峰赛的所有题目的难度评级为：

题目编号	题目标题	难度
A.	数组中未出现的 K 的最小倍数	入门
B.	美丽数 III	普及-
C.	元素距离积（简单）	入门
D.	元素距离积（困难）	普及
E.	最小化两数组的距离	普及+/提高
F.	统计操作后不同的序列	提高+/省选-

本场比赛题目侧重对于选手数学能力的考察，其中：
$\tt{D}$ 题和 $\tt{E}$ 题考察了拆解「绝对值」和根据数据范围变换代数式求解的方法。
$\tt{F}$ 题考察了对于「平均数」的处理技巧和方法。

以上方法皆为算法竞赛中常见的数学处理方法。

题目解析

A - 数组中未出现的 K 的最小倍数

模拟；枚举

我们可以直接从小到大枚举 $K$ 的倍数 $X$ ，并检检查数组中是否存在 $X$ 即可；
由于 $K(\le 9)$ 和 $A_i(\le 100)$ 的值域都比较小，所以 $X$ 最多不会超过 $108$ 。

#include <bits/stdc++.h>

constexpr int N = 100;

int main() {
    int n, k;
    std::cin >> n >> k;
    int a[N];
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    for (int x = 0; x <= N + k; x += k) {
        bool flag = true;
        for (int i = 0; i < n; ++i)
            if (x == a[i]) flag = false;
        if (flag == true) {
            std::cout << x << "\n";
            break;
        }
    }
    return 0;
}

B - 美丽数 III

数学；枚举

令 $K$ 为「美丽数」的位数，不难发现 $K \ge 2$ ，同时 $K = 2$ 的「美丽数」有 $36$ 个， $K = 3$ 的「美丽数」也有 $36$ 个……
「美丽数」每增长 $1$ 位，就会多出 $36$ 个「美丽数」，所以要想知道第 $N$ 个「美丽数」，我们就可以先计算出其位数 $K$ ，再枚举 $a$ 和 $b$ 即可。

#include <bits/stdc++.h>

int main() {
    int n; std::cin >> n;
    int m = (n - 1) / 36 + 1, k = (n - 1) % 36;
    for (int a = 1; a <= 9; ++a)
        for (int b = a + 1; b <= 9; ++b) {
            if (k == 0)  {
                std::cout << a;
                for (int i = 0; i < m; ++i)
                    std::cout << b;
                return 0;
            }
            k -= 1;
        }
    return 0;
}

C - 元素距离积（简单）

模拟；枚举

按照题意，使用双重循环枚举 $i$ 和 $j$ 计算答案；计算绝对值可以使用内置函数 abs。整个代码时间复杂度为 $\mathrm{O}(N^2)$ 。

#include <bits/stdc++.h>

int main() {
    int n; std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    int res = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            res += std::abs(j - i) * std::abs(a[i] - a[j]);
    std::cout << res << "\n";
    return 0;
}

D - 元素距离积（困难）

数学；枚举；计数

我们先处理题目式子中的绝对值。

由于 $\sum_{i=1}^N \vert i - i \vert \times \vert A_i - A_i \vert = 0$ ，所以原式可化为：

$\left( \sum_{i=1}^{N-1}\sum_{j=i+1}^N (j - i) \times \vert A_i - A_j \vert \right) \times 2$

注意到，本题 $A_i(\le 500)$ 的范围较小，我们可以围绕此，对上式进行变换，从而高速计算。

对于上式，我们考虑枚举 $i$ ，同时

令 $cnt_x$ 代表 $i$ 之前所有元素中值 $x$ 出现的次数；
令 $sum_x$ 代表 $i$ 之前所有元素中值为 $x$ 的下标之和；

那么可以将上式转化为：

$\left( \sum_{i = 1}^{N} \sum_{x=0}^{500} (i \times cnt_x - sum_x) \times \vert A_i - x \vert \right) \times 2$

计算上式的时间复杂度为 $\mathrm{O}(N \times \max(A))$ ，这样我们便可以高效地计算出答案。

#include <bits/stdc++.h>

using i64 = long long;

constexpr int M = 500;

int main() {
    int n; std::cin >> n;
    i64 res = 0;
    std::vector<i64> cnt(M + 1), sum(M + 1);
    for (int i = 1; i <= n; ++i) {
        int x; std::cin >> x;
        for (int y = 1; y <= M; ++y)
            res += (i * cnt[y] - sum[y]) * std::abs(x - y);
        cnt[x] += 1;
        sum[x] += i;
    }
    std::cout << res * 2 << "\n";
    return 0;
}

E - 最小化两数组的距离

数学；枚举；二分

对于只交换 $1$ 对二元组的情况，我们直接枚举 $A$ 中要交换的二元组和 $B$ 中要交换的二元组即可，时间复杂度 $\mathrm{O}(N^2)$ 。

我们主要考虑交换 $2$ 对二元组的情况。

首先考虑 $\tt{S}$ ，在未交换交换元素时，令：

$\tt{diffS = \sum_i^NAx_i - \sum_i^NBx_i}$

此时若交换的 $1$ 对二元组分别为 $A_i$ 和 $B_j$ ，那么：

$\tt{S = \vert diffS - 2 \times (Ax_i - Bx_j) \vert}$

对于交换 $2$ 对二元组的情况，我们只需要将 $A$ 中的元素两两结合， $B$ 中的元素两两结合，就可以把选择 $2$ 对二元组交换转化为选择 $1$ 对两两结合后的二元组交换。

那么对于上式，我们可以枚举 $\tt{Ax_i}$ ，二分 $\tt{Bx_j}$ 。

具体的，我们把 $B$ 的两两结合的 $\tt{Bx_j}$ 排序去重，然后找到最大的 $\tt{Bx_j}$ 使得 $\tt{diffS - 2 \times (Ax_i - Bx_j) \lt 0}$ ，此时 $\tt{Bx_j}$ 和 $\tt{Bx_{j + 1}}$ 即为与 $\tt{Ax_i}$ 交换后能够使得 $\tt{S}$ 最小的两个元素，其中 $\tt{Bx_j}$ 或 $\tt{Bx_{j + 1}}$ 可能有一个不存在，要注意判别。

对于 $\tt{T}$ 同理。

整个算法时间复杂度 $\mathrm{O}(N^2\log{N^2})$ 。

#include <bits/stdc++.h>

using pair = std::pair<int, int>;

constexpr int N = 1000;

int main() {
    int n; std::cin >> n;
    std::vector<int> x1(n), y1(n), x2(n), y2(n);
    for (int i = 0; i < n; ++i)
        std::cin >> x1[i] >> y1[i];
    for (int i = 0; i < n; ++i)
        std::cin >> x2[i] >> y2[i];
	int diffS = 0, diffT = 0;
    for (int i = 0; i < n; ++i) {
        diffS += x1[i] - x2[i];
        diffT += y1[i] - y2[i];
    }
    int s = std::abs(diffS), t = std::abs(diffT);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            int ns = std::abs(diffS - 2 * (x1[i] - x2[j]));
            int nt = std::abs(diffT - 2 * (y1[i] - y2[j]));
            std::tie(s, t) = std::min(pair{s, t}, pair{ns, nt});
        }
    std::vector<int> stX, stY[N + 1];
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {
            int x = x2[i] + x2[j], y = y2[i] + y2[j];
            stX.push_back(x);
            stY[x].push_back(y);
        }
    std::sort(stX.begin(), stX.end());
    stX.erase(std::unique(stX.begin(), stX.end()), stX.end());
    for (auto &a : stY) {
        std::sort(a.begin(), a.end());
        a.erase(std::unique(a.begin(), a.end()), a.end());
    }
    auto nearest = [&](std::vector<int> &a, int t) {
        int p = -1;
        for (int i = 1 << 10; i > 0; i >>= 1)
            if (p + i < a.size() and t + a[p + i] * 2 < 0) p += i;
        std::vector<int> res;
        if (p >= 0) res.push_back(a[p]);
        if (p + 1 < a.size()) res.push_back(a[p + 1]);
        return res;
    };
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {
            int sx1 = x1[i] + x1[j], sy1 = y1[i] + y1[j];
            for (auto &sx2 : nearest(stX, diffS - 2 * sx1))
                for (auto &sy2 : nearest(stY[sx2], diffT - 2 * sy1)) {
                    int ns = std::abs(diffS - 2 * (sx1 - sx2));
                    int nt = std::abs(diffT - 2 * (sy1 - sy2));
                    std::tie(s, t) = std::min(pair{s, t}, pair{ns, nt});     
                }
        }
    std::cout << s << ' ' << t << '\n';
    return 0;
}

F - 统计操作后不同的序列

数学；前缀和；枚举；计数

每次操作后都可以得到一个序列， $(L, R)$ 二元组的总数量是 $\dfrac{N(N + 1)}{2}$ 。

我们考虑将其中操作后得到的重复序列去除掉。

令 $X = \dfrac{\sum_{i=L}^R A_i}{R - L + 1}$ ，那么对于 $A_L = X$ 或 $A_R = X$ 的情况，我们将 $L$ 向右边移动 $1$ 或将 $R$ 向左移动 $1$ ，操作后的序列不会发生变化。

我们考虑找到那些使得 $(A_L, \ldots, A_R)$ 的平均值与 $A_L$ 或 $A_R$ 相等的 $(L, R)$ 将其从总数中去掉。

具体地，对于 $x = 1, \ldots, \max{A}$ ，进行如下操作：
定义 $(B_1, \ldots, B_N) = (A_1 - x, \ldots, A_N - x)$ 并构造 $B$ 的前缀和序列 $(S_0 = 0, S_1 = B_1, \ldots, S_N = \sum_{i=1}^N B_i)$ 。

对于 $i = 1, \ldots, N$ ：

若 $B_i = 0$ ，则从答案中减去满足 $0 \le j < i$ 且 $S_j = S_i$ 的 $j$ 的个数。
对应平均值为 $x$ 、右端为 $x$ 而左端任意的情况。
若 $B_i \ne 0$ ，则从答案中减去满足 $0 \le j < i$ 且 $B_{j+1} = 0$ 且 $S_j = S_i$ 的 $j$ 的个数。
对应于平均值为 $x$ 、右端不为 $x$ 而左端为 $x$ 的情况。

对于每个 $x$ 的计算时间复杂度为 $\mathrm{O}(N)$ 。

因此，整体的时间复杂度为 $\mathrm{O}(N\max{A})$ 。

#include <bits/stdc++.h>

using i64 = long long;

constexpr int M = 30;

int main() {
    int n; std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    i64 res = n * (n + 1LL) / 2; 
    for (int x = 1; x <= M; ++x) {
        std::vector<int> b(n + 1), s(n + 1);
        for (int i = 1; i <= n; ++i)
            b[i] = a[i] - x;
        std::partial_sum(b.begin(), b.end(), s.begin());
        const int DELTA = n * M;
        auto f = [&](int v) {return DELTA + v;};
        std::vector<int> zero(DELTA * 2 + 1);
        std::vector<int> nzero(DELTA * 2 + 1);
        for (int i = 1; i <= n; ++i)
            if (b[i] == 0) {
                zero[f(s[i - 1])] += 1;
                res -= zero[f(s[i])] + nzero[f(s[i])];
            }
            else {
                nzero[f(s[i - 1])] += 1;
                res -= zero[f(s[i])];
            }
    }
    std::cout << res + 1 << "\n";
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 10

李总
顶

2025-02-27 来自四川
1
༺ཌༀ我不会身法ༀད༻
666,70多名都能加分.,

2025-03-06 来自北京
0
张子渝
@像素君T4和T5看不了一点

2025-03-02 来自北京
0
‌
有人吗？什么时候发呀

2025-03-02 来自北京
0
- ‮队团加不）童帅_者仇复
  回复‌
  在发了
  
  2025-03-02 来自广东
  0
- ‌
  回复‌
  出题老师
  
  2025-03-02 来自北京
  0
hopebetter
非常好的题，让我的代码旋转

2025-03-01 来自浙江
0
A MC Lover
我就蹭个排位分

2025-02-27 来自浙江
0
- wlx不存在了
  回复A MC Lover
  +1
  
  2025-02-28 来自北京
  0
咕咕咕
₆

2025-02-27 来自江西
0
༺ཌༀ我不会身法ༀད༻
666，牢师，你这也太懒了。

2025-02-27 来自北京
0
‮队团加不）童帅_者仇复
qp

2025-02-27 来自广东
0
wlx不存在了
@アイドル

2025-02-27 来自北京
0