官方题解｜巅峰赛#17

アイドル

2025-02-05 20:30:32

发布于：北京

215阅读

0回复

0点赞

ACGO 巅峰赛#17 题解

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

题目编号	题目标题	难度
A.	纪念品商店	入门
B.	删除元素使数组去重	入门
C.	摩天轮	普及-
D.	线性探查法	普及
E.	统计 acgo 出现的次数	普及
F.	美丽数 II	普及
G.	数的集合	普及+/提高
H.	巨大的表格	提高+/省选-

题解简述

以下提供每道题目的思路简述，详细题解的AC代码包括复杂度分析，请点击题目标题查看。

A - 纪念品商店

模拟；数学

我们可以实现一个函数 int clamp(v, lo, hi)。

这个函数会返回 $\tt{[lo, hi]}$ 区间内，距离 $\tt{v}$ 最近的点。

那么显然，如果 $\tt{v}$ 在 $\tt{[lo, hi]}$ 内，函数返回 $\tt{v}$ ；若不在区间内，则有两种情况：

$\tt{v \lt lo}$ ，此时显然返回 $\tt{lo}$ ；
$\tt{v \gt hi}$ ，此时显然返回 $\tt{hi}$ ；

有了这个函数我们就可以判断 $\tt{[A, B]}$ 内离 $\tt{C}$ 最近的点和 $\tt{C}$ 的距离是否小于等于 $\tt{D}$ ，从而得出答案。

在 C++17 此函数已加入标准库，定义在头文件 <algorithm> 中。

#include <bits/stdc++.h>

int clamp(int v, int lo, int hi) {
    return v < lo ? lo : v > hi ? hi : v;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    int x = std::abs(clamp(c, a, b) - c);
    std::cout << (x <= d ? "Yes" : "No") << '\n';
    return 0;
}

B - 删除元素使数组去重

模拟

本题数据范围比较小，做法很多。这里使用一种时间复杂度较小，且通用的方法。

我们从后到前考虑整个数组中的元素，不断将元素添加至集合中，直至某个元素已经在集合中出现过。

此时数组中剩下的未被遍历的元素数量即为最小操作次数。

此方法时间复杂度 $\mathrm{O}(N\log{N})$ 。

#include <bits/stdc++.h>

int main() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (auto &x : a) std::cin >> x;
    std::set<int> st;
    while (!a.empty() and !st.count(a.back())) {
        st.insert(a.back());
        a.pop_back();
    }
    std::cout << a.size() << '\n';
    return 0;
}

C - 摩天轮

模拟；数学

对于任意时刻 $S_i$ ，我们考虑小码君的位置为 $(X_0, Y_0, Z_0)$ ，小码酱的位置为 $(X_1, Y_1, Z_1)$ ，那么二者之间的俯角或仰角度数为：

$\arctan\left(\frac{\vert Z_0 - Z_1 \vert}{\sqrt{(X_0 - X_1)^2 + (Y_0 - Y_1)^2}}\right) \cdot \frac{180}{\pi}$

我们假定摩天轮的位置都是 $(0, 0)$ ，然后根据计算出的位置，加上原来的位置，就可以得出实际的位置。

#include <bits/stdc++.h>

const double PI = std::acos(-1);

auto calc(double r, double p) {
    return std::make_pair(r * std::cos(p), r * std::sin(p));
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t; std::cin >> t;
    int xa, ya, la, xb, yb, lb;
    std::cin >> xa >> ya >> la;
    std::cin >> xb >> yb >> lb;
    int q; std::cin >> q;
    while (q--) {
        int s; std::cin >> s;
        auto [y0, z0] = calc(la / 2.0, (1.0 * s / t - 0.25) * PI * 2);
        auto [y1, z1] = calc(lb / 2.0, (1.0 * s / t - 0.25) * PI * 2);
        y0 = -y0 + ya;
        y1 = -y1 + yb;
        z0 += la / 2.0;
        z1 += lb / 2.0;
        double res = std::atan2(std::abs(z0 - z1), std::hypot(xa - xb, y0 - y1)) * 180 / PI;
        std::cout << std::setprecision(9) << std::fixed << res << '\n';
    }
    return 0;
}

D - 线性探查法

数据结构（哈希表，平衡树）

我们考虑维护所有的为空的单元；对于「线性探测法」本质上就是找到 第一个大于等于 $X$ 的空单元，若不存在这样的空单元，则寻找 第一个大于等于 $0$ 的空单元。

那么我们可以考虑使用 std::set 来维护所有的 $N$ 个空单元，并使用 std::map 来记录所有已经插入哈希表的元素分配到的位置即可。

时间复杂度： $\mathrm{O}(Q\log{N})$ 。

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int n, q;
    std::cin >> n >> q;
    std::set<int> a;
    std::map<i64, int> mp;
    for (int i = 0; i < n; ++i)
        a.insert(i);
    while (q--) {
        i64 x; std::cin >> x;
        if (!mp.count(x)) {
            auto p = a.lower_bound(x % n);
            if (p == a.end()) p = a.lower_bound(0);
            mp[x] = *p;
            a.erase(p);
        }
        std::cout << mp[x] << '\n';
    }
    return 0;
}

E - 统计 acgo 出现的次数

动态规划；

我们考虑使用动态规划来统计所有的以 a，c，g，o 结尾的子序列的数量。

令 $A, C, G, O$ 分别表示 a，c，g，o 结尾的子序列的数量。

遍历字符串 $S$ ，对于字符串 $S$ 中的每个字符 $S_i$ ，若其为 a，则将 $A$ 加一；若其为 b，则将 $B$ 更新为 $B + A$ ；若其为 c，则将 $C$ 更新为 $C + B$ ；若其为 d，则将 $D$ 更新为 $D + C$ ；若为其他字符，则不做任何处理。

最终 $D$ 即为所求的答案。

#include <bits/stdc++.h>

const std::string S = "#acgo";
constexpr int MOD = 998244353;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n; std::cin >> n;
    std::string s; std::cin >> s;
    std::vector<int> dp(S.size());
    dp[0] = 1;
    for (auto &c : s) {
        auto p = S.find(c);
        if (p == std::string::npos) continue;
        dp[p] = (dp[p] + dp[p - 1]) % MOD;
    }
    std::cout << dp.back() << '\n';
    return 0;
}

我们可以把 $10^5$ 内所有的 $9592$ 个素数预处理，来加速质因数分解，使其复杂度降为 $\mathrm{O}(\pi(\lfloor\sqrt{\max(A_i)}\rfloor)$ 。这样整个算法时间复杂度为 $\mathrm{O}\left(N \times \pi(\lfloor\sqrt{\max(A_i)}\rfloor)\right)$ ；其计算量大约为 $10^4 \times 10^4 = 10^8$ ，可以在时限内通过题目。

#include <bits/stdc++.h>
 
using i64 = long long;

constexpr int N = 1e5;

std::bitset<N + 1> st;
std::vector<int> primes;

auto sieve = []() {
    for (i64 i = 2; i <= N; ++i) {
        if (st[i]) continue;
        for (i64 j = i * i; j <= N; j += i)
            st[j] = 1;
        primes.push_back(i);
    }
    return 0;
} ();

int solve() {
    i64 n; std::cin >> n;
    int cnt = 0;
    for (auto &p: primes) {
        while (n % p == 0) {
            n /= p;
            cnt += 1;
        }
        if (cnt > 3) break;
    }
    if (n > 1) cnt += 1;
    std::cout << (cnt == 3 ? "Yes" : "No") << '\n';
    return 0;   
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int _; std::cin >> _;
    while (_--) solve();
    return 0;
}

G - 数的集合

质数筛；并查集；前缀和

本题有两种方法可以解决，前者的切入点更平滑，后者更偏向于数学直觉一些。

方法一（并查集）

比较直接的一个想法，从 $N$ 开始执行搜索，把 $[2, N - 1]$ 中未加入集合且与当前元素不互质的元素加入集合 $S$ 。

那么显然我们的目标就是如何快速地找到与 $N$ 不互质的元素集合 $S'$ ，对于 $S'$ 中的每个元素，再找到与其不互质的元素，以此类推。

由于本题中的操作具有传递性质： $X$ 与 $Y$ 不互质； $Y$ 与 $Z$ 不互质，那么 $X$ ， $Y$ ， $Z$ 都属于同一个集合。

我们可以从小到大考虑每个元素 $X$ ，令 $X$ 的最小质因子 $P(X)$ ，那么有：

若 $X$ 为质数，显然集合中只有 $X$ 本身。
若 $X$ 不为质数，那么显然我们将其拆分为 $P(X)$ 与 $\dfrac{X}{P(X)}$ ，那么二者所在的集合可以借助 $X$ 合并起来。

我们将处理到元素 $X$ 时，其所在的集合的大小设为 $f(X)$ ，那么对应的操作次数为 $f(X) - 1$ 。

所以我们可以预处理 $3 \times 10^6$ 中的所有元素，然后依次回答每个查询即可。

令 $M = \max(N_i)$ ，此方法时间复杂度为 $\mathrm{O}(M\alpha(M) + M\log{\log{M}} + T)$ 。

并查集每个操作平均时间复杂度为 $\alpha(M)$ ，其中 $\alpha$ 为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

方法二详情点击标题链接查看。

#include <bits/stdc++.h>

// class: UnionFind

constexpr int N = 3e6;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int st[N + 1]{};
    for (int i = 2; i * i <= N; ++i) {
        if (st[i]) continue;
        for (int j = i * i; j <= N; j += i)
            st[j] = i;
    }
    UnionFind d(N + 1);
    int res[N + 1]{};
    for (int i = 2; i <= N; ++i) {
        if (st[i]) {
            d.unite(i, st[i]);
            d.unite(i, i / st[i]);
        }
        res[i] = d.size(i) - 1;
    }
    int q; std::cin >> q;
    while (q--) {
        int n; std::cin >> n;
        std::cout << res[n] << '\n';
    }   
    return 0;
}

H - 巨大的表格

递推；矩阵快速幂

我们可以先计算出 $1$ 列的所有元素的值，然后考虑表格中每一列元素的值，可以发现，对于 $i(i > 1)$ 列的 $N$ 个元素的值，可以完全由 $i - 1$ 列的元素得到：

$\begin{split} A_{0, i} = A_{0, i - 1} + 1 \end{split}$

$\begin{split} A_{1, i} &= A_{0, i} \times S + A_{1, i - 1} \times T \\ &= (A_{0, i - 1} + 1) \times S + A_{1, i - 1} \times T \\ &= A_{0, i - 1} \times S + A_{1, i - 1} \times T + S \end{split}$

$\begin{split} A_{2, i} &= A_{1, i} \times S + A_{2, i - 1} \times T \\ &= (A_{0, i - 1} \times S + A_{1, i - 1} \times T + S) \times S + A_{2, i - 1} \times T\\ &= A_{0, i - 1} \times S^2 + A_{1, i - 1} \times ST + A_{2, i - 1} \times T + S^2 \end{split}$

$\begin{split} A_{3, i} &= A_{2, i} \times S + A_{3, i - 1} \times T \\ &= (A_{0, i - 1} \times S^2 + A_{1, i - 1} \times ST + A_{2, i - 1} \times T + S^2) \times S + A_{3, i - 1} \times T\\ &= A_{0, i - 1} \times S^3 \times A_{1, i - 1} \times S^2T + A_{2, i} \times ST + A_{3, i - 1} \times T + S^3 \end{split}$

$\begin{split} A_{N - 1, i} &= A_{N - 2, i} \times S + A_{N - 1, i - 1} \times T \\ &= A_{0, i - 1} \times S^{N - 1} + A_{1, i - 1} \times S^{N-2}T + A_{2, i - 1} \times S^{N - 3}T + \cdots + A_{N, i - 1} \times T + S^N \\ &= A_{0, i - 1} \times S^{N - 1} + \sum_{j = 1}^{N - 1} A_{j, i - 1} \times S^{N - j} T + S^{N-1} \end{split}$

由于 $0$ 号元素每次加 $1$ ，所以我们可以考虑在最后给表格加一行全为 $1$ 的元素作为 $N$ 行上的元素，接着可以把转移写成矩阵的形式。

那么我们有：

$\left[ \begin{matrix} 1 & S & S^2 & S^3 & S^4 & \cdots & S^{N - 1} & 0\\ 0 & T & T \times S^1 & T \times S^2 & T \times S^3 & \cdots & T \times S^{N - 2} & 0 \\ 0 & 0 & T & T \times S^1 & T \times S^2 & \cdots & T \times S^{N - 3} & 0\\ 0 & 0 & 0 & T & T \times S^1 & \cdots & T \times S^{N - 4} & 0 \\ 0 & 0 & 0 & 0 & T & \cdots & T \times S^{N - 5} & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & 0 & \cdots & T & 0\\ 1 & S & S^2 & S^3 & S^4 & \cdots & S^{N-1} & 1\\ \end{matrix} \right]$

由于 $M$ 很大，对于每个查询 $(R_i, C_i)$ ，我们可以使用矩阵快速幂来计算出表格中 $C_i$ 上的所有元素。

整个算法时间复杂度： $\mathrm{O}(QN^3\log{M})$ 。

#include <bits/stdc++.h>

// namespace: Matrix

// class: Modint

using mint = Modint<998244353>;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;
    Matrix::Mat<mint> dp = {std::vector<mint>(n + 1)};
    dp[0][0] = 1;
    for (int i = 1; i < n; ++i) {
        int x; std::cin >> x;
        dp[0][i] = dp[0][i - 1] * s + 1LL * x * t;
    }
    dp[0][n] = 1;
    Matrix::Mat<mint> a = Matrix::e<mint>(n + 1);
    a[n][0] = 1;
    for (int i = 1; i < n; ++i) {
        a[i][i] = t;
        for (int j = i - 1; j >= 0; --j)
            a[j][i] = a[j + 1][i] * s;
        a[0][i] /= t;
        a[n][i] = a[n][i - 1] * s;
    }
    int q; std::cin >> q;
    while (q--) {
        int r, c;
        std::cin >> r >> c;
        auto res = Matrix::multi(dp, Matrix::pow(a, c - 1));
        std::cout << res[0][r].val() << '\n';
    }
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 3

亚洲卷王 AK IOI
666建议C题给个公式不然谁的击败知道怎么写

2025-02-05 来自浙江
1
- ‮队团加不）童帅_者仇复
  回复亚洲卷王 AK IOI
  直言不讳（
  
  2025-02-05 来自广东
  0
- アイドル
  回复亚洲卷王 AK IOI
  C题给了公式呀
  
  2025-02-05 来自北京
  0
- 亚洲卷王 AK IOI
  回复アイドル
  我说的是 $\arctan$ 这一坨石
  
  2025-02-05 来自浙江
  0
༺ཌༀ我不会身法ༀད༻
std::cin.tie(nullptr)->sync_with_stdio(false);啥意思？

2025-02-11 来自北京
0
- ༺ཌༀ我不会身法ༀད༻
  回复༺ཌༀ我不会身法ༀད༻
  @‮队团加）ด้้童帅_者仇复
  
  2025-02-11 来自北京
  0
- ‮队团加不）童帅_者仇复
  回复༺ཌༀ我不会身法ༀད༻
  取消输入同步流，可以让 cin 变得和 scanf 一样快，副作用是不能同时使用 cin 和 scanf,getchar 等
  
  2025-02-11 来自广东
  0
‮队团加不）童帅_者仇复
顶

2025-02-04 来自广东
0