← 返回题目列表

Codeforces · 1251/B

B. 二进制回文

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

回文是一个字符串 $$$t$$$,它向后读取的内容与向前读取的内容相同(形式上,$$$t[i] = t[|t| + 1 - i]$$$ 对于 [1, |t|]$$$ 中的所有 $$$i \)。这里$$$|t|$$$表示字符串$$$t$$$的长度。例如,字符串 010、1001 和 0 是回文。

您有 $$$n$$$ 二进制字符串 $$$s_1, s_2, \dots, s_n$$$ (每个 $$$s_i$$$ 由零和/或一组成)。您可以任意次数地交换任意一对字符(可能为零)。字符可以来自同一个字符串,也可以来自不同的字符串——没有限制。

正式来说,您一步即可:

- 选择四个整数 $$$x, a, y, b$$$ 使得 $$$1 \le x, y \le n$$$ 和 $$$1 \le a \le |s_x|$$$ 和 $$$1 \le b \le |s_y|$$$ (其中 $$$x$$$ 和 $$$y$$$ 是字符串索引,$$$a$$$ 和$$$b$$$ 分别是字符串 $$$s_x$$$ 和 $$$s_y$$$ 中的位置),
- 交换(交换)字符 $$$s_x[a]$$$ 和 $$$s_y[b]$$$。

最多可以同时生成回文字符串数是多少?

输入

第一行包含单个整数 $$$Q$$$ ($$$1 \le Q \le 50$$$) — 测试用例的数量。

每个测试用例的第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 二进制字符串的数量。

接下来的 $$$n$$$ 行包含二进制字符串 $$$s_1, s_2, \dots, s_n$$$ — 每行一个。保证 $$$1 \le |s_i| \le 50$$$ 并且所有字符串均由零和/或一组成。

输出

打印 $$$Q$$$ 整数 — 每个测试用例一个。第 $$$i$$$ 个整数应该是在第 $$$i$$$ 个测试用例中同时对字符串执行零次或多次交换时可以实现的回文字符串的最大数量。

示例

输入 #1

4
1
0
3
1110
100110
010101
2
11111
000001
2
001
11100111

输出 #1

1
2
2
2

注意

在第一个测试用例中,$$$s_1$$$ 是回文,所以答案是 $$$1$$$。

在第二个测试用例中,您不能同时将所有三个字符串设为回文,但可以将任意一对字符串设为回文。例如,让我们设置 $$$s_1 = \text{0110}$$$、$$$s_2 = \text{111111}$$$ 和 $$$s_3 = \text{010000}$$$。

在第三个测试用例中,我们可以将两个字符串设为回文。例如,$$$s_1 = \text{11011}$$$ 和 $$$s_2 = \text{100001}$$$。

在最后一个测试用例中,$$$s_2$$$ 是回文,您可以通过交换 $$$s_1[2]$$$ 和 $$$s_1[3]$$$ 来使 $$$s_1$$$ 成为回文。