309813: CF1739E. Cleaning Robot
Memory Limit：512 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Cleaning Robot
题意翻译
给定一个由 $2\times n$ 个格子组成的走廊。有一些格子是脏的。你会从 $(1,1)$ 释放一个机器人。每次操作机器人会选定离它最近的一个脏格子，移动到那个格子上并清理该格子，重复此操作直至全部脏格子被清理。 然而机器人如果在选定下一个清理的脏格子时，有两个或更多脏格子离它最近，那么机器人会崩溃。 你的任务是事先清理手动尽量少的脏格子，使得机器人可以正常清理完所有格子。 输出你清理完后剩下的脏格子数量。题目描述
Consider a hallway, which can be represented as the matrix with $ 2 $ rows and $ n $ columns. Let's denote the cell on the intersection of the $ i $ -th row and the $ j $ -th column as $ (i, j) $ . The distance between the cells $ (i_1, j_1) $ and $ (i_2, j_2) $ is $ |i_1 - i_2| + |j_1 - j_2| $ . There is a cleaning robot in the cell $ (1, 1) $ . Some cells of the hallway are clean, other cells are dirty (the cell with the robot is clean). You want to clean the hallway, so you are going to launch the robot to do this. After the robot is launched, it works as follows. While at least one cell is dirty, the robot chooses the closest (to its current cell) cell among those which are dirty, moves there and cleans it (so the cell is no longer dirty). After cleaning a cell, the robot again finds the closest dirty cell to its current cell, and so on. This process repeats until the whole hallway is clean. However, there is a critical bug in the robot's program. If at some moment, there are multiple closest (to the robot's current position) dirty cells, the robot malfunctions. You want to clean the hallway in such a way that the robot doesn't malfunction. Before launching the robot, you can clean some (possibly zero) of the dirty cells yourself. However, you don't want to do too much dirty work yourself while you have this nice, smart (yet buggy) robot to do this. Note that you cannot make a clean cell dirty. Calculate the maximum possible number of cells you can leave dirty before launching the robot, so that it doesn't malfunction.输入输出格式
输入格式
The first line contains one integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of columns in the hallway. Then two lines follow, denoting the $ 1 $ -st and the $ 2 $ -nd row of the hallway. These lines contain $ n $ characters each, where 0 denotes a clean cell and 1 denotes a dirty cell. The starting cell of the robot $ (1, 1) $ is clean.
输出格式
Print one integer — the maximum possible number of cells you can leave dirty before launching the robot, so that it doesn't malfunction.
输入输出样例
输入样例 #1
2
01
11输出样例 #1
2输入样例 #2
2
01
01输出样例 #2
2输入样例 #3
4
0101
1011输出样例 #3
4输入样例 #4
4
0000
0000输出样例 #4
0输入样例 #5
5
00011
10101输出样例 #5
4输入样例 #6
6
011111
111111输出样例 #6
8输入样例 #7
10
0101001010
1010100110输出样例 #7
6说明
In the first example, you can clean the cell $ (1, 2) $ , so the path of the robot is $ (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) $ . In the second example, you can leave the hallway as it is, so the path of the robot is $ (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) $ . In the third example, you can clean the cell $ (1, 2) $ , so the path of the robot is $ (1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4) $ . In the fourth example, the hallway is already clean. Maybe you have launched the robot earlier?Input
题意翻译
给定一个由 $2\times n$ 个格子组成的走廊。有一些格子是脏的。你会从 $(1,1)$ 释放一个机器人。每次操作机器人会选定离它最近的一个脏格子，移动到那个格子上并清理该格子，重复此操作直至全部脏格子被清理。 然而机器人如果在选定下一个清理的脏格子时，有两个或更多脏格子离它最近，那么机器人会崩溃。 你的任务是事先清理手动尽量少的脏格子，使得机器人可以正常清理完所有格子。 输出你清理完后剩下的脏格子数量。Output
**题意翻译**
给定一个由 $2 \times n$ 个格子组成的走廊。有一些格子是脏的。你将从 $(1,1)$ 位置释放一个机器人。每次操作机器人会选择离它最近的脏格子，移动到那里并清理该格子，重复此操作直到所有脏格子都被清理。
然而，如果机器人选择下一个要清理的脏格子时，有两个或两个以上的脏格子与它的距离相等，那么机器人会崩溃。
你的任务是事先手动清理尽量少的脏格子，以确保机器人可以正常清理完所有格子。
输出你清理完后剩下的脏格子数量。
**题目描述**
考虑一个走廊，可以用一个 $2$ 行 $n$ 列的矩阵来表示。我们将第 $i$ 行和第 $j$ 列交叉的单元格表示为 $(i, j)$。单元格 $(i_1, j_1)$ 和 $(i_2, j_2)$ 之间的距离是 $|i_1 - i_2| + |j_1 - j_2|$。
有一个清洁机器人在单元格 $(1, 1)$。走廊的一些单元格是干净的，其他单元格是脏的（机器人所在的单元格是干净的）。你想清洁走廊，所以你将启动机器人来做这件事。
机器人启动后，它的工作方式如下。只要至少有一个单元格是脏的，机器人就会选择离它当前单元格最近的脏单元格，移动到那里并清理它（这样单元格就不再脏了）。清理一个单元格后，机器人再次找到离它当前单元格最近的脏单元格，如此往复。这个过程一直持续到整个走廊都被清理干净。
然而，机器人的程序中有一个关键的错误。如果在某个时刻，有两个或两个以上的脏单元格与机器人当前位置的距离相等，机器人就会发生故障。
你希望以机器人不会发生故障的方式清洁走廊。在启动机器人之前，你可以自己清洁一些（可能是零个）脏单元格。然而，你不想自己做太多脏活，因为你有一个好用的、智能的（尽管有故障的）机器人来做这件事。注意，你不能让一个干净的单元格变脏。
计算在启动机器人之前，你可以留下的最大可能的脏单元格数量，以确保它不会发生故障。
**输入输出格式**
**输入格式**
第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) — 走廊的列数。
然后是两行，分别表示走廊的第 1 行和第 2 行。这些行每个包含 $n$ 个字符，其中 0 表示干净单元格，1 表示脏单元格。机器人的起始单元格 $(1, 1)$ 是干净的。
**输出格式**
打印一个整数 — 在启动机器人之前，你可以留下的最大可能的脏单元格数量，以确保它不会发生故障。
**输入输出样例**
**输入样例 #1**
```
2
01
11
```
**输出样例 #1**
```
2
```
**输入样例 #2**
```
2
01
01
```
**输出样例 #2**
```
2
```
**输入样例 #3**
```
4
0101
1011
```
**输出样例 #3**
```
4
```
**输入样例 #4**
```
4
0000
0000
```
**输出样例 #4**
```
0
```
**输入样例 #5**
```
5
00011
10101
```
**输出样例 #5**
```
4
```
**输入样例 #6**
```
6
011111
111111
```
**输出样例 #6**
```
8
```
**输入样例 #7**
```
10
0101001010
1010100110
```
**输出样例 #7**
```
6
```
**说明**
在第一个例子中，你可以清洁单元格 $(1, 2)$，所以机器人的路径是 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$。
在第二个例子中，你可以让走廊保持原样，所以机器人的路径是 $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$。
在第三个例子中，你可以清洁单元格 $(1, 2)$，所以机器人的路径是 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$。
在第四个例子中，走廊已经干净。也许你之前已经启动过机器人了？**题意翻译** 给定一个由 $2 \times n$ 个格子组成的走廊。有一些格子是脏的。你将从 $(1,1)$ 位置释放一个机器人。每次操作机器人会选择离它最近的脏格子，移动到那里并清理该格子，重复此操作直到所有脏格子都被清理。 然而，如果机器人选择下一个要清理的脏格子时，有两个或两个以上的脏格子与它的距离相等，那么机器人会崩溃。 你的任务是事先手动清理尽量少的脏格子，以确保机器人可以正常清理完所有格子。 输出你清理完后剩下的脏格子数量。 **题目描述** 考虑一个走廊，可以用一个 $2$ 行 $n$ 列的矩阵来表示。我们将第 $i$ 行和第 $j$ 列交叉的单元格表示为 $(i, j)$。单元格 $(i_1, j_1)$ 和 $(i_2, j_2)$ 之间的距离是 $|i_1 - i_2| + |j_1 - j_2|$。 有一个清洁机器人在单元格 $(1, 1)$。走廊的一些单元格是干净的，其他单元格是脏的（机器人所在的单元格是干净的）。你想清洁走廊，所以你将启动机器人来做这件事。 机器人启动后，它的工作方式如下。只要至少有一个单元格是脏的，机器人就会选择离它当前单元格最近的脏单元格，移动到那里并清理它（这样单元格就不再脏了）。清理一个单元格后，机器人再次找到离它当前单元格最近的脏单元格，如此往复。这个过程一直持续到整个走廊都被清理干净。 然而，机器人的程序中有一个关键的错误。如果在某个时刻，有两个或两个以上的脏单元格与机器人当前位置的距离相等，机器人就会发生故障。 你希望以机器人不会发生故障的方式清洁走廊。在启动机器人之前，你可以自己清洁一些（可能是零个）脏单元格。然而，你不想自己做太多脏活，因为你有一个好用的、智能的（尽管有故障的）机器人来做这件事。注意，你不能让一个干净的单元格变脏。 计算在启动机器人之前，你可以留下的最大可能的脏单元格数量，以确保它不会发生故障。 **输入输出格式** **输入格式** 第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) — 走廊的列数。 然后是两行，分别表示走廊的第 1 行和第 2 行。这些行每个包含 $n$ 个字符，其中 0 表示干净单元格，1 表示脏单元格。机器人的起始单元格 $(1, 1)$ 是干净的。 **输出格式** 打印一个整数 — 在启动机器人之前，你可以留下的最大可能的脏单元格数量，以确保它不会发生故障。 **输入输出样例** **输入样例 #1** ``` 2 01 11 ``` **输出样例 #1** ``` 2 ``` **输入样例 #2** ``` 2 01 01 ``` **输出样例 #2** ``` 2 ``` **输入样例 #3** ``` 4 0101 1011 ``` **输出样例 #3** ``` 4 ``` **输入样例 #4** ``` 4 0000 0000 ``` **输出样例 #4** ``` 0 ``` **输入样例 #5** ``` 5 00011 10101 ``` **输出样例 #5** ``` 4 ``` **输入样例 #6** ``` 6 011111 111111 ``` **输出样例 #6** ``` 8 ``` **输入样例 #7** ``` 10 0101001010 1010100110 ``` **输出样例 #7** ``` 6 ``` **说明** 在第一个例子中，你可以清洁单元格 $(1, 2)$，所以机器人的路径是 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$。 在第二个例子中，你可以让走廊保持原样，所以机器人的路径是 $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$。 在第三个例子中，你可以清洁单元格 $(1, 2)$，所以机器人的路径是 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$。 在第四个例子中，走廊已经干净。也许你之前已经启动过机器人了？
给定一个由 $2 \times n$ 个格子组成的走廊。有一些格子是脏的。你将从 $(1,1)$ 位置释放一个机器人。每次操作机器人会选择离它最近的脏格子，移动到那里并清理该格子，重复此操作直到所有脏格子都被清理。
然而，如果机器人选择下一个要清理的脏格子时，有两个或两个以上的脏格子与它的距离相等，那么机器人会崩溃。
你的任务是事先手动清理尽量少的脏格子，以确保机器人可以正常清理完所有格子。
输出你清理完后剩下的脏格子数量。
**题目描述**
考虑一个走廊，可以用一个 $2$ 行 $n$ 列的矩阵来表示。我们将第 $i$ 行和第 $j$ 列交叉的单元格表示为 $(i, j)$。单元格 $(i_1, j_1)$ 和 $(i_2, j_2)$ 之间的距离是 $|i_1 - i_2| + |j_1 - j_2|$。
有一个清洁机器人在单元格 $(1, 1)$。走廊的一些单元格是干净的，其他单元格是脏的（机器人所在的单元格是干净的）。你想清洁走廊，所以你将启动机器人来做这件事。
机器人启动后，它的工作方式如下。只要至少有一个单元格是脏的，机器人就会选择离它当前单元格最近的脏单元格，移动到那里并清理它（这样单元格就不再脏了）。清理一个单元格后，机器人再次找到离它当前单元格最近的脏单元格，如此往复。这个过程一直持续到整个走廊都被清理干净。
然而，机器人的程序中有一个关键的错误。如果在某个时刻，有两个或两个以上的脏单元格与机器人当前位置的距离相等，机器人就会发生故障。
你希望以机器人不会发生故障的方式清洁走廊。在启动机器人之前，你可以自己清洁一些（可能是零个）脏单元格。然而，你不想自己做太多脏活，因为你有一个好用的、智能的（尽管有故障的）机器人来做这件事。注意，你不能让一个干净的单元格变脏。
计算在启动机器人之前，你可以留下的最大可能的脏单元格数量，以确保它不会发生故障。
**输入输出格式**
**输入格式**
第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) — 走廊的列数。
然后是两行，分别表示走廊的第 1 行和第 2 行。这些行每个包含 $n$ 个字符，其中 0 表示干净单元格，1 表示脏单元格。机器人的起始单元格 $(1, 1)$ 是干净的。
**输出格式**
打印一个整数 — 在启动机器人之前，你可以留下的最大可能的脏单元格数量，以确保它不会发生故障。
**输入输出样例**
**输入样例 #1**
```
2
01
11
```
**输出样例 #1**
```
2
```
**输入样例 #2**
```
2
01
01
```
**输出样例 #2**
```
2
```
**输入样例 #3**
```
4
0101
1011
```
**输出样例 #3**
```
4
```
**输入样例 #4**
```
4
0000
0000
```
**输出样例 #4**
```
0
```
**输入样例 #5**
```
5
00011
10101
```
**输出样例 #5**
```
4
```
**输入样例 #6**
```
6
011111
111111
```
**输出样例 #6**
```
8
```
**输入样例 #7**
```
10
0101001010
1010100110
```
**输出样例 #7**
```
6
```
**说明**
在第一个例子中，你可以清洁单元格 $(1, 2)$，所以机器人的路径是 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$。
在第二个例子中，你可以让走廊保持原样，所以机器人的路径是 $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$。
在第三个例子中，你可以清洁单元格 $(1, 2)$，所以机器人的路径是 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$。
在第四个例子中，走廊已经干净。也许你之前已经启动过机器人了？**题意翻译** 给定一个由 $2 \times n$ 个格子组成的走廊。有一些格子是脏的。你将从 $(1,1)$ 位置释放一个机器人。每次操作机器人会选择离它最近的脏格子，移动到那里并清理该格子，重复此操作直到所有脏格子都被清理。 然而，如果机器人选择下一个要清理的脏格子时，有两个或两个以上的脏格子与它的距离相等，那么机器人会崩溃。 你的任务是事先手动清理尽量少的脏格子，以确保机器人可以正常清理完所有格子。 输出你清理完后剩下的脏格子数量。 **题目描述** 考虑一个走廊，可以用一个 $2$ 行 $n$ 列的矩阵来表示。我们将第 $i$ 行和第 $j$ 列交叉的单元格表示为 $(i, j)$。单元格 $(i_1, j_1)$ 和 $(i_2, j_2)$ 之间的距离是 $|i_1 - i_2| + |j_1 - j_2|$。 有一个清洁机器人在单元格 $(1, 1)$。走廊的一些单元格是干净的，其他单元格是脏的（机器人所在的单元格是干净的）。你想清洁走廊，所以你将启动机器人来做这件事。 机器人启动后，它的工作方式如下。只要至少有一个单元格是脏的，机器人就会选择离它当前单元格最近的脏单元格，移动到那里并清理它（这样单元格就不再脏了）。清理一个单元格后，机器人再次找到离它当前单元格最近的脏单元格，如此往复。这个过程一直持续到整个走廊都被清理干净。 然而，机器人的程序中有一个关键的错误。如果在某个时刻，有两个或两个以上的脏单元格与机器人当前位置的距离相等，机器人就会发生故障。 你希望以机器人不会发生故障的方式清洁走廊。在启动机器人之前，你可以自己清洁一些（可能是零个）脏单元格。然而，你不想自己做太多脏活，因为你有一个好用的、智能的（尽管有故障的）机器人来做这件事。注意，你不能让一个干净的单元格变脏。 计算在启动机器人之前，你可以留下的最大可能的脏单元格数量，以确保它不会发生故障。 **输入输出格式** **输入格式** 第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) — 走廊的列数。 然后是两行，分别表示走廊的第 1 行和第 2 行。这些行每个包含 $n$ 个字符，其中 0 表示干净单元格，1 表示脏单元格。机器人的起始单元格 $(1, 1)$ 是干净的。 **输出格式** 打印一个整数 — 在启动机器人之前，你可以留下的最大可能的脏单元格数量，以确保它不会发生故障。 **输入输出样例** **输入样例 #1** ``` 2 01 11 ``` **输出样例 #1** ``` 2 ``` **输入样例 #2** ``` 2 01 01 ``` **输出样例 #2** ``` 2 ``` **输入样例 #3** ``` 4 0101 1011 ``` **输出样例 #3** ``` 4 ``` **输入样例 #4** ``` 4 0000 0000 ``` **输出样例 #4** ``` 0 ``` **输入样例 #5** ``` 5 00011 10101 ``` **输出样例 #5** ``` 4 ``` **输入样例 #6** ``` 6 011111 111111 ``` **输出样例 #6** ``` 8 ``` **输入样例 #7** ``` 10 0101001010 1010100110 ``` **输出样例 #7** ``` 6 ``` **说明** 在第一个例子中，你可以清洁单元格 $(1, 2)$，所以机器人的路径是 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$。 在第二个例子中，你可以让走廊保持原样，所以机器人的路径是 $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$。 在第三个例子中，你可以清洁单元格 $(1, 2)$，所以机器人的路径是 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$。 在第四个例子中，走廊已经干净。也许你之前已经启动过机器人了？