挑战赛#22非官方题解
2025-09-08 20:22:05
发布于：天津
第一次来写比赛题解，轻喷
仅为个人观点
| 题目 | 知识点 |
|---|---|
| 大大和1 | 数学思维、找规律 |
| 午枫的博弈 | 数学思维、找规律 |
| 小午的请求 | 数学知识 |
| 小枫爬山 | 前缀和、二分查找 |
| 午枫的双人挑战 | 贪心、优先队列 |
| 大大和2 |
大大和1
问题分析
给定一个数组，需要判断是否存在一个连续子数组，使得该子数组的最大值大于等于该子数组所有元素的和。
仔细观察和认真烧烤
-
对于任意单个元素，最大值等于和，所以总是满足条件。
-
因此，只要数组非空，一定存在这样的子数组。
解题思路
直接对于每个测试用例，输出"YES"。
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
cout << "YES\n";
return;
}
signed main() {
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
时间复杂度
空间复杂度
午枫的博弈
问题分析
这是一个两人博弈游戏，小午先手，双方轮流隐藏数字（小午隐藏奇数位置的数，小枫隐藏偶数位置的数），最后剩下一个数字时，如果是奇数则小午胜，偶数则小枫胜。
仔细观察和认真烧烤
情况1：n为奇数（奇数个数字）
-
小午先手，小枫后手，共进行 (n-1) 轮操作
-
操作轮次：小午、小枫、小午、小枫...（交替进行）
-
由于n为奇数，最后剩下的数字位置取决于操作过程
关键点：
-
小午只能隐藏奇数位置的数，小枫只能隐藏偶数位置的数
-
如果数组中存在至少一个奇数数字，小午有可能获胜
-
如果数组中全是偶数数字，小午无法获胜（因为剩下的数字必然是偶数）
情况2：n为偶数（偶数个数字）
-
小午先手，小枫后手，共进行 (n-1) 轮操作
-
操作轮次：小午、小枫、小午、小枫...（交替进行）
关键点：
-
如果数组中存在至少一个偶数数字，小枫有可能获胜
-
如果数组中全是奇数数字，小枫无法获胜（因为剩下的数字必然是奇数）
解题思路
根据n的奇偶性和数组中数字的奇偶性分布来判断：
当n为奇数时：
-
如果数组中存在奇数数字 → 小午获胜（输出"Noon"）
-
如果数组中全是偶数数字 → 小枫获胜（输出"Maple"）
当n为偶数时：
-
如果数组中存在偶数数字 → 小枫获胜（输出"Maple"）
-
如果数组中全是奇数数字 → 小午获胜（输出"Noon"）
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n;
cin >> n;
vector<int> a(n);
bool f = false, b = false;
for (auto &x : a) {
cin >> x;
if (x & 1)
f = true;
else
b = true;
}
if (n & 1) {
if (f)
cout << "Noon\n";
else
cout << "Maple\n";
} else {
if (b)
cout << "Maple\n";
else
cout << "Noon\n";
}
return 0;
}
时间复杂度
空间复杂度
小午的请求
问题分析
给定n个正整数，需要从中选出一些数，使得选出的数之和为偶数，并且这个和要尽可能大。
仔细观察和认真烧烤
众所周知，所有数字之和是最大的。那么就计算所有数字的总和
所有数之和：如果所有数的和已经是偶数，那么这就是最大的偶数和
和为奇数的情况：如果所有数的和是奇数，我们需要减去一个最小的奇数来使和变为偶数
为什么是最小的奇数：因为减去最小的奇数可以保证损失最小，从而得到最大的偶数和
解题思路
计算所有数字的总和
如果总和是偶数，直接输出总和
否则减去最小的奇数（根据小学知识，奇数-奇数=偶数）
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n;
cin >> n;
vector<int> a(n);
int ans = 0;
int mn = INT_MAX;
for (auto &x : a) {
cin >> x;
ans += x;
if (x & 1) {
mn = min(mn, x);
}
}
if (ans & 1) {
cout << ans - mn << "\n";
} else {
cout << ans << "\n";
}
return 0;
}
时间复杂度
空间复杂度
小枫爬山
问题分析
给定n个非递减的台阶高度和m个爬山者的腿长，每个爬山者只能爬过高度差不超过其腿长的台阶。需要计算每个爬山者能到达的最大高度。
仔细观察和认真烧烤
楼梯是单调递增的且爬山者只能跨过高度差 ≤ 腿长的台阶
解题思路
预处理高度差：计算相邻台阶之间的高度差数组d
计算前缀最大值：创建前缀数组pre，其中pre[i]表示前i+1个高度差中的最大值
二分查找：对于每个爬山者，在前缀数组pre中二分查找第一个大于其腿长的位置
- 这个位置表示从哪个台阶开始，高度差超过了爬山者的腿长
- 爬山者最多只能到达这个位置之前的最后一个台阶
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(m);
a[0] = 0;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (auto &x : b)
cin >> x;
vector<int> d(n);
for (int i = 0; i < n; i++) {
d[i] = a[i + 1] - a[i];
}
vector<int> pre(n);
pre[0] = d[0];
for (int i = 0; i + 1 < n; i++) {
pre[i + 1] = max(pre[i], d[i + 1]);
}
for (int i = 0; i < m; i++) {
int pos = upper_bound(pre.begin(), pre.end(), b[i]) - pre.begin();
cout << a[pos] << " ";
}
return;
}
signed main() {
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
时间复杂度
空间复杂度
午枫的双人挑战
问题分析
这是一个双人协作的关卡通关问题，小午负责解密部分，小枫负责战斗部分。游戏有 个关卡，每个关卡必须按顺序进行（解密 需要先完成解密 ）。需要计算完成k个关卡的最短时间。
仔细观察和认真烧烤
关卡必须按顺序完成，解密 需要先完成解密
总时间 = 所有完成的解密时间 + 选择的战斗时间
总而言之，解密必须一关一关解，战斗可以在解完密的关卡中选择
解题思路
前缀和预处理：计算前i个关卡解密部分的总时间pre[i] = a[0] + a[1] + ... + a[i-1]
对于每个查询k：
-
首先选择前k个关卡的战斗部分，计算初始总时间：pre[k] + sum(b[0]到b[k-1])
-
使用最大堆（优先队列）维护当前选择的k个最小的战斗时间
-
从第k个关卡开始，尝试用后面关卡的更小战斗时间替换当前选择中较大的战斗时间
-
每次替换后更新总时间，并记录最小值
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, q;
cin >> n >> q;
vector<int> a(n), b(n);
for (auto &x : a)
cin >> x;
for (auto &x : b)
cin >> x;
vector<int> pre(n + 1);
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + a[i - 1];
}
while (q--) {
int k;
cin >> k;
priority_queue<int> pq;
int sum = 0;
for (int i = 0; i < k; i++) {
pq.push(b[i]);
sum += b[i];
}
int ans = pre[k] + sum;
for (int i = k; i < n; i++) {
if (b[i] < pq.top()) {
int t = pq.top();
pq.pop();
sum = sum - t + b[i];
pq.push(b[i]);
}
ans = min(ans, pre[i + 1] + sum);
}
cout << ans << "\n";
}
return 0;
}
时间复杂度
空间复杂度
大大和2
问题分析
类似第一题，只不过是给定一个数组，需要判断是否存在所有连续子数组，使得该子数组的最大值大于等于该子数组所有元素的和。
仔细观察和认真烧烤
不会
求救大佬
解题思路
主包本来是想将数组分成两个元素一组和三个元素一组，分别判断，结果WA了八个点。
于是主包转攻暴力，WA了四个。
经过一番打补丁，终于是又A了一个点。
随后主包开始加快读，尝试多骗一点（未果）。
最后主包急眼了，直接调小了循环范围，结果AC了
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void solve() {
int n = read();
vector<int> a(n);
bool f = true;
for (int i = 0; i < n; i++) {
a[i] = read();
if (a[i] > 0) {
f = false;
}
}
if (f) {
puts("YES");
return;
}
for (int i = 0; i + 1 < n; i++) {
if (max(a[i], a[i + 1]) < a[i] + a[i + 1] || (a[i] > 0 && a[i + 1] > 0)) {
puts("NO");
return;
}
}
for (int i = 0; i + 2 < n; i++) {
if (a[i] > 0 && a[i + 1] <= 0 && a[i + 2] > 0) {
if (max({a[i], a[i + 1], a[i + 2]}) < a[i] + a[i + 1] + a[i + 2]) {
puts("NO");
return;
}
}
}
for (int i = 0; i < n; i++) {
if (a[i] <= 0)
continue;
int sum = 0;
int mx = LLONG_MIN;
int l = min(n, 10000ll);
for (int j = i; j < l; j++) {
sum += a[j];
if (a[j] > mx)
mx = a[j];
if (mx < sum) {
puts("NO");
return;
}
if (sum < 0 && j < n - 1 && a[j + 1] <= 0) {
break;
}
}
}
puts("YES");
return;
}
signed main() {
int T = read();
while (T--)
solve();
return 0;
}
时间复杂度
空间复杂度
求讲解
这是蒟蒻第一次ak挑战赛，求求了@AC君
@NoonMaple顾老师快来看我写的题解
有帮助，赞一个