C. Manipulating History（贪心/哈希/思维/好题）

题目

题意

给定一个原始字符串 s s s，长度为1。 现有n次操作， 对于第 i i i次操作，选择当前字符串 s ′ s' s′的子串 t 2 i − 1 t_{2i-1} t2i−1​，并将该字符串替换为 t 2 i t_{2i} t2i​，得到新的字符串 s ′ ′ s'' s′′，即 s ′ ′ = s ′ . r e p l a c e ( t 2 i − 1 , t 2 i ) s''=s'.replace(t_{2i-1},t_{2i}) s′′=s′.replace(t2i−1​,t2i​) 经过n次操作后，得到最终的字符串 f f f。

现给定最终的字符串 f f f，以及打乱的 2 n 2n 2n个 t t t的字符串，求原来的字符串 s s s。

输入给定的字符串，都只由小写字母组成。 输入保证有解，且解有唯一性。

思路

乍一看，这是一道字符串查找和替换的题目。 第一反应，bfs暴搜试试，往这个方向去思考，然后就自闭了哈哈哈哈哈。

想到了就不难了；没想到，就觉得这题放在C题，是不是不合适，怀疑人生ing

我们来抓住题目的关键信息：

1. 原始字符串 s s s的长度为1
2. 题目保证有解，且解唯一

根据第一个信息，我们可以推断，题目的最终的解很简单，结合输入只包含小写字母，那我们的解就无外乎就是a到z其中一个了。

题目保证有解，且解唯一。这个替换过程，我们实际上不需要关心，我们只需要关心最终的解是谁就可以了。 实际上，我们可以把这个过程逆过来思考，也是等价的：给定原始字符串 f f f，经过n次替换后，求最终得到的字符串 s s s。 过程如下： s 1 = f . r e p l a c e ( t 2 , t 1 ) s_1=f.replace(t_2,t_1) s1​=f.replace(t2​,t1​) s 2 = s 1 . r e p l a c e ( t 4 , t 3 ) s_2=s_1.replace(t_4,t_3) s2​=s1​.replace(t4​,t3​) . . . ... ... s n = s n − 1 . r e p l a c e ( t 2 n , t 2 n − 1 ) s_n=s_{n-1}.replace(t_{2n},t_{2n-1}) sn​=sn−1​.replace(t2n​,t2n−1​)

最终得到的 s n s_n sn​即为所求 s s s。该过程中，我们不知道的是给定的 t t t的顺序，不知道给定的2n个字符串中，它们各自的位置。 但我们观察下上述替换过程，我们发现，每个字符串都出现了“两次”： t 2 t_2 t2​这个字符串是 f f f的子串，它和 f f f的子串一并出现，并被替换为 t 1 t_1 t1​。 t 1 t_1 t1​被并入 f f f后，做为新的字符串 s 1 s_1 s1​。 t 4 t_4 t4​这个字符串是 s 1 s_1 s1​的子串，它和 s 1 s_1 s1​的子串一并出现，并被替换为 t 3 t_3 t3​。 t 3 t_3 t3​被并入 s 1 s_1 s1​后，做为新的字符串 s 2 s_2 s2​。 . . . ... ...

我们发现，字符串 f f f和字符串 t 1 , t 2 , . . . , t 2 n t_1,t_2,...,t_{2n} t1​,t2​,...,t2n​，出现的字符个数都是几乎偶数个的，并巧妙的在替换过程中，相互抵消了。 唯一出现奇数次的，实际上就是我们的要求的字符串 s s s了。

最终发现，这是一道披着字符串匹配外壳的贪心题，我们只需要统计下字符数，找出那个出现次数为奇数次的字符即可。

代码

#include 
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
const int maxn = 200010;

int n;
char s[maxn];
int mp[30];
void cal() {
	int m = strlen(s);
	for (int i = 0; i