非官方题解-ACGO挑战赛#17
2025-04-23 18:54:27
发布于：四川
39阅读
0回复
0点赞
非官方题解-ACGO挑战赛#17
T1：凤梨酥
这道题目要求我们根据给定的馅料含量百分比（ ）和风梨占总重量的百分比（ ）来判断风梨酥的等级。根据题目描述，等级划分如下：
- 一等风梨酥：馅料含量 且风梨占比 。
- 二等风梨酥：馅料含量 且风梨占比 但 。
- 三等风梨酥：馅料含量 或风梨占比 。
我们需要根据输入的 和 值，输出对应的等级（1、2或3）。
解决代码
#include <iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
if (a >= 50 && b >= 30) {
cout << 1 << endl;
} else if (a >= 50 && b >= 15) {
cout << 2 << endl;
} else {
cout << 3 << endl;
}
return 0;
}
代码解释
- 输入处理：读取两个整数a和b，分别代表馅料含量百分比和风梨占比百分比。
- 等级判断：
- 如果 且 ，输出
1（一等风梨酥）。 - 否则，如果 且 ，输出
2（二等风梨酥）。 - 其他情况（ 或 ），输出
3（三等风梨酥）。
- 如果 且 ，输出
- 输出结果：根据条件判断输出对应的等级。
这样就能正确判断并输出风梨酥的等级了。
T2：买凤梨1
这道题目要求我们从给定的n个风梨中，统计出满足以下两个条件的风梨数量：
- 重量在 到 之间（包括 和 ）。
- 重量是一个回文数。
解决思路
- 输入处理：首先读取整数n，表示风梨的数量，然后读取n个风梨的重量。
- 条件判断：对于每个风梨的重量，检查是否满足：
- 重量在 到 之间。
- 重量是回文数。
- 统计结果：统计满足上述条件的风梨数量，并输出结果。
解决代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isPalindrome(int num) {
if (num < 10) return true; // 一位数都是回文数
string s = to_string(num);
string rev = s;
reverse(rev.begin(), rev.end());
return s == rev;
}
int main() {
int n;
cin >> n;
vector<int> weights(n);
for (int i = 0; i < n; ++i) {
cin >> weights[i];
}
int count = 0;
for (int weight : weights) {
if (weight >= 500 && weight <= 10000 && isPalindrome(weight)) {
count++;
}
}
cout << count << endl;
return 0;
}
代码解释
- 函数
isPalindrome：判断一个数字是否是回文数。- 将数字转换为字符串，反转后与原字符串比较，如果相同则是回文数。
- 主函数
main：- 读取风梨的数量n和每个风梨的重量。
- 遍历所有重量，检查是否满足条件（重量在 到 之间且是回文数）。
- 统计满足条件的风梨数量并输出。
这样就能高效地统计出最多可以买回多少个好的风梨。
T3：集训课
这道题目要求我们找到一段最长的连续天数，使得在这段天数内，所有学生都在学校（即他们的日程表中对应天数均为1）。我们需要遍历每一天，检查从该天开始的最长连续天数满足所有学生都在学校。
解决思路
- 输入处理：读取学生数量 和天数 ，然后读取每个学生的日程表。
- 检查每一天：对于每一天，检查从该天开始的最长连续天数，使得所有学生在这段天数内都为1。
- 更新最长天数：在遍历过程中，记录满足条件的最大连续天数。
解决代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> schedule(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> schedule[i][j];
}
}
int max_days = 0;
for (int start = 0; start < m; ++start) {
int end = start;
while (end < m) {
bool all_present = true;
for (int i = 0; i < n; ++i) {
if (schedule[i][end] == 0) {
all_present = false;
break;
}
}
if (all_present) {
end++;
} else {
break;
}
}
max_days = max(max_days, end - start);
}
cout << max_days << endl;
return 0;
}
代码解释
- 输入处理：读取 和 ，然后读取每个学生的日程表，存储在二维向量
schedule中。 - 遍历每一天：对于每一天
start，初始化end为start，然后检查从start到end的天数是否所有学生都在学校。 - 更新最长天数：如果所有学生都在学校，则
end递增，直到不满足条件为止。更新max_days为当前最大连续天数。 - 输出结果：最终输出满足条件的最大连续天数。
这种方法确保了我们能够高效地找到最长的连续天数，使得所有学生都在学校。
T5：买凤梨2
这道题目要求我们处理多个甜度区间的推荐，并回答多个查询，每个查询询问某个区间内有多少个甜度被至少
本书推荐。我们需要高效地处理这些区间和查询。
解决思路
- 差分数组处理区间：使用差分数组来统计每个甜度被多少本书推荐。
- 前缀和数组：将差分数组转换为前缀和数组，得到每个甜度被推荐的总次数。
- 合适甜度标记：创建一个数组标记哪些甜度是被至少 本书推荐的。
- 前缀和优化查询：使用前缀和数组来快速回答每个查询区间内合适甜度的数量。
解决代码
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, q;
cin >> n >> k >> q;
const int MAX = 200000 + 5;
vector<int> diff(MAX + 2, 0);
for (int i = 0; i < n; ++i) {
int l, r;
cin >> l >> r;
diff[l]++;
diff[r + 1]--;
}
vector<int> count(MAX + 1, 0);
for (int i = 1; i <= MAX; ++i) {
count[i] = count[i - 1] + diff[i];
}
vector<int> suitable(MAX + 1, 0);
for (int i = 1; i <= MAX; ++i) {
suitable[i] = (count[i] >= k) ? 1 : 0;
}
vector<int> prefix(MAX + 1, 0);
for (int i = 1; i <= MAX; ++i) {
prefix[i] = prefix[i - 1] + suitable[i];
}
while (q--) {
int l, r;
cin >> l >> r;
cout << prefix[r] - prefix[l - 1] << '\n';
}
return 0;
}
代码解释
- 差分数组处理区间：使用差分数组
diff来记录每个甜度区间的开始和结束，这样可以高效地统计每个甜度被推荐的次数。 - 前缀和数组计算推荐次数：通过差分数组计算前缀和
count，得到每个甜度被推荐的总次数。 - 标记合适甜度：创建数组
suitable，标记哪些甜度是被至少 本书推荐的。 - 前缀和优化查询：构建前缀和数组
prefix，使得每个查询可以通过prefix[r] - prefix[l - 1]快速得到区间 内合适甜度的数量。
这种方法确保了我们能够高效地处理大规模数据，并在常数时间内回答每个查询。
有帮助，赞一个