【问题描述】
众所周知,和字符串相关的题,无非就是哈希二分马拉车,后缀数组KMP,AC自动机加上动态规划,所以说非常简单,但是今天有一道题,你就算写上前面所有算法,都过不去,这道神仙题究竟是什么呢,让我们一探究竟。 炮姐和黑子有两个字符串,他们长度相同,且都是由小写字母组成,不过既然她们要百合,起码有的字符串得一样吧,所以现在黑子有一个魔法棒,每次释放一个魔法可以将两个字符串中的任意数量的两种字母“c1”和“c2”互相任意转化,现在黑子想知道最少施法多少次可使两个字符串转化为相同的字符串。
由于这道题目难度太过巨大,ACM-ICPC世界冠军都写不出来,所以如果大家对题面有问题,请举手问出题人,相信你会豁然开朗。
【输入形式】
单组输入
第一行一个整数n,表示两个字符串的长度,1<=n<=1e5。
接下来两行只由小写字母构成的字符串表示炮姐和黑子拥有的字符串。【输出形式】
由于原题难度太过巨大,对于每组数据,现在只要求你输出最少操作次数即可。
【样例输入】
样例1: 3 abb dad 样例2: 8 drpepper cocacola
【样例输出】
样例1: 2 样例2: 7
【样例说明】
操作方式不唯一,存在多种交换方式和答案,在此只给出一种。
对于第一个样例,我们为了解释方便,我的解释方式为:第一行输出最少操作次数x,接下来输出x行,每行两个字母,表示我要相互转化的两个字母。
2
a d
b a
对于第二个样例:
7
l e
e d
d c
c p
p o
o r
r a
【评分标准】
难度等级: | 0 |
总通过次数: | 10 |
总提交次数: | 31 |