← 返回题目列表

Codeforces · 1775/B

B. 园丁和阵列

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

园丁 Kazimir Kazimirovich 有一个 $$$n$$$ 整数数组 $$$c_1, c_2, \dots, c_n$$$。

他想要检查原始数组中是否存在两个不同的子序列 $$$a$$$ 和 $$$b$$$,其中 $$$f(a) = f(b)$$$,其中 $$$f(x)$$$ 是序列 $$$x$$$ 中所有数字的按位或。

如果 $$$q$$$ 可以通过删除几个(可能没有或全部)元素从 $$$p$$$ 获得,则序列 $$$q$$$ 是 $$$p$$$ 的子序列。

如果两个子序列的元素在原序列中的索引集合不同,则认为两个子序列不同,即在比较子序列时不考虑元素的值。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$c$$$ 的大小。

本题中数组 $$$c$$$ 的描述是隐式给出的,以加快输入速度。

测试用例的以下 $$$n$$$ 行中的 $$$(i + 1)$$$-st 以整数 $$$k_i$$$ 开头 ($$$1 \le k_i \le 10^5$$$) — 数字 $$$c_i$$$ 中设置的位数。接下来是 $$$k_i$$$ 不同的整数 $$$p_{i, 1}, p_{i, 2}, \dots, p_{i, k_i}$$$ ($$$1 \le p_i \le 2 \cdot 10^5$$$) - 数字 $$$c_i$$$ 中设置为 1 的位数。换句话说,$$$c_i = 2^{p_{i, 1}} + 2^{p_{i, 2}} + \ldots + 2^{p_{i, k_i}}$$$。

保证所有测试中$$$k_i$$$的总和不超过$$$10^5$$$。

输出

对于每组输入,如果存在 $$$f(a) = f(b)$$$ 的两个不同子序列,则打印“Yes”,否则打印“No”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

5
3
2 1 5
2 2 4
2 2 3
2
2 1 2
1 2
4
3 1 2 4
2 2 4
4 1 2 5 6
2 2 5
5
3 3 1 2
3 2 5 3
5 7 2 3 1 4
5 1 2 6 3 5
3 2 6 3
2
1 1
1 2

输出 #1

No
Yes
Yes
Yes
No

注意

可以证明,在第一个测试用例中,不存在两个不同的子序列$$$a$$$和$$$b$$$,其中$$$f(a) = f(b)$$$。

在第二个测试用例中,可能的答案之一是以下子序列:由位置$$$1$$$处的元素形成的子序列$$$a$$$,以及由位置$$$1$$$和$$$2$$$处的元素形成的子序列$$$b$$$。

在第三个测试用例中,可能的答案之一是以下子序列:由位置 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$4$$$ 处的元素形成的子序列 $$$a$$$,以及由位置 $$$2$$$、$$$3$$$ 和 $$$3$$$ 处的元素形成的子序列 $$$b$$$ $$$4$$$。