官方题解 | 欢乐赛#84题解
2026-10-21 14:26:20
发布于:浙江
导语
本次为欢乐赛#84的题解,整体难度不难,多加了两道题目,希望大家AK慢一点 (加量不加价)
目录
| 题号 | 题目名称 | 知识点 | 难度 |
|---|---|---|---|
| T1 | 时间整理 | 算术运算符 | 入门 |
| T2 | 偶数数位 | 循环结构;算术运算符 | 入门 |
| T3 | 连续达标 | 循环结构 | 入门 |
| T4 | 口令压缩 | 字符串 | 入门 |
| T5 | 矩阵亮点 | 多维数组 | 普及- |
| T6 | 三种奖券 | 枚举;循环嵌套 | 普及- |
| T7 | 数值档案 | 结构体排序 | 普及- |
| T8 | 训练营排名 | 结构体排序 | 普及- |
T1 时间整理
原题:A172796 时间整理
题意简述
输入总分钟数 ,其中 。每 分钟算一个完整小时,输出完整小时数和剩余分钟数。
例如, 分钟可以分成 个完整小时和 分钟,输出 2 15。
解题思路
题意分析
每凑够 分钟,就能得到一个完整小时。两个整数相除时,C++ 的整数除法会舍去小数部分,因此 n / 60 就是完整小时数。
取余运算 n % 60 得到凑完这些完整小时后剩余的分钟数。设完整小时数为 ,剩余分钟数为 ,那么 ,并且 ,恰好符合题目要求。
当 时,整数除法得到 ,取余得到 ;当 恰好是 的倍数时,剩余分钟数为 。这两种情况都能直接按同一方法处理。
实现步骤
- 读入总分钟数 。
- 用
n / 60计算完整小时数,用n % 60计算剩余分钟数。 - 按“小时数、分钟数”的顺序输出,中间加一个空格。
复杂度分析
只进行固定次数的整数运算,时间复杂度为 ,额外空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int hour = n / 60; // 能凑出的完整小时数
int minute = n % 60; // 凑完后剩余的分钟数
cout << hour << " " << minute << "\n";
return 0;
}
T2 偶数数位
原题:A172797 偶数数位
题意简述
输入非负整数 ,其中 ,统计十进制表示中偶数数位的数量。、、、、 都是偶数数位,不同位置分别计数。整数 只有一个数位 ,因此答案为 。
样例中的 含有偶数数位 和 ,答案为 。
解题思路
题意分析
对于正整数,n % 10 可以取出当前个位数字,n / 10 可以去掉当前个位数字。反复执行这两个操作,就能从右向左检查每一个数位。
取出的数字设为 。当 d % 2 == 0 时,它是偶数数位,答案增加 。每检查一位就把它从整数中去掉,因此每一个数位恰好统计一次,不会遗漏,也不会重复。统计数量与检查数位的先后顺序无关。
需要单独处理输入为 的情况。若直接使用条件为 n > 0 的循环,循环一次也不会执行,但题目规定此时有一个偶数数位。因此先将这种情况的答案设为 。
由于输入可达 ,保存编号的变量使用 long long。单个数位和答案都很小,可以使用 int。
实现步骤
- 用
long long读入 ,将答案初始化为 。 - 如果 ,将答案设为 。
- 当 时,取出个位数字,判断它是否为偶数,再去掉这一位。
- 输出统计结果。
复杂度分析
设 为 的十进制数位个数,每个数位检查一次,时间复杂度为 ,额外空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n; // 编号可能达到 10 的 18 次方
cin >> n;
int ans = 0;
if (n == 0) {
ans = 1; // 整数 0 本身有一个偶数数位
}
while (n > 0) {
int d = n % 10;
if (d % 2 == 0) {
ans++;
}
n /= 10; // 去掉刚刚检查过的个位
}
cout << ans << "\n";
return 0;
}
T3 连续达标
原题:A172798 连续达标
题意简述
有 次练习,第 次的得分为 ,得分满足 时达标。求按原顺序连续达标的最长一段有多少次;没有达标练习时输出 。
其中 ,。样例一的达标线为 ,最后三次得分都是 ,构成长度为 的连续达标段。
解题思路
题意分析
从前往后检查练习,用变量 len 记录以当前练习结尾的连续达标长度,用 ans 记录已经找到的最长长度。
如果当前得分不低于 ,它可以接在前面连续达标的练习之后,于是 len 增加 。如果当前得分低于 ,任何以它结尾的连续段都不满足要求,因此把 len 清零。
每次处理后,用当前的 len 更新 ans。任意一段连续达标练习都有一个结束位置,检查到该位置时,它的长度一定会被考虑。因此扫描结束后,ans 就是最长长度。
答案初始为 ,所以全部不达标时会输出 。每读入一个得分就完成更新,也能直接统计出延伸到最后一次练习的达标段。
实现步骤
- 读入 和达标线 ,将
len、ans初始化为 。 - 依次读入每次练习的得分。
- 得分大于或等于 时,将
len加 ;否则将它清零。 - 用
len更新最长长度ans。 - 读完所有得分后,输出
ans。
复杂度分析
每个得分处理一次,时间复杂度为 。读入时直接统计,只使用几个变量,额外空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x;
cin >> n >> x;
int len = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
int score;
cin >> score;
if (score >= x) {
len++;
} else {
len = 0; // 当前练习不达标,连续段在这里中断
}
ans = max(ans, len);
}
cout << ans << "\n";
return 0;
}
T4 口令压缩
原题:A172799 口令压缩
题意简述
给定只含大写英文字母的字符串 ,把每一段连续相同的字母写成“字母加出现次数”,再按原顺序连接。长度为 的段也要输出次数 ,各段之间不加空格。
字符串长度满足 。例如,AAABBCCCCA 分为四段,压缩后为 A3B2C4A1。
解题思路
题意分析
用 ch 保存当前段的字母,用 cnt 保存当前段已经出现的次数。字符串非空,所以可以从第一个字母开始,将 cnt 初始化为 。
随后从第二个字母开始向后扫描。如果当前字母与 ch 相同,就把它加入当前段,让 cnt 增加 。如果不同,说明原来的一段已经结束,先输出它的字母和次数,再用新字母开始下一段,并把 cnt 重置为 。
扫描结束后,最后一段还没有遇到不同字母,需要再输出一次。这样,每一段都在遇到下一段或字符串结束时恰好输出一次,输出的顺序也与原字符串一致。
同一个字母被其他字母隔开时,会形成不同的段,分别处理。次数直接作为整数输出,因此连续出现次数超过 时也能正确输出多位数字。
实现步骤
- 读入字符串,将当前字母设为第一个字母,当前次数设为 。
- 从第二个字母开始,依次检查后面的字母。
- 与当前字母相同则累加次数;不同则输出旧段,并开始记录新段。
- 循环结束后输出最后一段,再输出换行。
复杂度分析
设字符串长度为 。扫描和输出的总规模均为 ,时间复杂度为 。除保存输入字符串所需的 空间外,只使用固定数量的变量,额外空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size();
char ch = s[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
if (s[i] == ch) {
cnt++;
} else {
cout << ch << cnt;
ch = s[i];
cnt = 1;
}
}
cout << ch << cnt << "\n"; // 补上最后一段
return 0;
}
T5 矩阵亮点
原题:A172800 矩阵亮点
题意简述
给定一个 行 列的矩阵。如果一个格子的值严格大于它上、下、左、右所有实际存在的相邻格子的值,这个格子就是亮点。求矩阵中亮点的数量。其中 ,。
只比较共用一条边的邻格,不比较斜对角。矩阵外的方向不参与比较;如果矩阵只有一个格子,这个格子就是亮点。
样例 1 中,第 行第 列、第 行第 列、第 行第 列和第 行第 列都是亮点,共有 个。
解题思路
题意分析
一个格子是否为亮点,只与它和周围实际存在的邻格有关。先用二维数组保存整个矩阵,再逐个检查每个格子即可。
检查一个格子时,先假设它是亮点,用变量 ok 记录。对于上、下、左、右四个方向,先判断邻格是否在矩阵内。如果邻格存在,而且当前格子的值小于或等于邻格的值,就说明它不满足“严格大于”的要求,把 ok 改为 false。
每个实际存在的邻格都会被检查。只要有一个邻格不满足要求,当前格子就不会被计数;如果检查结束后 ok 仍为 true,就说明当前格子严格大于所有实际存在的邻格,应当计入答案。因此,逐个检查后得到的数量正好是亮点总数。
边界格子只比较矩阵内的邻格,不能把矩阵外的值当成 ,因为矩阵中的数可以是负数。只有一个格子时,四个方向都没有邻格,ok 保持为 true,符合题目规定。
实现步骤
- 读入矩阵的行数 、列数 ,再把所有元素存入二维数组
a。 - 将亮点数量
ans初始化为 。 - 用两层循环枚举每个格子,并将
ok初始化为true。 - 依次检查四个方向;邻格存在且当前值小于或等于邻格值时,把
ok改为false。 - 如果
ok仍为true,将ans加 。 - 输出
ans。
复杂度分析
矩阵共有 个格子,每个格子最多比较 个邻格,所以时间复杂度为 。
二维数组用于保存矩阵,空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int a[205][205];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
bool ok = true;
// 先判断邻格是否存在,再比较数值。
if (i > 1) {
if (a[i][j] <= a[i - 1][j]) {
ok = false;
}
}
if (i < n) {
if (a[i][j] <= a[i + 1][j]) {
ok = false;
}
}
if (j > 1) {
if (a[i][j] <= a[i][j - 1]) {
ok = false;
}
}
if (j < m) {
if (a[i][j] <= a[i][j + 1]) {
ok = false;
}
}
if (ok) {
ans++;
}
}
}
cout << ans << '\n';
return 0;
}
T6 三种奖券
原题:A172801 三种奖券
题意简述
三种奖券的分值分别为 、、,满足 。每种奖券可以选任意非负整数张,求总分恰好为 的方案数,以及所有方案中使用奖券的最少总张数。
一种方案由三种奖券各自的张数 、、 决定,需要满足 。即使两种奖券的分值相同,它们仍是不同种类,各自的张数不同就属于不同方案。如果没有方案,输出 和 。
样例 1 中,三种奖券的分值为 、、,目标总分为 。四种方案的张数分别为 、、 和 ,所以方案数为 ,最少需要 张奖券。
解题思路
题意分析
直接枚举三种奖券的张数,会使用三层循环。实际上,只要确定前两种奖券的张数,第三种奖券需要补出的分数也就确定了,因此只需要两层循环。
先枚举第一种奖券的张数 。因为分值均为正数, 不能超过 。确定 后,再枚举第二种奖券的张数 ,保证 。此时还差的分数为 。
第三种奖券每张得到 分。如果 能被 整除,就能取 张第三种奖券,得到一种合法方案。因为 非负,所以算出的 也是非负整数。如果不能整除,当前的 、 就无法组成目标总分。
对于每种合法方案,将方案数加 ,并用 更新最少张数。每个合法三元组中的 、 都会被两层循环枚举到;固定这两个数以后, 只有一个可能值,因此不会遗漏方案,也不会重复计数。三种奖券分别用不同变量记录,即使它们分值相同,也会按种类分别计数。
最少张数可以先设为 。因为每张奖券至少得到 分,任何合法方案的总张数都不会超过 ,所以这个初始值一定比合法答案大。如果最终方案数仍为 ,就输出规定的无解结果。
由于 ,可枚举的非负整数对 、 最多有 个,方案数也不会超过这个上界,使用 int 即可。
实现步骤
- 读入三种奖券的分值 、、 和目标总分 。
- 将方案数
cnt初始化为 ,最少张数ans初始化为 。 - 枚举 ,范围为 到 。
- 对于每个 ,枚举 ,范围为 到 。
- 计算剩余分数 。如果 能被 整除,计算 ,增加方案数并更新最少张数。
- 如果方案数为 ,输出
0 -1;否则输出方案数和最少张数。
复杂度分析
最多有 种取值, 最多有 种取值。每次枚举只进行固定次数的计算,所以时间复杂度为 ,最坏为 。
程序只使用固定数量的变量,空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, s;
cin >> a >> b >> c >> s;
int cnt = 0;
int ans = s + 1;
for (int x = 0; x <= s / a; x++) {
for (int y = 0; y <= (s - a * x) / b; y++) {
int r = s - a * x - b * y;
// 前两种的张数确定后,检查剩余分数能否由第三种补齐。
if (r % c == 0) {
int z = r / c;
cnt++;
ans = min(ans, x + y + z);
}
}
}
if (cnt == 0) {
cout << "0 -1\n";
} else {
cout << cnt << ' ' << ans << '\n';
}
return 0;
}
T7 数值档案
原题:A172802 数值档案
题意简述
给定 条整数记录,每条记录的原下标从 开始。对于每一种不同的数值,统计它的出现次数和所有原下标之和。
先输出不同数值的数量,再按数值从小到大输出每种数值、出现次数和原下标之和。其中 ,。
例如,记录为 时,数值 出现在原下标 ,出现次数为 ,原下标之和为 。
解题思路
题意分析
如果直接按照原来的顺序统计,相同数值可能分散在许多位置。题目又要求按数值从小到大输出,因此可以先排序,把相同数值放到一起。
排序会改变记录的位置,所以每条记录都要保存两个信息:数值 value 和原下标 pos。原下标在读入时确定,排序后仍使用保存的 pos 参与求和,不能用排序后的数组下标代替。
按数值升序排序后,每一种数值都恰好对应一段连续记录。先扫描数组:第一个位置一定开始一个新组,之后每当当前数值与前一个数值不同,就增加一组。这样得到的组数就是不同数值的数量 。
接下来再次扫描数组,每次处理一组相同数值。组内每条记录使出现次数增加 ,并将它保存的原下标加入总和。每组只包含该数值的记录,而且包含它的全部记录,因此得到的次数和原下标之和都正确。各组按照排序后的顺序输出,数值也就保持升序。
数值、出现次数和原下标都可以使用 int。原下标之和最大为 ;当 时,结果为 ,超过 int 的范围,因此使用 long long 保存原下标之和。
实现步骤
- 读入 ,用结构体数组保存每条记录的数值和原下标。
- 按数值升序排序,扫描相邻数值,统计并输出不同数值的数量 。
- 从第一条记录开始,每次向后扫描一组相同数值,统计出现次数和原下标之和。
- 输出当前组的数值、次数和原下标之和,再处理下一组,直到所有记录处理完毕。
复杂度分析
排序需要 时间,两次扫描各需要 时间,因此总时间复杂度为 。
结构体数组保存 条记录,每条记录占用固定空间,因此空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
struct Record {
int value;
int pos;
};
Record a[200005];
bool cmp(Record x, Record y) {
return x.value < y.value;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].value;
a[i].pos = i;
}
sort(a + 1, a + n + 1, cmp);
int k = 0;
for (int i = 1; i <= n; i++) {
if (i == 1 || a[i].value != a[i - 1].value) {
k++;
}
}
cout << k << '\n';
int i = 1;
while (i <= n) {
int j = i;
int cnt = 0;
long long sum = 0;
// 每次统计一整组相同数值,累加保存的原下标。
while (j <= n && a[j].value == a[i].value) {
cnt++;
sum += a[j].pos;
j++;
}
cout << a[i].value << ' ' << cnt << ' ' << sum << '\n';
i = j;
}
return 0;
}
T8 训练营排名
题意简述
给定 名学员的编号、三项成绩和用时。每名学员的有效分是最高两项成绩之和,满分项数是三项成绩中等于 的项数。
排名依次比较:有效分高的在前;有效分相同时,满分项数多的在前;仍相同时,用时少的在前;最后按编号从小到大排列。输出排名后的每名学员编号和有效分。其中 ,编号互不相同且在 到 之间,三项成绩均在 到 之间,用时在 到 之间。
解题思路
题意分析
每名学员只有三项成绩。三项成绩的总和减去其中最小的一项,剩下的就是最高两项的总和,所以有效分可以直接计算为 。即使有多项成绩相同,这个计算方法也成立。
满分项数按照原来的三项成绩统计。分别判断每一项是否等于 ,每遇到一项满分,就将满分项数增加 。
完成计算后,每名学员只需要保存编号 id、有效分 score、满分项数 full 和用时 time。使用结构体将这四个信息放在一起,再编写比较函数,依次实现题目规定的四层排名规则。
比较两名学员时,先看有效分是否不同;如果不同,直接让有效分较高的排在前面。只有有效分相同,才继续比较满分项数。之后的用时和编号也采用同样的处理方式:前面的条件全部相同时,才使用后一项决定顺序。
这样,每一对学员的先后顺序都由题目规定的第一个不同条件确定。编号互不相同,最后一定可以确定先后,因此排序后得到的顺序就是所要求的排名。例如,有效分同为 时,一项成绩满分的学员应排在没有满分成绩的学员前面,即使用时更长也不改变这一点。
三项成绩均不超过 ,有效分不超过 ,满分项数不超过 ;编号和用时不超过 。这些数值及计算过程均可以使用 int。
实现步骤
- 读入 ,依次读入每名学员的编号、三项成绩和用时。
- 用三项成绩的总和减去最低成绩,求出有效分;分别判断三项成绩是否为 ,统计满分项数。
- 将编号、有效分、满分项数和用时保存在结构体数组中。
- 使用比较函数,按有效分降序、满分项数降序、用时升序、编号升序排序。
- 按排序后的顺序输出每名学员的编号和有效分。
复杂度分析
每名学员的信息计算和输出都只需要固定次数操作,共需要 时间。结构体排序需要 时间,因此总时间复杂度为 。
结构体数组保存 名学员的信息,因此空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
struct Student {
int id;
int score;
int full;
int time;
};
Student a[100005];
bool cmp(Student x, Student y) {
// 只有前一项相同,才使用后一项决定排名。
if (x.score != y.score) {
return x.score > y.score;
}
if (x.full != y.full) {
return x.full > y.full;
}
if (x.time != y.time) {
return x.time < y.time;
}
return x.id < y.id;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int s1, s2, s3;
cin >> a[i].id >> s1 >> s2 >> s3 >> a[i].time;
int lowest = min(s1, min(s2, s3));
a[i].score = s1 + s2 + s3 - lowest;
a[i].full = 0;
if (s1 == 100) {
a[i].full++;
}
if (s2 == 100) {
a[i].full++;
}
if (s3 == 100) {
a[i].full++;
}
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++) {
cout << a[i].id << ' ' << a[i].score << '\n';
}
return 0;
}
全部评论 39
2
1周前 来自 浙江
12666
1周前 来自 浙江
111
1周前 来自 浙江
9
666
1周前 来自 浙江
101
1周前 来自 浙江
5
632847956578657856457845963457grt3653243
1周前 来自 浙江
6666
1周前 来自 浙江
61
1周前 来自 浙江
2666
3天前 来自 浙江
1
2414454365345423454523532543
1周前 来自 浙江
52222
1周前 来自 浙江
5121212
1周前 来自 浙江
5666
4天前 来自 山东
3O(nlogn)
4天前 来自 广东
3H
1周前 来自 浙江
3good
1周前 来自 浙江
3666
5天前 来自 浙江
2https://www.acgo.cn/application/2115766520641433600
6天前 来自 广东
2https://www.acgo.cn/team/2096190617811324928
6天前 来自 广东
2good
1周前 来自 浙江
2为什么没有欢乐赛#83的题解
1周前 来自 重庆
2谁
3天前 来自 浙江
0
妙趣横生
1周前 来自 上海
2NB
2026-10-22 来自 浙江
2Good
2026-10-22 来自 浙江
2




























































有帮助,赞一个