巅峰赛#18 官方题解分析

‌

2025-03-03 02:08:03

发布于：北京

104阅读

0回复

0点赞

巅峰赛#18官方题解链接 👉戳

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

整体思路：旨在找到给定数组中未出现的K的最小倍数。采用模拟和枚举的策略，从小到大依次检查K的倍数是否在数组中存在，一旦找到不存在的倍数，即为所求。
操作方法：在代码中，首先读取数组长度n和倍数K。接着，通过循环读入数组元素。然后，外层循环以步长K枚举K的倍数x（从0开始，最大到N + K），内层循环遍历数组，检查x是否在数组中。若x不在数组中，则输出x并结束程序。

#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;
}

复杂度分析：时间复杂度为 $O(n \times k)$ ，其中n是数组的长度，k是K的取值范围（本题中K <= 9）。因为对于每个可能的倍数x，都需要遍历数组进行检查。空间复杂度为 $O(1)$ ，仅使用了固定数量的额外变量，不随输入规模增长。
综合评价：该方法思路直观、简单易懂，非常适合初学者理解枚举算法的基本应用。但由于采用了双重循环，在处理大规模数组或较大K值时效率较低。不过，鉴于本题数据范围较小（K <= 9且 $A_i$ <= 100 ），这种方法能快速准确地得出结果。

B - 美丽数III

整体思路：通过研究美丽数的规律，根据其位数与数量的关系，计算出目标美丽数的位数，进而枚举具体数字来确定第N个美丽数。
操作方法：读入目标美丽数的序号n后，计算其位数m和在该位数下的偏移量k。利用两层循环枚举数字a（从1到9）和b（从a + 1到9），当偏移量k为0时，输出由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;
}

复杂度分析：时间复杂度为 $O(1)$ ，虽然存在两层循环，但循环次数是固定的，不依赖于输入规模。空间复杂度为 $O(1)$ ，仅使用了几个简单变量，不随数据规模变化。
综合评价：该算法巧妙地利用了美丽数的规律，极大地减少了计算量。通过预先计算位数和偏移量，直接定位到目标美丽数的组成数字，效率很高。这种方法对于解决有明显规律的数字问题非常有效，但局限性在于仅适用于此类特殊规律的场景。

C - 元素距离积（简单）

整体思路：按照题目定义，计算数组中所有元素对之间的距离积并求和。采用双重循环枚举所有元素对的方式实现。
操作方法：读取数组长度n后，读入数组元素。使用两层嵌套循环，外层循环控制第一个元素的下标i，内层循环控制第二个元素的下标j。对于每一对元素，计算它们的下标差的绝对值与元素值差的绝对值的乘积，并累加到结果变量res中。

#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;
}

复杂度分析：时间复杂度为 $O(N^2)$ ，由于存在两层嵌套循环遍历数组，每个元素都要与其他所有元素进行计算。空间复杂度为 $O(N)$ ，主要用于存储输入的数组，若不考虑输入数组，仅算法本身使用的额外空间为 $O(1)$ 。
综合评价：算法实现简单直接，易于理解和编写。但 $O(N^2)$ 的时间复杂度使得它在处理大规模数据时效率较低，计算量会随着数据规模的增大而急剧增加。适用于小规模数据的计算场景。

D - 元素距离积（困难）

整体思路：先对题目中的绝对值式子进行化简，再根据数据范围较小的特点，通过枚举和计数的方式优化计算过程，从而高效地计算元素距离积。
操作方法：将原式化简后，通过枚举i，在每次循环中更新 $cnt_x$ （记录i之前元素中值x出现的次数）和 $sum_x$ （记录i之前元素中值为x的下标之和）。利用这两个数组，计算当前元素与之前所有元素的距离积并累加。

#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;
}

复杂度分析：时间复杂度为 $O(N \times \max(A))$ ，其中N是数组长度， $\max(A)$ 是数组中元素的最大值（本题中 $\max(A)$ <= 500）。相比简单版本的 $O(N^2)$ 有显著优化，因为减少了不必要的重复计算。空间复杂度为 $O(\max(A))$ ，用于存储 $cnt_x$ 和 $sum_x$ 数组。
综合评价：通过对数学式子的优化和利用数据范围进行预处理，该算法在效率上有很大提升。适用于处理中等规模数据且对时间复杂度有较高要求的场景。但它依赖于数据范围较小这一条件，如果数据范围过大，空间复杂度会成为问题，且算法的适用性会降低。

E - 最小化两数组的距离

整体思路：分别处理交换1对和2对二元组的情况，通过枚举和二分查找的方法，找到交换后能使两数组距离最小的组合。
操作方法：先计算未交换时两数组差值的和 $diffS$ 和 $diffT$ 。对于交换1对二元组，直接枚举A和B数组中的所有元素对，计算交换后的距离并更新最小值。对于交换2对二元组，将A和B数组中的元素两两结合，对B数组结合后的结果排序去重。然后枚举A中结合后的元素，通过二分查找在B中找到合适的元素，使得交换后两数组距离最小。

#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() && 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;
}

复杂度分析：交换1对二元组时时间复杂度为 $O(N^2)$ ，交换2对二元组时，排序的时间复杂度为 $O(N^2 \log N)$ ，二分查找的时间复杂度为 $O(N^2 \log N)$ ，整体时间复杂度为 $O(N^2\log{N^2})$ 。空间复杂度为 $O(N^2)$ ，用于存储结合后的数组stX和stY。
综合评价：算法针对不同交换情况分别进行处理，通过将交换2对二元组转化为交换1对二元组的问题，并结合二分查找优化，在一定程度上提高了效率。但整体复杂度仍然较高，在大规模数据下，时间和空间消耗较大。不过对于中等规模数据，且对精度要求较高（需要考虑多种交换情况）时，该算法能准确找到最小距离。

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

~~T6基本全是TLE，MLE好改，我是用剪枝，时间复杂度和空间复杂度都比O(N^2)小一点，剪枝策略遇到这题根本没用。~~

1. 整体思路

本题的目标是统计对给定序列进行特定操作（将区间内元素替换为该区间元素的平均值）后得到不同序列的数量。官方解法的核心思路是先算出所有可能的操作组合（即区间组合）数量，然后通过分析找出其中会产生重复序列的操作情况，从总数量中减去这些重复的情况，从而得到不同序列的实际数量。

2. 操作组合数量

“每次操作后都可以得到一个序列，(L, R) 二元组的总数量是 $\frac{N(N + 1)}{2}$ ”。这里 (L, R) 代表操作的区间，N 是序列的长度。从 N 个元素中选取区间 [L, R]（ $1 \leq L \leq R \leq N$ ）的组合数，根据组合数学的知识，就是 $\frac{N(N + 1)}{2}$ 种，这是所有可能操作的总数。

3. 重复序列的判断

“令 $X = \frac{\sum_{i = L}^{R} A_{i}}{R - L + 1}$ ，那么对于 $A_{L} = X$ 或 $A_{R} = X$ 的情况，我们将 L 向右边移动 1 或将 R 向左移动 1，操作后的序列不会发生变化”。意思是当区间 [L, R] 的平均值等于区间左端点 $A_{L}$ 或者右端点 $A_{R}$ 时，对区间进行微调（左端点右移 1 位或右端点左移 1 位），得到的新序列和原来操作后的序列是一样的，也就是产生了重复。所以要找出这些会产生重复的区间组合，从总数量中减去。

4. 具体操作步骤

“具体地，对于 $x = 1, ..., \max A$ ，进行如下操作：定义 $(B_{1}, ..., B_{N}) = (A_{1} - x, ..., A_{N} - x)$ 并构造 B 的前缀和序列 $(S_{0} = 0, S_{1} = B_{1}, ..., S_{N} = \sum_{i = 1}^{N} B_{i})$ ”。这里是通过枚举可能的平均值 $x$ （范围是从 1 到序列中的最大值 $\max A$ ），将原序列 $A$ 的每个元素都减去 $x$ 得到新序列 $B$ ，并计算 $B$ 的前缀和序列 $S$ 。这样做的目的是为了后续方便判断重复情况。
“对于 $i = 1, ..., N$ $i = 1, ..., N$ ：
- 若 $B_{i} = 0$ ，则从答案中减去满足 $0 \leq j < i$ 且 $S_{j} = S_{i}$ 的 $j$ 的个数。对应平均值为 $x$ 、右端为 $x$ 而左端任意的情况”。当 $B_{i} = 0$ 时，意味着原序列中 $A_{i} = x$ （因为 $B_{i} = A_{i} - x$ ），此时通过查找前缀和相等的位置 $j$ 来确定重复的区间，这些重复区间对应的是右端点值等于平均值 $x$ 的情况。
- 若 $B_{i} \neq 0$ ，则从答案中减去满足 $0 \leq j < i$ 且 $B_{j + 1} = 0$ 且 $S_{j} = S_{i}$ 的 $j$ 的个数。对应于平均值为 $x$ 、右端不为 $x$ 而左端为 $x$ 的情况”。当 $B_{i} \neq 0$ 时，查找满足特定条件（ $B_{j + 1} = 0$ 且 $S_{j} = S_{i}$ ）的 $j$ ，来确定重复的区间，这些重复区间对应的是左端点值等于平均值 $x$ 的情况。

5. 时间复杂度

“对于每个 $x$ 的计算时间复杂度为 $O(N)$ ”。因为在处理每个可能的平均值 $x$ 时，对序列的遍历操作（如判断 $B_{i}$ 是否为 0 等）都是线性的，所以是 $O(N)$ 。
“因此，整体的时间复杂度为 $O(N \max A)$ ”。由于要对从 1 到 $\max A$ 这么多个可能的平均值 $x$ 进行上述操作，所以整体时间复杂度就是 $O(N \max A)$ 。

整体难点分析：

ACGO巅峰赛#18包含六道题目，涵盖不同难度和算法知识点，每道题目的难点各有不同，具体如下：

A - 数组中未出现的K的最小倍数
- 难点：数据范围的把握。虽然题目整体思路简单，但需要根据给定的K（≤9）和数组元素Aᵢ（≤100）的范围，确定枚举K的倍数的合理边界，以避免无效枚举。若不能准确判断这个边界，可能会导致不必要的循环，增加时间复杂度，甚至在处理大规模数据时出现超时问题。
B - 美丽数III
- 难点：寻找美丽数的规律。需要发现美丽数的位数与数量之间的关系，即K每增加1位，美丽数增加36个。理解并运用这个规律来计算目标美丽数的位数和具体数字组合是解题关键。如果无法找出该规律，可能会采用暴力枚举的方法，大大增加计算量和时间复杂度。
C - 元素距离积（简单）
- 难点：在于理解题意并正确实现计算逻辑。要准确使用双重循环枚举所有元素对，并正确计算元素间的距离积，对初学者来说，正确实现嵌套循环以及计算过程中的绝对值处理可能存在一定挑战，容易出现逻辑错误。
D - 元素距离积（困难）
- 难点：一是对原式进行数学化简和变换，需要有较强的数学功底和算法思维，理解如何通过变换式子来优化计算。二是利用数据范围（Aᵢ≤500）进行高效计算，构建和维护辅助数组（cntₓ和sumₓ）来统计信息，对编程技巧和逻辑的要求较高，实现过程较为复杂，容易出错。
E - 最小化两数组的距离
- 难点：处理交换两对二元组的复杂情况。需要将交换两对二元组的问题转化为交换一对二元组的问题，通过对数组元素的两两结合、排序去重以及二分查找来实现。涉及较多的数据处理和算法结合，对逻辑思维和代码实现能力要求高。尤其是二分查找中边界条件的判断和处理，若考虑不周全，容易导致结果错误。
F - 统计操作后不同的序列
- 难点：重复序列的判断和处理较为复杂。需要通过巧妙地构造新序列B及其前缀和序列S，根据Bᵢ的值分情况判断并统计重复的区间组合。在枚举平均值x和遍历序列过程中，准确把握各种条件（如Bᵢ是否为0、前缀和相等的判断等），逻辑复杂，对编程细节要求极高，代码实现难度较大。此外，时间复杂度受限于 $O(N \max A)$ ，当 $\max A$ 较大时，性能优化困难，如出现T6中TLE（Time Limit Exceeded，时间超限）的情况，即使采用剪枝策略也难以改善。