巅峰赛#24 T1 题解 100% AC

飞的智动

2025-08-25 18:14:28

发布于：江苏

33阅读

0回复

0点赞

题目讲解

题目要求：
我们需要判断一个压缩后的字符串是否被充分压缩。充分压缩的定义是：相邻的两个压缩元素的字符互不相同。也就是说，对于压缩后的字符串中的每一个元素（由字符和长度组成），不能有连续的两个元素具有相同的字符。

输入格式：

第一行是一个整数 $k$ ，表示压缩后的字符串的元素数量。
接下来的 $k$ 行，每行是一个字符 $c_i$ 和一个整数 $num_i$ ，表示第 $i$ 个压缩元素的字符和长度。

输出格式：

如果字符串被充分压缩，输出 Yes；否则输出 No。

示例分析：

示例1：
- 输入：
```
3
a 1
b 1
c 1
```
- 解释：三个元素的字符分别是 $a$ 、 $b$ 、 $c$ ，相邻字符均不相同，因此输出 Yes。
示例2：
- 输入：
```
3
a 1
a 1
b 1
```
- 解释：前两个元素的字符都是 $a$ ，相邻字符相同，因此输出 No。

代码讲解

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

int main() {
    int k;
    cin >> k;  // 读取压缩元素的数量
    char p = '\0';  // 初始化前一个字符为空字符
    bool flag = 1;  // 标记是否充分压缩，初始为 true（充分压缩）

    for (int i = 0; i < k; i++) {
        char c;
        int num;
        cin >> c >> num;  // 读取当前字符和长度
        if (c == p) {  // 如果当前字符与前一个字符相同
            flag = 0;  // 标记为未充分压缩
        }
        p = c;  // 更新前一个字符为当前字符
    }

    cout << (flag ? "Yes" : "No");  // 根据标记输出结果
    return 0;
}

代码注释

头文件和命名空间：
```
#include <bits/stdc++.h>
using namespace std;
```
- #include <bits/stdc++.h> 是一个万能头文件，包含了所有标准库头文件。
- using namespace std 允许直接使用标准库中的名称（如 cin、cout）而不需要加 std:: 前缀。
主函数：
```
int main() {
```
- 程序的入口点。
读取输入：
```
int k;
cin >> k;
```
- 读取压缩元素的数量 $k$ 。
初始化变量：
```
char p = '\0';
bool flag = 1;
```
- $p$ 用于存储前一个字符，初始化为空字符 '\0'。
- $flag$ 是一个布尔标记，初始为 true（即 1），表示默认是充分压缩的。
循环处理每个压缩元素：
```
for (int i = 0; i < k; i++) {
    char c;
    int num;
    cin >> c >> num;
```
- 循环 $k$ 次，每次读取一个字符 $c$ 和一个整数 $num$ 。
检查相邻字符是否相同：
```
if (c == p) {
    flag = 0;
}
```
- 如果当前字符 $c$ 与前一个字符 $p$ 相同，则将 $flag$ 设为 false（即 0），表示未充分压缩。
更新前一个字符：
```
p = c;
```
- 将 $p$ 更新为当前字符 $c$ ，以便下一次比较。
输出结果：
```
cout << (flag ? "Yes" : "No");
```
- 根据 $flag$ 的值输出 Yes 或 No。
程序结束：
```
return 0;
```
- 返回 0，表示程序正常结束。

总结

算法思路：
- 遍历所有压缩元素，检查当前字符是否与前一个字符相同。
- 如果发现任何相邻字符相同的情况，立即标记为未充分压缩。
- 最后根据标记输出结果。
时间复杂度：
- 只需要一次遍历，时间复杂度为 $O(k)$ ，其中 $k$ 是压缩元素的数量。
- 由于 $k$ 最多是 $10^6$ ，这种复杂度是完全可行的。
空间复杂度：
- 只使用了常数个额外变量（ $p$ 和 $flag$ ），空间复杂度为 $O(1)$ 。