CF1913C

Dawn_cx · 2023-12-19 16:58:16 · 题解

题意：给定一个空集合，并进行 n 次操作，操作有两种，第一种是向集合里添加 2^x，第二种是询问这个集合的子集是否存在一个满足子集中所有数的和等于所询问的数。

对所有数进行二进制拆分，将集合中每个数的每一位存到数组 d 中，向集合里添加 2^x 后，我们令 d_x+1，这样就存下了集合中二进制每一位有几个。

询问时我们从第 0 位开始，每次枚举当前位集合中数量和询问的数的数量，如果集合中数量少于 1 并且询问的数这一位有 1 则输出 NO。否则进行进位并继续判断到最高位即可

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int n,op,x,d[N],p[N];
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&op,&x);
        if(op==1)d[x]++;
        else{
            int flag=0;
            for(int i=0;i<=30;i++)p[i]=d[i];
            for(int i=0;i<=30;i++){
                if((x>>i)&1){
                    if(!p[i]){
                        flag=1;
                        break;
                    }
                    else p[i]--;
                }
                p[i+1]+=p[i]/2;
            }
            if(flag)puts("NO");
            else puts("YES");
        }
    }
    return 0;
}