QOJ.ac

QOJ

Límite de tiempo: 1.0 s Límite de memoria: 256 MB Puntuación total: 100 Hackeable ✓

#10846. 尼尔的机器

Estadísticas

Sigmund Corp. 的技术专家 Neil Watts 博士开发了一台原型机,能够修改绝症患者的记忆。他用字符串来表示这些记忆。

在此场景中,我们使用两个长度相同的字符串,分别记为 $S$ 和 $T$。这两个字符串均仅由小写英文字母组成。字符串 $S$ 代表患者最初的记忆,而字符串 $T$ 代表目标记忆。最终目标是对字符串 $S$ 进行若干次操作,使其变得与字符串 $T$ 完全相同。

记忆修改机使用一种称为 rshift k 的基本函数进行操作,其中 $1 \le k \le 25$。该函数将字母更改为字母表中其后的第 $k$ 个字母。在此语境下,字母 $z$ 之后的字母被视为 $a$。

然而,由于记忆修改可能会改变时间线的走向,Watts 博士每次只能对字符串 $S$ 的一个后缀执行 rshift k 操作。每次操作中,$k$ 的值和后缀的长度都可以任意选择。

例如,如果对以 $w$ 开头的后缀应用 rshift 3,字符串 uvwxyz 将变为 uvzabc

由于过多的记忆操作可能导致意想不到的后果,Watts 博士需要最小化执行的操作次数。因此,他需要你的帮助来确定将字符串 $S$ 转换为字符串 $T$ 所需的最少操作次数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$),表示字符串的长度。 第二行包含一个由 $n$ 个小写英文字母组成的字符串 $S$。 第三行包含一个由 $n$ 个小写英文字母组成的字符串 $T$。

输出格式

输出一个整数,表示将字符串 $S$ 转换为字符串 $T$ 所需的最少操作次数。

样例

输入 1

4
aaaa
aaaa

输出 1

0

输入 2

9
aaaaaaaaa
aaabbbaaa

输出 2

2

输入 3

17
sofiawilumerrymee
sofiawillumarryme

输出 3

8

输入 4

32
takethesebrokenwingandlearntofly
takethesesunkeneyesandlearntosee

输出 4

12

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.