2680. 「BalticOI 2010」糖果 candies 题解

问题分析

我们有 $N$ 个包装，每个包装有 $B_i$ 颗糖果。我们可以选择任意一些包装给顾客，糖果总数就是这些包装的和。

目标：

1. 初始状态：可以构成多少种不同的糖果总数（不同选项数）
2. 可以修改一个包装的糖果数（从 $B_i$ 改为某个值 $Q$）
3. 要求最大化可以构成的不同糖果总数
4. 输出方案：要修改哪个包装（$P$），改成什么值（$Q$）
   • 如果有多个最优解，输出 $P$ 最小的
   • 如果 $P$ 相同，输出 $Q$ 最小的

关键观察

1. 问题转化

这是一个子集和问题：给定 $N$ 个数，能组成哪些不同的和？

初始的不同选项数 = 能组成的不同正整数的个数（因为不能给 0 个糖果）。

2. 修改策略

我们只能修改一个数，将其值 $P$ 改为 $Q$。

对于每个可能的 $P$（即每个 $B_i$），我们枚举所有可能的 $Q$（从 1 到某个上限），计算修改后的不同选项数。

3. 计算不同选项数

使用动态规划 / 背包：

• 初始：dp[s] = true 表示能组成和 $s$
• 修改一个数 $P→Q$：相当于从集合中删除 $P$，加入 $Q$

算法思路

1. 初始状态计算

用 bitset 优化：

bitset<MAX_SUM> dp;
dp[0] = 1;  // 可以组成0
for (int i = 0; i < N; i++) {
    dp |= dp << B[i];
}
// 能组成的不同正整数的个数 = dp中1的个数 - 1（去掉0）
int initial_cnt = dp.count() - 1;

2. 修改一个数的计算

对于每个 $P$（每个包装值）：

1. 先去掉 $P$：相当于反向操作
2. 然后加入 $Q$：枚举可能的 $Q$

关键优化：不需要对每个 $Q$ 都重新计算整个背包。

我们可以先预处理：

• dp_without_P：去掉 $P$ 后能组成的和
• 然后对于每个 $Q$，在 dp_without_P 基础上加入 $Q$

3. 计算 dp_without_P

使用逆背包思想：

• 正常背包：dp_new = dp_old | (dp_old << x)
• 逆背包：dp_without = dp_all & ~(dp_without << x) >> x（需要仔细推导）

更简单的方法：对于每个 $P$，重新计算去掉 $P$ 的背包，复杂度 $O(N \cdot MAX_SUM)$，对于 $N=100, MAX_SUM=7000*100=7\times10^5$ 可能较大。

但我们可以优化：由于 $N$ 不大（100），可以接受 $O(N^2 \cdot MAX_SUM/N)$ 的复杂度。

详细算法

方法1：暴力枚举（可行）

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

const int MAX_SUM = 7000 * 100 + 10;  // 最大可能和

int main() {
    int N;
    cin >> N;
    vector<int> B(N);
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }
    
    // 初始背包
    bitset<MAX_SUM> dp_init;
    dp_init[0] = 1;
    for (int x : B) {
        dp_init |= dp_init << x;
    }
    int initial_cnt = dp_init.count() - 1;
    
    // 尝试修改每个数
    int best_P = 0, best_Q = 0, best_cnt = initial_cnt;
    
    // 枚举要修改哪个包装
    for (int idx = 0; idx < N; idx++) {
        int P = B[idx];
        
        // 计算去掉P后的背包
        bitset<MAX_SUM> dp_without;
        dp_without[0] = 1;
        for (int i = 0; i < N; i++) {
            if (i != idx) {
                dp_without |= dp_without << B[i];
            }
        }
        
        // 枚举新的值Q
        // Q的范围：1到某个上限，比如最大和+1
        int max_Q = MAX_SUM - 1;
        for (int Q = 1; Q <= max_Q; Q++) {
            if (Q == P) continue;  // 修改为相同值无意义
            
            // 在dp_without基础上加入Q
            bitset<MAX_SUM> dp_new = dp_without | (dp_without << Q);
            int cnt = dp_new.count() - 1;
            
            if (cnt > best_cnt || (cnt == best_cnt && (P < best_P || (P == best_P && Q < best_Q)))) {
                best_cnt = cnt;
                best_P = P;
                best_Q = Q;
            }
        }
    }
    
    cout << best_P << " " << best_Q << endl;
    return 0;
}

问题：复杂度太高

• 外层：枚举 $N$ 个 $P$（100）
• 内层：枚举 $Q$（最多 $7\times10^5$）
• 计算每个 $Q$ 的背包：$O(MAX_SUM/word)$ ≈ $7\times10^5/64 ≈ 10^4$
• 总复杂度：$100 \times 7\times10^5 \times 10^4 ≈ 7\times10^{11}$ 太大

优化方法

1. 减少 $Q$ 的枚举范围

$Q$ 不需要枚举到 $MAX_SUM$，只需枚举到当前最大和 + 最大 $B_i$ 即可。

2. 预处理去掉每个 $P$ 的背包

我们可以先计算完整的背包 dp_all，然后对于每个 $P$，用逆背包快速计算 dp_without_P。

逆背包公式： 如果 dp_all 是包含所有数的背包，那么去掉 $x$ 后的背包可以通过：

dp_without = dp_all;
for (int s = x; s <= max_sum; s++) {
    if (dp_without[s] && dp_without[s - x]) {
        dp_without[s] = 0;
    }
}

但这样可能会错误地去掉一些组合。

更可靠的方法：使用生成函数思想，但实现复杂。

3. 更好的方法：重新思考问题

我们其实不需要枚举所有 $Q$！可以观察到：

• 修改一个数 $P→Q$ 后，新的能组成的集合 = 旧集合 ∪ (旧集合 + (Q-P))
• 因为只是把 $P$ 换成了 $Q$，相当于所有包含原来 $P$ 的组合，现在 $P$ 变成 $Q$，所以和增加了 $Q-P$

设 $S$ 是原集合（能组成的和），$S_P$ 是包含 $P$ 的和组成的集合，那么： 新集合 = $S ∪ (S_P + (Q-P))$

其中 $S_P$ 可以通过：$S_P = S ∩ (S >> P)$（需要处理边界）

最终算法

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

const int MAX_SUM = 7000 * 100 + 10;

int main() {
    int N;
    cin >> N;
    vector<int> B(N);
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }
    
    // 初始背包
    bitset<MAX_SUM> dp;
    dp[0] = 1;
    for (int x : B) {
        dp |= dp << x;
    }
    
    // 计算包含每个数P的集合
    vector<bitset<MAX_SUM>> contain_P(N);
    for (int i = 0; i < N; i++) {
        int P = B[i];
        // 计算不包含P的背包
        bitset<MAX_SUM> dp_without;
        dp_without[0] = 1;
        for (int j = 0; j < N; j++) {
            if (j != i) {
                dp_without |= dp_without << B[j];
            }
        }
        // 包含P的集合 = 全集 - 不包含P的集合
        contain_P[i] = dp ^ dp_without;
    }
    
    // 初始计数
    int best_cnt = dp.count() - 1;
    int best_P = 0, best_Q = 0;
    
    // 枚举每个P和可能的Q
    for (int i = 0; i < N; i++) {
        int P = B[i];
        
        // Q的范围：我们只需要考虑能增加新和的Q
        // 新的和 = 旧和 ∪ (包含P的集合 + d)，其中d=Q-P
        
        // 枚举d的变化范围
        int max_d = 20000;  // 合理范围，因为最大和约70000
        for (int d = -P+1; d <= max_d; d++) {
            int Q = P + d;
            if (Q <= 0) continue;
            
            // 计算新集合
            bitset<MAX_SUM> new_dp = dp;
            
            // 将包含P的集合平移d
            if (d > 0) {
                new_dp |= contain_P[i] << d;
            } else {
                new_dp |= contain_P[i] >> (-d);
            }
            
            int cnt = new_dp.count() - 1;
            if (cnt > best_cnt || (cnt == best_cnt && (P < best_P || (P == best_P && Q < best_Q)))) {
                best_cnt = cnt;
                best_P = P;
                best_Q = Q;
            }
        }
    }
    
    cout << best_P << " " << best_Q << endl;
    return 0;
}

复杂度分析

预处理

• 计算初始背包：$O(N \cdot MAX_SUM / word)$
• 计算每个 contain_P[i]：$O(N^2 \cdot MAX_SUM / word)$ 对于 $N=100, MAX_SUM=70000$，大约 $100^2 \times 70000/64 ≈ 10^7$ 次操作，可行。

枚举

• 外层：$N$ 次（100）
• 内层：枚举 $d$，假设范围 20000
• 每次操作：bitset 移位和或运算，$O(MAX_SUM/word) ≈ 70000/64≈1000$
• 总复杂度：$100 \times 20000 \times 1000 ≈ 2\times10^9$ 稍大，但 bitset 操作很快，可能能过

进一步优化

1. 减少 $d$ 的枚举范围：实际上 $d$ 不需要太大，因为和超出最大范围无意义
2. 只枚举有意义的 $d$：观察哪些 $d$ 能产生新和

更优的 $d$ 枚举方法

我们不需要枚举所有 $d$，只需要枚举那些能让 contain_P[i] 产生新和的 $d$。

对于每个缺失的和 $t$（即 $dp[t]=0$ 但 $t>0$），我们需要检查是否存在某个 $s$ 使得：

• $s$ 在 contain_P[i] 中（即 $s$ 包含 $P$）
• $s + d = t$，其中 $d = Q - P$

所以 $d = t - s$。

因此，对于每个缺失的和 $t$，我们检查是否存在 s \in \text{contain_P[i]} 使得 $t-s$ 是合法的 $d$。

枚举所有缺失的和 $t$（最多 $MAX_SUM$ 个），对于每个 $t$，检查是否存在 $s$。

// 更高效的枚举d
bitset<MAX_SUM> missing = ~dp;  // 不能组成的和
missing[0] = 0;  // 0不算

// 对于每个P
for (int i = 0; i < N; i++) {
    int P = B[i];
    
    // 收集所有可能的d
    unordered_set<int> candidate_d;
    
    // 对于每个缺失的和t
    for (int t = 1; t < MAX_SUM; t++) {
        if (!missing[t]) continue;
        
        // 我们需要检查是否存在s使得s在contain_P[i]中且t-s是合理的d
        // 更高效：遍历contain_P[i]中的s
        // 我们可以用bitset快速检查
        // 但这里简化：只检查几个值
        
        // 限制范围：s应该在[P, max_sum]之间
        // 实际上，contain_P[i]中的最小和是P
        int min_s = P;
        int max_s = min(t + P, MAX_SUM-1);  // 因为d不能太大
        
        for (int s = min_s; s <= max_s; s++) {
            if (contain_P[i][s]) {
                int d = t - s;
                if (d != 0) {  // d=0无意义
                    candidate_d.insert(d);
                }
            }
        }
    }
    
    // 枚举候选的d
    for (int d : candidate_d) {
        int Q = P + d;
        if (Q <= 0) continue;
        
        bitset<MAX_SUM> new_dp = dp;
        if (d > 0) {
            new_dp |= contain_P[i] << d;
        } else {
            new_dp |= contain_P[i] >> (-d);
        }
        
        int cnt = new_dp.count() - 1;
        if (cnt > best_cnt || (cnt == best_cnt && (P < best_P || (P == best_P && Q < best_Q)))) {
            best_cnt = cnt;
            best_P = P;
            best_Q = Q;
        }
    }
}

总结

本题的关键：

1. 使用 bitset 高效处理子集和问题
2. 理解修改一个数的影响：新集合 = 旧集合 ∪ (包含该数的集合平移 $d$)
3. 通过预处理 contain_P[i] 加速计算
4. 合理枚举 $d$ 值，而不是枚举所有 $Q$