语法周赛round30

T1¶

题目大意

一天有 $24$ 小时，每小时有 $60$ 分钟。现在给出从零点（00:00）开始经过了多少分钟，请你把这时候的时间用时钟的样子画出来：比如 |0|1|:|0|0| 就代表 01:00。

题目分析

题目核心难点在“分钟—时钟”转换。我们可以按照以下思路完成这道题目。

把分钟数换成小时和分钟：用 x / 60 算出多少小时，x % 60 算出还剩多少分钟。
让数字变成两位数：比如说 $1$ 要变成 01，$3$ 要变成 03。我们可以先拿到十位和个位：
- 十位：h / 10
- 个位：h % 10 同样的方法也可以算出分钟的十位和个位。按照要求格式拼接：得到两个两位数后，将这些数字加上 | 和 : 拼在一起即可。

核心代码片段

int h = x / 60, m = x % 60;
cout << "|" << h / 10 << "|" << h % 10 << "|:|" << m / 10 << "|" << m % 10 << "|";

T3¶

题目大意

小明想乘火车旅行 $x$ 公里。车票价格如下：

前 $1\sim 10$ 公里，每公里 $20$ 元；
超过 $10$ 公里至 $50$ 公里部分，每 $5$ 公里 $80$ 元（不足 $5$ 公里也按 $5$ 公里计算）；
超过 $50$ 公里部分，每 $10$ 公里 $120$ 元（不足 $10$ 公里也按 $10$ 公里计算）。

小明可以用一张票或两张票，票的公里数可以随意拆分，目标是总费用最少。求完成 $x$ 公里所需的最小花费。

题目分析

本题的核心在于两个方面：

设计单张票的计费方法；
在所有一张票或两张票的拆分方式中，枚举求出总费用的最小值。

单张票计费方法

我们首先仅考虑一张票，计算长度为 $d$ 公里的单张车票价格：

前 $10$ 公里按每公里 $20$ 元计费；
若 $d>10$，其超出部分最多至 $50$ 公里部分，分为若干个 $5$ 公里段，不足 $5$ 公里部分按 $5$ 公里算，每段收费 $80$ 元；
若 $d>50$，其超出部分继续按照每 $10$ 公里 $120$ 元计费，若不足 $10$ 公里也按 $10$ 公里计费。

int money = 0;
money += 20 * min(d, 10);
d -= min(d, 10);
int per5km = min(d, 50 - 10) / 5;
if (min(d, 50 - 10) % 5 != 0) 
{
    per5km++;
}
money += 80 * per5km;
d -= min(d, 50 - 10);
int per10km = d / 10;
if (d % 10 != 0) 
{
    per10km++;
}
money += 120 * per10km;

枚举所有可能拆分方式

在明确一张票的计算方式后，我们可以自然地枚举 $0\leq i\leq x$，设第一张票走 $i$ 公里，第二张票走 $x−i$ 公里（可为 $0$ 公里）。对于每一组划分，计算 $i$ 公里的费用和 $x−i$ 公里的费用的总和。

在上述的所有总和中取最小值，即为答案，最终输出即可。

T4¶

题目大意

给定 $n$ 个车站和它们之间的行车时间。一些车站会短暂停留，停靠时间和停靠车站已知。你需要计算从第 $s$ 站上车到第 $t$ 站下车，你一共在车上花费了多少时间。需要注意的是，上下车站点的停靠时间不计入总时间，只有中间经过的停靠站才计算停靠时间。

题目分析

首先，我们来拆解总时间：总时间 $=$ 行车时间 $+$ 停靠时间。

计算行车时间

从第 $s$ 站上车，到第 $t$ 站下车，列车会经过 $s$ 到 $s+1$, $s+1$ 到 $s+2,\ldots ,t−1$ 到 $t$ 这一系列的路段。因此，行车时间就是这些路段的时间总和。我们可以通过一个循环，从 $i=s$ 到 $t−1$ 遍历，累加 $a_i$ 即可。

long long total_travel_time = 0;
for (int i = s; i < t; ++i) 
{
   total_travel_time += a[i];
}

计算停靠时间

题目中明确指出，只有中间经过的车站才计算停靠时间，即第 $s$ 站和第 $t$ 站的停靠时间不计入总时间。这意味着，对于每一个已知的停靠车站 $b_j$，我们都需要检查它是否在 $s\sim t$ 内。如果 $b_j>s$ 且 $b_j<t$，那么它就是一个中间经过的停靠站，其对应的停靠时间 $c_j$ 应该被加到总时间中。

long long total_stop_time = 0;
for (int i = 1; i <= k; ++i) 
{
   if (b[i] > s && b[i] < t) 
   {
      total_stop_time += c[i];
   }
}

将这两部分时间相加，即为最终的答案。

最后，$n,k$ 的最大值为 $10^5$。任何一个总时间都可能达到近似 $\approx 10^{10}$，因此需要注意使用 long long 类型来存储，以防止溢出。

T5¶

题目大意

给定一个正整数 $x$，定义一次“数字转转转”操作为将其每一位数字相加得到一个新数。例如，$375$ 经过一次操作变为 $3+7+5=15$，再次操作变为 $1+5=6$。现在，对于 $1$ 到 $n$ 的每个数字，需要对其进行 $a_i$ 次“数字转转转”操作，并输出最终的结果。

题目分析

对于每个数字 $i$（从 $1$ 到 $n$），我们将其作为初始值 $x$。然后，循环 $a_i$ 次。在一个内部循环中，计算 $x$ 的各位数字之和，并将结果赋值回。

计算各位数字之和的方法：

int sum = 0;
while (num > 0) 
{
   sum += num % 10; // 取出个位数字
   num /= 10;       // 去掉个位数字
}
return sum;

将这个逻辑应用到题目中：

// 对于从1到n的每个数字i
for (int i = 1; i <= n; ++i) 
{
    int cnt; // 当前数字i需要进行的转转转次数
    cin >> cnt;
    int x = i; // 初始值为i
    // 进行转转转操作，最多cnt次，但只要x变为个位数就停止
    for (int j = 1; j <= cnt; ++j) 
    {
        int sum = 0;
        // 计算x的各位数字之和
        while (x > 0) 
        {
            sum += x % 10;
            x /= 10;
        }
        x = sum; // 更新x为各位数字之和
        if (x < 10) // 如果x已经是小于10的个位数，则后续操作结果不变
        {    
            break;      // 跳出内层循环
        }
    }
    cout << x << " "; // 输出最终结果
}

代码中有一个 if (x < 10) { break; }，现对其作一个直观解释。

由于“数字转转转”操作的最终结果是一个个位数，并且一旦达到个位数，后续操作结果不变，这意味着我们不需要真正执行 $a_i$ 次操作。实际上，对于任何大于 $9$ 的数，经过两三次操作通常就会变成小于 $10$ 的数。例如 $99999\to 9+9+9+9+9=45\to 4+5=9$。即使 $a_i$ 非常大（例如 $10^9$），我们也不需要循环 $10^9$ 次。我们只需要循环直到当前数字变为个位数即可。一旦变为个位数，就可以直接跳出循环，输出结果。

题目中的 $a_i$ 实际上只影响循环的上限，真正决定循环次数的是 $x<10$ 的条件，次数可能远远达不到 $a_i$。因为一旦 $x$ 变为个位数，它就不会再改变，所以即使 $a_i$ 很大，我们也不需要执行那么多次操作，很少次数（两三次）的操作即可。这正是代码中的 if (x < 10) break; 的作用。

T6¶

题目大意

给定一个由多个小节拼接而成的咒语字符串，每个小节的格式是 (内容)[次数]。你需要将每个小节解压：把 内容 部分重复 次数 遍。最后，将所有解压后的小节拼接起来，并在整个结果字符串的最前面和最后面各加上一个星号 * 后输出。

题目分析

本题的核心是字符串的解析和重复拼接。我们需要遍历输入的咒语字符串，识别出每个小节的“内容”和“次数”，然后根据规则进行重复拼接。

输入的咒语是一个连续的字符串，由多个 (内容)[次数] 这样的模式拼接而成。我们可以通过遍历字符串，并根据特殊字符 (, ), [, ] 来判断当前正在读取的是“内容”还是“次数”。

我们可以维护一个状态变量，表示当前正在解析的部分：

状态 0 (初始/空闲): 没有正在解析任何部分。
状态 1 (读取内容): 当前字符属于 内容 部分。
状态 2 (读取次数): 当前字符属于 次数 部分。

当遇到不同的字符时，我们切换状态并进行相应的处理：

遇到 (: 进入“读取内容”状态 (状态 1)，清空之前存储的“内容”字符串，准备读取新的内容。
遇到 ): 退出“读取内容”状态 (状态 1)，进入“空闲”状态 (状态 0)。此时“内容”部分已完整读取。
遇到 [: 进入“读取次数”状态 (状态 2)，清空之前存储的“次数”数值，准备读取新的次数。
遇到 ]: 退出“读取次数”状态 (状态 2)，进入“空闲”状态 (状态 0)。此时“次数”部分已完整读取。此时，我们已经获取了一个完整的小节的“内容”和“次数”，可以执行解压并拼接操作。
遇到其他字符 (非特殊字符):
- 如果当前是“读取内容”状态 (状态 1)，则将字符添加到“内容”字符串中。
- 如果当前是“读取次数”状态 (状态 2)，则将字符转换为数字并累加到“次数”变量中。由于“次数”可能不止一位，需要进行数值累加，例如 cnt = cnt * 10 + (c - '0')。

最后，由于 内容 部分可能包含空格，因此不能使用 cin >> s; 来读取输入。可以应该使用 getline(cin, s); 来读取整行（含空格）的字符串。

string s;
getline(cin, s); // 读取包含空格的完整行

cout << "*"; // 输出开头的星号

string cur; // 用于存储当前小节的“内容”
int count = 0; // 用于存储当前小节的“次数”
int state = 0; // 0: 空闲, 1: 读取内容, 2: 读取次数

int n = s.size();
for (int i = 0; i < n; ++i) 
{
   char c = s[i];
   if (c == '(') 
   {
      cur.clear(); // 清空内容，准备读取新的内容
      state = 1;       // 进入读取内容状态
   } 
   else if (c == ')') 
   {
      state = 0;        // 退出读取内容状态
   } 
   else if (c == '[') 
   {
      count = 0; // 重置次数，准备读取新的次数
      state = 2;        // 进入读取次数状态
   } 
   else if (c == ']') 
   {
      // 完成一个完整的 (内容)[次数] 小节的读取
      // 将内容重复指定次数并输出
      for (int j = 0; j < count; ++j) 
      {
         cout << cur;
      }
      state = 0;        // 退出读取次数状态
   } 
   else 
   {
      // 处理普通字符 (内容或次数的数字)
      if (state == 1) // 如果在读取内容状态
      { 
         cur += c;
      } 
      else if (state == 2) // 如果在读取次数状态
      { 
         count = count * 10 + (c - '0');
      }
   }
}
cout << "*" << endl; // 输出结尾的星号和换行符

语法周赛round30

T1¶

T2¶

T3¶

T4¶

T5¶

T6¶