包含

GCD

https://ac.nowcoder.com/acm/contest/7607/A

通过化简易知道,题目要求是否中的一个元素,使得的子集

每次读入时,将的每个子集暴力加入桶中,之后地判断

显然,这样的时间复杂度为

所以我们在的时候进行剪枝,因为当桶中存在值的子集也存在桶中,此时可以

时间复杂度为

#include<bits/stdc++.h>
using namespace std;
# define Type template<typename T>
# define ll long long
# define read read1<ll>()
Type T read1(){
    T t=0;char k;
    bool v=0;
    do (k=getchar())=='-'&&(v=1);while('0'>k||k>'9');
    while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
    return v?-t:t;
}
bool vis[1000005];
int s,m;
void dfs(int x){
    if(vis[x]||!x)return;
    vis[x]=1;
    for(int i=0;i<20;++i)
        if(x>>i&1)
            dfs(x^(1<<i));
}
int main(){
    s=read;m=read;
    for(int i=1;i<=s;++i)
        dfs(read);
    vis[0]=1;
    for(int i=1;i<=m;++i)
        puts(vis[read]?"yes":"no");
    return 0;
}
全部评论
CU 求
点赞 回复 分享
发布于 2020-10-20 22:15
通过势能分析可求得时间复杂度
点赞 回复 分享
发布于 2020-10-20 22:17
时间复杂度应该是O(m+x)把,桶内每个值只会被遍历一次
点赞 回复 分享
发布于 2020-10-20 22:20

相关推荐

评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务