310161: CF1791C. Prepend and Append
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Prepend and Append
题意翻译
对于一个字符串 $s$,你可以进行如下操作: - 在 $s$ 左侧添加字符 $\texttt1$,右侧添加字符 $\texttt0$;或者在 $s$ 左侧添加字符 $\texttt0$,右侧添加字符 $\texttt1$。 现给你一个字符串 $t$,求可以通过若干次操作变成字符串 $t$ 的字符串的最短长度。题目描述
Timur initially had a binary string $ ^{\dagger} $ $ s $ (possibly of length $ 0 $ ). He performed the following operation several (possibly zero) times: - Add $ \texttt{0} $ to one end of the string and $ \texttt{1} $ to the other end of the string. For example, starting from the string $ \texttt{1011} $ , you can obtain either $ \color{red}{\texttt{0}}\texttt{1011}\color{red}{\texttt{1}} $ or $ \color{red}{\texttt{1}}\texttt{1011}\color{red}{\texttt{0}} $ . You are given Timur's final string. What is the length of the shortest possible string he could have started with? $ ^{\dagger} $ A binary string is a string (possibly the empty string) whose characters are either $ \texttt{0} $ or $ \texttt{1} $ .输入输出格式
输入格式
The first line of the input contains an integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of testcases. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2000 $ ) — the length of Timur's final string. The second line of each test case contains a string $ s $ of length $ n $ consisting of characters $ \texttt{0} $ or $ \texttt{1} $ , denoting the final string.
输出格式
For each test case, output a single nonnegative integer — the shortest possible length of Timur's original string. Note that Timur's original string could have been empty, in which case you should output $ 0 $ .
输入输出样例
输入样例 #1
9
3
100
4
0111
5
10101
6
101010
7
1010110
1
1
2
10
2
11
10
1011011010
输出样例 #1
1
2
5
0
3
1
0
2
4
说明
In the first test case, the shortest possible string Timur started with is $ \texttt{0} $ , and he performed the following operation: $ \texttt{0} \to \color{red}{\texttt{1}}\texttt{0}\color{red}{\texttt{0}} $ . In the second test case, the shortest possible string Timur started with is $ \texttt{11} $ , and he performed the following operation: $ \texttt{11} \to \color{red}{\texttt{0}}\texttt{11}\color{red}{\texttt{1}} $ . In the third test case, the shortest possible string Timur started with is $ \texttt{10101} $ , and he didn't perform any operations. In the fourth test case, the shortest possible string Timur started with is the empty string (which we denote by $ \varepsilon $ ), and he performed the following operations: $ \varepsilon \to \color{red}{\texttt{1}}\texttt{}\color{red}{\texttt{0}} \to \color{red}{\texttt{0}}\texttt{10}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{0101}\color{red}{\texttt{0}} $ . In the fifth test case, the shortest possible string Timur started with is $ \texttt{101} $ , and he performed the following operations: $ \texttt{101} \to \color{red}{\texttt{0}}\texttt{101}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{01011}\color{red}{\texttt{0}} $ .Input
题意翻译
对于一个字符串 $s$,你可以进行如下操作: - 在 $s$ 左侧添加字符 $\texttt1$,右侧添加字符 $\texttt0$;或者在 $s$ 左侧添加字符 $\texttt0$,右侧添加字符 $\texttt1$。 现给你一个字符串 $t$,求可以通过若干次操作变成字符串 $t$ 的字符串的最短长度。Output
**题目大意:**
对于字符串s,可以执行以下操作:
- 在s的左侧添加字符`1`,在右侧添加字符`0`;或者在s的左侧添加字符`0`,在右侧添加字符`1`。
现给定一个字符串t,求可以通过若干次操作变成字符串t的字符串的最短长度。
**输入输出数据格式:**
**输入格式:**
- 第一行输入一个整数t(1≤t≤100),表示测试用例的数量。
- 每个测试用例的第一行输入一个整数n(1≤n≤2000),表示Timur最终字符串的长度。
- 每个测试用例的第二行输入一个长度为n的字符串s,由字符`0`或`1`组成,表示最终的字符串。
**输出格式:**
- 对于每个测试用例,输出一个非负整数,表示Timur原始字符串的最短可能长度。注意,Timur的原始字符串可能为空,在这种情况下应输出0。
**输入输出样例:**
**输入样例 #1:**
```
9
3
100
4
0111
5
10101
6
101010
7
1010110
1
1
2
10
2
11
10
1011011010
```
**输出样例 #1:**
```
1
2
5
0
3
1
0
2
4
```**题目大意:** 对于字符串s,可以执行以下操作: - 在s的左侧添加字符`1`,在右侧添加字符`0`;或者在s的左侧添加字符`0`,在右侧添加字符`1`。 现给定一个字符串t,求可以通过若干次操作变成字符串t的字符串的最短长度。 **输入输出数据格式:** **输入格式:** - 第一行输入一个整数t(1≤t≤100),表示测试用例的数量。 - 每个测试用例的第一行输入一个整数n(1≤n≤2000),表示Timur最终字符串的长度。 - 每个测试用例的第二行输入一个长度为n的字符串s,由字符`0`或`1`组成,表示最终的字符串。 **输出格式:** - 对于每个测试用例,输出一个非负整数,表示Timur原始字符串的最短可能长度。注意,Timur的原始字符串可能为空,在这种情况下应输出0。 **输入输出样例:** **输入样例 #1:** ``` 9 3 100 4 0111 5 10101 6 101010 7 1010110 1 1 2 10 2 11 10 1011011010 ``` **输出样例 #1:** ``` 1 2 5 0 3 1 0 2 4 ```
对于字符串s,可以执行以下操作:
- 在s的左侧添加字符`1`,在右侧添加字符`0`;或者在s的左侧添加字符`0`,在右侧添加字符`1`。
现给定一个字符串t,求可以通过若干次操作变成字符串t的字符串的最短长度。
**输入输出数据格式:**
**输入格式:**
- 第一行输入一个整数t(1≤t≤100),表示测试用例的数量。
- 每个测试用例的第一行输入一个整数n(1≤n≤2000),表示Timur最终字符串的长度。
- 每个测试用例的第二行输入一个长度为n的字符串s,由字符`0`或`1`组成,表示最终的字符串。
**输出格式:**
- 对于每个测试用例,输出一个非负整数,表示Timur原始字符串的最短可能长度。注意,Timur的原始字符串可能为空,在这种情况下应输出0。
**输入输出样例:**
**输入样例 #1:**
```
9
3
100
4
0111
5
10101
6
101010
7
1010110
1
1
2
10
2
11
10
1011011010
```
**输出样例 #1:**
```
1
2
5
0
3
1
0
2
4
```**题目大意:** 对于字符串s,可以执行以下操作: - 在s的左侧添加字符`1`,在右侧添加字符`0`;或者在s的左侧添加字符`0`,在右侧添加字符`1`。 现给定一个字符串t,求可以通过若干次操作变成字符串t的字符串的最短长度。 **输入输出数据格式:** **输入格式:** - 第一行输入一个整数t(1≤t≤100),表示测试用例的数量。 - 每个测试用例的第一行输入一个整数n(1≤n≤2000),表示Timur最终字符串的长度。 - 每个测试用例的第二行输入一个长度为n的字符串s,由字符`0`或`1`组成,表示最终的字符串。 **输出格式:** - 对于每个测试用例,输出一个非负整数,表示Timur原始字符串的最短可能长度。注意,Timur的原始字符串可能为空,在这种情况下应输出0。 **输入输出样例:** **输入样例 #1:** ``` 9 3 100 4 0111 5 10101 6 101010 7 1010110 1 1 2 10 2 11 10 1011011010 ``` **输出样例 #1:** ``` 1 2 5 0 3 1 0 2 4 ```