字符串变换

GitHub跳转原题关系图 Canvas 关系图返回列表

把字符替换函数视为字符集合上的置换，用二进制倍增预处理字符经过 $2^j$ 次替换后的结果。

OJ: shumeng

题目 ID: CSP202409B

难度:普及-

标签:字符串置换倍增

日期: 2026-07-31 16:21

形式化题目

给定一个字符替换函数：每个字符替换为另一个字符（未定义的字符保持不变），以及一个初始字符串 $s$ 。有 $m$ 次查询，每次给定替换次数 $k$ ，输出 $s$ 经过函数重复作用 $k$ 次后的结果。

注意字符串与字符对都用 # 包裹，字符串内部可能含空格，需要按行读取。

思路

$k$ 最大可达 $10^9$ ，逐次替换显然不可行，需要把“重复作用 $k$ 次”压缩成对数次跳转。

朴素做法：直接重复替换

先看直接模拟：每轮把整串字符同时替换一次，重复 $k$ 轮。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，直接重复执行 k 次字符替换，只适合 k 很小的数据。
#include <bits/stdc++.h>
using namespace std;

const int MAXC = 128;

int next_char[MAXC]; // 每个字符经过一次替换后的字符

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 输入行形如 #Hello World#，需要整行读取
    string line;
    getline(cin, line);
    string initial = line.substr(1, line.size() - 2); // 去掉两侧的 # 得到初始字符串

    int n;
    cin >> n;
    getline(cin, line);
    // 未定义的字符替换为自身
    for (int i = 0; i < MAXC; i++) next_char[i] = i;
    for (int i = 0; i < n; i++) {
        getline(cin, line); // 形如 #a b# 或 #x y#
        next_char[(unsigned char)line[1]] = (unsigned char)line[2];
    }

    int m;
    cin >> m;
    for (int query = 0; query < m; query++) {
        int k;
        cin >> k;
        // 每轮把整串字符同时替换一次
        string result = initial;
        for (int step = 0; step < k; step++) {
            for (int i = 0; i < (int)result.size(); i++) {
                result[i] = (char)next_char[(unsigned char)result[i]];
            }
        }
        cout << '#' << result << "#\n";
    }

    return 0;
}

复杂度与 $k$ 成正比，只适合小数据验证规则。

把替换看成字符函数

建立 next_char[ch]：未定义的字符指向自身，输入的字符对覆盖对应映射。函数作用在有限的字符集合上，是一个置换，字符永远只会在这有限集合中移动。

二进制倍增

定义 jump[j][ch] 表示字符 ch 经过 $2^j$ 次替换后得到的字符：

jump[0][ch] = f(ch), \qquad jump[j][ch] = jump[j-1][\,jump[j-1][ch]\,]。

预处理 $31$ 层即可覆盖 $k \le 10^9 < 2^{30}$ 。查询时把 $k$ 写成二进制，从低位到高位处理：第 $j$ 位为 1 就把当前字符替换为 jump[j][current]。初始字符串的每个字符独立完成这个过程，最后补回两侧的 # 输出。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXC = 128; // ASCII 字符范围
const int LOG = 31;   // 2^30 > 1e9，31 层足够覆盖最大变换次数

int next_char[MAXC];  // next_char[c] 表示字符 c 经过一次替换后的字符
int jump[LOG][MAXC];  // jump[j][c] 表示字符 c 经过 2^j 次替换后的字符

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 输入行形如 #Hello World#，需要整行读取
    string line;
    getline(cin, line);
    string initial = line.substr(1, line.size() - 2); // 去掉两侧的 # 得到初始字符串

    int n;
    cin >> n;
    getline(cin, line);
    // 未定义的字符替换为自身
    for (int i = 0; i < MAXC; i++) next_char[i] = i;
    for (int i = 0; i < n; i++) {
        getline(cin, line); // 形如 #a b# 或 #x y#
        next_char[(unsigned char)line[1]] = (unsigned char)line[2];
    }

    // 预处理跳转表：jump[j][c] = jump[j-1][ jump[j-1][c] ]
    for (int i = 0; i < MAXC; i++) jump[0][i] = next_char[i];
    for (int bit = 1; bit < LOG; bit++) {
        for (int i = 0; i < MAXC; i++) {
            jump[bit][i] = jump[bit - 1][jump[bit - 1][i]];
        }
    }

    int m;
    cin >> m;
    for (int query = 0; query < m; query++) {
        long long k;
        cin >> k;
        // 每个字符独立地完成 k 次替换：把 k 按二进制拆成若干 2^j 段
        string result;
        for (int i = 0; i < (int)initial.size(); i++) {
            int current = (unsigned char)initial[i];
            long long steps = k;
            int bit = 0;
            while (steps > 0) {
                if (steps & 1) current = jump[bit][current];
                steps >>= 1;
                bit++;
            }
            result.push_back((char)current);
        }
        cout << '#' << result << "#\n";
    }

    return 0;
}

复杂度

设初始字符串长度为 $L$ 、查询数 $m$ 、最大替换次数 $K$ 。

时间：跳转表预处理 $O(128 \log K)$ ；每次查询每个字符做 $O(\log K)$ 次跳转，总时间复杂度 $O((128 + mL) \log K)$ 。
空间：跳转表 $O(128 \log K)$ ，字符串 $O(L)$ 。

总结

重复应用同一个字符函数会形成周期，但不需要显式求周期。二进制倍增把 $k$ 次替换拆成若干 $2^j$ 次替换，既能处理 $10^9$ 的大次数，又能为所有查询复用同一张字符跳转表。

题目来自第 35 次 CSP 认证 T2，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

本题涉及字符包括大小写字母（A-Z 和 a-z）、数字（0-9）和空格共 $63$ 种。在这个字符集合上，小 P 定义了一个字符替换函数 $f(ch)$ ，表示将字符 $ch$ 替换为 $f(ch)$ 。例如 $f(a) = b$ 表示将 a 替换为 b， $f(b) = 0$ 表示将 b 替换为 0。进而可以将其扩展为字符串变换函数 $F(s)$ ，表示对字符串 s 进行变换，将 s 中每个字符 $ch$ 都替换为 $f(ch)$ 。

字符替换函数 $f$ 可表示为 $n$ 个字符对 $(ch_1, ch_2)$ ，即 $f(ch_1) = ch_2$ 。

$n$ 个字符对中， $ch_1$ 两两不同，即不会出现同时定义了 $f(a) = b$ 和 $f(a) = 0$ 的情况；
未定义的 $f(ch)$ ，可视为 $f(ch) = ch$ ，即字符 $ch$ 保持不变；
函数 $f$ 为单射，即当 $ch1 \neq ch2$ 时有 $f(ch1) \neq f(ch2)$ ，例如不会同时有 $f(b) = 0$ 和 $f(0) = 0$ （b 和 0 都被替换为 0）。

现给定初始字符串 s，试处理 $m$ 个查询：每个查询包含一个正整数 $k$ ，询问对初始字符串 s 变换 $k$ 次后的结果 $F^{k}(s)$ 。

输入格式

从标准输入读入数据。

输入共 $n + 4$ 行。

输入的第一行包含一个字符串，形如 #s#，即用两个井号字符 # 将初始字符串 s 囊括其中。

输入的第二行包含一个正整数 $n$ ，表示组成函数 $f$ 的字符对数；接下来 $n$ 行每行输入一个形如 #xy# 的字符串，表示 $f(x) = y$ 。

输入的第 $n+3$ 行包含一个正整数 $m$ ，表示查询的个数；下一行包含空格分隔的 $m$ 个正整数 $k_1, k_2, \cdots, k_m$ ，表示 $m$ 个查询。

输出格式

输出到标准输出。

输出共 $m$ 行，依次输出 $m$ 个查询的结果；输出时每行同样是一个形如 #s# 的字符串，即用两个井号把变换后的字符串 s 括起。

input1

1
2
3
4
5
6
7
8
9
10#Hello World#
6
#HH#
#e #
# r#
#re#
#oa#
#ao#
3
1 2 3

output1

1
2
3#H llarWaeld#
#HrlloeWo ld#
#Hella Warld#

子任务

前 $60\%$ 的测试数据保证初始字符串 s 仅包含小写字母，且输入的 $n$ 个字符对也皆为小写字母（即保证小写字母仅会被替换为小写字母）；

前 $80\%$ 的测试数据保证查询数量 $m \le 10$ 、变换次数 $k \le 100$ ；

全部测试数据保证 $0 < n \le 63,\ 0 < m \le 10^{3},\ 0 < k \le 10^{9}$ 且初始字符串 s 包含不超过 100 个字符。

提示

由于读入的字符串中包含空格字符，推荐使用按行读取的方式，避免读入时跳过空格（如 cin 直接读入字符串）。

C 语言：可以使用 fgets() 函数读入整行，fgets(s, count, stdin) 会从标准连续输入读入至多 count - 1 个字符，并存入字符数组 s，直到遇到换行符或文件末尾为止。在前一种情况下，s 结尾处会存有读入的换行符。也可使用 getchar() 函数逐个字符读入，如 char ch = getchar();，这种方法需手动判断是否到达行末，即返回值是否为 \n。

C++：可以使用 std::getline() 函数读入整行：std::getline(std::cin, s) 会从标准输入读入字符，并存入字符串 std::string s 中，直到换行符或文件末尾为止。在前一种情况下，换行符会从标准输入中读出，但不会存入字符串 s 中。

Python：使用 input() 函数即可读入整行。