C/C百题打卡做到第9题正好撞上蓝桥杯2021省赛的“砝码称重”。这道题题面短、坑不少网上各种解法满天飞但大部分人只贴一个set版本或DP版本很少有人把三种能AC的思路放在一起对比。这篇就把我的完整拆解写下来包含集合滚动模拟、二维布尔DP、bitset偏移优化以及我在调试时踩过的几个典型坑。如果你正在备赛蓝桥杯或者想练一练“状态设计”这篇可以直接当模板抄。题目背景不复杂有n个砝码每个砝码重量为wi砝码可以放在天平的任意一边也可以不放问一共能称出多少种不同的正整数重量。我举例时最喜欢用两个砝码1和4能称出的重量是1、3、4、5而不是只有1、4、5。因为4放右边、1放左边时差值3也能平衡。就这个“减法”细节让很多第一次接触的人直接翻车。数据范围给得也很“蓝桥”n最大100所有砝码总重量不超过100000。这意味着你可以容忍O(n*W)级别的算法但绝对没法跑3^n。1. 题目理解与考点拆解1.1 天平的数学模型每个砝码只有三种状态把待测物体放在天平左盘砝码可以放在左盘或右盘。平衡条件就是物体重量 左盘砝码总重量 右盘砝码总重量所以物体重量 右侧砝码总和 - 左侧砝码总和。每个砝码最终对答案的贡献只有三种放在右侧时取wi放在左侧时取-wi不放时取0。问题就变成给一组数每个数可以赋系数1、-1或0求能得到多少个不同的正结果。这个“系数化”是整道题的题眼。很多同学上来就想着模拟天平左右盘其实一旦抽象成加减法天平物理模型就不重要了。剩下的工作就是想办法枚举这些系数组合。n100时组合数是3^100显然不能硬来但所有结果都落在[0, sum]这个区间sum不超过100000这就给DP、集合、bitset留了充足空间。看到这个特征第一反应就应该是状态压缩类DP而不是DFS。1.2 数据范围决定算法选型先列一下评测数据的边界n最大100单个砝码重量最大100000但总重量被限制在100000。也就是说数组第二维撑死100000开成100005完全够用。在这个量级下DFS每层三个分支不用算都知道会超时剪枝也救不回来因为不是搜索空间小而是状态组合爆炸的问题。也正因如此三种能过的解法本质上都在做同一件事维护一个“当前可达重量集合”每来一个砝码就把集合里的每个状态和这个砝码做“加、减、不变”三种运算得到新的集合。区别只在于用什么数据结构去存这个集合以及转移方式。set版本是把集合原样摆出来DP版本是用布尔数组表示集合bitset版本是把集合压进位运算里。后面每一节都围绕这个核心展开。2. 解法一集合滚动模拟set2.1 用set存状态三种运算一次到位这是最直观、也最好写的方法。维护一个set s里面存放“处理完当前砝码后可以称出的重量”注意包括0。一开始只有0表示空组合。每读入一个砝码w我们不直接改s而是先拷贝出一份nxt再把所有新状态插进去。为什么一定要拷贝因为这一轮要基于“上一轮的集合”计算如果边遍历s边往里插这个新砝码会被当成上一轮已有的状态反复使用结果完全错乱。比如当前集合有0和1新砝码是4如果边遍历边插入从0得到4和插入然后遍历到1时又可能用到刚插入的4等于把同一个砝码用了多次最终状态会偏大。具体做法是对s里的每个重量xnxt里保留x本身表示砝码不放插入xw表示砝码放在物体对面再插入abs(x-w)表示砝码放在物体同侧最终重量取绝对值。取绝对值那里刚开始可能不习惯比如当前s里有1新砝码是4abs(1-4)得到3代表4克砝码放一边、1克砝码放另一边时能称出3克物体。如果不取绝对值而存-3后面统计和转移都麻烦取绝对值不仅保留信息还让集合规模控制在[0, sum]。2.2 完整代码与复杂度#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; setint s; s.insert(0); for (int i 0; i n; i) { int w; cin w; setint nxt(s); for (int x : s) { nxt.insert(x w); nxt.insert(abs(x - w)); } s.swap(nxt); } cout s.size() - 1 \n; return 0; }这个解法的时间复杂度是O(n * |s| * log|s|)。|s|是当前集合大小最坏约为sum1也就是10万级别。n100时总插入次数大约在千万级别set的log常数会有点慢但蓝桥杯的数据一般能过。空间上就是存一个setO(sum)。如果担心set太慢可以用unordered_set但一定要先把上一轮的集合快照保存到一个vector里再遍历vector生成新集合否则迭代器会失效且状态会串。我实测下来set版本在这道题里代码最短很适合考场上快速拿分。3. 解法二常规动态规划二维bool3.1 状态定义与转移方程如果想把解法一的“集合思维”升级成标准DP可以用布尔数组表示集合dp[i][j]表示处理完前i个砝码后能否称出重量j。true表示可以false表示不能。j的范围是0到sum。初始化dp[0][0]true因为一个砝码都不用时只能称出0这个0在最终统计时不计数。转移时对第i个砝码w分三种情况不放这个砝码状态继承dp[i-1][j]这个砝码贡献为w那么来源可能是原来的j-w也可能是w-j统一写成dp[i-1][abs(j-w)]这个砝码贡献为-w来源是原来的jw所以看dp[i-1][jw]前提是jw不超过sum。所以转移方程写成dp[i][j] dp[i-1][j] || dp[i-1][abs(j-w)] || (jw sum dp[i-1][jw])这里有个易错点第二项不要写成jw时才看dp[i-1][j-w]。当jw时目标重量j也可能从w-j转移过来。比如已有重量1来一个砝码4能称出3。这个3的来源是4-1而不是34因此必须用abs(j-w)把两种情况都覆盖。很多题解用j-w写也能过某些样例只是因为样例没触发jw的情况一旦数据加强就会WA。3.2 滚动数组与代码实现直接开二维bool数组dp[105][100005]内存大约是1001000051字节10MB左右蓝桥杯完全够。如果不想开二维也可以用滚动数组第i行只依赖第i-1行用dp[2][MAXSUM]即可。计算前把当前行清零再逐列转移注意每轮都要从上一行取值不能像普通01背包那样用一维逆序循环直接原地改因为这里有abs(j-w)和jw两个方向原地更新很容易覆盖掉本轮还没用的状态。#include bits/stdc.h using namespace std; const int MAXN 105; const int MAXSUM 100005; int w[MAXN]; bool dp[MAXN][MAXSUM]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; int sum 0; for (int i 1; i n; i) { cin w[i]; sum w[i]; } dp[0][0] true; for (int i 1; i n; i) { for (int j 0; j sum; j) { dp[i][j] dp[i - 1][j]; if (dp[i - 1][abs(j - w[i])]) dp[i][j] true; if (j w[i] sum dp[i - 1][j w[i]]) dp[i][j] true; } } int ans 0; for (int j 1; j sum; j) { if (dp[n][j]) ans; } cout ans \n; return 0; }时间复杂度O(nsum)空间复杂度O(nsum)。如果改成滚动数组空间可以降到O(sum)。这个解法最适合用来理解“状态设计”的完整逻辑也是我在打卡计划里优先手写的一版。真正比赛时不求花哨能用一对滚动数组把这个转移写对已经很稳了。4. 解法三bitset偏移优化比赛推荐4.1 用一位bit表示一个重量状态前两种解法都在用数组或set保存“哪些重量可达”本质上每个重量只是一个0/1标记。bool数组一个字节装一个标记太浪费C的bitset可以把多个标记压进一个字节还能用位运算一次性处理一整排状态。但如果直接写bs bs | (bs w) | (bs w)会遇到问题。这个公式在01背包类题目里没问题因为只做加法砝码称重有减法右移w会把重量小于w的那部分状态直接移到负下标然后丢弃。举个例子当前能称出1新砝码是4理论上34-1应该被加入但简单右移得到的下标是1-4-3bitset没有负下标于是3丢了。解决办法是给所有真实重量加一个偏移base。让bitset下标等于真实重量加base这样负重量也能映射到非负下标。base取多少取所有砝码总重量或者直接用题目给出的上限100000。真实重量范围是[-sum, sum]加上base后就会落在[base-sum, basesum]始终在bitset范围内。这样左移代表真实重量加w右移代表真实重量减w减法产生的负状态也不会丢。4.2 完整实现与答案统计转移过程依然是一条位运算bs bs | (bs w) | (bs w)。因为有base垫底右移不会把负状态丢掉它们会落在base左边对应的位置。统计答案时不能直接bs.count()-1因为同一个真实重量v可能同时存在于正方向和负方向。比如砝码1、4能称出3真实重量3在下标base3真实重量-3在下标base-3两个bit可能都为1但它们都算同一种称量结果。正确做法是遍历v从1到sum检查basev和base-v任意一个是否为1。#include bits/stdc.h using namespace std; const int MAXS 100005; const int BASE 100000; bitsetMAXS * 2 5 bs; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; int sum 0; vectorint w(n); for (int i 0; i n; i) { cin w[i]; sum w[i]; } bs[BASE] 1; for (int x : w) { bs bs | (bs x) | (bs x); } int ans 0; for (int v 1; v sum; v) { if (bs[BASE v] || bs[BASE - v]) ans; } cout ans \n; return 0; }时间复杂度接近O(n * sum / 机器字长)空间是常数级bitset约25KB是三种解法里最快的。要注意BASE按题目给的上限100000开如果题目总重量上限变了需要同步调整。实际刷题时也可以先把sum算出来再手动把bitset长度开到2*sum5但bitset模板参数必须是编译期常量动态sum不方便直接作为模板参数所以很多题解直接开200005。5. 三种解法对比与适用场景5.1 对比表格解法核心思想时间复杂度空间复杂度代码量推荐场景set模拟集合滚动存可达重量O(nSlogS)S≤sumO(sum)最短考场快速AC二维bool DP状态转移三种操作O(n*sum)O(n*sum)中等理解DPbitset偏移位运算压缩状态O(n*sum/word)O(sum)较短大范围/追求性能从结果看三者都能AC但思考角度略有不同。set模拟最接近人类直觉是“动态维护答案集合”的直接实现DP把集合概念变成状态表是算法竞赛的通用语言bitset则是对DP数组的极致压缩把状态转移变成一次位运算。实际打比赛时我一般先用set写通再用bitset优化两个版本互相验证比只背一个模板更踏实。5.2 比赛时怎么选如果你是第一次遇到这种题建议先写set。代码短、逻辑直不容易出现下标错误。如果你平时习惯动态规划也可以直接上滚动bool数组只要记得abs(j-w)那个坑就行。如果你已经确定数据范围大、时间紧那bitset是首选因为一次位运算能处理多个状态跑起来非常快。我个人还有一个习惯所有解法都先用题目样例跑一遍再用一个极小的随机数据对拍。比如随机生成n5、砝码重量在1到10之间的数据用DFS暴力结果和正解对拍能排查出很多隐蔽错误。等三份代码都输出一致再去提交基本不会翻车。6. 常见问题与调试技巧6.1 为什么DP第二项要写abs(j-w)而不是j-w这是评论区问得最多的问题。大多数背包题里状态转移是“只加不减”所以从j-w到j是唯一来源j-w为负就说明不可达。但砝码称重里新砝码可能比当前状态更大目标重量j可能是w-j得到的。比如当前状态1新砝码4能产生3此时来源是4-13如果你只判断j-w-3当然找不到。所以统一用abs(j-w)把这个“反向来源”也纳入考虑才能覆盖减法产生的所有可能。6.2 bitset右移丢状态的问题前面提过直接bs | (bsw) | (bsw)在无偏移时会丢掉“小状态减大砝码”的负结果。但有些网上的题解偏偏这样写原因是他们把砝码重量数组先排了序或者只处理了从小到大组合的情况才会恰好不漏。比赛时不要赌这种特殊情况一律用偏移量版本才安全。如果真遇到某道题状态全为正再考虑无偏移版本。6.3 数组越界与答案去重DP里abs(j-w[i])最大就是sum不会越界但jw[i]要判断小于等于sum否则可能读到数组外面。统计答案时从1开始跳过0set版本用s.size()-1注意0始终存在如果你初始化忘了insert(0)最后减1就错了。bitset统计时要按真实重量v循环检查正负两个偏移位置千万别图快直接count。6.4 环境与编译小提醒我用VS Code配的C/C环境跑这道题核心代码不依赖特定IDE命令行g也行。只是bitset头文件确实存在但建议直接#include bits/stdc.h省事。还有一点蓝桥杯评测机一般开O2bitset在O2下速度会更好本地调试时如果觉得慢可以在编译选项里加-O2试试。这道题我前前后后写过不止三遍。第一遍用set五分钟AC但没弄懂为什么abs第二遍写二维DP才真正理解状态转移的方向第三遍用bitset发现还可以这样压状态。刷题打卡的价值就在这里同一个问题换不同思路重写一遍比盲目刷十道新题更有用。如果你现在卡在“看似会做换数据就WA”的阶段建议把砝码称重的三种解法全部手敲一遍重点看转移方程里abs的位置以及bitset的偏移量设计。这两处弄通后天平类、差分约束类、甚至很多“正负系数”问题都能一眼看穿。最后再分享一个小技巧做题时先用样例确认“减法”带来的边界状态比如1和4产生31、2、3能称出6这类小数据最能暴露出abs和负下标问题。备赛蓝桥杯时把所有AC代码固定成自己的模板考试时直接调用思路会稳很多。