官方题解 | 欢乐赛#85题解
2026-11-04 11:28:28
发布于：浙江
导语
以下为欢乐赛#85的题解，最后两道题对于数学和代码构建能力有了一定要求，如果你有着不错的思维和代码实现能力，那么在学完语法阶段后，是可以做出最后两题的。
可以在帖子下面留言相关建议与难度调整建议，若采纳会给予回复。
目录
| 名字 | 难度 | 知识点 |
|---|---|---|
| A 卡片入框 | 入门 | 分支结构、逻辑运算符 |
| B 最长纸带 | 入门 | 循环结构、分支结构 |
| C 三格合计 | 入门 | 一维数组、循环结构 |
| D 接龙断点 | 入门 | 字符串、循环结构 |
| E 竖直落珠 | 普及- | 一维数组、循环嵌套 |
| F 彩带对齐 | 普及- | 枚举、一维数组 |
| G 最近刻度 | 普及- | sort排序、一维数组 |
| H 连续整数拼和 | 普及- | 枚举、算术运算符 |
A 卡片入框
题意简述
输入一行四个整数 ，依次表示框的高、框的宽、卡片原来的高和宽，满足 。卡片可以保持原方向，也可以旋转四分之一圈，边缘重合允许放入。
按优先顺序输出结果：原方向可放入时输出 ；否则旋转后可放入时输出 ；两个方向都放不入时输出 。
样例 #1 中，框高为 、宽为 ，卡片高为 、宽为 。原方向超过框高，旋转后高为 、宽为 ，所以输出 。
解题思路
题意分析
原方向放入时，高和宽需要同时满足 、。旋转后卡片的高、宽交换，条件变为 、。
题目要求优先保持原方向，所以先判断原方向。这个条件失败后，再判断旋转方向。最后剩下的情况就是两个方向都无法放入。每个长度至多为 ，代码只比较长度，使用普通整数即可。
部分分说明：
- 测试点 （全量数据，每点 分）：按上述顺序判断两个方向，使用完整的三分支算法；本题采用普通逐点计分。
实现步骤
- 读入框和卡片的四个长度。
- 如果 且 ，输出 。
- 否则，如果 且 ，输出 。
- 否则，输出 。
正确性说明
卡片边缘与框边平行时，卡片高和宽分别不超过框的对应长度，就是放入的充要条件。程序首先检查原方向的充要条件，成功时按优先规则输出 ；失败后检查旋转方向的充要条件，成功时输出 ；两种条件都失败时输出 。因此所有情况下输出都符合题目规则。
复杂度分析
程序只进行常数次比较，时间复杂度为 ，额外空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
// h：框高；w：框宽；a：卡片高；b：卡片宽
int h, w, a, b;
cin >> h >> w >> a >> b;
// && 表示两个方向的长度条件都要满足
if (a <= h && b <= w) {
cout << 1 << endl;
} else if (b <= h && a <= w) {
cout << 2 << endl;
} else {
cout << 0 << endl;
}
return 0;
}
B 最长纸带
题意简述
第一行输入纸带根数 ，第二行输入 根纸带的长度 。满足 ，。
输出一个整数，表示最长纸带的长度。即使有多根纸带并列最长，也只输出这个长度一次。
样例 #1 的五个长度为 ，最大长度是 ，所以输出 。
解题思路
题意分析
用变量 记录已经读入的纸带中的最大长度。每读到一根新纸带，设长度为 ，将它与 比较；如果 更大，就把 改成 。
所有长度都是正整数，所以初始值可以取 。这样第一根纸带读入后也能正常更新。全部读完时， 就是所有纸带中的最大长度。题目只做比较，长度至多为 ，普通整数能够保存。
部分分说明：
- 测试点 （全量数据，每点 分）：依次读入并维护最大长度，使用完整的线性扫描算法；本题采用普通逐点计分。
实现步骤
- 读入纸带根数 ，将 初始化为 。
- 依次读入每根纸带的长度 。
- 如果 ，令 。
- 全部读完后，输出 。
正确性说明
读入第一根纸带前，，小于所有合法长度。每次读入新长度时，程序保留原先已读长度的最大值与当前长度中较大的一个。因此，每轮结束后， 都是当前所有已读纸带的最大长度。读完全部 根纸带后，它就是题目要求的答案。
复杂度分析
每根纸带只读入并比较一次，时间复杂度为 。只保存当前长度和最大长度，额外空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; // n：纸带根数
cin >> n;
int mx = 0; // mx：已读纸带的最大长度
// i：当前读入的纸带编号
for (int i = 1; i <= n; i++) {
int x; // x：当前纸带的长度
cin >> x;
if (x > mx) {
mx = x;
}
}
cout << mx << endl;
return 0;
}
C 三格合计
题意简述
第一行输入格子数量 ，第二行输入按原顺序排列的数值 。满足 ，。
选择恰好连续的三个格子，输出最大的三格合计，以及获得这个合计的最小起点编号。起点从 开始，格子保持原顺序，首尾不相接。
样例 #1 的数值为 。四个合法起点的合计依次为 。最大值是 ，最早起点为 ，所以依次输出 和 。
解题思路
题意分析
一次选择由起点 唯一确定，包含的位置是 。为了让最后一个位置不超过 ，合法起点恰好是 。
先读入数组，再从左到右枚举每个起点，直接计算三项和
用 保存目前的最大合计，用 保存对应起点。只有 时才更新两个值。因为起点按从小到大的顺序检查，相等时保留旧记录，就保留了最早起点。
所有数值都不小于 ，所以将 初始化为 ，第一次检查一定会更新。三个数的和最大为 ，超过常见 位整数的上限，因此数组和求和变量使用 C++ 的 long long 类型。
部分分说明：
- 测试点 （全量数据，每点 分）：枚举所有合法起点，计算三项和并维护最早最优起点；本题采用普通逐点计分，完整算法适用于全部测试点。
实现步骤
- 读入 和数组，令 、。
- 依次枚举起点 。
- 计算 。
- 如果 ，令 、；相等时保持原记录。
- 依次输出 和 。
正确性说明
每种合法选择都由最左边的起点唯一确定，且所有合法起点恰好是 。循环检查了这些起点，所以全部合法选择都被计算。
每检查一个起点，程序在原最大合计与当前合计之间保留较大的一个。因此循环结束时， 就是所有合法选择中的最大合计。
循环按起点升序进行，只有合计严格变大才更新 。遇到相同合计时，旧起点更早且被保留。因此最终 是获得最大合计的最小起点，两个输出都正确。
复杂度分析
读入 个数后检查 个起点，每个起点只做常数次运算，时间复杂度为 。保存整个数组，额外空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
long long a[100005]; // a：各格数值，用长整数参与求和
int main() {
int n; // n：格子数量
cin >> n;
// i：读入的格子编号
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
long long mx = -1; // mx：最大合计，可能超过 int 上限
int pos = 1; // pos：最大合计对应的最早起点
// i：当前三个连续格子的起点
for (int i = 1; i <= n - 2; i++) {
long long sm = a[i] + a[i + 1] + a[i + 2]; // sm：三格合计
// 严格变大才更新，相等时保留较早起点
if (sm > mx) {
mx = sm;
pos = i;
}
}
cout << mx << ' ' << pos << endl;
return 0;
}
D 接龙断点
题意简述
第一行输入单词数量 ，接下来 行依次输入单词。满足 ，每个单词长度为 到 ，只包含小写英文字母。
从第 个单词开始，比较前一个单词的末字符与当前单词的首字符。输出第一个接龙失败的当前单词编号；全部成功时输出 。
样例 #1 中，map、pen、nose、egg、goat 的相邻首尾字符依次相同，所以输出 。样例 #2 中，bc 的末字符与 da 的首字符不同，第一次失败发生在第 个单词，所以输出 。
解题思路
题意分析
用字符数组 保存前一个单词，用 读入当前单词。设前一个单词长度为 ，它的末字符下标是 ，当前单词首字符下标为 。
将答案 初始化为 。从编号 开始按顺序比较：当 且两个字符不同时，把当前编号记为答案。一旦记录了首次失败，后续比较保持答案不变。
每轮结束时，把当前单词复制到前一个单词的位置，供下一轮比较。长度为 的单词也按相同规则处理，因为此时首、末字符的下标都是 。
部分分说明：
- 测试点 （全量数据，每点 分）：按原顺序检查每对相邻单词并保留首次失败编号；本题采用普通逐点计分，完整算法适用于全部测试点。
实现步骤
- 读入 和第一个单词，令 。
- 依次读入编号 的当前单词。
- 求出前一个单词的长度，比较前词末字符与当前首字符。
- 如果本轮失败且 ，令 。
- 用当前单词更新前一个单词；全部处理完后输出 。
正确性说明
检查编号 前， 保存编号 的单词， 读入编号 的单词。因此本轮比较的正是题目要求的相邻首尾字符。检查后把当前单词复制给前一个单词，所以下一轮仍满足这一对应关系。
编号按升序检查，第一次字符不同时，记录的是最早失败的后一个单词编号。此后答案保持不变。若所有相邻单词都符合规则，答案始终为 。因此输出符合题意。
复杂度分析
设所有单词的总长度为 ，最长单词长度为 。每个单词只进行常数次读入、求长度与复制，时间复杂度为 。只保存两个单词，额外空间复杂度为 ；本题 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; // n：单词数量
// pre：前一个单词；cur：当前单词
char pre[105], cur[105];
cin >> n >> pre;
int ans = 0; // ans：第一次接龙失败的单词编号
// i：当前单词的编号
for (int i = 2; i <= n; i++) {
cin >> cur;
int len = strlen(pre); // len：前一个单词的长度
// && 表示尚未记录失败，且本次两个字符不同
if (ans == 0 && pre[len - 1] != cur[0]) {
ans = i;
}
// 当前单词成为下一轮的前一个单词
strcpy(pre, cur);
}
cout << ans << endl;
return 0;
}
E 竖直落珠
题意简述
盒子有 行 列，每格用 或 表示空格或珠子。所有珠子只在原列向下落，最后紧靠这一列的底部。
输入先给出 ，再给出整个表格；输出珠子停止后的 行 列表格。数据范围为 。
样例一中，盒子有 行 列，每列都有 颗珠子。因此停止后前两行都是 ，后两行都是 。
解题思路
题意分析
珠子只能在原列中移动，所以每一列的珠子数量始终不变。设第 列有 颗珠子，那么停止后这一列最下面的 个格子是 ，其余格子是 。
共有 行，空格恰好占据前 行。因此输出第 行第 列时，若 ，就输出 ；否则输出 。读入表格时只需累加各列的珠子数量。
部分分说明：
- 测试点 （全量数据）：本题按测试点计分，每点 分，共 分，未划分独立子任务。对所有测试点使用按列计数、从底部填充的完整算法。
实现步骤
- 读入 ，将各列珠子数量初始化为 。
- 按行读入表格，把每个格子的值加到它所在列的计数中。
- 依次输出每个格子：满足 时输出 ，否则输出 。
- 同一行的相邻数字之间输出一个空格，每行结束后换行。
正确性说明
第 列下落前后都有 颗珠子。全部停止时，任一珠子下方都不能有空格，否则它还能继续下落。因此该列所有珠子必定紧靠底部，最终状态唯一：最后 格为 ，前面的格子为 。
程序统计的数量与原表格一致，并按这一唯一状态输出每列，所以整个输出表格正确。
复杂度分析
读入和输出各访问 个格子，时间复杂度为 。保存各列计数需要 的额外空间。
参考代码
#include <bits/stdc++.h>
using namespace std;
int cnt[105]; // cnt[j]：第j列的珠子数量
int main() {
int n, m; // n：行数；m：列数
cin >> n >> m;
// i：当前读入的行号
for (int i = 1; i <= n; i++) {
// j：当前读入的列号
for (int j = 1; j <= m; j++) {
int x; // x：当前格子的状态
cin >> x;
cnt[j] += x;
}
}
// i：当前输出的行号
for (int i = 1; i <= n; i++) {
// j：当前输出的列号
for (int j = 1; j <= m; j++) {
if (j > 1) {
cout << ' ';
}
// 这一列最下面cnt[j]个格子有珠子
if (i > n - cnt[j]) {
cout << 1;
} else {
cout << 0;
}
}
cout << endl;
}
return 0;
}
F 彩带对齐
题意简述
长彩带有 格，短彩带有 格。保持短彩带方向不变，将其完全放在长彩带上，覆盖位置颜色相同就得 分。
输入两条彩带的长度及各格颜色，输出最高分和达到最高分的不同起点数量。数据范围为 ，颜色编号不超过 。
样例一中，长彩带颜色依次为 ，短彩带为 。从起点 或 放置都得到 分，其余起点得到 分，所以输出的最高分为 ，最优起点数量为 。
解题思路
题意分析
短彩带必须完整落在长彩带内，所以合法起点为 。固定起点 后，短彩带第 格覆盖长彩带第 格。依次比较这 对颜色，就能求出当前得分。
用 保存已检查摆放的最高分，用 保存对应起点数量。如果当前得分更高，更新最高分，并把计数设为 ；如果得分相同，计数增加 。
最高分初始设为 ，而合法得分最小为 ，因此第一个起点一定能建立答案。即使所有摆放得分都是 ，也能统计全部最优起点。
部分分说明：
- 测试点 （全量数据）：本题按测试点计分，每点 分，共 分，未划分独立子任务。对每个起点逐格比较颜色，使用完整枚举算法。
实现步骤
- 读入两条彩带的长度和颜色数组。
- 枚举起点 ，范围从 到 ，包含两端。
- 对当前起点，比较 与 ，将同色的覆盖对数累加为本次得分。
- 根据本次得分与最高分的大小关系，更新最高分和最优起点数量。
- 输出最终的最高分和数量。
正确性说明
固定一个起点时，内层循环恰好检查全部 对覆盖方格，颜色相同才计分，因此得到的就是该次摆放的真实得分。
外层循环枚举所有合法起点。遇到更高分时，以前记录的起点不再最优，所以重新计数为 ；遇到同分时，当前起点恰好提供一个新最优摆放，所以增加计数。由此，每次检查后，保存的分数和数量都对应已检查起点中的最优结果。全部起点检查结束后，输出即为题目所求。
复杂度分析
共进行 次颜色比较，时间复杂度为 。保存两条彩带需要 空间。
参考代码
#include <bits/stdc++.h>
using namespace std;
int a[305], b[305]; // a：长彩带颜色；b：短彩带颜色
int main() {
int n, m; // n：长彩带长度；m：短彩带长度
cin >> n >> m;
// i：长彩带上的位置
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// j：短彩带上的位置
for (int j = 1; j <= m; j++) {
cin >> b[j];
}
int mx = -1, cnt = 0; // mx：最高分；cnt：最优起点数量
// s：短彩带在长彩带上的起点
for (int s = 1; s <= n - m + 1; s++) {
int sm = 0; // sm：当前摆放的得分
// j：当前比较的短彩带位置
for (int j = 1; j <= m; j++) {
if (a[s + j - 1] == b[j]) {
sm++;
}
}
if (sm > mx) {
mx = sm;
cnt = 1; // 发现更高分，重新统计最优起点
} else if (sm == mx) {
cnt++;
}
}
cout << mx << ' ' << cnt << endl;
return 0;
}
G 最近刻度
题意简述
有 个独立的刻度牌，第 个牌上的数为 。选择两个不同的刻度牌，求它们数值差的最小值，并统计达到最小差值的无序对数。
输入刻度牌数量及全部数值，输出最小差值和对应对数。相同数值的不同刻度牌仍是不同物品，每对只计一次。数据范围为 ，。
样例一中，数值 出现两次，组成 对；数值 出现三次，组成 对。最小差值是 ，达到这一差值的共有 对。
解题思路
题意分析
先将所有数从小到大排序，再分两种情况处理。
如果存在重复数，最小差值一定是 。某个数出现 次，从中选两个不同刻度牌共有
种方法。分母中的 用于去掉同一对的两种先后顺序。遍历每段相同数值，把各段的贡献相加，就得到全部零差值对数。
如果所有数都不同，排序后任意不相邻两数的差，都是至少两个正的相邻差之和，因此严格大于其中的相邻差。于是最小差值只能出现在相邻位置。检查每一对相邻数，维护最小差及其出现次数即可。
对数最大为
超过常见 位整数范围，因此对数及分组长度乘法使用 long long。数值和差值均不超过 ，可以使用 int。
部分分说明：
- 测试点 （全量数据）：本题按测试点计分，每点 分，共 分，未划分独立子任务。使用排序后的分组计数与相邻差统计完整算法，兼顾重复值和大对数。
实现步骤
- 读入全部数值，按从小到大的顺序排序。
- 依次找到每个相同数值分组，按组长 累加 。
- 若零差值对数大于 ，直接输出最小差值 和这个对数。
- 否则遍历所有相邻差；出现更小差值时重设计数，出现相同最小差值时增加计数。
- 输出保存的最小差值和对数。
正确性说明
若存在重复数，最小差值为 。差值为 的一对刻度牌必定来自同一个相同值分组，每组恰好有 对。不同分组的牌不会组成零差值对，故所有分组贡献之和就是答案。
若没有重复数，排序后的相邻差都为正。任何不相邻两数的差均严格大于某个相邻差，所以不可能达到全局最小差。程序检查全部相邻位置，并在发现更小差值时更新答案、相同差值时增加计数，因而得到全部最优对。
这两种情况覆盖所有输入，程序输出正确。
复杂度分析
排序需要 时间，其余扫描需要 时间，总时间复杂度为 。保存数组需要 空间，排序额外调用栈为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int a[100005]; // a：刻度牌上的数，排序后从小到大
int main() {
int n; // n：刻度牌数量
cin >> n;
// i：当前读入的位置
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
long long z = 0; // z：零差值对数，最大值超过int范围
int l = 1; // l：当前相同数值分组的左端位置
while (l <= n) {
int r = l; // r：第一个不属于当前分组的位置
// 先确认位置合法，再比较数值
while (r <= n && a[r] == a[l]) {
r++;
}
long long c = r - l; // c：本组刻度牌数量，用64位乘法
z += c * (c - 1) / 2;
l = r;
}
if (z > 0) {
cout << 0 << ' ' << z << endl;
return 0;
}
int mn = 1000000001; // mn：当前最小差值
long long cnt = 0; // cnt：达到最小差值的刻度牌对数
// i：相邻一对中较小数的位置
for (int i = 1; i < n; i++) {
int d = a[i + 1] - a[i]; // d：当前相邻差值
if (d < mn) {
mn = d;
cnt = 1;
} else if (d == mn) {
cnt++;
}
}
cout << mn << ' ' << cnt << endl;
return 0;
}
H 连续整数拼和
题意简述
给定正整数 ，选择至少两个连续正整数，使它们的和恰好为 。首项不同或长度不同，都算不同方案。
输入一个 ，输出方案总数和所有方案中的最大长度；没有方案时两项均为 。数据范围为 ，首项必须至少为 。
样例一中，，共有 种方案，最长使用 个数，因此输出 和 。
解题思路
题意分析
枚举连续整数列的长度 。由于首项至少为 ，长度为 时，最小的和是 。把这一列正着、倒着各写一次，对应位置相加都等于 ，从而得到
因此，只需枚举满足 且 的长度。这样的长度最多约为 ，在本题范围内可以逐个检查。
固定长度 ，设首项为 。每个数都包含一个 ，额外增加的部分依次为 ，所以
令剩余量
若 能被 整除，就能得到唯一的整数首项 。长度上界已经保证 ，所以 ，这个首项一定为正整数。
按长度递增枚举，每遇到一个合法长度就把方案数增加 ，并将最长长度更新为当前长度。输入和中间乘法均使用 long long，以容纳 量级的数。
部分分说明：
- 测试点 （全量数据）：本题按测试点计分，每点 分，共 分，未划分独立子任务。枚举所有满足长度上界的 ，用整除条件判断首项，使用完整算法。
实现步骤
- 读入 ，将方案数和最长长度都初始化为 。
- 从 开始递增枚举，循环条件为 。
- 计算 ，检查 是否为 。
- 若能够整除，将方案数增加 ，并将最长长度更新为 。
- 输出方案数和最长长度；没有合法长度时，两个初始值都会保留为 。
正确性说明
任一合法方案的长度至少为 ，且它的和不小于 ，因此其长度一定在循环枚举范围内。其首项满足求和式，所以对应剩余量一定是 的倍数，程序会将它计入。
每个被程序计入的长度都通过了整除检查，因此首项是整数；循环范围又保证首项至少为 。按此首项写出的连续整数列，长度至少为 ，且求和恰好为 ，所以每次计入的方案都合法。
对于固定长度，求和式唯一确定首项，因此不同计数对应不同方案，且不会重复。程序按长度递增检查，最后记录的合法长度就是最大长度；无方案时保留 。故两项输出均正确。
复杂度分析
最多检查约 个长度，每次检查只进行常数次算术运算。因此时间复杂度为 ，额外空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n; // n：需要拼出的和，可达到10的12次方
cin >> n;
long long cnt = 0, mx = 0; // cnt：方案数；mx：最长长度
// k：当前枚举的长度，乘法使用64位整数
for (long long k = 2; k * (k + 1) / 2 <= n; k++) {
long long rem = n - k * (k - 1) / 2; // rem：首项的k倍
if (rem % k == 0) {
cnt++;
mx = k; // 长度递增，最新合法长度就是当前最长长度
}
}
cout << cnt << ' ' << mx << endl;
return 0;
}
这里空空如也
有帮助，赞一个