309605: CF1705D. Mark and Lightbulbs
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Mark and Lightbulbs
题意翻译
有两个长度为 $n$ 的 01 串 $s$ 和 $t$。你可以在 $s$ 上做一些操作： - 在 $i=2\cdots n-1$ 中选一个，满足 $s_{i-1}\neq s_{i+1}$。 - 反转 $s_i$，即若 $s_i=\text{0}$，则令 $s_i=\text{1}$，反之同理。题目描述
Mark has just purchased a rack of $ n $ lightbulbs. The state of the lightbulbs can be described with binary string $ s = s_1s_2\dots s_n $ , where $ s_i=\texttt{1} $ means that the $ i $ -th lightbulb is turned on, while $ s_i=\texttt{0} $ means that the $ i $ -th lightbulb is turned off. Unfortunately, the lightbulbs are broken, and the only operation he can perform to change the state of the lightbulbs is the following: - Select an index $ i $ from $ 2,3,\dots,n-1 $ such that $ s_{i-1}\ne s_{i+1} $ . - Toggle $ s_i $ . Namely, if $ s_i $ is $ \texttt{0} $ , set $ s_i $ to $ \texttt{1} $ or vice versa. Mark wants the state of the lightbulbs to be another binary string $ t $ . Help Mark determine the minimum number of operations to do so.输入输出格式
输入格式
The first line of the input contains a single integer $ q $ ( $ 1\leq q\leq 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 3\leq n\leq 2\cdot 10^5 $ ) — the number of lightbulbs. The second line of each test case contains a binary string $ s $ of length $ n $ — the initial state of the lightbulbs. The third line of each test case contains a binary string $ t $ of length $ n $ — the final state of the lightbulbs. It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2\cdot 10^5 $ .
输出格式
For each test case, print a line containing the minimum number of operations Mark needs to perform to transform $ s $ to $ t $ . If there is no such sequence of operations, print $ -1 $ .
输入输出样例
输入样例 #1
4
4
0100
0010
4
1010
0100
5
01001
00011
6
000101
010011输出样例 #1
2
-1
-1
5说明
In the first test case, one sequence of operations that achieves the minimum number of operations is the following. - Select $ i=3 $ , changing $ \texttt{01}\color{red}{\texttt{0}}\texttt{0} $ to $ \texttt{01}\color{red}{\texttt{1}}\texttt{0} $ . - Select $ i=2 $ , changing $ \texttt{0}\color{red}{\texttt{1}}\texttt{10} $ to $ \texttt{0}\color{red}{\texttt{0}}\texttt{10} $ . In the second test case, there is no sequence of operations because one cannot change the first digit or the last digit of $ s $ .In the third test case, even though the first digits of $ s $ and $ t $ are the same and the last digits of $ s $ and $ t $ are the same, it can be shown that there is no sequence of operations that satisfies the condition. In the fourth test case, one sequence that achieves the minimum number of operations is the following: - Select $ i=3 $ , changing $ \texttt{00}\color{red}{\texttt{0}}\texttt{101} $ to $ \texttt{00}\color{red}{\texttt{1}}\texttt{101} $ . - Select $ i=2 $ , changing $ \texttt{0}\color{red}{\texttt{0}}\texttt{1101} $ to $ \texttt{0}\color{red}{\texttt{1}}\texttt{1101} $ . - Select $ i=4 $ , changing $ \texttt{011}\color{red}{\texttt{1}}\texttt{01} $ to $ \texttt{011}\color{red}{\texttt{0}}\texttt{01} $ . - Select $ i=5 $ , changing $ \texttt{0110}\color{red}{\texttt{0}}\texttt{1} $ to $ \texttt{0110}\color{red}{\texttt{1}}\texttt{1} $ . - Select $ i=3 $ , changing $ \texttt{01}\color{red}{\texttt{1}}\texttt{011} $ to $ \texttt{01}\color{red}{\texttt{0}}\texttt{011} $ .Input
题意翻译
有两个长度为 $n$ 的 01 串 $s$ 和 $t$。你可以在 $s$ 上做一些操作： - 在 $i=2\cdots n-1$ 中选一个，满足 $s_{i-1}\neq s_{i+1}$。 - 反转 $s_i$，即若 $s_i=\text{0}$，则令 $s_i=\text{1}$，反之同理。Output
**题目大意：**
题目描述了一个关于灯泡的问题。有两个长度为 $ n $ 的二进制字符串 $ s $ 和 $ t $，表示一排灯泡的初始和最终状态，其中 $ s_i=\text{1} $ 表示第 $ i $ 个灯泡是开启的，$ s_i=\text{0} $ 表示关闭的。可以通过以下操作改变灯泡状态：
- 在 $ i=2,\dots,n-1 $ 中选择一个位置，使得 $ s_{i-1} \neq s_{i+1} $。
- 反转 $ s_i $ 的状态，即如果 $ s_i=\text{0} $，则变为 $ \text{1} $，反之亦然。
目标是使 $ s $ 变为 $ t $，需要帮助确定实现这一目标所需的最少操作次数。如果不能通过操作实现，则输出 $ -1 $。
**输入输出数据格式：**
**输入格式：**
- 第一行包含一个整数 $ q $（$ 1 \leq q \leq 10^4 $），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数 $ n $（$ 3 \leq n \leq 2 \cdot 10^5 $），表示灯泡的数量。
- 每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $，表示灯泡的初始状态。
- 每个测试用例的第三行包含一个长度为 $ n $ 的二进制字符串 $ t $，表示灯泡的最终状态。
- 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。
**输出格式：**
- 对于每个测试用例，输出一行，包含将 $ s $ 变为 $ t $ 所需执行的最少操作次数。如果不能通过操作实现，则输出 $ -1 $。
**输入输出样例：**
**输入样例 #1:**
```
4
4
0100
0010
4
1010
0100
5
01001
00011
6
000101
010011
```
**输出样例 #1:**
```
2
-1
-1
5
```
**说明：**
- 在第一个测试用例中，可以通过选择 $ i=3 $ 和 $ i=2 $ 的操作，实现 $ s $ 到 $ t $ 的转换。
- 在第二个测试用例中，由于无法改变 $ s $ 的第一个或最后一个数字，因此无法实现转换。
- 在第三个测试用例中，尽管 $ s $ 和 $ t $ 的第一个和最后一个数字相同，但可以证明没有满足条件的操作序列。
- 在第四个测试用例中，可以通过选择 $ i=3 $、$ i=2 $、$ i=4 $、$ i=5 $ 和 $ i=3 $ 的操作，实现 $ s $ 到 $ t $ 的转换。**题目大意：** 题目描述了一个关于灯泡的问题。有两个长度为 $ n $ 的二进制字符串 $ s $ 和 $ t $，表示一排灯泡的初始和最终状态，其中 $ s_i=\text{1} $ 表示第 $ i $ 个灯泡是开启的，$ s_i=\text{0} $ 表示关闭的。可以通过以下操作改变灯泡状态： - 在 $ i=2,\dots,n-1 $ 中选择一个位置，使得 $ s_{i-1} \neq s_{i+1} $。 - 反转 $ s_i $ 的状态，即如果 $ s_i=\text{0} $，则变为 $ \text{1} $，反之亦然。 目标是使 $ s $ 变为 $ t $，需要帮助确定实现这一目标所需的最少操作次数。如果不能通过操作实现，则输出 $ -1 $。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 $ q $（$ 1 \leq q \leq 10^4 $），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数 $ n $（$ 3 \leq n \leq 2 \cdot 10^5 $），表示灯泡的数量。 - 每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $，表示灯泡的初始状态。 - 每个测试用例的第三行包含一个长度为 $ n $ 的二进制字符串 $ t $，表示灯泡的最终状态。 - 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出格式：** - 对于每个测试用例，输出一行，包含将 $ s $ 变为 $ t $ 所需执行的最少操作次数。如果不能通过操作实现，则输出 $ -1 $。 **输入输出样例：** **输入样例 #1:** ``` 4 4 0100 0010 4 1010 0100 5 01001 00011 6 000101 010011 ``` **输出样例 #1:** ``` 2 -1 -1 5 ``` **说明：** - 在第一个测试用例中，可以通过选择 $ i=3 $ 和 $ i=2 $ 的操作，实现 $ s $ 到 $ t $ 的转换。 - 在第二个测试用例中，由于无法改变 $ s $ 的第一个或最后一个数字，因此无法实现转换。 - 在第三个测试用例中，尽管 $ s $ 和 $ t $ 的第一个和最后一个数字相同，但可以证明没有满足条件的操作序列。 - 在第四个测试用例中，可以通过选择 $ i=3 $、$ i=2 $、$ i=4 $、$ i=5 $ 和 $ i=3 $ 的操作，实现 $ s $ 到 $ t $ 的转换。
题目描述了一个关于灯泡的问题。有两个长度为 $ n $ 的二进制字符串 $ s $ 和 $ t $，表示一排灯泡的初始和最终状态，其中 $ s_i=\text{1} $ 表示第 $ i $ 个灯泡是开启的，$ s_i=\text{0} $ 表示关闭的。可以通过以下操作改变灯泡状态：
- 在 $ i=2,\dots,n-1 $ 中选择一个位置，使得 $ s_{i-1} \neq s_{i+1} $。
- 反转 $ s_i $ 的状态，即如果 $ s_i=\text{0} $，则变为 $ \text{1} $，反之亦然。
目标是使 $ s $ 变为 $ t $，需要帮助确定实现这一目标所需的最少操作次数。如果不能通过操作实现，则输出 $ -1 $。
**输入输出数据格式：**
**输入格式：**
- 第一行包含一个整数 $ q $（$ 1 \leq q \leq 10^4 $），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数 $ n $（$ 3 \leq n \leq 2 \cdot 10^5 $），表示灯泡的数量。
- 每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $，表示灯泡的初始状态。
- 每个测试用例的第三行包含一个长度为 $ n $ 的二进制字符串 $ t $，表示灯泡的最终状态。
- 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。
**输出格式：**
- 对于每个测试用例，输出一行，包含将 $ s $ 变为 $ t $ 所需执行的最少操作次数。如果不能通过操作实现，则输出 $ -1 $。
**输入输出样例：**
**输入样例 #1:**
```
4
4
0100
0010
4
1010
0100
5
01001
00011
6
000101
010011
```
**输出样例 #1:**
```
2
-1
-1
5
```
**说明：**
- 在第一个测试用例中，可以通过选择 $ i=3 $ 和 $ i=2 $ 的操作，实现 $ s $ 到 $ t $ 的转换。
- 在第二个测试用例中，由于无法改变 $ s $ 的第一个或最后一个数字，因此无法实现转换。
- 在第三个测试用例中，尽管 $ s $ 和 $ t $ 的第一个和最后一个数字相同，但可以证明没有满足条件的操作序列。
- 在第四个测试用例中，可以通过选择 $ i=3 $、$ i=2 $、$ i=4 $、$ i=5 $ 和 $ i=3 $ 的操作，实现 $ s $ 到 $ t $ 的转换。**题目大意：** 题目描述了一个关于灯泡的问题。有两个长度为 $ n $ 的二进制字符串 $ s $ 和 $ t $，表示一排灯泡的初始和最终状态，其中 $ s_i=\text{1} $ 表示第 $ i $ 个灯泡是开启的，$ s_i=\text{0} $ 表示关闭的。可以通过以下操作改变灯泡状态： - 在 $ i=2,\dots,n-1 $ 中选择一个位置，使得 $ s_{i-1} \neq s_{i+1} $。 - 反转 $ s_i $ 的状态，即如果 $ s_i=\text{0} $，则变为 $ \text{1} $，反之亦然。 目标是使 $ s $ 变为 $ t $，需要帮助确定实现这一目标所需的最少操作次数。如果不能通过操作实现，则输出 $ -1 $。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 $ q $（$ 1 \leq q \leq 10^4 $），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数 $ n $（$ 3 \leq n \leq 2 \cdot 10^5 $），表示灯泡的数量。 - 每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $，表示灯泡的初始状态。 - 每个测试用例的第三行包含一个长度为 $ n $ 的二进制字符串 $ t $，表示灯泡的最终状态。 - 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出格式：** - 对于每个测试用例，输出一行，包含将 $ s $ 变为 $ t $ 所需执行的最少操作次数。如果不能通过操作实现，则输出 $ -1 $。 **输入输出样例：** **输入样例 #1:** ``` 4 4 0100 0010 4 1010 0100 5 01001 00011 6 000101 010011 ``` **输出样例 #1:** ``` 2 -1 -1 5 ``` **说明：** - 在第一个测试用例中，可以通过选择 $ i=3 $ 和 $ i=2 $ 的操作，实现 $ s $ 到 $ t $ 的转换。 - 在第二个测试用例中，由于无法改变 $ s $ 的第一个或最后一个数字，因此无法实现转换。 - 在第三个测试用例中，尽管 $ s $ 和 $ t $ 的第一个和最后一个数字相同，但可以证明没有满足条件的操作序列。 - 在第四个测试用例中，可以通过选择 $ i=3 $、$ i=2 $、$ i=4 $、$ i=5 $ 和 $ i=3 $ 的操作，实现 $ s $ 到 $ t $ 的转换。