题解：P15353 [COCI 2025/2026 #4] 冰激凌 / Sladoled

· · 题解

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。

关键点总结：


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