跳转至

语法周赛round17

T1 应急食品

✅ 实现思路：

这道题属于基础的条件判断题。题目给定一个字符（A 或 B），我们只需要根据这个字符判断旅行者的选择，然后输出对应的结果：

  • 如果输入是 A，说明旅行者认为派蒙是应急食品，输出 food。
  • 如果输入是 B，说明旅行者认为派蒙不是应急食品，输出 paimeng。

因为题目明确说“旅行者一定是正确的”，所以我们只需根据输入直接输出对应答案。

📚 考察知识点：

  • 条件判断（if-else）
    • 判断一个字符的值，并做出不同的处理。
  • 输入输出处理
    • 正确读取一个字符输入，并根据条件输出字符串。
  • 基础题意理解
    • 阅读理解题目设定和题干逻辑，特别是“旅行者一定是正确的”这一前提。

T2 购物节

这是一道典型的贪心 + 数学模拟题。我们需要根据优惠后的价格，灵活选择单本装和十本装的组合，使得在“恰好买 n 本”的前提下，花费最少的钱。

✅ 实现思路：

  • 计算优惠后的价格：
    • 单本装变为 x - 1 元；
    • 十本装变为 y - 1 元。
  • 目标：恰好买 n 本，花钱最少。
    • 贪心策略：要先判断是单买10本更优惠还是买十本装的更优惠。
    • 单买更优惠直接单买 (x-1)*n。
    • 十本装更优惠先买十本装的，剩下的单买补齐即可t*(y-1)+n%10*(x-1) t 表示10本装的件数：

📚 考察知识点：

  • 数学建模与优化策略
    • 把现实问题抽象为数学公式，设计算法进行优化；
  • 贪心算法思想
    • 考虑那种方式更优
  • 大数计算/输入处理能力
    • 处理数据范围在 $10^9$ 的大数场景，注意效率和数据类型

示例代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n, x, y;
    cin >> x >> y >> n;
    // 判断哪个更优惠
    if ((x - 1) * 10 < y - 1) // 单买更优惠
    {
        cout << (x - 1) * n;
    }
    else
    {
        ll t = n / 10;
        cout << t * (y - 1) + n % 10 * (x - 1);
    }
    return 0;
}

T3 玉桂狗

这是一道非常经典的筛选 + 最大值查找问题，难度不高，但可以有效锻炼输入处理和条件判断能力。

✅ 实现思路：

我们有 $n$ 个玩偶，每个玩偶有：

  • 可爱度 $k$，
  • 价格 $p$。

目标是找出在预算 $R$ 元内，可购买的玩偶中可爱度最大的那个。

步骤如下：

  • 读入 $n$ 和 $R$：分别表示玩偶数量和可支配的钱数；
  • 依次读取 $n$ 个玩偶的数据；
    • 对每个玩偶，如果它的价格 $p \le R$，表示可以买；
    • 在所有可以买的玩偶中，找出最大的可爱度 $k$。
  • 输出这个最大值。

📚 考察知识点：

  • 遍历与条件判断：
    • 需要判断每个玩偶的价格是否符合预算；
  • 最大值维护：
    • 经典模式，遍历中不断更新当前最大可爱度；

示例代码

#include <bits/stdc++.h>
using namespace std;
int n, r, k, p, ans;
int main()
{
    cin >> n >> r;
    for (int i = 1; i <= n; i++)
    {
        cin >> k >> p;
        if (r >= p) // 能买到
        {
            ans = max(ans, k);  // 更新最值
        }
    }
    cout << ans;
    return 0;
}

T4 配餐

这是一道典型的映射还原题，本质是按照某个索引映射关系对原数组进行重新组织。

✅ 实现思路：

我们有：

  • 一个映射数组 r = [r₁, r₂, ..., rₙ]，表示编号为 i 的小朋友拿到了从左到右数第 rᵢ 份餐；
  • 一个参数数组 a = [a₁, a₂, ..., aₙ]，表示第 i 份餐的参数值；
  • 目标是输出每个小朋友拿到的餐的参数，也就是 a[r₁], a[r₂], ..., a[rₙ]。

注意事项：

  • 所有 rᵢ 是从 1 到 n 的排列，两两不同，可以放心使用索引。

📚 考察知识点：

  • 数组索引映射
    • 根据一个数组的值在另一个数组中查找并映射；
  • 输入输出处理效率
    • 因为 $n$ 可达 $10^5$，需避免低效操作，如频繁字符串拼接；

🧠 复杂度分析：

  • 时间复杂度：$O(n)$，只需一次遍历；
  • 空间复杂度：$O(n)$，用于保存结果；

示例代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int r[N], a[N], n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> r[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cout << a[r[i]] << " ";
    return 0;
}

T5 垃圾分类

这是一道典型的贪心模拟题，思路清晰，考察对条件判断与循环累加的掌握能力。

✅ 实现思路：

我们有：

  • n 类垃圾，每类数量为 a[i]；
  • n 个对应的专属垃圾桶，容量为 r[i]；
  • 第 n+1 个垃圾桶接受任何垃圾，但每个垃圾收费 c。

我们需要最小化花费 —— 即尽量往免费的桶里扔，多余的扔收费桶。

👇 步骤如下：

  • 初始化总费用 ans = 0；
  • 对于每类垃圾 i = 1...n：
    • 可免费扔掉的数量是 min(a[i], r[i])；
    • 多出来的垃圾数量是 max(0, a[i] - r[i])，这些垃圾需要扔进收费桶；
    • 每个多余的垃圾收费 c，所以总费用增加 c × (a[i] - r[i])（只在 a[i] > r[i] 时生效）；
  • 累加所有类的费用，输出。

🧠 复杂度分析：

  • 时间复杂度：$O(n)$，一次遍历即可；
  • 空间复杂度：$O(1)$（不计输入存储）；

📚 考察知识点：

  • 贪心思想：尽量利用免费资源，最小化付费；
  • 条件判断：是否需要向收费垃圾桶投放；
  • 累加与数学运算；
  • 输入处理与高效遍历，尤其是在 $n$ 达到 $10^6$ 时。

示例代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 5;
int r[N];
ll ans, n, c;
int main()
{
    cin >> n >> c;
    for (int i = 1; i <= n; i++) cin >> r[i];
    for (int i = 1; i <= n; i++)
    {
        int x;  // 每类垃圾数量只使用一次，直接用一个变量x代替
        cin >> x;
        // 超过的装到第n+1个垃圾桶，花费 c*(x-r[i]) 代价
        if (x > r[i]) 
         ans += c * (x - r[i]);    

    }
    cout << ans;
    return 0;
}

T6 标题修改

这是一道字符串处理的模拟题，核心是按单词为单位，对每个字母进行奇数位大写、偶数位小写的处理。

✅ 实现思路：

  • 按空格分隔原字符串 S，得到若干个单词；
  • 对每个单词：
    • 使用 while (cin >> s) 进行读入；
    • 从左到右遍历每个字符；
    • 若为第奇数个字符（下标从 1 开始），转为大写；
    • 若为第偶数个字符，转为小写；
  • 将处理后的单词用空格连接成新的字符串输出。

📌 注意点：

  • 输入是一个整行字符串，可能包含多个单词；
  • 每个单词的下标从 1 开始计数；
  • 所有输入都是小写和空格，不含其他符号；

📚 考察知识点：

  • 字符串处理与遍历；
  • 字母大小写转换；
  • 字符串的拼接与分割；

🧠 复杂度分析：

  • 时间复杂度：$O(|S|)$，每个字符遍历一次；
  • 空间复杂度：$O(|S|)$，用于保存结果字符串。

示例代码：

#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
    while (cin >> s)
    {
        for (int i = 0; i < s.size(); i++)
        {
            // 因为从0开始遍历，所以奇偶判断位置刚好相反
            if (i % 2 == 0) // 偶数下标，奇数位置，转大写
            {
                s[i] -= 32;
            }
        }
        cout << s << ' ';
    }
    return 0;
}

T7 题目名

✅ 实现思路：

  • 读取输入整数 n，范围保证在 $100 \le n \le 999$；
  • 拆解三位数：
    • 百位：int a = n / 100;
    • 十位：int b = n / 10 % 10;
    • 个位：int c = n % 10;
  • 映射规则：
    • 大写字母：char upper = 'A' + a;
    • 小写字母：char lower = 'z' - c;
    • 十位数字直接输出即可；
  • 拼接输出：
    • 使用 cout << upper << b << lower << endl;

📚 考察知识点：

  • 整数拆位技巧：

    • 通过 / 和 % 运算提取百、十、个位；

  • ASCII 字符运算：

    • 利用 'A' + 数字 获取大写；
    • 利用 'z' - 数字 获取对应小写；
  • 字符与整数之间的转换：
    • 使用 char 和 int 在输出时灵活转换；
  • 基础输出语法：
    • cout 连续输出字符与数字组成的字符串；

示例代码：

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

int main()
{
    int x, a, b, c;
    cin >> x;
    a = x / 100;
    b = x / 10 % 10;
    c = x % 10;
    char upper = 'A' + a;
    char lower = 'z' - c;
    cout << upper << b << lower;
    return 0;
}

T8 图书新编

✅ 实现思路：

  • 存储图书编码：
    • 用 string s[1005] 保存图书编码；
  • 读者需求处理：
    • 每次输入一个读者的需求长度 lent 和需求码 t；

  • 匹配逻辑：

    • 遍历所有图书编码字符串；
    • 判断其后缀是否与该需求码字符串相等：
      • 获取图书编码的长度 lens；
      • 若长度 lens < lent 不够截取，直接跳过，否则截取图书编码长度的后 lent 个字符进行匹配；
      • 采用方法 s[i].substr(lens-lent, lent)。
    • 累计匹配的数量。

  • 输出匹配数量。

📚 考察知识点：

  • 字符串数组处理：
    • 使用二维 char 数组/字符串数组进行存储；
  • 字符串后缀比较：
    • 使用 substr(pos, len) 方法截取后缀字符串 。

示例代码：

#include <bits/stdc++.h>
using namespace std;
string s[1005];
int n, q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> s[i];
    while (q--)
    {
        int lent, cnt = 0;
        string t;
        cin >> lent >> t;
        for (int i = 1; i <= n; i++)
        {
            int lens = s[i].size();
            if (lens < lent) continue;  // 长度不够截取，直接跳过
            if (s[i].substr(lens-lent, lent) == t) cnt++;   // 截取末尾lent个字符进行匹配
        }
        cout << cnt << "\n";
    }
    return 0;
}