CCF CSP题解：字符串变换（str）（202409-2）

题目和思路

题目描述

本题涉及字符包括大小写字母（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$ 个字符对 $(c{h}_1,c{h}_2)$，即 $f(c{h}_1)=c{h}_2$。

• $n$ 个字符对中，$ch1$ 两两不同，即不会出现同时定义了 $f(a)=b$ 和 $f(a)=0$ 的情况；
• 未定义的 $f(ch)$，可视为 $f(ch)=ch$，即字符 $ch$ 保持不变；
• 函数 $f$ 为单射，即当 $ch1=ch2$ 时有 $f(ch1)=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,...,k_m$，表示 $m$ 个查询。

输出格式

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

样例输入

#Hello World#
6
#HH#
#e #
# r#
#re#
#oa#
#ao#
3
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 103$、$0<k\le 109$ 且初始字符串 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() 函数即可读入整行。

题解

基本思路

本题定义了一个函数，将字符串的每一个字符映射为另一个字符。多次嵌套该函数，即可获得一个新的字符串。然而，如果嵌套次数足够多，将导致用时过长，因此需要优化。

实际上，该二元关系具有周期性，例如我们观察定义在$a,b,c$的函数$F$,$F(a)=b$，$F(b)=c$，$F(c)=d$，$F(d)=a$，容易看出，$F^{4k}(x)=F^{4k+4}(x)$，即一个字母经过4次函数映射，又可以变回自身。既然每个字母经过整数倍个周期就可以回到自身，那么，我们只需要找出每个字母的周期，这样，就可以极大减小$k$对整体运行时间的影响。

AC代码

基于上述思想，我们给出完整的AC代码。需要注意，由于getline函数可能会将上一行的\n读入，因此在部分位置加入getchar函数。

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

#define VS2019 1

string s;
char f[256];
vector<int>zhouqi(256);// 循环周期
int n;
int cnt = 0;

void printZhouqi() {
	for (char i = 0; i < 127; i++) {
		cout << "ch: " << i << ", zhouqi: " << zhouqi[i] << endl;
	}
}

void initF() {
	cin >> n;
#ifdef VS2019
	getchar();
#endif // VS2019
	for (int i = 0; i < 256; i++) {
		f[i] = i;
		zhouqi[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		string tmp;
		getline(cin,tmp);
		f[tmp[1]] = tmp[2];
		if (tmp[1] != tmp[2])
			zhouqi[tmp[1]] = -1;
	}

	for (int i = 0; i < 256; i++) {
		if (zhouqi[i] != -1)
			continue;
		zhouqi[i] = 0;
		char newChar = i;
		do {
			newChar = f[newChar];
			zhouqi[i]++;
		} while (i != newChar);
	}
	//printZhouqi();
}

void preprocessString(string& s) {
	getline(cin, s);
	//s.pop_back();
	//s = s.substr(1);

	//cout << s << endl;
}

string getResult(int k) {
	string ret;
	for (const auto& ch : s) {
		char newChar = ch;
		int k1 = k;
		if (zhouqi[ch] != -1)
			k1 %= zhouqi[ch];

		for (int i = 0; i < k1; i++) {
			if (newChar == f[newChar])
				zhouqi[newChar] = i + 1;
			else
				newChar = f[newChar];
		}
		ret.push_back(newChar);
	}
	return ret;
}

int main() {
	preprocessString(s);
	initF();

	int t; // query count
	cin >> t;

	//int aMagicNumber = 2;

	while (t--) {
		int k;
		cin >> k;
		//k %= aMagicNumber;
		//while (getResult(k) != getResult(k % aMagicNumber))
		//	aMagicNumber++;

		cout << getResult(k) << endl;

	}

	//cout << "Magic Number: " << aMagicNumber << endl;
}

/*
input:

#Hello World#
6
#HH#
#e #
# r#
#re#
#oa#
#ao#
3
1 2 3

*/