310147: CF1789B. Serval and Inversion Magic

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Serval and Inversion Magic

题意翻译

给你一个仅由 $01$ 组成的字符串 $s$,你需要进行一次以下操作: + 选择 $s$ 的一个子区间 $[l,r]$,然后翻转所有 $s_i\ (l \le i \le r)$,这里的翻转指的是 $0$ 变 $1$,$1$ 变 $0$。 请问你是否能把这个字符串变成一个回文串。 Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)

题目描述

Serval has a string $ s $ that only consists of 0 and 1 of length $ n $ . The $ i $ -th character of $ s $ is denoted as $ s_i $ , where $ 1\leq i\leq n $ . Serval can perform the following operation called Inversion Magic on the string $ s $ : - Choose an segment $ [l, r] $ ( $ 1\leq l\leq r\leq n $ ). For $ l\leq i\leq r $ , change $ s_i $ into 1 if $ s_i $ is 0, and change $ s_i $ into 0 if $ s_i $ is 1. For example, let $ s $ be 010100 and the segment $ [2,5] $ is chosen. The string $ s $ will be 001010 after performing the Inversion Magic. Serval wants to make $ s $ a palindrome after performing Inversion Magic exactly once. Help him to determine whether it is possible. A string is a palindrome iff it reads the same backwards as forwards. For example, 010010 is a palindrome but 10111 is not.

输入输出格式

输入格式


Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\leq t\leq 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2\leq n\leq 10^5 $ ) — the length of string $ s $ . The second line of each test case contains a binary string $ s $ of length $ n $ . Only characters 0 and 1 can appear in $ s $ . It's guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

输出格式


For each test case, print Yes if $ s $ can be a palindrome after performing Inversion Magic exactly once, and print No if not. You can output Yes and No in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

输入输出样例

输入样例 #1

3
4
1001
5
10010
7
0111011

输出样例 #1

Yes
Yes
No

说明

In the first test case, Serval can perform Inversion Magic on the segment $ [1,4] $ . The string $ s $ will be 0110 after the magic. In the second test case, Serval can perform Inversion Magic on the segment $ [1,3] $ . The string $ s $ will be 01110 after the magic. In the third test case, Serval can't make $ s $ a palindrome by performing Inversion Magic exactly once.

Input

题意翻译

给你一个仅由 $01$ 组成的字符串 $s$,你需要进行一次以下操作: + 选择 $s$ 的一个子区间 $[l,r]$,然后翻转所有 $s_i\ (l \le i \le r)$,这里的翻转指的是 $0$ 变 $1$,$1$ 变 $0$。 请问你是否能把这个字符串变成一个回文串。 Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)

Output

**题意翻译**

给你一个仅由 $01$ 组成的字符串 $s$,你需要进行一次以下操作:

选择 $s$ 的一个子区间 $[l,r]$,然后翻转所有 $s_i\ (l \le i \le r)$,这里的翻转指的是 $0$ 变 $1$,$1$ 变 $0$。

请问你是否能把这个字符串变成一个回文串。

**题目描述**

Serval有一个只由0和1组成的字符串 $ s $,长度为 $ n $。字符串 $ s $ 的第 $ i $ 个字符表示为 $ s_i $,其中 $ 1\leq i\leq n $。

Serval可以在字符串 $ s $ 上执行以下称为Inversion Magic的操作:

- 选择一个区间 $[l, r]$($ 1\leq l\leq r\leq n $)。对于 $ l\leq i\leq r $,如果 $ s_i $ 是0,则将其变为1,如果 $ s_i $ 是1,则将其变为0。

例如,让 $ s $ 为010100,并选择区间 $[2,5]$。执行Inversion Magic后,字符串 $ s $ 将为001010。

Serval想要在执行一次Inversion Magic后使 $ s $ 成为回文串。帮助他确定是否可能。

一个字符串是回文当且仅当它从后往前读和从前往后读相同。例如,010010是回文串,但10111不是。

**输入输出格式**

**输入格式**

每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $($ 1\leq t\leq 10^4 $)。测试用例描述如下。

每个测试用例的第一行包含一个整数 $ n $($ 2\leq n\leq 10^5 $)——字符串 $ s $ 的长度。

每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $。字符串 $ s $ 只能包含字符0和1。

保证所有测试用例的 $ n $ 之和不超过 $ 2\cdot 10^5 $。

**输出格式**

对于每个测试用例,如果 $ s $ 可以在执行一次Inversion Magic后成为回文串,则打印Yes,如果不能,则打印No。

你可以以任何大小写输出Yes和No(例如,yEs、yes、Yes和YES都将被识别为积极响应)。

**输入输出样例**

**输入样例 #1**

```
3
4
1001
5
10010
7
0111011
```

**输出样例 #1**

```
Yes
Yes
No
```

**说明**

在第一个测试用例中,Serval可以在区间 $[1,4]$ 上执行Inversion Magic。字符串 $ s $ 在魔法后将变为0110。

在第二个测试用例中,Serval可以在区间 $[1,3]$ 上执行Inversion Magic。字符串 $ s $ 在魔法后将变为01110。

在第三个测试用例中,Serval无法通过执行一次Inversion Magic使 $ s $ 成为回文串。**题意翻译** 给你一个仅由 $01$ 组成的字符串 $s$,你需要进行一次以下操作: 选择 $s$ 的一个子区间 $[l,r]$,然后翻转所有 $s_i\ (l \le i \le r)$,这里的翻转指的是 $0$ 变 $1$,$1$ 变 $0$。 请问你是否能把这个字符串变成一个回文串。 **题目描述** Serval有一个只由0和1组成的字符串 $ s $,长度为 $ n $。字符串 $ s $ 的第 $ i $ 个字符表示为 $ s_i $,其中 $ 1\leq i\leq n $。 Serval可以在字符串 $ s $ 上执行以下称为Inversion Magic的操作: - 选择一个区间 $[l, r]$($ 1\leq l\leq r\leq n $)。对于 $ l\leq i\leq r $,如果 $ s_i $ 是0,则将其变为1,如果 $ s_i $ 是1,则将其变为0。 例如,让 $ s $ 为010100,并选择区间 $[2,5]$。执行Inversion Magic后,字符串 $ s $ 将为001010。 Serval想要在执行一次Inversion Magic后使 $ s $ 成为回文串。帮助他确定是否可能。 一个字符串是回文当且仅当它从后往前读和从前往后读相同。例如,010010是回文串,但10111不是。 **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $($ 1\leq t\leq 10^4 $)。测试用例描述如下。 每个测试用例的第一行包含一个整数 $ n $($ 2\leq n\leq 10^5 $)——字符串 $ s $ 的长度。 每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $。字符串 $ s $ 只能包含字符0和1。 保证所有测试用例的 $ n $ 之和不超过 $ 2\cdot 10^5 $。 **输出格式** 对于每个测试用例,如果 $ s $ 可以在执行一次Inversion Magic后成为回文串,则打印Yes,如果不能,则打印No。 你可以以任何大小写输出Yes和No(例如,yEs、yes、Yes和YES都将被识别为积极响应)。 **输入输出样例** **输入样例 #1** ``` 3 4 1001 5 10010 7 0111011 ``` **输出样例 #1** ``` Yes Yes No ``` **说明** 在第一个测试用例中,Serval可以在区间 $[1,4]$ 上执行Inversion Magic。字符串 $ s $ 在魔法后将变为0110。 在第二个测试用例中,Serval可以在区间 $[1,3]$ 上执行Inversion Magic。字符串 $ s $ 在魔法后将变为01110。 在第三个测试用例中,Serval无法通过执行一次Inversion Magic使 $ s $ 成为回文串。

加入题单

算法标签: