https://codeforces.com/contest/1913/problem/C
题目大意
给出 $m \ (m \le 10^5)$ 次操作，每次操作为之下两种之一：
- 给出 $x \ (0 \le x \le 29)$ 将 $2 ^ x$ 加入可重集。
- 给出 $y \ (0 \le x \le 10^9)$，问是否可以选出一些可重集中的元素使其和为 $y$。
简要题解
因为 $x$ 很小所以数组 $cnt$ 保存个数即可。
对于询问，这是一个特殊的背包问题。
可以从低位开始，假设 $cnt[0] == 0$ 但是 $y$ 的最低位是 $1$ 则显然无解。其他情况，我们让 $1$ 先贡献出 $y$ 的最低位，并从 $y$ 中减掉这个最低位，此时 $2 | y$，然后我们可以将多出来的 $1$ 尽量的转化为 $2$，以后都用不到 $1$ 了。将 $y$ 除以 $2$，将 $cnt$ 数组整体下标 $-1$ 之后，我们得到了原问题吗，因此我们递归这个过程，直到 $y$ 为 $0$ 或所有数字用尽即可。
当然从高位贪心也行，从 $2^{29}$ 开始尝试取尽量多的即可。对于 $y$ 中 $i$ 位的 $1$，肯定是靠 $cnt[0] \sim cnt[i]$ 解决的。对于最高位的 $i$，对于 $y$ 中（从低位为 $0$）, $0 \sim i - 1$ 中的所有 $1$ 都无法靠 $cnt[i]$ 解决，必然靠低位解决。假定最优解中并没有使用尽可能多的 $cnt[i]$，比如可以用 $k$ 个却只用了 $j$ 个，则意味着低位必然可以组合出 $k - j$ 个 $2 ^ i$ 那和直接用也没区别。去掉最高位之后，对于 $i - 1$ 问题完全一致，得证。
复杂度
$T$：$O(m \max(x))$
$S$：$O(\max(x))$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int MB = 30;
void solve() {
int n; cin >> n;
int op, v;
vector<int> cnt(MB);
for (int i = 0; i < n; i++) {
cin >> op >> v;
if (op == 1) {
cnt[v]++;
} else {
for (int i = MB - 1; i >= 0; i--) {
int diff = min(cnt[i], (v >> i));
v -= (diff << i);
}
cout << (v ? "NO" : "YES") << '\n';
}
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. You Are Given a WASD-string... - Educational Codeforces Round 70 (Rated for Div. 2)