题解 1：时间计算问题

问题描述

题目要求将 Csvoner 的时间往前调整 15 个小时，得出 Vv 的时间，且输入与输出格式都需保持为标准的 HH:MM 格式。

在这道题中，需要特别注意几点：

1. 时区差异：Vv 的时间比 Csvoner 的时间早 15 个小时。
2. 时间合法性：需要处理小时减去 15 后可能出现的负数情况，这涉及到时间换算的循环性。
3. 输入输出格式：时间需始终保持为两位数形式（如 03:05）。

解题思路

1. 将输入的 HH:MM 字符串解析为整数，分别表示小时（hour）和分钟（minute）。
2. 将 hour 值减去 15，若结果为负数，需加上 24 以确保时间格式正确（即处理时间循环性）。
3. 输出时，小时和分钟需要分别判断是否小于 10，若是，则需补充前导零以符合 HH:MM 格式要求。

---

数学公式

• 对于小时数的计算：

  $$\text{new\_hour} = (\text{hour} - 15 + 24) \, \% \, 24 $$

• 对于分钟数不需要做任何变化，直接保留输入中的值。

---

代码实现

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

string a;  
int hour , minute;  

int main() {  
    cin >> a;  
    hour = int(a[0] - '0') * 10 + int(a[1] - '0');  
    minute = int(a[3] - '0') * 10 + int(a[4] - '0');  
    hour -= 15;  
    if(hour < 0) hour += 24;  
    if(hour < 10) cout << 0;  
    cout << hour << ":";  
    if(minute < 10) cout << 0;  
    cout << minute;  
}

---

输入输出样例

输入	输出
23:15	08:15
15:30	00:30
08:30	17:30

---

复杂度分析

• 时间复杂度：$O(1)$，因为只是简单的解析和计算，不随输入规模变化。
• 空间复杂度：$O(1)$，不需要额外的内存空间。

---

总结

这是一道典型的时间计算问题，主要考察时间调整中的循环处理、以及格式化输出的技巧。通过数学公式和逻辑判断可以轻松解决。

---

题解 2：数位和及数字根

问题描述

给定一个整数 $n$，求从 $1$ 到 $n$ 之间每个整数的 一位数位和，并将这些一位数位和累加得到总和。计算一位数位和的方法如下：

1. 对于每个数，计算其数位和，直到结果为一位数。
2. 将得到的一位数加入到结果总和中。

---

解题思路

数位和规律

1. 每个整数的 一位数位和 可通过数位和反复累加得出，称之为数字的 数字根。
2. 计算 数字根 的高效公式：$$\text{digit\_root}(x) = \begin{cases} x \mod 9 & \text{if } x \mod 9 \neq 0 \\ 9 & \text{if } x \mod 9 = 0 \text{ and } x \neq 0 \end{cases} $$
3. 对于 $1 \sim n$，每 $9$ 个数的数字根分布为 $1, 2, ..., 9$，形成周期重复。

---

总和计算

• 观察到数字根 $1 \sim n$ 的总和可以分解为：

  • 完整周期的总和：$1 + 2 + \dots + 9 = 45$
  • 剩余部分的计算：单独累加数字根。

• 公式：

  $$\text{sum} = 45 \cdot \left\lfloor \frac{n}{9} \right\rfloor + \text{remainder\_sum} $$

---

代码实现

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

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

    long long cnt = 0;  
    cnt += 45 * (n / 9);  
    n = n % 9;  
    if (n != 0) {  
        while (n) {  
            cnt += n;  
            n--;  
        }  
        cout << cnt;  
        return 0;  
    } else {  
        cout << cnt;  
    }  
}  

---

输入输出样例

输入	输出
5	15
15	66
19970111	99850548

---

复杂度分析

• 时间复杂度：$O(1)$，主要涉及周期的快速计算和余数的处理。
• 空间复杂度：$O(1)$，无需额外的存储空间。

---

总结

通过观察数字根的周期性规律和数学公式，可以快速求解超大范围内的数字根和问题，而无需逐个遍历，极大地优化了时间复杂度。

---

题解 3：字符串与质数问题

问题描述

给定一个两位数 $n$，需要生成从 $10$ 到 $n$ 之间的所有数字的拼接字符串，并统计其中所有长度为 4 的子串中是四位质数的数量。

---

解题思路

1. 字符串构建：

   • 遍历从 $10$ 到 $n$ 的所有整数，将它们逐个拼接成一个长字符串。
   • 使用数组模拟字符连接，提高效率。

2. 四位子串提取：

   • 提取拼接字符串中所有连续长度为 4 的子串，转化为整数进行处理。
   • 跳过前导零的情况，确保子串为四位数。

3. 质数判断：

   • 使用试除法判断一个数是否为质数。
   • 优化试除法：只需判断是否能被小于等于 $\sqrt{x}$ 的数整除。

---

代码实现

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

bool is_prime(int n) {  
    if (n < 2) return false;  
    for (int i = 2; i * i <= n; i++) {  
        if (n % i == 0)  
            return false;  
    }  
    return true;  
}  

int main() {  
    int n;  
    cin >> n;  
    vector<int> a;  

    for (int i = 10; i <= n; i++) {  
        a.push_back(i / 10);  
        a.push_back(i % 10);  
    }  

    int len = a.size();  
    int cnt = 0;  

    for (int i = 0; i < len - 3; i++) {  
        if (a[i] == 0) continue;  
        int num = a[i] * 1000 + a[i + 1] * 100 + a[i + 2] * 10 + a[i + 3];  
        if (is_prime(num)) cnt++;  
    }  

    cout << cnt << endl;  
}  

---

输入输出样例

输入	输出
33	3
99	18

---

复杂度分析

1. 时间复杂度：$O(n)$ 构建字符串，$O(n \cdot \sqrt{x})$ 检测子串质数。
2. 空间复杂度：$O(n)$ 存储拼接字符串。

---

总结

通过构建拼接字符串和优化的质数判断，合理实现了统计四位质数子串数量的功能。

---

题解 4：模拟转盘问题

问题描述

Csvoner 有一个写有 A, B, C, D 四个字符的方形转盘。输入两个字符串 spin 和 out：

• 字符串 spin 表示对转盘的操作，其中 'L' 表示逆时针旋转 90 度，'R' 表示顺时针旋转 90 度。
• 字符串 out 中每个字符为 'o' 或 'x'。当为 'o' 时，输出当前转盘上正面的字符。

需要根据输入的操作，依次输出 out 中每个 'o' 所对应的转盘字符。

---

解题思路

1. 初始化：使用数组 a[4] = {'A', 'B', 'C', 'D'} 表示转盘的 4 个字符。

   • a[0] 表示正面的字符，顺时针依次为 a[1], a[2], a[3]。

2. 模拟旋转：

   • 遍历字符串 spin，根据字符 L 或 R 调整指针位置 way。
     • L: 指针加 1（逆时针旋转）。
     • R: 指针减 1（顺时针旋转）。
   • 用模运算处理越界：
     • 如果 way > 3，减去 4。
     • 如果 way < 0，加上 4。

3. 处理输出：

   • 遍历 out，当字符为 'o' 时，输出当前 a[way]。

---

数学公式

• 指针更新公式：
  • 如果是逆时针旋转：way = (way + 1) % 4
  • 如果是顺时针旋转：way = (way + 3) % 4 （等价于减 1，再模 4）

---

代码实现

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

string spin; // 表示旋转操作  
string out;  // 表示输出指令  

// 转盘的字符  
char a[4] = {'A', 'B', 'C', 'D'};  

int main() {  
    cin >> spin >> out;  
    int len = spin.size();  
    int way = 0; // 指针，指向当前转盘正面  

    // 遍历 spin 和 out  
    for (int i = 0; i < len; i++) {  
        if (spin[i] == 'L') { // 逆时针旋转  
            way++;  
            if (way > 3) way -= 4;  
        } else if (spin[i] == 'R') { // 顺时针旋转  
            way--;  
            if (way < 0) way += 4;  
        }  
        if (out[i] == 'o') cout << a[way]; // 如果是 'o'，输出当前正面的字符  
    }  
}  

---

输入输出样例

示例 1

输入：

LLLRRLLRR
oxoxoxoxox

输出：

BADB

示例 2

输入：

LRLRLR
ooxoxo

输出：

AB

---

复杂度分析

1. 时间复杂度：$O(n)$，其中 $n$ 为字符串长度。

   • 遍历字符串 spin 和 out 共需 $O(n)$。
   • 每次旋转操作和输出字符的复杂度均为常数。

2. 空间复杂度：$O(1)$。

   • 使用固定长度的数组 a 和若干变量，无需额外的存储空间。

---

总结

该问题通过模拟字符串操作和转盘旋转，考察了循环数组的应用和字符串操作的逻辑处理能力。在处理循环边界时，模运算简化了逻辑。