BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（初中组） 第 20 题

第 3 题

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

int main(){
    char a[259] = "";
    int len, j, i, num;
    cin >> a;
    len = strlen(a);
    for (i = 0; i < len;) {
        if (a[i] == a[i + 1]) {
            for (num = 2, j = i + 2; a[i] == a[j]; j++)
                num++;
            cout << a[i] << num;
            i = j;
        } else {
            cout << a[i];
            i++;
        }
    }
    return 0;
}

输入：$\tt{abaaaacaaadabcbbbbcccceffffgh}$

这题是经典的字符串压缩（Run-Length Encoding），拿到题先别急着看选项，把代码逻辑顺一遍：外层循环负责跳过一个字符块，内层循环负责数连续相同的个数，最后输出字符和计数。输入是'abaaaacaaadabcbbbbcccceffffgh'，按这个逻辑跑一遍就能得到答案。

很多学生会把压缩规则记混，以为是把所有连续段都压缩成'字符 + 数量'的形式，或者把单个字符也压缩成'字符 + 1'。但本题的写法里，只有当检测到相邻字符相同时才进入内层循环计数，且一旦检测到不相等就立即输出并跳出内层循环，这意味着单个字符不会被压缩成'字符 + 1'，而是直接输出字符。另外，学生容易忽略循环变量的更新时机，比如在内层循环结束后没有正确更新外层循环的索引 i，导致死循环或漏掉字符。

这道题考查的是基础算法中的字符串压缩（Run-Length Encoding）思想，核心在于如何识别连续相同的字符块，并统计其长度。命题人喜欢在这种看似简单的模拟题里挖坑，比如混淆压缩规则（是否压缩单个字符）、循环变量更新位置、以及边界条件处理。学生拿到题时，最容易犯的错误是机械地套用‘字符 + 数量’的输出格式，而忽略了代码中具体的逻辑分支。

我们先把代码逻辑理顺：程序读入一个字符串 a，用 len 记录其长度。外层循环 for (i = 0; i < len;) 负责遍历整个字符串，但注意这里的 i 不是每次加 1，而是根据内部逻辑动态更新。在内层，它首先检查 a[i] 和 a[i+1] 是否相等。如果不相等，说明当前字符是孤立的，直接输出 a[i]，然后 i++ 继续下一个。如果相等，就说明发现了一个连续块，于是进入内层循环 for (num = 2, j = i + 2; a[i] == a[j]; j++)，从 i+2 开始往后数，只要还等于 a[i]，num 就加 1，j 也往后移。当内层循环结束时，j 指向的是第一个不等于 a[i] 的位置，此时 num 已经统计好了连续块的长度。接着输出 a[i] << num，然后把 i 直接跳到 j，这样外层循环就能接着处理下一个新块。

现在用这个逻辑去跑输入：'abaaaacaaadabcbbbbcccceffffgh'。

• 第一个字符 'a'，后面是 'b'，不相等，输出 'a'，i 变成 1。
• 第二个字符 'b'，后面是 'a'，不相等，输出 'b'，i 变成 2。
• 第三个字符 'a'，后面是 'a'，相等，进入内层循环：j 从 4 开始，a[4]='a'，num=3；j=5，a[5]='a'，num=4；j=6，a[6]='c'，不相等，跳出。输出 'a4'，i 跳到 6。
• i=6 是 'c'，后面是 'a'，不相等，输出 'c'，i=7。
• i=7 是 'a'，后面是 'a'，相等，内层循环：j=9，a[9]='a'，num=3；j=10，a[10]='d'，不相等。输出 'a3'，i=10。
• 依此类推，直到处理完所有字符。

最终输出结果是：'aba4ca3dabcb4c4ef4gh'，对应选项 B。

避坑方面，最容易错的是以为单个字符也会被压缩成 '字符 + 1'，比如把开头的 'a' 输出成 'a1'，或者把中间的 'c' 输出成 'c1'，这样就会得到类似 D 或 C 的选项。实际上代码里只有当检测到相邻相等时才压缩，单个字符直接输出。另一个坑是循环变量更新，如果学生手动模拟时把 i 更新成 i+1 而不是跳到 j，就会漏掉后面的字符，导致结果偏短。还有边界情况：字符串末尾如果是一个连续块，比如 '...ffff'，内层循环结束后 j 会等于 len，此时 i=j 正好跳出外层循环，不会越界，这也是代码写得巧妙的地方。

从考频来看，字符串压缩这类题目在 CSP-J/S 和 GESP 中属于高频考点，尤其在 GESP 的 P7 和 P8 级别几乎每年都会出现变体，比如要求输出格式不同、或者需要处理多组数据。CSP-J/S 的初赛和复赛也常考类似的模拟逻辑，但往往结合数组或链表操作。近三年趋势是越来越偏向‘理解代码逻辑 + 手动模拟’，而不是单纯考数学计算，命题人喜欢在细节上设陷阱，比如循环条件、变量初始化、输出顺序等。

预测未来可能的考法：基于现有数据，这类题目大概率会继续以‘阅读程序 + 手动模拟’的形式出现，但可能会增加一层复杂度，比如要求处理多个连续块、或者在压缩过程中进行额外操作（如反转、插入字符等）。也可能出现变体，比如不直接输出字符和数量，而是要求统计某种特定模式的压缩结果。如果数据不足以支撑更具体的预测（例如没有明确的变体案例），则暂无足够依据预测，但总体方向不变：模拟 + 细节陷阱仍是主流。

总之，做这类题的关键是‘慢下来，一步一步模拟’，不要急着看选项，先把代码逻辑吃透，再结合输入逐字符推演，就能稳稳拿到正确答案。