题目
In this problem, you are initially given an empty multiset. You have to process two types of queries:
- ADD \(x\) — add an element equal to \(2^{x}\) to the multiset;
- GET \(w\) — say whether it is possible to take the sum of some subset of the current multiset and get a value equal to \(w\).
Input
The first line contains one integer \(m\) (\(1 \le m \le 10^5\)) — the number of queries.
Then \(m\) lines follow, each of which contains two integers \(t_i\), \(v_i\), denoting the \(i\)-th query. If \(t_i = 1\), then the \(i\)-th query is ADD \(v_i\) (\(0 \le v_i \le 29\)). If \(t_i = 2\), then the \(i\)-th query is GET \(v_i\) (\(0 \le v_i \le 10^9\)).
7
1 0
1 1
1 2
1 10
2 4
2 6
2 7
Output
For each GET query, print YES if it is possible to choose a subset with sum equal to \(w\), or NO if it is impossible.
YES
YES
YES
题解
解题思路
由于每次给的数是\(2^n\),因此对于一个合法的数必然是由不同的\(2^n\)组合出来的,同时由于\(n\)的规模比较小,因此可以暴力枚举。
枚举过程中使用二分加速搜索,找最大小于查找值\(x\)的指数\(n\),最后判断是否能将\(x\)归零即可
Code
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr);
using namespace std;
typedef long long LL;
const int N=1e5+5;
int v[N];
bool ck(int x){
for(int i=29;i>=0;i--){
int l=0,r=v[i],ans=0;
while(l<=r){
int mid=l+r>>1;
if((mid<<i)<=x){
ans=mid;l=mid+1;
}
else r=mid-1;
}
x-=ans<<i;
}
return !x;
}
signed main(){
IOS;
int _;cin>>_;
while(_--){
int op,x;cin>>op>>x;
if(op==1) v[x]++;
else{
if(ck(x)){
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
}
return 0;
}
标签:le,GET,int,CF1913C,Game,th,query,Multiset,YES
From: https://www.cnblogs.com/TaopiTTT/p/18236074