目录

now116658f: AND VS MEX

2025-09-07 约 155 字预计阅读 1 分钟次阅读

目录

now116658f: AND VS MEX

sosdp

从二进制集合考虑
假如数 i 存在的所有超集取与后得到 i，则 i 能取到
因此从大到小遍历，维护所有超集的与即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


import sys
input = lambda: sys.stdin.readline().rstrip()

def II(base=10):
    return int(input(),base)

def LI():
    return list(map(int,input()))

def LII():
    return list(map(int,input().split()))

def main():
    n = II()
    A = LII()
    m = max(A).bit_length()
    N = 1<<m
    f = [-1]*N
    for x in A:
        f[x] = x
    for i in range(N-1,0,-1):
        for j in range(m):
            f[i] &= f[i|1<<j]
    for i in range(1,N):
        if f[i]!=i:
            print(i)
            return
    print(N)

for _ in range(II()):
    main()

841 ms