← 返回题目列表

Codeforces · 1789/B

B. 薮和反转魔法

中文机器翻译题面 查看原题

Serval 有一个字符串 $$$s$$$,仅由 0 和 1 组成,长度为 $$$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,则将 $$$s_i$$$ 更改为 1;如果 $$$s_i$$$ 为 1,则将 $$$s_i$$$ 更改为 0。

例如,令 $$$s$$$ 为 010100,并选择段 $$$[2,5]$$$。执行反转魔法后,字符串 $$$s$$$ 将变为 001010。

Serval 想要在执行一次反转魔法后将 $$$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$$$。

输出

对于每个测试用例,如果执行 Inversion Magic 一次后 $$$s$$$ 可以是回文,则打印 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$$$ 成为回文。