很明显的 bitset 优化背包，感觉没有哪里不好想。

看注释：

#include<bits/stdc++.h>
using namespace std;

const int M = 110;        // 最多支持的背包个数（n 应 <= M）
const int T = 50001;      // 金额上限（0 ~ 50000）bitset 要开大一个，因为从 0 开始计算空间 

bitset<T> bs[M];          // bs[x] 表示第 x 个背包可达金额集合，第 i 位为 1 表示金额 i 可达
bitset<T> tp;          
int ans[M];               // ans[x] 存储第 x 个背包当前可达的非零金额个数

// 将面额 y 作为无限硬币加入到第 x 个背包中，并返回更新后的非零金额个数
// 参数 x：背包编号，y：新加入的硬币面额（保证 y > 0）
int work(int x, int y) {
    // 利用二进制拆分思想，将无限数量的 y 拆分成 y, 2y, 4y, ... 等“物品”
    // 每个“物品”可看作重量为 i 的硬币，但此处通过左移操作实现完全背包的效果
    for (int i = y; i <= T; i *= 2) {
        // 将当前背包集合整体左移 i 位，相当于在原有可达金额上再加上 i
        // 然后与原集合取并，实现“添加无限个 i”的效果（因为每次都用更新后的集合继续操作）
        tp = bs[x] << i;
        bs[x] |= tp;
    }
    // bs[x].count() 返回集合中 1 的个数，包括金额 0
    // 减 1 去掉金额 0，得到非零可达金额个数
    return bs[x].count() - 1;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;          // n 个背包，q 次操作

    // 初始化每个背包：只有金额 0 可达
    for (int i = 1; i <= n; i ++) {
        bs[i].reset();
        bs[i][0] = 1;       // 第 0 位设为 1
    }

    for (int i = 1; i <= q; i ++) {
        int x, y;
        cin >> x >> y;

        // 如果第 x 个背包已经能组成金额 y，说明该面额已经添加过
        // （因为一旦添加过 y，work 会使其成为无限硬币，所以再次查询无需重复计算）
        if (bs[x][y]) {
            cout << ans[x] << "\n";
            continue;
        }

        // 否则将面额 y 加入背包，更新答案并输出
        ans[x] = work(x, y);
        cout << ans[x] << "\n";
    }

    return 0;
}

P15353 冰激凌 题解

题目传送门

更好的阅读体验

思路：

这本质上是个完全背包问题：每个数可以无限用，问能凑出 $1\sim50000$ 里多少个数。

暴力做法就是每次加一个数 $b$，然后跑一遍背包：

for j = b → 50000:
    if 能凑出 j-b: 能凑出 j = 1

但 $q$ 有 $10^5$，每次跑 $50000$ 肯定炸。

优化：

1. bitset 压位
   dp 里只有 $0/1$，直接换成 bitset，一次算 $64$ 位。转移变成 dp[a] |= dp[a] << b。

2. 二进制拆分做完全背包
   只移一次 $b$ 相当于 0/1 背包。要能无限取，得依次移 $b,2b,4b,8b,\dots$ 然后全或起来。

3. 记忆化判重
   如果 $b$ 已经在集合里（f[a][b] == 1），直接输出上次记下的答案，不要再重算。

这样就能稳稳过掉所有点。

AC 代码（有注释）：

#include<bits/stdc++.h>
using namespace std;
// f[a] 的第 j 位是 1 就表示第 a 个集合能凑出 j
bitset<50001> f[101];
// ans[a] 存一下上次的答案，重复问的时候直接输出
int ans[101];

int main(){
    int n, q;
    scanf("%d%d", &n, &q);
    // 0 这个数啥也不选就能凑出来，方便后面转移
    for(int i = 1; i <= n; i++) f[i].set(0);

    while(q--){
        int a, b;
        scanf("%d%d", &a, &b);
        // 如果 b 已经加过了，直接扔缓存答案，省时间
        if(f[a][b]){
            printf("%d\n", ans[a]);
            continue;
        }
        // 二进制拆分模拟完全背包：b, 2b, 4b, ... 挨个左移或上去
        for(int i = b; i <= 50000; i *= 2)
            f[a] |= f[a] << i;
        // 统计能凑出的数的个数，第 0 位不算，减掉
        ans[a] = f[a].count() - 1;
        printf("%d\n", ans[a]);
    }
    return 0;
}

DP 版本（仅供理解，会超时）

这个就是不用 bitset 的纯暴力写法，思路很直白，但只能过小数据。

#include<bits/stdc++.h>
using namespace std;
// dp[a][j] 表示第 a 个集合能不能凑出 j
bool dp[101][50001];
// vis[a][b] 标记 b 是不是已经加进过第 a 个集合
bool vis[101][50001];
// cnt[a] 记录第 a 个集合当前能凑出的数的个数
int cnt[101];

int main(){
    int n, q;
    scanf("%d%d", &n, &q);
    // 0 是可以凑出来的（一个数都不选）
    for(int i = 1; i <= n; i++) dp[i][0] = 1;

    while(q--){
        int a, b;
        scanf("%d%d", &a, &b);
        // 已经加过了，直接输出答案
        if(vis[a][b]){
            printf("%d\n", cnt[a]);
            continue;
        }
        vis[a][b] = 1;
        // 正着循环就是完全背包
        for(int j = b; j <= 50000; j++){
            // 如果 j 本来不能凑出，但 j-b 能凑出，那 j 就变得能凑出了
            if(!dp[a][j] && dp[a][j-b]){
                dp[a][j] = 1;
                cnt[a]++;   // 新凑出来一个数
            }
        }
        printf("%d\n", cnt[a]);
    }
    return 0;
}

虽然这个版本代码简单好懂，但 $q=10^5$ 的时候它要跑 $5\times 10^9$ 次循环，铁定超时，所以正式过题还得用 bitset。

关键点总结：

• 完全背包 → 二进制拆分 + bitset 左移
• 判重用 f[a][b] 直接看位
• 答案 count() - 1，减掉 $0$ 占的那一位

麻烦管理员大佬审核通过一下，这是本人第一篇题解，十分感谢!