官方题解 | 挑战赛#30

NoonMaple

2026-04-22 10:13:01

发布于：浙江

24阅读

0回复

0点赞

挑战赛30题解

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目标题	难度
T1	小午的家族谱	入门
T2	午枫的卡片匹配游戏	普及-
T3	午枫的登山挑战	普及-
T4	午枫的积分记录	普及/提高-
T5	午枫的涂色游戏	普及/提高-
T6	午枫的排列	普及/提高-

T1 小午的家族谱

题目大意

给定一棵以 $1$ 为根的家族树，每个人只有一个父亲，且父亲编号比自己小，求从编号为 $n$ 的小午一路向上追溯到编号为 $1$ 的午枫，一共经过多少代。

题解思路

由于每个人的父亲编号都小于自己，其实已经隐含给出了一条从 $n$ 指向 $1$ 的唯一链。要求的代数就是这条链的长度。最直接的做法是从 $n$ 开始，不断跳到它的父亲 $p_n$ ，再跳到父亲的父亲，一直走到编号为 $1$ 为止，每走一步就把答案加一。因为保证最终一定能到达 $1$ ，而且每次编号都会变小，所以循环次数最多是 $n$ 次，复杂度是 $O(n)$ ，在数据范围内完全没有问题。

参考代码

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

const int N = 60;

int n;
int p[N];

int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> p[i];
    }

    int ans = 0;
    int cur = n;
    while (cur != 1) {
        cur = p[cur];
        ans++;
    }

    cout << ans << '\n';
    return 0;
}

T2 午枫的卡片匹配游戏

题目大意

给定一个长度为 $n$ 的数组 $a$ ，统计有多少对下标 $(i,j)$ （ $1 \le i < j \le n$ ），使得 $\min(a_i,a_j)=i$ 且 $\max(a_i,a_j)=j$ 。

题解思路

题目条件等价于：第 $i$ 张和第 $j$ 张卡片上的数字正好是 $\{i,j\}$ 这一对。于是只会有两种情况。第一种是两张卡片都放在了“正确位置”，也就是 $a_i=i$ 且 $a_j=j$ ，只要数出所有满足 $a_x=x$ 的位置个数，任取两个就能组成一个合法的卡片对，这一部分直接用组合数计算即可。第二种情况是成对互换，即 $a_i=j$ 且 $a_j=i$ ，这种每一对只能算一次，从前往后扫数组，用一个标记数组避免重复统计即可。把这两类情况的数量加起来就是答案，整体只需要线性扫描，时间复杂度是 $O(n)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 500010;

int a[N];
int used[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    long long ans = 0;

    // 情况一：a[i] == i
    long long cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == i) {
            cnt++;
        }
    }
    ans += cnt * (cnt - 1) / 2;

    // 情况二：a[i] = j 且 a[j] = i
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;
        int j = a[i];
        if (j >= 1 && j <= n && j != i) {
            if (a[j] == i && i < j) {
                ans++;
                used[j] = 1;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

T3 午枫的登山挑战

题目大意

从营地 $1$ 出发，初始体力为 $T$ ，每次从营地 $i$ 走到 $i+1$ 需要消耗 $A_i$ 点体力，到达部分营地时可以恢复体力，问在体力始终大于 $0$ 的前提下，是否能够到达营地 $N$ 。

题解思路

这条登山路线本身就是一条从 $1$ 到 $N$ 的直线，没有任何选择分支，因此可以直接按顺序模拟整个过程。用一个变量记录当前体力值，从营地 $1$ 开始依次向前走，每次先减去对应的体力消耗，如果减完后体力小于等于 $0$ ，就说明无法继续前进，可以直接输出 No。如果成功到达下一个营地，再检查这个位置是否有补给点，有的话就把体力加上去。由于补给点的位置是按编号递增给出的，用一个指针顺序处理即可。只要能顺利走到营地 $N$ ，中途没有失败，就输出 Yes。整个过程只需一次遍历，时间复杂度为 $O(N+M)$ 。

参考代码

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

const int N = 100010;

int n, m;
long long t;
long long a[N];
int x[N];
long long y[N];

int main() {
    cin >> n >> m >> t;
    for (int i = 1; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
    }

    long long cur = t;
    int id = 1;

    for (int i = 1; i < n; i++) {
        cur -= a[i];
        if (cur <= 0) {
            cout << "No\n";
            return 0;
        }
        if (id <= m && x[id] == i + 1) {
            cur += y[id];
            id++;
        }
    }

    cout << "Yes\n";
    return 0;
}

T4 午枫的积分记录

题目大意

给定一个长度为 $n$ 的整数序列 $a$ ，统计有多少个连续区间 $[l,r]$ ，使得区间和 $\sum_{i=l}^r a_i$ 能被 $M$ 整除。

题解思路

这是一个典型的前缀和取模问题。设前缀和 $s_i=a_1+a_2+\dots+a_i$ ，那么区间 $[l,r]$ 的和可以表示为 $s_r-s_{l-1}$ 。这个值能被 $M$ 整除，当且仅当 $s_r \bmod M = s_{l-1} \bmod M$ 。因此问题转化为：在所有前缀和模 $M$ 的结果中，有多少对下标满足模值相同。可以一边计算前缀和，一边统计每种模值出现的次数。每当当前模值为 $k$ ，就可以和之前所有同样模值的前缀组成合法区间，直接把对应的计数加到答案中。需要注意数组中可能有负数，取模时要调整为非负。整体只需一次线性扫描，时间复杂度是 $O(n+M)$ 。

参考代码

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

const int N = 200010;

int n, m;
long long a[N];
long long c[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    long long ans = 0;
    long long sum = 0;

    c[0] = 1;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        int md = (sum % m + m) % m;
        ans += c[md];
        c[md]++;
    }

    cout << ans << '\n';
    return 0;
}

T5 午枫的涂色游戏

题目大意

有一排 $n$ 个格子，每个格子有初始颜色价值 $c_i$ 。小午可以把前 $l$ 个格子全部涂成价值为 $x$ ，小枫可以把后 $r$ 个格子全部涂成价值为 $y$ ，且小枫后涂会覆盖小午。两人可以任选 $l,r$ ，问最终所有格子的颜色价值总和最小是多少。

题解思路

因为小午只影响前缀，小枫只影响后缀，最终的状态一定是：前面一段被小午涂成 $x$ ，中间一段保持原样，后面一段被小枫涂成 $y$ ，并且如果两段有重叠，重叠部分全部算作 $y$ 。可以先算出原数组的前缀和 $s_i$ 。考虑只让小午行动，枚举他涂前 $i$ 个格子时的总和，即 $i \cdot x + (s_n - s_i)$ ，并维护前 $i$ 的最小值，记为 $l_i$ ，表示“小午最多涂到 $i$ 为止时，能得到的最小总和”。接下来再枚举小枫从右往左涂色，假设她从位置 $i$ 开始往右全部涂成 $y$ ，那么中间原本的贡献需要扣掉，再加上 $(n-i+1)\cdot y$ ，此时左侧最优情况就是 $l_{i-1}$ 。把所有这些情况取最小值即可。整个过程只需要前后各扫一遍，时间复杂度是 $O(n)$ 。

参考代码

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

const int N = 200010;

long long a[N];
long long s[N];
long long l[N];

int main() {
    int n;
    long long x, y;
    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    // 只考虑小午
    l[0] = s[n];
    for (int i = 1; i <= n; i++) {
        long long cur = i * x + (s[n] - s[i]);
        l[i] = min(l[i - 1], cur);
    }

    long long ans = l[n];

    // 再考虑小枫
    for (int i = n; i >= 1; i--) {
        long long cur = l[i - 1] - (s[n] - s[i - 1]) + (n - i + 1) * y;
        ans = min(ans, cur);
    }

    cout << ans << '\n';
    return 0;
}

T6 午枫的排列

题目大意

给定 $1\sim n$ 的一个排列，并给出若干个限制条件，要求在排列中每个 $a_i$ 都必须出现在对应的 $b_i$ 之前。在所有满足条件的排列中，输出字典序最小的一个；如果不存在满足条件的排列，则输出 -1。

题解思路

每个限制关系“ $a_i$ 在 $b_i$ 之前”都可以看成一条从 $a_i$ 指向 $b_i$ 的有向边，这样所有限制就构成了一张有向图。题目要求的排列本质上就是这张图的一个拓扑序。如果图中存在环，那么无论如何都无法满足所有限制，直接输出 -1。如果图是有向无环图，那么就可以进行拓扑排序。为了得到字典序最小的拓扑序，在排序过程中，每一步都从当前所有入度为 $0$ 的点中选择编号最小的那个加入结果即可。实现时先统计每个点的入度，用一个小根堆维护当前入度为 $0$ 的点集合，不断取出最小值并更新其后继节点的入度。最终如果能取出恰好 $n$ 个点，就得到了答案，否则说明图中存在环。

参考代码

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

const int N = 200010;

int n, m;
int in[N];
int res[N];
vector<int> g[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        in[b]++;
    }

    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            pq.push(i);
        }
    }

    int cnt = 0;
    while (!pq.empty()) {
        int u = pq.top();
        pq.pop();
        res[++cnt] = u;
        for (int v : g[u]) {
            in[v]--;
            if (in[v] == 0) {
                pq.push(v);
            }
        }
    }

    if (cnt != n) {
        cout << "-1\n";
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << res[i];
    }
    cout << '\n';
    return 0;
}