← 返回题目列表

Codeforces · 1006/D

D. 两个字符串交换

中文机器翻译题面 查看原题

给定两个由小写英文字母组成的字符串 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$。 The characters of both strings have indices from $$$1$$$ to $$$n$$$, inclusive.

您可以进行以下更改:

- Choose any index $$$i$$$ ($$$1 \le i \le n$$$) and swap characters $$$a_i$$$ and $$$b_i$$$;
- 选择任意索引 $$$i$$$ ($$$1 \le i \le n$$$) 并交换字符 $$$a_i$$$ 和 $$$a_{n - i + 1}$$$;
- 选择任意索引 $$$i$$$ ($$$1 \le i \le n$$$) 并交换字符 $$$b_i$$$ 和 $$$b_{n - i + 1}$$$。

请注意,如果 $$$n$$$ 是奇数,则正式允许您将 $$$a_{\lceil\frac{n}{2}\rceil}$$$ 与 $$$a_{\lceil\frac{n}{2}\rceil}$$$ 交换(与字符串 $$$b$$$ 相同),但此举动毫无用处。您也可以交换两个相同的字符,但此操作也无用。

您必须通过按任意顺序应用上述任意数量的更改来使这些字符串相等。 But it is obvious that it may be impossible to make two strings equal by these swaps.

In one preprocess move you can replace a character in $$$a$$$ with another character.换句话说,在单个预处理移动中,您可以选择任何索引 $$$i$$$ ($$$1 \le i \le n$$$)、任何字符 $$$c$$$ 并设置 $$$a_i := c$$$。

您的任务是找到要应用的预处理移动的最小数量,以便在它们之后您可以通过应用上面列表中描述的一些更改来使字符串 $$$a$$$ 和 $$$b$$$ 相等。

Note that the number of changes you make after the preprocess moves does not matter. Also note that you cannot apply preprocess moves to the string $$$b$$$ or make any preprocess moves after the first change is made.

输入

The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of strings $$$a$$$ and $$$b$$$.

第二行包含字符串 $$$a$$$,由 $$$n$$$ 小写英文字母组成。

The third line contains the string $$$b$$$ consisting of exactly $$$n$$$ lowercase English letters.

输出

打印单个整数 - 在更改之前应用的预处理移动的最小数量,以便可以通过上面列表中的一系列更改使字符串 $$$a$$$ 等于字符串 $$$b$$$。

示例

输入 #1

7
abacaba
bacabaa

输出 #1

4

输入 #2

5
zcabd
dbacz

输出 #2

0

注意

In the first example preprocess moves are as follows: $$$a_1 := $$$'b', $$$a_3 := $$$'c', $$$a_4 := $$$'a' and $$$a_5:=$$$'b'. Afterwards, $$$a = $$$"bbcabba". Then we can obtain equal strings by the following sequence of changes: $$$swap(a_2, b_2)$$$ and $$$swap(a_2, a_6)$$$.在一系列更改之前,无法使用少于 $$$4$$$ 的预处理移动来使字符串相等,因此本示例中的答案是 $$$4$$$。

In the second example no preprocess moves are required. We can use the following sequence of changes to make $$$a$$$ and $$$b$$$ equal: $$$swap(b_1, b_5)$$$, $$$swap(a_2, a_4)$$$.