题目大意

已知 $N$ 种配料的所有非空子集的价格和（共 $2^N-1$ 个值），要求恢复出每种配料的价格。如果数据有误则输出 -1。

解题思路

核心思想

增量构造 + 频数分析

1. 频数统计：统计每个价格值在所有子集和中出现的次数
2. 最小元素原则：当前未使用的最小正数一定是某个配料的价格
3. 频数消去：确定一个配料价格后，消去所有包含该配料的子集和的影响

算法流程详解

1. 频数统计

• 用 dp 数组统计每个数值在所有子集和中出现的次数
• 注意：算法中令 dp[0] = 1，表示空集出现1次（便于后续计算）

2. 恢复过程

对于每次迭代：

1. 找到最小候选：找到当前最小的正数 i 满足 dp[i] > 0
2. 确定为配料价格：该值一定是某个配料的价格
3. 频数消去：对于所有 j >= i，执行 dp[j] -= dp[j-i]

3. 频数消去的原理

设当前已确定的配料集合为 $S$，新确定的配料价格为 $x$，那么：

• 包含 $x$ 的子集和 = 不包含 $x$ 的子集和 + $x$
• 因此：dp[包含x的子集和] 应该等于 dp[不包含x的子集和]
• 通过 dp[j] -= dp[j-x] 来消去包含 $x$ 的子集的影响

4. 验证条件

• 单调性检查：dp[j] >= dp[j-i] 必须成立
• 完全消去：最终所有 dp[i] 应该为0（除了 dp[0]）

复杂度分析

• 时间复杂度：$O(N \times M)$，其中 $M = 10^6$ 是数值范围
• 空间复杂度：$O(M)$

总结

本题的巧妙解法基于以下关键观察：

1. 最小元素性质：在当前剩余的子集和中，最小的正数一定是某个单元素配料的价格

2. 频数传递关系：包含某个配料的子集和频数等于不包含该配料的对应子集和频数

3. 逐步消去：通过频数相减来消除已确定配料的影响，逐步还原所有配料价格