非官方题解 | 挑战赛#24

杰杰

2025-11-04 15:12:31

发布于：香港

0阅读

0回复

0点赞

非官方题解 | 挑战赛#24

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平(仅供参考）

题目编号	题目标题	难度
T1	午枫喝水	入门
T2	午枫的排队	普及-
T3	午枫坐公交	普及-
T4	午枫的双向奔赴2	普及/提高-
T5	午枫的填数游戏	普及/提高-
T6	午枫的字符串反转	普及+/提高

T1 午枫喝水

题型：模拟，分支结构

题目大意

小午有一个 $a$ 毫升的杯子，小枫有一个 $b$ 毫升的杯子，而我们可以保证 $a < b$ 。一开始，两个人的被子都是空的，然后他们会执行 $k$ 此操作：（为方便表示，小午现有的水是 $wa$ ，小枫则是 $wb$ ）

如果小午的杯子已经装满水（即 $wa = a$ ），则小午把水全部喝掉（即 $wa = 0$ ）
否则，如果小枫的杯子是空的（即 $wb = 0$ ），则小枫把杯子填满（即 $wb = b$ ）
如果以上皆不满足，则将小枫杯子中的水倒入小午杯子中，直到小枫杯子为空或者小午杯子装满为止。

输出格式：小午杯子中剩的水小枫杯子中剩的水（即wa wb）

解题思路

建造两个变量模拟小午杯中的水量，小风杯中的水量。使用题目给定的分支条件，直接做即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
 	int n, a, b; cin >> n >> a >> b;
    int wu = 0, feng = 0;
    for(int i = 1; i <= n;i ++) {
     	if(wu == a) wu = 0;
        else if(feng == 0) feng = b;
        else {
         	int p = min(feng, a - wu);
            wu += p;
            feng -= p;
        }
    }
    cout << wu << " " << feng;
}

T2 午枫的排队

题型：数组

题目大意

给你一个长度为 $n$ 数组 $a$ ，其中只包括：

$-1$
$\geq 1$

的数字。其中， $-1$ 只有一个；而其他的则有 $n-1$ 个。 $-1$ 表示队头；否则，表示第 $i$ 个人站在第 $a_i$ 个人后面。请输出排队候的队列。

解题思路

创建一个 $next$ 数组，其中 $next_i$ 表示第 $i$ 个数后面的数是几。

参考代码

#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
int a[300010], nxt[300010];
int main() {
 	int n; cin >> n;
    int si;
    int head = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(a[i] == -1) head = i;
        else nxt[a[i]] = i;   
    }
    int cur = head;
    for(int i = 1; i <= n; i++) {
    	cout << cur << " ";
        cur = nxt[cur];
    }
}

T3 午枫坐公交

题型：二分答案

题目大意

给你一个长度为 $n$ 的数组 $a$ ，其中 $a_i$ 表示在这站，有多少个人会上车 / 下车。但是车内的人数不能为负数。车内一开始有一定的人数，请问，一开始的人数最少是多少，才可以让车内的人不为负数。
注：答案为最后车厢人数。

解题思路

我们可以使用二分答案，来求出最小初始车上人数。最后求出车内剩余人数即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

long long a[200010], n;

bool check(long long x) {
    long long sum = x;
 	for(long long i = 1; i <= n; i++) {
     	sum += a[i];
        if(sum < 0) return false;
    }
    return true;
}

int main() {
 	cin >> n; 
    for(int i = 1; i <= n; i++) cin >> a[i];
    long long l = 0, r = 1e18;
    long long ans = -1;
    while(l <= r) {
        long long mid = l + (r - l) / 2;
     	if(check(mid)) {
            ans = mid;
            r = mid - 1;   
        } else {
         	l = mid + 1;   
        }
    }
    long long ans1 = ans;
    for(int i = 1; i <= n; i++) {
    	ans1 += a[i];
    }
    cout << ans1;
}