#创作计划ACGO个人题解（欢乐赛50）
2025-07-01 22:25:00
发布于：福建
T1：50!
题干信息解读：
题目要求输出固定图案，无输入处理
输出格式严格固定为5行7列
图案表示数字50的图形化显示
实现方案：
直接使用字符串数组存储图案
逐行输出预定义的图案
无需任何计算过程
方法一：数组存储
#include <bits/stdc++.h>
using namespace std;
int main() {
// 预定义图案的5行字符串
string pattern[5] = {
"###.###",
"#...#.#",
"###.#.#",
"..#.#.#",
"###.###"
};
// 逐行输出图案
for(int i=0; i<5; i++) {
cout << pattern[i] << endl;
}
return 0;
}
复杂度分析：
时间复杂度：O(1)，仅执行固定次数的输出操作5
空间复杂度：O(1)，使用固定大小的字符串数组存储图案5
注意事项：
图案必须严格匹配样例输出
每行末尾不能有多余空格
行末需要换行符
直接硬编码图案是最简单可靠的解决方案
cout方法：
#include <bits/stdc++.h>
using namespace std;
int main() {
cout << "###.###" << endl;
cout << "#...#.#" << endl;
cout << "###.#.#" << endl;
cout << "..#.#.#" << endl;
cout << "###.###" << endl;
return 0;
}
printf方法：
#include <bits/stdc++.h>
int main() {
printf("###.###\n");
printf("#...#.#\n");
printf("###.#.#\n");
printf("..#.#.#\n");
printf("###.###\n");
return 0;
}
复杂度分析：
时间复杂度：O(1)，仅执行固定次数的输出操作
空间复杂度：O(1)，不依赖输入规模，使用固定内存
两种实现方式在性能上没有实质性差异
T2：农场修缮
题干信息解读
农场是一个n×m的网格
需要修建：
1一条固定宽度a的水平道路
2一条从q个备选宽度中选择的垂直道路
两条道路会有交叉重叠部分
目标是计算剩余的最大可耕种面积
整体做题思路
剩余面积 = 总面积 - 道路面积 + 重叠部分
数学推导可得：剩余面积 = (n - a) × (m - b)
要使剩余面积最大，需要选择最小的b值
因此只需在给定的b数组中找出最小值
题目难点和注意事项
理解道路交叉部分的面积计算
注意数据范围可能导致的整数溢出
需要高效地找出b数组中的最小值
输入规模较大时要注意算法效率
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, a, q;
cin >> n >> m >> a >> q;
int b[10005]; // 存储备选宽度
int min_b = 10001; // 初始化最小值
// 读取所有b值并找出最小值
for (int i = 0; i < q; i++) {
cin >> b[i];
if (b[i] < min_b) {
min_b = b[i];
}
}
// 计算最大剩余面积，使用long long防止溢出
long long area = 1LL * (n - a) * (m - min_b);
cout << area << endl;
return 0;
}
复杂度分析
时间复杂度：O(q)，因为需要遍历q个b值找最小值
空间复杂度：O(q)，用于存储b数组
在题目给定的约束下(1≤q≤10000)，这个复杂度完全可接受
T3：赛马大会
题干信息解读
题目描述了两支马队的比赛，每队各有n匹马，按照固定顺序出战1
比赛规则：
速度快的马得3分
平局双方不得分
速度慢的马扣3分
需要计算小明队伍的总得分
整体做题思路
同时遍历两个马队的数组
逐对比较马匹速度
根据比较结果累加得分：
a[i] > b[i]：总分+3
a[i] == b[i]：总分不变
a[i] < b[i]：总分-3
题目难点和注意事项
数据规模较大(n≤1e5)，需要使用O(n)算法
注意整数溢出问题，总分可能达到3e5
输入输出效率对时间限制敏感（但建议还是用cin cout）
#include <bits/stdc++.h>
using namespace std;
int main() {
// 读取马匹数量
int n;
cin >> n;
// 定义速度数组（C99变长数组，非标准C++）
int a[n], b[n]; // a:第一组马速，b:第二组马速
// 读取第一组马匹速度
for(int i=0; i<n; i++) {
cin >> a[i]; // 存储到数组a
}
// 读取第二组马匹速度
for(int i=0; i<n; i++) {
cin >> b[i]; // 存储到数组b
}
// 初始化得分
int score = 0;
// 逐对比较马匹速度
for(int i=0; i<n; i++) {
if(a[i] > b[i]) {
score += 3; // 当前马匹更快，加3分
} else if(a[i] < b[i]) {
score -= 3; // 当前马匹更慢，减3分
}
// 速度相同时不做处理
}
// 输出最终得分
cout << score << endl;
return 0; // 程序正常结束
}
时间复杂度：O(n)，需要遍历所有马匹一次
空间复杂度：O(n)，需要存储两个马队的速度数组
T4:小明和藏宝库
题干信息解读
题目描述小明需要找到一个数字，该数字能够解锁所有n个宝箱。每个宝箱有m个不同的密码，只要数字匹配其中任意一个密码即可解锁该宝箱。目标是统计能同时解锁所有宝箱的数字个数
关键信息点：
输入包含n个宝箱，每个宝箱有m个密码
密码范围1≤a_ij≤100000
需要找出同时存在于所有宝箱密码集合中的数字
输出满足条件的数字个数
整体做题思路
数据收集：读取所有宝箱的密码集合
交集计算：找出所有宝箱密码集合的交集
结果输出：统计交集元素数量
核心算法是集合交集运算，需要高效处理最多5000个宝箱，每个宝箱最多5000个密码的情况
/*
* 功能：统计能打开所有宝箱的公共密码数量
* 算法：基于数组标记的集合求交法
* 输入：
* - 第一行：n(宝箱数), m(每个宝箱密码数)
* - 接下来n组m个密码数字
* 输出：公共密码的数量
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX_NUM = 100000; // 密码最大值常量定义
int main() {
// 输入宝箱数量和每个宝箱的密码数
int n, m;
cin >> n >> m;
// 初始化统计数组
int count[MAX_NUM + 1] = {0}; // 记录密码出现次数
int first_box[MAX_NUM + 1] = {0}; // 记录第一个宝箱的密码
// 处理第一个宝箱的密码
for(int j=0; j<m; j++) {
int num;
cin >> num;
first_box[num] = 1; // 标记存在的密码
}
// 处理后续n-1个宝箱
for(int i=1; i1]<n; i++) {
int temp[MAX_NUM + = {0}; // 临时存储当前宝箱密码
// 读取当前宝箱的m个密码
for(int j=0; j<m; j++) {
int num;
cin >> num;
temp[num] = 1; // 标记当前宝箱的密码
}
// 更新公共密码计数器
for(int k=1; k]]1<=MAX_NUM; k++) {
if(first_box[k && temp[k]) {
count[k++; // 仅在首次宝箱和当前宝箱都存在的密码才计数
}
}
}
// 统计结果：出现n-1次的密码（与所有宝箱交集）
int result = 0;
for(int k=; k<=MAX_NUM; k++) {
if(count[k] == n-1) { // 密码出现在所有后续宝箱
result++;
}
}
cout << result <0< endl;
return ;
}
题目中的难点和注意事项
大数据量处理：n和m都可能达到5000，需要O(nm)的算法
内存限制：128MB内存需合理使用数据结构
时间限制：1秒时间限制要求算法复杂度不超过O(nm)
密码范围：密码值可能达到100000，适合用数组计数
密码唯一性：每个宝箱的m个密码互不相同
T5；指针夹角
整体做题思路
计算时钟指针夹角的核心在于分别计算时针和分针相对于12点位置的角度，然后求两者差值的较小值。具体步骤为：
计算分针角度：每分钟6度（360°/60分钟）
计算时针角度：每小时30度（360°/12小时）加上每分钟0.5度（30°/60分钟）
计算绝对差值后取min(差值,360-差值)得到较小夹角
题目难点和注意事项
时针的复合运动：时针位置受小时和分钟共同影响，需加上分钟带来的偏移量
12小时制处理：当输入为0时应视为12点位置
角度方向判断：需考虑顺时针和逆时针两种方向的较小夹角
浮点精度：分钟对时针的影响是0.5度/分钟，需用浮点数计算
#include <bits/stdc++.h>
using namespace std;
int main() {
int hour, minute;
cin >> hour >> minute;
// 计算时针角度：每小时30度 + 每分钟0.5度
double hour_angle = 30.0 * hour + 0.5 * minute;
// 计算分针角度：每分钟6度
double minute_angle = 6.0 * minute;
// 计算两针夹角（取较小值）
double angle = abs(hour_angle - minute_angle);
angle = min(angle, 360 - angle);
// 输出结果保留两位小数
cout << fixed << setprecision(2) << angle << endl;
return 0;
}
时间复杂度：O(1)
仅进行固定次数的算术运算，与输入规模无关
空间复杂度：O(1)
只使用常数级别的存储空间（几个double变量），
T6：（重磅题目）小明的ACM罚时
整体做题思路
数组存储：使用固定大小的二维数组存储队伍信息
罚时计算：为每道题维护错误次数和通过状态
手动排序：实现冒泡排序处理多条件排序
题目难点和注意事项
数组大小限制：需预先分配足够空间（n≤100，题目数≤13）
状态记录：需要同时跟踪每道题的通过状态和错误次数
排序稳定性：确保相同条件下按队伍编号排序
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// teams[][0]=通过数, [][1]=罚时, [][2]=队伍编号
int teams[100][3] = {0};
// 记录每队每题的提交情况：[0]=错误次数, [1]=是否通过
int problems[100][13][2] = {0};
for (int i = 0; i < n; i++) {
int m;
cin >> m;
teams[i][2] = i + 1; // 设置队伍编号
while (m--) {
int a, b, c;
cin >> a >> b >> c;
b--; // 题目转为0-based
if (c == 1 && problems[i][b][1] == 0) { // 首次通过
problems[i][b][1] = 1;
teams[i][0]++;
teams[i][1] += a + problems[i][b][0] * 15;
} else if (c == 0 && problems[i][b][1] == 0) { // 错误提交
problems[i][b][0]++;
}
}
}
// 冒泡排序实现多条件排序
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
bool need_swap = false;
// 条件1：通过题数更多
if (teams[j][0] < teams[j + 1][0]) need_swap = true;
// 条件2：通过数相同但罚时更少
else if (teams[j][0] == teams[j + 1][0] && teams[j][1] > teams[j + 1][1]) need_swap = true;
// 条件3：前两者相同但编号更小
else if (teams[j][0] == teams[j + 1][0] && teams[j][1] == teams[j + 1][1]
&& teams[j][2] > teams[j + 1][2]) need_swap = true;
if (need_swap) {
// 交换三个字段
for (int k = 0; k < 3; k++) {
int temp = teams[j][k];
teams[j][k] = teams[j + 1][k];
teams[j + 1][k] = temp;
}
}
}
}
// 输出结果
for (int i = 0; i < n; i++) {
cout << teams[i][2];
if (i < n - 1) cout << " ";
}
return 0;
}
时间复杂度：O(n²) - 冒泡排序主导，n≤100时完全可接受
空间复杂度：O(n) - 使用固定大小数组，problems数组大小100×13×2=2600个int
这里空空如也
有帮助，赞一个