ACGO 挑战赛#17 非官方题解

userId_undefined

天之神-新手RE WA TLE

倔强青铜

2025-04-21 15:08:08

发布于：香港

48阅读
0回复
0点赞

T1 个人难度：简单
这道题目要求根据凤梨酥的馅料含量和凤梨占比来判断凤梨酥的等级。
根据题目的描述，我们可以得出以下几个条件：

  1. 一等凤梨酥：
    • 馅料含量占比 >= 50%。
    • 凤梨占比 >= 30%。
  2. 二等凤梨酥：
    • 馅料含量占比 >= 50%。
    • 凤梨占比 >= 15% 且 < 30%。
  3. 三等凤梨酥：
    • 任何情况不符合一等或二等的都属于三等凤梨酥。
    解题思路： 我们可以通过顺序判断这些条件：
    • 如果 a >= 50 且 b >= 30，则是一等。
    • 如果 a >= 50 且 b >= 15 且 b < 30，则是二等。 •
    其他情况属于三等。

C++实现代码：

    #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 && b < 30) {
        cout << 2 << endl;  // 二等凤梨酥
    } else {
        cout << 3 << endl;  // 三等凤梨酥
    }

    return 0;
}

复杂度分析：
• 时间复杂度：O(1)，因为只进行几个简单的判断操作。
• 空间复杂度：O(1)，只用了常量空间。 这样，我们就可以根据输入的凤梨酥的馅料含量和凤梨占比，判断其等级了。

T2个人难度：简单
题目分析： 这道题要求我们判断多少个凤梨的重量满足以下条件：

  1. 重量在 500g 到 10000g 之间。
  2. 重量是一个回文数。 对于给定的每个凤梨的重量，我们需要检查是否满足上述两个条件。若满足，则可以将其计入我们能购买的凤梨数量。
    解题思路：
  3. 判断重量是否在有效区间内：
    对于每个凤梨的重量 𝑎𝑖，检查是否满足： 500≤𝑎𝑖≤10000
  4. 判断重量是否是回文数：
    一个数字如果正着读和反着读是一样的，那它就是一个回文数。可以将重量转化为字符串，判断字符串是否等于其反转的版本。 例如，12321 是回文数，而 12345 不是回文数。
  5. 流程：
    • 读取输入数据。
    • 对每个凤梨的重量进行检查：
    • 判断其是否在合法范围内。
    • 判断其是否是回文数。
    • 统计满足条件的凤梨数量。

C++实现代码：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>  // 添加此头文件来使用 reverse 函数
using namespace std;

// 判断一个数字是否是回文数
bool isPalindrome(int x) {
    string s = to_string(x);
    string rev = s;
    reverse(rev.begin(), rev.end());  // 使用 reverse 函数
    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 i = 0; i < n; i++) {
        int weight = weights[i];
        
        // 检查重量是否在范围内且是回文数
        if (weight >= 500 && weight <= 10000 && isPalindrome(weight)) {
            count++;
        }
    }

    // 输出符合条件的凤梨数量
    cout << count << endl;
    
    return 0;
}

不要忘了#include <algorithm>
因为我刚开始忘了

复杂度分析：
• 时间复杂度：
每个凤梨的重量需要转换为字符串并反转，因此每个数字的时间复杂度是 𝑂(𝑑)，其中 𝑑 是数字的位数。对于每个凤梨，最多有 5 位（因为最大重量是 10000）。所以，每个重量检查的复杂度是 𝑂(1)。 因此，整体时间复杂度为 𝑂(𝑛)，其中 𝑛 是凤梨的数量。
• 空间复杂度：
除了输入的凤梨重量外，我们只使用了常数空间来存储一些临时变量，因此空间复杂度是 𝑂(𝑛)。

T3个人难度:稍简单
这道题目要求我们找出最长可以持续的连续集训时间，也就是说我们需要找出一个最长的连续天数，使得所有学生在这段时间内都在学校。

题目分析
每个学生在接下来的
m 天内有一个日程表，用数字 1 表示在学校，0 表示不在学校。

我们需要找出一个连续的时间段，使得所有学生在该时间段内都在学校。

解题思路
考虑每一天：
对于每一天，如果所有学生都在学校（即该天所有学生的日程表值均为 1），那么这一段时间就可以算作集训的一部分。

关键问题：
我们需要找到最长的连续天数，使得在这段时间内，所有学生的日程表都是 1。这就转化为滑动窗口问题，即对于每一天，查看从这一天开始连续多少天内，所有学生都在学校。

具体步骤：
对于每一天 i，从这一天开始，检查接下来的所有天数，直到有某个学生在某一天不在学校。
记录下连续的天数，并更新最长的连续时间段。
优化：
如果某天所有学生都在学校，则可以继续检查接下来的天数。如果某天有一个学生不在学校，则无法继续延续这段时间，应该停止。
C++代码实现

#include <iostream>
#include <vector>
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_consecutive_days = 0;

    // 遍历每一天作为开始，检查从这一天开始连续多少天所有学生都在学校
    for (int start_day = 0; start_day < m; start_day++) {
        int consecutive_days = 0;
        
        // 计算从start_day开始，连续多少天所有学生都在学校
        while (start_day + consecutive_days < m) {
            bool all_in_school = true;
            for (int i = 0; i < n; i++) {
                if (schedule[i][start_day + consecutive_days] == 0) {
                    all_in_school = false;
                    break;
                }
            }
            if (all_in_school) {
                consecutive_days++;
            } else {
                break;
            }
        }
        
        // 更新最长连续天数
        max_consecutive_days = max(max_consecutive_days, consecutive_days);
    }

    // 输出最长的连续天数
    cout << max_consecutive_days << endl;

    return 0;
}

复杂度分析：
• 时间复杂度：
外层循环遍历 m 天，内层循环对每一天检查所有 n 个学生。所以总的时间复杂度是 𝑂(𝑛×𝑚2)，在最坏情况下，最多执行 500×5002=125000000 次操作，应该在时间限制内。
• 空间复杂度：
我们使用了一个大小为 n * m 的二维数组 schedule 来存储每个学生的日程表，空间复杂度是 𝑂(𝑛×𝑚)。

T4个人难度：稍简单

题目分析
菠萝同学在工作期间想要抓住机会休息，也就是“摸鱼”。题目给定了他的工作时长和常客的光顾时间，要求我们计算他能够在不受常客打扰的时间段内摸鱼的最大次数。

常客光顾时间： 每个常客在某个时间段 [L, R] 会光顾店铺，菠萝同学不能在这些时间段摸鱼。

摸鱼时间： 菠萝同学每次摸鱼需要 a 分钟。

工作时长： 总工作时长为 T 分钟。

思路
可用时间段：
菠萝同学可以在工作时长内的某些空闲时间段摸鱼。首先，我们需要找出所有常客光顾期间的时间段，然后从总工作时长中减去这些时间段，剩下的就是他可以摸鱼的空闲时间。

合并重叠区间：
如果多个常客的光顾时间有重叠，我们需要合并这些重叠的时间段。否则，空闲时间就更大，菠萝同学能摸鱼的次数就更多。

计算空闲时间：
在合并后的常客光顾时间段之间，剩下的就是空闲时间。然后根据空闲时间计算最多能摸鱼多少次。

求解最大摸鱼次数：
在每个空闲时间段内，菠萝同学每次摸鱼需要 a 分钟，因此在该段时间内最多可以摸 空闲时间 // a 次鱼。

步骤
合并时间段：
按照常客光顾时间的起始时间排序，并合并重叠的时间段。

计算空闲时间段：
从 0 到第一个常客的光顾时间段之前的时间是空闲的，两个常客的时间段之间的时间也是空闲的，最后一个常客的光顾时间段之后的时间也是空闲的。

计算能摸鱼的次数：
对每个空闲时间段，计算可以摸鱼的最大次数。
C++代码实现

 #include <bits/stdc++.h>

using namespace std;

int main() {
    int n , L , a;
    cin >> n >> L >> a;
    vector<int> arr(2e5 + 10 , 0);
    for (int i = 0 ; i < n ; i ++) {
        int l , r;
        cin >> l >> r;
        arr[l]++;
        arr[r + 1]--;
    }
    for (int i = 1 ; i < 2e5 + 10 ; i ++) {
        arr[i] += arr[i - 1];
    }
    int ans = 0;
    int cnt = 0;
    for (int i = 1 ; i <= L ; i ++) {
        if (arr[i] == 0) {
            cnt++;
        }
        else {
            ans += cnt / a;
            cnt = 0;
        }
    }
    ans += cnt / a;
    cout << ans << endl;
}

额，时间复杂度我自己都不知道

T5个人难度：稍难

问题分析 ：
我们有多个美食书籍推荐的凤梨甜度区间，并且对于每个查询，我们需要回答该区间内有多少个甜度是“合适”的。一个甜度如果在至少 k 本书推荐的区间中出现，则视为合适。

解题思路 ：

  1. 定义合适甜度
    每本书推荐了一个甜度区间 [l, r]，如果一个甜度 x 出现于至少 k 本书的推荐区间内，则我们认为 x 是合适的。
  1. 转换问题
    对于每个甜度区间 [l, r]，我们可以使用一个“区间加法”的方法（通过差分数组实现），来标记每个甜度被多少本书推荐。
  1. 解决方案步骤：
    1. 统计甜度的出现次数：
    • 对于每本书的区间 [l, r]，在 l 位置加 1，在 r + 1 位置减 1，表示在 l 之后开始增加推荐次数，到 r + 1 结束。
    • 然后，使用前缀和计算每个甜度出现的总次数，得出每个甜度的推荐次数。
    2. 确定合适的甜度：
    • 计算出每个甜度被推荐的次数，并标记出哪些甜度被推荐的次数大于等于 k，这些甜度是合适的。
    3. 快速查询：
    • 使用前缀和来记录每个甜度合适的数量。对于查询区间 [l, r]，可以通过差分数组快速计算该区间内合适的甜度个数。

C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 200000;  // 最大甜度值

int main() {
    int n, k, q;
    cin >> n >> k >> q;

    // 定义差分数组和推荐数组
    vector<int> diff(MAX + 2, 0); // 用于记录差分
    vector<int> recommended(MAX + 2, 0); // 存储每个甜度被推荐的次数
    vector<int> valid(MAX + 2, 0); // 存储每个甜度是否合适

    // 处理每本书的推荐区间
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        diff[l] += 1;
        diff[r + 1] -= 1;
    }

    // 计算每个甜度的被推荐次数（前缀和）
    recommended[0] = diff[0];
    for (int i = 1; i <= MAX; i++) {
        recommended[i] = recommended[i - 1] + diff[i];
    }

    // 标记合适的甜度
    for (int i = 1; i <= MAX; i++) {
        if (recommended[i] >= k) {
            valid[i] = 1;
        }
    }

    // 计算合适甜度的前缀和
    vector<int> prefix(MAX + 2, 0);
    prefix[0] = valid[0];
    for (int i = 1; i <= MAX; i++) {
        prefix[i] = prefix[i - 1] + valid[i];
    }

    // 处理每个查询
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        // 查询区间[l, r]中合适甜度的数量
        cout << prefix[r] - prefix[l - 1] << endl;
    }

    return 0;
}

T6 个人难度：能做出来的都是神

userId_undefined
去预览
0/2000

全部评论 3

热门讨论