/ WHOJ / 题库 / 生日 /

题解

1 条题解

  • 1
    @ 2022-09-01 22:40:40
    #include <stdio.h>
    #include <string.h>
    const int maxnode=2000000,hsize=500007;
    struct{
      int v,next;
    } node[maxnode];
    int w1[30],w2[30],hash[hsize],totn,lim,c,n,r,v[50];
    
    void insert(int v){
        int p=v%hsize;
        node[++totn].v=v; node[totn].next=hash[p]; hash[p]=totn;
    }
    
    int query(int v){
        int p=v%hsize,i;
        for(i=hash[p]; i; i=node[i].next)
            if(node[i].v==v) return 1;
        return 0;
    }
    
    void dfs1(int i){
        if(c>r) return;
        if(i==lim) insert(c); else
        {
            c+=v[i]; dfs1(i+1);
            c-=v[i]; dfs1(i+1);
        }
    }
    
    int flag;
    void dfs2(int i){
        if(c>r) return;
        if(i==lim)
        {
            flag=query(r-c);
            return;
        }
        c+=v[i]; dfs2(i+1);
        if(flag) return;
        c-=v[i]; dfs2(i+1);
    }
    
    int main(){
        int i;
        //freopen("bday.in","r",stdin);
        //freopen("bday.out","w",stdout);
        while(scanf("%d%d",&n,&r)!=EOF)
        {
            memset(hash,0,sizeof(hash)); totn=flag=c=0;
            for(i=0; i<n; ++i) scanf("%d",v+i);
            lim=n/2; dfs1(0);
            lim=n; dfs2(n/2);
            if(flag) puts("YES"); else puts("NO");
        }
        return 0;
    }
    
  • 1

信息

ID
1618
难度
9
分类
搜索 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者