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

题目

题意

给定一个原始字符串$s$，长度为1。
现有n次操作，
对于第$i$次操作，选择当前字符串$s^{\prime }$的子串$t_{2i-1}$，并将该字符串替换为$t_{2i}$，得到新的字符串$s^{\prime \prime }$，即$s^{\prime \prime }=s^{\prime }.replace(t_{2i-1},t_{2i})$
经过n次操作后，得到最终的字符串$f$。

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

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

思路

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

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

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

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

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

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

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

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

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

代码

#include<bits/stdc++.h> 
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 < m; ++i) {
    
		++mp[s[i]-'a'];
	}
}
void solve() {
    
	scanf("%d", &n);
	memset(mp, 0, sizeof(mp));
	n *= 2;
	while (n--) {
    
		scanf("%s", s);
		cal();
	}
	scanf("%s", s);
	cal();
	char res;
	for (int i = 0; i < 26; ++i) {
    
		if (mp[i] & 1) {
    
			res = 'a' + i;
			break;
		}
	}
	printf("%c\n", res);
}
int main() {
    
	int t;
	scanf("%d", &t);
	while (t--) {
    
		solve();
	}
}