题目
题意
给定一个原始字符串
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
我们来抓住题目的关键信息：
- 原始字符串 s s s的长度为1
- 题目保证有解，且解唯一
根据第一个信息，我们可以推断，题目的最终的解很简单，结合输入只包含小写字母，那我们的解就无外乎就是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
关注
打赏
![]()
查看更多评论
