题目描述

难度分:$1300$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的$k$之和$\leq 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和$n$行，每行输入$k(1 \leq k \leq 10^5)$和$k$个不同数字，范围$[1,2 \times 10^5]$。

这$k$个数字表示一个二进制数比特$1$的位置。例如给你$2,3,5$表示二进制101100（从右往左读）。所以，输入相当于给你一个长为$n$的数组，包含$n$个二进制数。

你需要从数组中选择两个不同的子序列，使得这两个子序列的OR（按位或）相等。
能否做到？输出Yes或No。

注：子序列不要求连续。
注：只要有一个元素的下标不在另一个子序列的元素下标中，两个子序列就算不同的。

例如$[1,1,1]$中有 三个 不同的子序列$[1,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

输出样例

No
Yes
Yes
Yes
No

算法

贪心构造

刚开始读了个假题，以为这两个序列不能重叠，感觉怎么$1300$的题目这么难。

两个序列是可以重叠的就好办了，设所有数或起来的结果为xor，它们构成第一个子序列。我们再随便找一个数，这个数为$1$的那些位在其他数中全部都出现过就行了，这样一来第一个子序列剔除这个数形成第二个子序列。

这两个子序列的OR结果都是xor，如果不存在这样一个数，就无法构造出符合题意的两个子序列。

复杂度分析

时间复杂度

先遍历一遍每个数的位集，统计各个数字的出现频率，存入到哈希表$counter$中。然后再遍历一遍每个数的位集，看是否存在一个数，它所有为$1$的位在其他数字中都出现过。对于每个$case$，一共就遍历了两遍数据，时间复杂度为$O(nk)$。

空间复杂度

空间消耗就是频数表$counter$，在最差情况下有$nk$个键值对，因此额外空间复杂度为$O(nk)$。

$python$代码

from collections import defaultdict

T = int(input())
for _ in range(T):
    n = int(input())
    nums = []
    counter = defaultdict(lambda: 0)
    for _ in range(n):
        params = list(map(int, input().split()))
        bits = params[1:]
        for b in bits:
            counter[b] += 1
        nums.append(bits)
    for i in range(n):
        flag = True
        for b in nums[i]:
            if counter[b] == 1:
                flag = False
                break
        if flag:
            print("YES")
            break
    else:
        print("NO")