題意

判斷能否取多集中若干個數使得它們的和等于 \(w\)。

解析

由于給的數都是 \(2\) 的冪，所以我們可以每次讓 \(w\) 減去不大于它的在集合中存在的二進制位數最多的數，如果能減完那么就說明可以，否則說明不可能。

怎么保證這種策略是最優的？

假設 \(n=\lfloor log_2w\rfloor\)，則有 \(2^n \le w\)。

如果不減 \(2^n\) 也能讓 \(w\) 變成 \(0\)，那么：

\(w=t_{n-1} \times 2^{n-1}+t_{n-2} \times 2^{n-2}+\dots+t_{0} \times 2^{0}\ge2^n\)

顯然，在上式中必定有一些 \(t\) 大于 \(1\)，我們不妨把它看成一個還沒有處理進位的二進制數，第 \(i\) 位的數值為 \(t_i\)。

那么，在處理完進位后，這個二進制數必定有第 \(n\) 位大于等于 \(1\)，這實際上是由若干個 \(2^i(0\le i<n)\) 組成的，于是我們就可以用 \(2^n\) 來替代這若干個 \(2^i\)。

故如果不減 \(2^n\) 能讓 \(w\) 變成 \(0\)，那么減去 \(2^n\) 也可以把 \(w\) 變成 \(0\)，并且這樣我們還省了若干個 \(2^i\)。

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int cnt[30];
bool find(int x,int pos){ //x：當前 w 還剩多少，pos：將要減去的二進制數的位數
	if(!x) return true;   
	if(pos < 0) return false;
	int num = x >> pos;   //計算 x 可以減去多少個2^pos
	if(cnt[pos] >= num) x -= num << pos; 
	else x -= cnt[pos] << pos;
	return find(x,pos - 1);
}
int main(){
	int T;
	cin>>T;
	while(T--){
		int t,x;
		cin>>t>>x;
		if(t == 1){
			cnt[x]++;
		}else{
			cout<<(find(x,29) ? "YES" : "NO")<<endl;
		}
	}
	return 0;
}