CF2050E.Three Strings

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你三个字符串： $a, b$ 和 $c$ ，由小写拉丁字母组成。字符串 $c$ 是通过以下方法得到的：
$1.$ 每一步都随机选择字符串 $a$ 或字符串 $b$ ，并从中删除所选字符串的第一个字符，将其添加到字符串 $c$ 的末尾，直到其中一个字符串用完为止。之后，将非空字符串的剩余字符添加到 $c$ 的末尾。
$2.$ 然后，随机更改字符串 $c$ 中的一些字符。
例如，从字符串 $a = \textcolor{red}{abra}$ 和 $b = \textcolor{blue}{cada}$ 中，在不替换字符的情况下，可以得到字符串 $\textcolor{blue}{ca}\textcolor{red}{ab}\textcolor{blue}{d}\textcolor{red}{ra}\textcolor{blue}{a}, \textcolor{red}{abra}\textcolor{blue}{cada}, \textcolor{red}{a}\textcolor{blue}{cada}\textcolor{red}{bra}$ 等。
求字符串 $c$ 中最少需要替换多少个字符。

输入格式

第一行输入一个整数 $t(1 \le t \le 10^3)$ ，表示测试用例的数量。
对于每个测试用例：

第一行输入一个只包含拉丁小写字母的字符串 $a(1 \le \lvert a \rvert \le 10^3)$ ，表示第一个字符串。
第二行输入一个只包含拉丁小写字母的字符串 $b(1 \le \vert b \rvert \le 10^3)$ ，表示第二个字符串。
第三行输入一个只包含拉丁小写字母的字符串 $c(\lvert c \rvert = \lvert a \rvert + \lvert b \rvert)$ ，表示第三个字符串。
保证 $\sum \lvert a \rvert \le 2 \times 10^3$ ，并且 $\sum \lvert b \rvert \le 2 \times 10^3$ 。

输出格式

对于每组测试数据，输出一行表示答案。

输入输出样例

输入#1

7
a
b
cb
ab
cd
acbd
ab
ba
aabb
xxx
yyy
xyxyxy
a
bcd
decf
codes
horse
codeforces
egg
annie
egaegaeg

输出#1

说明/提示

默认将字符串 $a$ 中的字母标为红色， $b$ 中的字母标为蓝色。
对于第一个测试数据： $c = \textcolor{red}{a}\textcolor{blue}{b}$ ，需要替换 $1$ 个字符。
对于第二个测试数据： $c = \textcolor{red}{a}\textcolor{blue}{c}\textcolor{red}{b}\textcolor{blue}{d}$ ，需要替换 $0$ 个字符。
对于第三个测试数据： $c = \textcolor{red}{ab}\textcolor{blue}{ba}$ ，需要替换 $2$ 个字符。
对于第四个测试数据： $c = \textcolor{red}{x}\textcolor{blue}{y}\textcolor{red}{x}\textcolor{blue}{y}\textcolor{red}{x}\textcolor{blue}{y}$ ，需要替换 $0$ 个字符。
对于第五个测试数据： $c = \textcolor{red}{a}\textcolor{blue}{bcd}$ ，需要替换 $3$ 个字符。
对于第六个测试数据： $c = \textcolor{red}{code}\textcolor{blue}{horse}\textcolor{red}{s}$ ，需要替换 $2$ 个字符。
对于第七个测试数据： $c = \textcolor{red}{eg}\textcolor{blue}{annie}\textcolor{red}{g}$ ，需要替换 $3$ 个字符。

输入解题思路，AI测评打分。不知道怎么写?

首页