开关游戏

NC53275. 开关游戏

描述

题目译自 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序列。

输出描述

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

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/3037

示例1

输入:

8
11011100
01101001

输出:

说明:

$\newcommand \u{ \; \! \!} \tt1 \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

输出:

示例3

输入:

18
001100010010000110
110110001000100101

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板