#3037. 「JOISC 2019 Day3」开关游戏

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hiuseues2

题目描述

题目译自 JOISC 2019 Day3 T2「ランプ / Lamps

走廊里有 N 盏灯,灯依次编为 1\cdots N 号。灯要么处于开启状态,要么处于关闭状态。

你有三种操作:

  • ON 操作:选择两个整数 p,q (1\le p\le q\le N) ,关闭 p\sim q 号灯;
  • OFF 操作:选择两个整数 p,q (1\le p\le q\le N) ,打开 p\sim q 号灯;
  • TOG 操作:选择两个整数 p,q (1\le p\le q\le N) ,将 p\sim q 号灯的状态取反(开→关,关→开)。

给出开始时灯的亮暗状态( 0 表示关闭, 1 表示开启),再给出目标状态,试求至少需要几次操作灯才能从开始状态变为目标状态。

输入格式

从标准输入中读入三行,第一行一个正整数 N 。接下来两行分别为灯的初始状态和目标状态,保证均为长度为 N 01 序列。

输出格式

输出到标准输出,一行一个整数,表示从开始状态变为目标状态的最少操作数。

样例

样例输入 1

8
11011100
01101001

样例输出 1

4

样例说明 1

\newcommand\u{\;\!\!}\tt 1\u1\u0\u1\u1\u1\u0\u0\xrightarrow{\large TOG(1,4)}0\u0\u1\u0\u1\u1\u0\u0\xrightarrow{\large ON(2,2)}0\u1\u1\u0\u1\u1\u0\u0\xrightarrow{\large TOG(6,8)}0\u1\u1\u0\u1\u0\u1\u1\xrightarrow{\large OFF(6,7)}0\u1\u1\u0\u1\u0\u0\u1

样例输入 2

13
1010010010100
0000111001011

样例输出 2

3

样例输入 3

18
001100010010000110
110110001000100101

样例输出 3

5

数据范围与提示

对于所有数据, 1\le N\le 10^6

子任务 1 2 3 4
分值 6 41 4 49
附加条件 N\le 18 N\le 2000 开始时灯全部处于关闭状态 无附加条件