题意:

你用无数个砝码,每个砝码的重量都是w的幂数,而且每个砝码重量都不同。
问能不能用天平与这些砝码称重量为m的物品。

解题思路:

如果让一些砝码表示m的话,只需要将m转化为w进制数,然后要求每一位不是0就是1,然而这里可以利用天平使m加上一个由0、1组成的w进制数等于另一个由0、1组成的w进制数,也就是说,转换成了m可以表示成两个由0、1组成的w进制数的差。

如果是0或1,明显这一位可以构造出来,不管m除以w继续变成子问题。
如果是w-1,那么被减数这一位是0,减数这一位是1,相减后还要借位,借位就是被减数减1,于是我们让m除以w再加1使得被减数无需减1,于是继续变成子问题。

因为是0和1组成的,所以想要构造出来只有这三种情况。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

51nod 1672 区间交 Previous
连通图专题 Next