CSP-S 2021 第一轮 第29题：对于任意不含空白字符的字符串str1，先执行程序输入“θstr1”，得到输出的第

题目

#include <iostream>
#include <string>
using namespace std;

char base[64];
char table[256];

void init()
{
    for (int i = 0; i < 26; i++) base[i] = 'A' + i;
    for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
    for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
    base[62] = '+', base[63] = '/';

    for (int i = 0; i < 256; i++) table[i] = 0xff;
    for (int i = 0; i < 64; i++) table[base[i]] = i;
    table['='] = 0;
}

string encode(string str)
{
    string ret;
    int i;
    for (i = 0; i + 3 <= str.size(); i += 3) {
        ret += base[str[i] >> 2];
        ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];
        ret += base[(str[i + 1] & 0x0f) << 2 | str[i + 2] >> 6];
        ret += base[str[i + 2] & 0x3f];
    }
    if (i < str.size()) {
        ret += base[str[i] >> 2];
        if (i + 1 == str.size()) {
            ret += base[(str[i] & 0x03) << 4];
            ret += "==";
        }
        else {
            ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];
            ret += base[(str[i + 1] & 0x0f) << 2];
            ret += "=";
        }
    }
    return ret;
}

string decode(string str)
{
    string ret;
    int i;
    for (i = 0; i < str.size(); i += 4) {
        ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;
        if (str[i + 2] != '=')
            ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
        if (str[i + 3] != '=')
            ret += table[str[i + 2]] << 6 | table[str[i + 3]];
    }
    return ret;
}

int main()
{
    init();
    cout << int(table[0]) << endl;

    int opt;
    string str;
    cin >> opt >> str;
    cout << (opt ? decode(str) : encode(str)) << endl;
    return 0;
}

假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：

对于任意不含空白字符的字符串 str1，先执行程序输入0 str1，得到输出的第二行记为 str2 再执行程序输入1 str2，输出的第二行必为 str1。（ ）

选项

• T. 正确
• F. 错误

答案

T

题解

选 T（正确）。 按这道题的考查意图，encode 和 decode 是互逆操作：先编码，再解码，就会还原原字符串。

关键是看懂它如何处理二进制位。假设原来的三个字符分别为：

``text abcdefgh ijklmnop qrstuvwx ``

encode 把这 24 位重新分成四组，每组 6 位：

``text abcdef ghijkl mnopqr stuvwx ``

每组的值都在 0～63，通过 base 转成一个字符。解码时，由于初始化保证了：

``cpp table[base[i]] == i ``

所以 decode 能查回这四组数，再通过移位和按位或，重新拼出原来的三个字符。整个过程没有丢失信息。

末尾不足三个字符也能还原：

• 剩一个字符：编码后补 ==，解码时只恢复一个字符。
• 剩两个字符：编码后补 =，解码时只恢复两个字符。

例如：

``text 输入 0 A → 第二行 QQ== 输入 1 QQ== → 第二行 A ``

因此，本题判断为正确。

补充：这是按竞赛题预期的普通 ASCII 字符来分析的。[原题](https://shicj0927.github.io/files/files/2021-CSP-S1.pdf)的“任意字符串”表述不够严谨；若包含高位为 1 的字节，有符号 char 可能导致编码时数组下标为负。做本题按上述编码、解码的可逆性判断即可。