CF1913C 题解

· · 题解

题目传送门

1. ADD

对于插入操作，使用一个桶来记录即可。

2. GET

首先，两个 2^x 可以拼成一个 2^{x+1}，但是一个 2^{x+1} 不能拆分成两个 2^x。

所以将给定的 w 的二进制表示从低位到高位枚举，当无法拼出当前这一位的 1 时，就直接无解。

为了方便，用一个变量 sum 来存储最多能拼出多少个当前的 2^i。

统计到第 i 位时，先令 sum 加上当前这一位对应桶里的数量，若 w 的二进制表示中这一位是 1，且 sum = 0，则无解，否则 sum 减一。检查完后要使 sum = \lfloor \frac{sum}{2} \rfloor，因为两个小的可以拼成一个大的，若 sum 为奇数，则多余的一个就只能扔掉了。

注意枚举的位数要够多，询问之间互相独立。

Code

#include <iostream>
using namespace std;
const int N = 35;
int S[N];
void get(int x)
{
    int sum = 0;
    for (int i=0;i<=30;i++)
    {
        sum += S[i];
        if (x >> i & 1)
        {
            if (!sum)
            {
                puts("NO");
                return;
            }
            else
                sum --;
        }
        sum >>= 1;
    }
    puts("YES");
}
int main()
{
    int m;
    scanf("%d", &m);
    while (m--)
    {
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1)
            S[x] ++;
        else
            get(x);
    }
    return 0;
}