UOJ Logo Universal Online Judge

UOJ

#353. 新年的代码

统计

SingleDog们设法进入了核心,他们发现,三台TPU主机的程序混在了一起,每个主机对应一种颜色,屏幕上出现了斑斓的色条!

具体来说,他们发现了一个长度为$n$的颜色串,每个位置是红/蓝/绿(记为 R/G/B )三个颜色中的一种。为了彻底杜绝AlphaGo的朋友圈狗粮,他们需要把这部分代码完全改写。

根据跳蚤国王发来的消息,每次你可以选择相邻的两个色块,进行一次操作,为了方便理解,记操作前的两个位置的颜色为 $c_a,c_b$ ,操作后的为 $c_a^{'},c_b^{'}$ 。

  1. 如果你选择的两个色块是同色( $c_a=c_b$ ),你可以把它们变成两种不同的新颜色(即 $c_a^{'}\neq c_b^{'},c_a\neq c_a^{'},c_b\neq c_b^{'}$ ),例如,当你选择了 GG 后,你可以将它们变为 RBBR
  2. 如果你选择的两个色块是异色( $c_a\neq c_b$ ),你可以把它们变成两种相同的新颜色(即 $c_a^{'}=c_b^{'},c_a\neq c_a^{'},c_b\neq c_b^{'}$ ),例如,当你选择了 RB 后,你可以将它们变为 GG

你的目标是把这串代码从状态 $S$ 变为状态 $T$ ,求最小步数。

输入格式

第一行一个正整数 $n$ ,表示这串代码的长度。

第二行一个长度为 $n$ 的字符串 $S$ ,表示这串代码的起始状态。

第三行一个长度为 $n$ 的字符串 $T$ ,表示这串代码的终止状态。

输出格式

输出一行一个整数,表示把这串代码从状态 $S$ 变为状态 $T$ 的最小步数。

样例一

input

3
GBR
BBB

output

3

explanation

第一次操作将 GB 改为 RR ,操作后的代码为 RRR

第二次操作将 RR 改为 BG ,操作后的代码为 BGR

第三次操作将 GR 改为 BB ,操作后的代码为 BBB

可以证明没有次数更少的操作序列。

样例二

input

4
GBRB
GRRG

output

2

explanation

第一次操作将 RB 改为 GG ,操作后的代码为 GBGG

第二次操作将 BG 改为 RR ,操作后的代码为 GRRG

可以证明没有次数更少的操作序列。

样例三

input

20
RBBGRBBGRBBBBGRBRGGB
RBGRRBRBGBRRGBBBGBGG

output

14

限制与约定

测试点编号 $n$的规模 其他
1$n \leq 10$
2
3$n = 100$存在一种步数不超过 50 且每次操作选取的 $i$ 在 $[1,n-1]$ 中随机的解
4
5
6
7$n\leq 5\times 10^5$
8
9
10

保证 $S$ 和 $T$ 只由大写字母 'R','G','B' 组成,保证存在一组操作方案将代码的状态从 $S$ 变为 $T$ 。

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

友情提示:题目难度和题目顺序没有关系

下载

样例数据下载