文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
p
t
i
o
n
Description
Description
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://ac.nowcoder.com/acm/contest/7607/B
D
e
s
c
r
i
p
t
i
o
n
Description
Description
定义元素
b
b
b包含于二进制集合
A
A
A当且仅当
∃
a
∈
A
,
a
&
b
=
b
\exist a\in A,a\&b=b
∃a∈A,a&b=b，现给定大小为
n
n
n的集合
A
A
A，有
m
m
m组询问，每次询问一个元素
b
b
b是否包含于
A
A
A集合
数据范围：
n
,
m
≤
1
0
5
,
x
,
a
i
≤
1
0
6
n,m\leq 10^5,x,a_i\leq 10^6
n,m≤105,x,ai≤106
S
o
l
u
t
i
o
n
Solution
Solution
设
t
i
t_i
ti表示
i
i
i是否属于
A
A
A集合，初始
t
a
i
=
1
t_{a_i}=1
tai=1
接着倒序枚举
i
i
i（保证无后效性），如果
t
i
=
1
t_i=1
ti=1，则将
i
i
i的所有1分别去掉并重新赋值为1即可（此时这些元素都能被
i
i
i包含，且保证他们可以再次转移）
最后输出
t
b
t_b
tb即可
时间复杂度：
O
(
n
+
m
+
a
i
log
a
i
)
O(n+m+a_i\log a_i)
O(n+m+ailogai)
C
o
d
e
Code
Code
#include<cstdio>
int n
,m
,a
;
bool t
[1<<20];
int main()
{
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=n
;i
++) scanf("%d",&a
),t
[a
]=true;
for(int i
=(1<<20)-1;i
;i
--) if(t
[i
]) for(int j
=0;j
<20;j
++) if((i
>>j
)&1) t
[i
^(1<<j
)]=true;
for(int i
=1;i
<=m
;i
++) scanf("%d",&a
),puts(t
[a
]?"yes":"no");
}
