题目分析

我们有一个长度为 $n$（$n$ 为偶数）的二进制字符串。
对于每一对对称位置 $(i, n-i+1)$，如果两个字符相同，则称为“好对”。
总共有 $\frac{n}{2}$ 对这样的位置。

我们可以任意重排字符串中的字符，问是否能恰好得到 $k$ 个好对。

---

核心思路

1. 统计字符数量

设字符串中 0 的数量为 $c_0$，1 的数量为 $c_1$，则

$$c_0 + c_1 = n$$

---

2. 最少好对数量

为了尽可能少的好对，我们把所有相同字符尽量放在不同的对称位置上。

一种构造方法：

• 把所有 0 放在字符串前面，所有 1 放在后面。
  此时，中间有一部分是 0 和 1 交错的位置，那里会形成好对。

更精确地：
令 $x = \max(c_0, c_1)$，$y = \min(c_0, c_1)$。
总共有 $\frac{n}{2}$ 对对称位置。
如果我们把 $x$ 个多的字符尽量放在不同的对称对中，那么这些对中有些会两个字符相同，有些不同。

最终得到的最小好对数为：

$$mn = \max(c_0, c_1) - \frac{n}{2}$$

推导：

• 设 $d = \max(c_0, c_1) - \frac{n}{2}$。
• 因为多出的 $d$ 个字符必须与另一端的字符相同（否则就会形成不同对），这些 $d$ 对就自动是好对。
• 其余部分可以安排成全部不同，从而不增加好对。

例子：$n=6, c_0=4, c_1=2$
$\frac{n}{2}=3$，$mn = 4-3=1$，确实至少 1 个好对。

---

3. 最多好对数量

为了最多好对，我们把相同的字符尽量放在一起，让对称位置字符相同。

每一对对称位置可以放两个相同字符。
所以：

• 0 可以组成 $\left\lfloor \frac{c_0}{2} \right\rfloor$ 个全 0 对
• 1 可以组成 $\left\lfloor \frac{c_1}{2} \right\rfloor$ 个全 1 对

因此最大好对数为：

$$mx = \left\lfloor \frac{c_0}{2} \right\rfloor + \left\lfloor \frac{c_1}{2} \right\rfloor $$

---

4. 可达到的 $k$ 的条件

必要条件：

$$mn \le k \le mx$$

但这是否充分？
不是，例如 $n=4, c_0=2, c_1=2$
$mn=2-2=0$，$mx=1+1=2$
我们可以得到 0 个好对（0101）和 2 个好对（0011），但不能得到 1 个好对。

为什么？因为每次交换两个字符（即重排），好对数量的变化只能是 $0$ 或 $2$。

变化量为偶数 的原因：
考虑交换两个不同对称对中的字符：

• 如果交换的两个字符相同，好对数不变。
• 如果交换的两个字符不同，好对数变化为 ±2（因为两个对称对的状态同时改变）。

因此，从最小好对数开始，每次可以增加 2，所以所有可达的好对数与 $mn$ 的差必须是偶数。

---

5. 最终条件

综上，$k$ 可达当且仅当：

1. $mn \le k \le mx$
2. $(k - mn) \bmod 2 = 0$

---

算法步骤

1. 统计 $c_0$ 和 $c_1$。
2. 计算 $mn = \max(c_0, c_1) - \frac{n}{2}$。
3. 计算 $mx = \lfloor c_0/2 \rfloor + \lfloor c_1/2 \rfloor$。
4. 如果 $mn \le k \le mx$ 且 $(k - mn)$ 是偶数，输出 "YES"，否则 "NO"。

时间复杂度：$O(n)$ 每个测试用例。
总复杂度：$O(\sum n) \le 2 \times 10^5$。

---

示例验证

例 1

$n=6, k=2$
s = 000000 → $c_0=6, c_1=0$
$mn = 6 - 3 = 3$
$mx = 3 + 0 = 3$
$k=2 < mn$ → NO

例 2

$n=2, k=1$
s = 01 → $c_0=1, c_1=1$
$mn = 1 - 1 = 0$
$mx = 0 + 0 = 0$
$k=1 > mx$ → NO

例 3

$n=4, k=1$
s = 1011 → $c_0=1, c_1=3$
$mn = 3 - 2 = 1$
$mx = 0 + 1 = 1$
$k=1$，$k-mn=0$ 偶数 → YES

例 4

$n=10, k=2$
s = 1101011001 → $c_0=4, c_1=6$
$mn = 6 - 5 = 1$
$mx = 2 + 3 = 5$
$k=2$，$k-mn=1$ 奇数 → NO

例 5

$n=10, k=1$
同上，$mn=1, mx=5$
$k=1$，$k-mn=0$ 偶数 → YES

例 6

$n=2, k=1$
s = 11 → $c_0=0, c_1=2$
$mn = 2 - 1 = 1$
$mx = 0 + 1 = 1$
$k=1$，$k-mn=0$ 偶数 → YES