← 返回题目列表

AtCoder · agc052_e

E. 3 个字母

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

分数: 1500 点

问题陈述

一个字符串,由字母组成 A, B,和 C,称为 好,如果每两个连续字母不同。例如,字符串 ABABAB 和 ABC 很好,同时 ABBA 和 AABBCC 不是。

你有两个 好 字符串 S 和 T 长度 N。 在一次操作中,您可以选择以下任意字母 S,并将其更改为其中的另一个字母 A, B,和 C,这样 S 仍然存在 好.

转换所需的最少操作数是多少 S 进入 T? 我们可以证明它总是可以通过有限次数的操作来完成。

约束

  • 1\le N \le 5\cdot 10^5
  • S 是 好 长度的字符串 N 组成 A, B,和 C
  • T 是 好 长度的字符串 N 组成 A, B,和 C

输入

输入由标准输入按以下格式给出:

N
S
T

输出

输出变换所需的最少操作数 S 进入 T.


样本输入 1

4
CABC
CBAC

示例输出 1

6

这是一种可能的长度操作序列 6:

CABC \to BABC \to BCBC \to BCAC \to ACAC \to ABAC \to CBAC

可以证明 6 对于这种情况需要进行操作。


示例输入 2

10
ABABABABAB
BABABABABA

示例输出 2

15