检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染.
现有 nnn 个砝码,重量分别为 aia_iai ,在去掉 mmm 个砝码后,问最多能称量出多少不同的重量(不包括 000).
观察数据范围,可以发现所有砝码组成的重量最大不超过 200020002000,考虑使用 bitset 维护.
显然重量 000 不需要任何砝码即可称量出,因此直接设置第 000 位为 111.然后对于所有的砝码,计算其与前面的砝码搭配能称出的重量,最后二进制下为 111 的位的个数即为当前状态下的结果.据此更新答案即可.
由于最终结果不能包括 000,因此需要在最终答案中 −1- 1−1.
喜欢这篇文章?为什么不考虑打赏一下作者呢?
转载或引用本文时请遵守许可协议,注明出处,不得用于商业用途!