3037 「JOISC 2019 Day3」开关游戏

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

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

你有三种操作：

• OFF 操作：选择两个整数 $p,q$ $(1\le p\le q\le N)$，关闭 $p\sim q$ 号灯；
• ON 操作：选择两个整数 $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$ 序列。

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

$$\tt 11011100\xrightarrow{\large TOG(1,4)}00101100\xrightarrow{\large ON(2,2)}01101100\xrightarrow{\large TOG(6,8)}01101011\xrightarrow{\large OFF(6,7)}01101001$$

对于所有数据，$1\le N\le 10^6$。