← 返回题目列表

Codeforces · 1324/A

A. 又一个俄罗斯方块问题

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

为您提供了一些由 $$$n$$$ 列组成的俄罗斯方块字段。该字段第 $$$i$$$ 列的初始高度为 $$$a_i$$$ 块。在这些列的顶部,您只能放置大小为 $$$2 \times 1$$$ 的图形(即该图形的高度为 $$$2$$$ 块,该图形的宽度为 $$$1$$$ 块)。请注意,您无法旋转这些数字。

你的任务是判断你是否可以通过放置这些人物来清除整个区域。

更正式地说,问题可以这样描述:

当至少有一个 $$$a_i$$$ 大于 $$$0$$$ 时,会发生以下过程:

1. 您放置一个数字$$$2 \times 1$$$(从$$$1$$$到$$$n$$$中选择一些$$$i$$$,并将$$$a_i$$$替换为$$$a_i + 2$$$);
2. 然后,当所有 $$$a_i$$$ 都大于零时,将每个 $$$a_i$$$ 替换为 $$$a_i - 1$$$。

你的任务是确定是否可以清除整个区域(即完成所描述的过程),并正确选择新人物的位置。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

接下来的 $$$2t$$$ 行描述测试用例。测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 俄罗斯方块字段中的列数。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$),其中 $$$a_i$$$ 是俄罗斯方块字段第 $$$i$$$ 列的初始高度。

输出

对于每个测试用例,如果您可以清除整个俄罗斯方块字段,则打印答案“是”(不带引号),否则打印“否”。

示例

输入 #1

4
3
1 1 3
4
1 1 2 1
2
11 11
1
100

输出 #1

YES
NO
YES
YES

注意

示例字段的第一个测试用例如下所示:

灰线是俄罗斯方块字段的边界。请注意,该字段没有上限。

正确答案之一是首先将数字放在第一列中。然后在该过程的第二步之后,该字段变为$$$[2, 0, 2]$$$。然后将数字放在第二列中,在过程的第二步之后,该字段变为$$$[0, 0, 0]$$$。

示例字段的第二个测试用例如下所示:

可以看出,您无法执行任何操作来结束该进程。

在示例的第三个测试用例中,您首先将流程第二步之后的数字放置在第二列中,该字段变为 $$$[0, 2]$$$。然后将数字放在第一列中,经过第二步处理后,该字段将变为 $$$[0, 0]$$$。

在示例的第四个测试用例中,将数字放在第一列中,则在流程的第一步之后该字段将变为 $$$[102]$$$,然后在流程的第二步之后该字段将变为 $$$[0]$$$。