CF939D.Love Rescue
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Valya and Tolya are an ideal pair, but they quarrel sometimes. Recently, Valya took offense at her boyfriend because he came to her in t-shirt with lettering that differs from lettering on her pullover. Now she doesn't want to see him and Tolya is seating at his room and crying at her photos all day long.
This story could be very sad but fairy godmother (Tolya's grandmother) decided to help them and restore their relationship. She secretly took Tolya's t-shirt and Valya's pullover and wants to make the letterings on them same. In order to do this, for one unit of mana she can buy a spell that can change some letters on the clothes. Your task is calculate the minimum amount of mana that Tolya's grandmother should spend to rescue love of Tolya and Valya.
More formally, letterings on Tolya's t-shirt and Valya's pullover are two strings with same length n consisting only of lowercase English letters. Using one unit of mana, grandmother can buy a spell of form (_c_1, _c_2) (where _c_1 and _c_2 are some lowercase English letters), which can arbitrary number of times transform a single letter _c_1 to _c_2 and vise-versa on both Tolya's t-shirt and Valya's pullover. You should find the minimum amount of mana that grandmother should spend to buy a set of spells that can make the letterings equal. In addition you should output the required set of spells.
瓦莉娅和托利娅是一对完美情侣,但他们有时也会吵架。最近,瓦莉娅生了男朋友的气,因为他穿着一件印有与她毛衣上不同文字的T恤来找她。现在她不想见他,而托利娅则坐在自己房间里,整天看着她的照片哭泣。
这个故事本可能非常悲伤,但仙女教母(托利娅的祖母)决定帮助他们,修复他们的感情。她悄悄取走了托利娅的T恤和瓦莉娅的毛衣,希望让两件衣服上的文字变得完全相同。为此,她每花费1单位魔力值,就可以购买一个能修改衣物上字母的魔法咒语。你的任务是计算出托利娅的祖母为拯救托利娅与瓦莉娅的爱情所需花费的最少魔力值。
更形式化地:托利娅T恤与瓦莉娅毛衣上的文字是两个长度均为 $ n $ 的字符串,且仅由小写英文字母组成。每花费1单位魔力值,祖母可购买一个形如 $ (c_1,,c_2) $ 的魔法咒语(其中 $ c_1 $ 和 $ c_2 $ 均为小写英文字母),该咒语可在两件衣物上任意多次将单个字母 $ c_1 $ 变为 $ c_2 $,或反之亦然(即双向变换)。你需要求出祖母为购买一组魔法咒语、使得两件衣物上的文字最终完全相等所需的最小魔力值;此外,还需输出这组所需的魔法咒语。
输入格式
The first line contains a single integer n (1 ≤ n ≤ 105) — the length of the letterings.
The second line contains a string with length n, consisting of lowercase English letters — the lettering on Valya's pullover.
The third line contains the lettering on Tolya's t-shirt in the same format.
第一行包含一个整数 n(1≤n≤105)—— 字母串的长度。
第二行包含一个长度为 n 的字符串,由小写英文字母组成——Valya 毛衣上的字母串。
第三行以相同格式给出 Tolya T 恤上的字母串。
输出格式
In the first line output a single integer — the minimum amount of mana t required for rescuing love of Valya and Tolya.
In the next t lines output pairs of space-separated lowercase English letters — spells that Tolya's grandmother should buy. Spells and letters in spells can be printed in any order.
If there are many optimal answers, output any.
第一行输出一个整数——营救瓦莉娅与托利娅的爱情所需的最小法力值 t。
接下来的 t 行中,每行输出一对由空格分隔的小写英文字母——即托利娅的祖母应购买的咒语。咒语及其所含字母的顺序可以任意。
若存在多个最优解,输出任意一个即可。
输入输出样例
输入#1
3 abb dad
输出#1
2 a d b a
输入#2
8 drpepper cocacola
输出#2
7 l e e d d c c p p o o r r a
说明/提示
In first example it's enough to buy two spells: ('a','d') and ('b','a'). Then first letters will coincide when we will replace letter 'a' with 'd'. Second letters will coincide when we will replace 'b' with 'a'. Third letters will coincide when we will at first replace 'b' with 'a' and then 'a' with 'd'.
在第一个例子中,只需购买两个咒语:('a','d') 和 ('b','a')。当我们把字母 'a' 替换为 'd' 时,第一个字母将变得相同;当我们把 'b' 替换为 'a' 时,第二个字母将变得相同;而当我们先将 'b' 替换为 'a'、再将 'a' 替换为 'd' 时,第三个字母将变得相同。
输入解题思路,AI测评打分。不知道怎么写?