果壳语法杯ROUND5题解

YZY Lv3
  2025-06-17 20:45:45 2025-06-17 20:45:45 Created   2025-06-17 20:45:45 2025-06-17 20:45:45 Updated      

「果壳语法杯」ROUND #5

题目名称 主要知识点 难度评定
噜噜的摇摆 字符串遍历；
自律的噜噜 等差分段求和；整数除法与取模
噜噜与 DT 算法竞赛 整数除法；总数减法
噜噜的饮食心情 简单遍历；布尔标记；条件分支
噜噜的旅行 枚举 + 欧氏距离计算

题目名称：摇摆的噜噜

题目背景

噜噜是一只热爱摇摆的生物。它根据一串表示情绪的 01 字符串 s 来决定何时摇摆，每次摇摆的强度又取决于它当前的体力值。但是体力有限，每次大幅摇摆后都会消耗体力；当遇到休息时，体力又能恢复到初始水平。

题目描述

给定一个由字符 '0'（休息）和 '1'（摇摆）组成的字符串 s，以及一个非负整数初始体力值 k。噜噜按顺序处理 s 中的每个字符：

  • 遇到 '1'：

    • 如果当前体力值为 m，则这次摇摆包含

      次基本摇摆动作；

    • 摇摆完成后，体力值减 1。如果此时体力值变为负，则摇摆完成但随后停止活动，输出 "gg"。

  • 遇到 '0'：

    • 休息一次，体力值直接恢复到初始值 k。

请计算噜噜在处理完整个 s 序列后，所完成的基本摇摆动作总次数；如果在过程中体力耗尽导致停止，则输出 "gg"。

输入格式

  • 第一行：字符串 s，长度 ，只包含字符 '0' 和 '1'。
  • 第二行：整数 k，表示初始体力值，满足 。

输出格式

  • 如果能够完成所有动作，输出一个整数，表示总的基本摇摆动作次数。
  • 如果在处理过程中体力变为负数，输出字符串 gg。

示例输入输出

输入 1

1
2
111
2

输出 1

1
gg

输入 2

1
2
110110
1

输出 2

1
gg

说明/提示

  • 在示例 1 中：
    初始体力 。

    • 第一次遇到 '1'：体力 ，摇摆 次，体力变为 。动作总次数 。
    • 第二次遇到 '1'：体力 ，摇摆 次，体力变为 。动作总次数 。
    • 第三次遇到 '1'：体力 ，摇摆 次，体力变为 。动作总次数 。此时体力变为负，摇摆已完成，但随后停止活动并输出 "gg"。

  • 在示例 2 中：
    初始体力 。

    • 第一次遇到 '1'：体力 ，摇摆 次，体力变为 。
    • 第二次遇到 '1'：体力 ，摇摆 次，体力变为 。此时体力变为负，输出 "gg" 并停止活动。

数据范围

  • 字符串 只包含 '0' 和 '1'。

解题思路：

  • 维护当前体力 stamina = k，累加结果 total = 0。
  • 遍历字符串 s：
    • 遇 '0'：stamina = k。
    • 遇 '1'：
      • 累加 到 total。
      • stamina--。
      • 若 stamina < 0，则输出 "gg" 并终止程序。
  • 若循环正常结束（未因体力耗尽而中断），则输出 total。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    string s;
    int k;
    cin >> s >> k;

    vector<long long> pow2(k + 2);
    pow2[0] = 1;
    for (int i = 1; i <= k + 1; ++i) {
        pow2[i] = pow2[i - 1] * 2;
    }

    int stamina = k;
    long long total = 0;

    for (char c : s) {
        if (c == '0') {
            stamina = k;
        } else if (c == '1') {
            total += pow2[stamina + 1] - 1;
            stamina--;
            if (stamina < 0) {
                cout << "gg" << endl;
                return 0;
            }
        }
    }
    cout << total << endl;
    return 0;
}

题目名称：自律的噜噜

题目背景

噜噜为了保持健康，决定开始进行波比跳训练。他制定了一个计划：第 1 天到第 10 天每天做 10 个波比跳，第 11 天到第 20 天每天做 11 个，第 21 天到第 30 天每天做 12 个，以此类推——每过 10 天，他的日常训练数量就增加 1 个。

题目描述

给定整数 ，表示训练的天数，计算并输出噜噜在前 天总共做了多少个波比跳。

输入格式

  • 一行，包含一个整数 （），表示训练的天数。

输出格式

  • 一行，输出一个整数 ans，表示前 天内完成的波比跳总数。

示例输入输出

输入

1
25

输出

1
270

说明/提示

  • 第 1 到第 10 天：每天 10 个，共
  • 第 11 到第 20 天：每天 11 个，共
  • 第 21 到第 25 天：每天 12 个，共
  • 总计：

数据范围

解题思路：

  • 设初始每天跳的数量为 base_jumps = 10。
  • 计算有多少个完整的10天周期：full_periods = n / 10。
  • 计算在最后一个（可能不完整的）周期中训练了多少天：remaining_days = n % 10。
  • 计算完整周期的总跳数：
    • 第 i 个完整周期（ 从 到 full_periods - 1），每天跳 base_jumps + i 个。
    • 此周期总跳数 '_' allowed only in math mode10 \times (\text{base_jumps} + i)。
    • 对所有完整周期求和：'_' allowed only in math mode\sum_{i=0}^{\text{full_periods}-1} 10 \times (\text{base_jumps} + i)。
    • 这可以展开为 '_' allowed only in math mode10 \times (\text{base_jumps} \times \text{full_periods} + \sum_{i=0}^{\text{full_periods}-1} i)
    • 即 '_' allowed only in math mode10 \times (\text{base_jumps} \times \text{full_periods} + \frac{(\text{full_periods}-1) \times \text{full_periods}}{2})。
  • 计算剩余 remaining_days 的总跳数：
    • 这些天属于第 full_periods 个周期（0-indexed），所以每天跳 base_jumps + full_periods 个。
    • 总跳数为 remaining_days '_' allowed only in math mode\times (\text{base_jumps} + \text{full_periods})。
  • 两部分相加即为答案。
  • 注意，当 n 是10的倍数时，remaining_days 会是 0，此时 full_periods 应该理解为已经完成的周期数，而 base_jumps + full_periods 这个表达式的 full_periods 对应的是下一个周期的计数。
    使用 g = n / 10 和 r = n % 10。
    • 完整 g 组总跳数：。
    • 余下 r 天，每天做 个，共 。
    • （代码中的公式 是 的等价形式，是正确的。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    int g = n / 10;
    int r = n % 10;

    long long total = 10LL * (1LL * g * (g + 1) / 2 + 9LL * g);
    total += 1LL * r * (9 + g + 1);

    cout << total << endl;
    return 0;
}

题目名称：噜噜与 DT 算法竞赛

题目背景

噜噜是一名算法竞赛爱好者，每参加四场语法周赛（weekly contest）之后，就会迎来一场算法月赛（monthly contest）。比赛编号从 1 开始，连续进行。现在，噜噜将参加编号从 1 到 的所有比赛，他想知道自己一共参加了多少场语法周赛和多少场算法月赛。

题目描述

给定正整数 ，表示比赛的最大编号（从 1 到 ）。编号序列中，每第五场（即编号为 5、10、15…）是算法月赛，其余场次是语法周赛。请统计并输出在前 场比赛中，语法周赛和算法月赛的场次数。

输入格式

  • 一行，包含一个正整数 （），表示比赛编号的上限。

输出格式

  • 一行，包含两个整数：语法周赛（weekly contests）的数量和算法月赛（monthly contests）的数量，用空格分隔。

示例输入输出

输入

1
10

输出

1
8 2

说明/提示

  • 编号 1–4、6–9 为语法周赛，共 8 场；
  • 编号 5 和 10 为算法月赛，共 2 场。

数据范围

解题思路：

  • 算法月赛是每第 5 场，所以算法月赛的场次数 monthly = n / 5。
  • 语法周赛是总场数减去算法月赛的场数：weekly = n - monthly。
  • 输出 weekly 和 monthly。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>

using namespace std;

int main() {
    long long n;
    cin >> n;

    long long monthly = n / 5;
    long long weekly = n - monthly;

    cout << weekly << " " << monthly << endl;
    return 0;
}

题目名称：噜噜的饮食心情

题目背景

噜噜是不挑食的乖宝宝，但也有三种它不能接受的食物，编号分别为：

  1. 糖醋鲤鱼 → 1
  2. 凉拌折耳根 → 2
  3. 豆汁 → 3

今天，噜噜的套餐可能包含了很多食物，甚至某些食物可能出现多次，但只要看到这三种食物中的任意一种，噜噜就会变得不开心。现在给定食物种类总数 n，以及今天套餐中包含的 m 件食物，请统计套餐中包含的这三种不可接受食物的不同编号种类数 c，并输出噜噜今天的心情。

  • c = 0 → happy
  • c = 1 → sad
  • c = 2 → no!
  • c ≥ 3 → die

题目描述

给定食物种类总数 ，以及今天套餐中包含的 件食物编号，请统计其中三种不可接受食物（编号 ）出现的不同编号数量 ，并根据 输出相应心情。

输入格式

  • 第一行：一个整数 ，表示食物编号的上限。
  • 第二行：一个整数 ，表示套餐中物品件数。
  • 第三行： 个整数 ，表示每件物品的编号。

输出格式

输出噜噜今天的心情单词。

示例输入输出

输入 1

1
2
3
5
4
3 4 5 1

输出 1

1
no!

输入 2

1
2
3
5
6
1 2 3 1 2 3

输出 2

1
die

输入 3

1
2
3
5
5
2 2 2 2 2

输出 3

1
sad

输入 4

1
2
3
5
3
4 5 3

输出 4

1
sad

说明/提示

  • 示例 1 中，套餐包含编号 1（糖醋鲤鱼）和编号 3（豆汁）两种不同的不可接受食物 ()，故输出 no!。
  • 示例 2 中，套餐包含了 1、2 和 3 三种不同的不可接受食物 ()，故输出 die。
  • 示例 3 中，套餐仅包含编号 2（凉拌折耳根）一种不可接受食物 ()，重复出现多次依然只算一种，故输出 sad。
  • 示例 4 中，套餐仅包含编号 3（豆汁）一种不可接受食物 ()，故输出 sad。

数据范围

解题思路：

  • 使用一个布尔数组 bool bad_food_present[4] = {false}; (1-indexed) 或 std::unordered_set<int> 来标记编号为 1、2、3 的食物是否在套餐中出现过。
  • 遍历输入的 个食物编号 ：
    • 如果 是 1、2 或 3，则在布尔数组中将对应项标记为 true，或者将 加入集合中。
  • 遍历完成后，统计布尔数组中 true 的数量（或者集合的大小），得到不同不可接受食物的种类数 c。
  • 根据 c 的值输出对应的心情：
    • c = 0 → happy
    • c = 1 → sad
    • c = 2 → no!
    • c ≥ 3 (即 c = 3 因为只有三种) → die
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    unordered_set<int> bad;
    for (int i = 0; i < m; ++i) {
        int x;
        cin >> x;
        if (x >= 1 && x <= 3) {
            bad.insert(x);
        }
    }

    int c = bad.size();
    if (c == 0) {
        cout << "happy" << endl;
    } else if (c == 1) {
        cout << "sad" << endl;
    } else if (c == 2) {
        cout << "no!" << endl;
    } else {
        cout << "die" << endl;
    }

    return 0;
}

题目名称：噜噜的旅行

题目背景

噜噜 非常喜欢旅行！今天，噜噜决定穿越一片神秘的草原，前往遥远的目的地。然而，草原中有一条蜿蜒的河流，河流横跨草原，长度是无限的。为了确保能够最短时间内到达目的地，噜噜决定选择一个最优的喝水点，横跨这条河流。

现给定噜噜的起始坐标 和目的地坐标 ，以及河流所在的 处。请你帮噜噜找到一个最佳的喝水点 ，使得从起点到喝水点，再到目的地的总距离最短。

题目描述

给定两个点 和 ，其中 且已知在 处有一条河流 ()，假设河流是无限长的。题目要求通过枚举所有可能的整数 坐标的喝水点 ，计算每个点的总旅行距离，并找出使总距离最短的那个 坐标。最后输出这个最优的 坐标。

输入格式

  • 第一行：两个整数 和 表示初始坐标。
  • 第二行：两个整数 和 表示目的地坐标。
  • 第三行：一个整数 表示河流所在的 坐标。

输出格式

输出一个整数 ，表示最佳喝水点的 坐标。

示例输入输出

输入 1

1
2
3
0 1
4 5
3

输出 1

1
2

输入 2

1
2
3
1 2
5 7
4

输出 2

1
3

说明/提示

示例 1：

起点为 ，目的地为 ，河流所在的 处。最优的喝水点为 ，此时总旅行距离最短。

枚举过程（部分，以整数 为例）：

  • **喝水点 (0, 3)**：

    • 从 到 的距离：
    • 从 到 的距离：
    • 总距离：

  • **喝水点 (1, 3)**：

    • 从 到 的距离：
    • 从 到 的距离：
    • 总距离：

  • **喝水点 (2, 3)**：

    • 从 到 的距离：
    • 从 到 的距离：
    • 总距离：

  • **喝水点 (3, 3)**：

    • 从 到 的距离：
    • 从 到 的距离：
    • 总距离：

  • **喝水点 (4, 3)**：

    • 从 到 的距离：
    • 从 到 的距离：
    • 总距离：

  • 喝水点 (5, 3) (此点超出了 到 的范围 ，但为了与原文对比而列出，通常枚举范围在 到 之间即可，除非题目有特殊说明)：

    • 从 到 的距离：
    • 从 到 的距离：
    • 总距离：

最短的总距离约为 5.656，此时最优喝水点为 ，对应的 坐标是 。

数据范围

  • (注意：题目中示例 与此不符，但通常竞赛题以数据范围为准。此处按 都在 处理。如果 可以是 或 等，代码中 min(x1,x2) 和 max(x1,x2) 的处理是普适的。题目描述暗示 “数据保证计算出的最优 为整数。” 是指 和 各自的范围，且 不一定小于 。原文档表格中写的是 ，这表示 小于等于 。这里以 不一定小于 的普适情况，用 来确定枚举范围。)
  • ，且
  • 数据保证计算出的最优 为整数。

解题思路：

  • 方法一（解析公式/几何光学原理）
    此问题等价于光线反射路径最短问题。可以将起点 关于河流 对称得到点 即 。然后连接 与目的地 ，这条直线与河流 的交点 就是最优喝水点。
    直线方程两点式，然后令 求 ：

    由于题目保证最优 是整数，可以直接计算此公式（需要注意浮点数精度，最后四舍五入或直接使用题目保证的整数特性）。但题目要求 “通过枚举所有可能的喝水点”，所以应使用方法二。

  • 方法二（枚举法）

    • 题目明确要求枚举，并且保证最优解 是整数。
    • 枚举喝水点 坐标。一个合理的枚举范围是 ，因为距离函数是凸函数，最小值通常在此区间内。如果 的范围更广，可以适当扩大搜索范围，例如 到 ，但对于此题，给定的 范围以及 的大小，直接遍历 是可行的。如果坐标可以非常分散，则需要三分法或解析解。鉴于数据范围 ，枚举从 到 也是一个可行的策略，或者更精确地是 到 （如果 的实际范围比 小）。
    • 对于每个枚举的整数 ：
      1. 计算起点到喝水点 的距离:
      2. 计算喝水点 到目的地的距离:
      3. 总距离 。
    • 记录使 最小的 。如果有多个 得到相同的最小距离，题目通常会说明如何选择（例如最小的 ），若无说明，任选一个即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm> 

using namespace std;

double dis(int x_val, int y_val, int x1_val, int y1_val){
    long long dx = x_val - x1_val;
    long long dy = y_val - y1_val;
    return sqrtl(dx * dx + dy * dy);
}

int main() {
    int x1, y1, x2, y2, n; 
    cin >> x1 >> y1 >> x2 >> y2 >> n;
    
    long double ans = 1e9; 
    int k = -1;            

    for(int i = min(x1,x2); i <= max(x1,x2); ++i){
        long double res = dis(x1, y1, i, n) + dis(x2, y2, i, n);
        if(res < ans){ 
            ans = res;
            k = i;
        }
    }
    
    cout << k;
    
    return 0;
}
  • Title: 果壳语法杯ROUND5题解
  • Author: YZY
  • Created at : 2025-06-17 20:45:45
  • Updated at : 2025-06-17 20:45:45
  • Link: https://blog.dtoj.team/2025/06/17/果壳语法杯ROUND5题解/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
果壳语法杯ROUND5题解
  1. 「果壳语法杯」ROUND #5
  2. 题目名称：摇摆的噜噜
    1. 题目背景
    2. 题目描述
    3. 输入格式
    4. 输出格式
    5. 示例输入输出
    6. 说明/提示
    7. 数据范围
    8. 解题思路：
  • 题目名称：自律的噜噜
    1. 题目背景
    2. 题目描述
    3. 输入格式
    4. 输出格式
    5. 示例输入输出
    6. 说明/提示
    7. 数据范围
    8. 解题思路：
  • 题目名称：噜噜与 DT 算法竞赛
    1. 题目背景
    2. 题目描述
    3. 输入格式
    4. 输出格式
    5. 示例输入输出
    6. 说明/提示
    7. 数据范围
    8. 解题思路：
  • 题目名称：噜噜的饮食心情
    1. 题目背景
    2. 题目描述
    3. 输入格式
    4. 输出格式
    5. 示例输入输出
    6. 说明/提示
    7. 数据范围
    8. 解题思路：
  • 题目名称：噜噜的旅行
    1. 题目背景
    2. 题目描述
    3. 输入格式
    4. 输出格式
    5. 示例输入输出
    6. 说明/提示
    7. 数据范围
    8. 解题思路：