CF1913C Game with Multiset

Zinc-Acetate / 2024-01-23 / 原文

~~寄，会写题不会讲~~

题目传送门

codeforces

洛谷

题面

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$).

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.

题目大意

在这个问题中，最初会给你一个空的多集。您必须处理两种类型的查询：

ADD $x$ - 在多集合中添加一个等于 $2^{x}$ 的元素；
GET $w$ - 询问是否可以取当前多集的某个子集之和，并得到等于 $w$ 的值。

思路

观察到所添加的元素都是 $2$ 的正整数次幂，我们可以考虑将每次查询拆成二进制来求解。先开一个桶 $a$ 用于记录多集，其中 $a_{i}$ 表示 $2^{i}$ 的个数，而且我们知道两个 $2^{i}$ 可以“合成”一个 $2^{i+1},$ 两个 $2^{i+1}$ 可以“合成”一个 $2^{i+2}\dots.$ 所以我们在进行操作 $2$ 的时候，将 $w$ 拆成二进制进行判断，从低位往高位，如果此时桶中 $2^{i-1}$ 的数量小于 $w$ 二进制第 $i$ 位的数，可以判断无法满足条件，如果不小于，则将剩余的 $2^{i-1}$ 两两合成 $2^{i}$ ，然后继续判断下一位……

~~好好好，越讲越乱~~

例：

假设多集中此时有 $4$ 个 $2^0$ 和 $1$ 个 $2^1$ ，此时进行操作 $2$ 查询 $w=5$ ，首先十进制的 $5$ 转成二进制是 101 ，从低到高第一位开始，此时多集中有 $4$ 个 $2^0$ ，数量足够，消耗 $1$ 个 $2^0$ ，还剩 $3$ 个，然后两两合成 $2^1$ ，一共能合成 $1$ 个，所以现在有了 $2$ 个 $2^1$ ；然后看 $w=5$ 第二位是 0 ， $2$ 个 $2^1$ 足够，剩余 $2$ ，合成 $1$ 个 $2^2$ ；最后看第三位 1 ，有 $1$ 个 $2^2$ 刚好满足，所以 $w=5$ 是可以满足条件的，输出 YES.

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int a[30];  // 记录多集中2^i的数量
void ADD(int x)
{
    a[x]++;
}
bool GET(int w)
{
    int k = 0;  // 用于记录多集中2^i的数量
    for (int i = 0; w; i++)
    {
        k += a[i];  // 加上此时的多集中2^i的数量
        if (k < (w & 1))    // 如果多集中2^i的数量不能满足w的第i位(w&1 == w%2)
        {                   // 肯定不能满足条件了，因为2^(i+1)可不能拆成2^i
            return false;
        }
        k -= w & 1;
        w >>= 1;    // w右移一位，用于之后取w二进制的下一位(相当于w/=2;)
        k >>= 1;    // 将剩余的2^i合成2^(i+1)
    }
    return true;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int m, t, v;
    cin >> m;
    while (m--)
    {
        cin >> t >> v;
        if (t == 1)
        {
            ADD(v);
        }
        else
        {
            if (GET(v))
            {
                cout << "YES\n";
            }
            else
            {
                cout << "NO\n";
            }
        }
    }
    return 0;
}