原题链接

反思：要把各种可能的情况都判断一遍再提交！不要急着提交

简介

仓库里有若干个二次方数，请问是否能取出若干数使得刚好等于给定数？

情况讨论

情况1.仓库里只有一个4，但是我要求2，求不得
情况2.仓库里有三个1，我要求3，能求

大概思路

从\(i\in[log2(v),0]\)遍历（从大到小），如果对于i，仓库里有，就一直减\(2^i\)直到无法再减（再减就小于零或库里的i次数用光了）

细节注意

1.for循环减法可以用一次性减法（除法找出减的次数）代替，速度会快很多
2.\(v\)不会超过\(10^9\)，所以\(2^i\)也不会超过long long 范围
3.pow函数比较耗时，可以用(1<<n)或者log2代替

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n;
    cin>>n;
    ll a[35]={0};
    while(n--)
    {
        ll q,v;
        cin>>q>>v;
        if(q==1) a[v]++;
        else
        {
            int i=log2(v);;//1.判断是否正常退出
            //2.代表最外面的1的位置
            for(i;i>=0;i--)//不从29开始，一定程度的优化
            {
                ll b=a[i];//仓库里i的数量
                ll d=pow(2,i);//当前i代表的实际值
                if(log2(v)>=i) v-=min(b,v/d)*d;//最多能减多少乘上减去的值，核心优化
                if(v==0)break;
            }
            if(i!=-1)puts("YES");
            else puts("NO");
        }
    }
    return 0;
}