2018-10-27

ZOJ 3987

大力贪心 + 还是要好好学 Python

ZOJ 3987 Numbers

题目描述

给你一个数 $n$ ，分成 $m$ 个数，要求：

$\sum ^m _ {i = 1} a_i = n$
$\texttt{OR} ^m_{i = 1}$ 最小

题解

对于 $m$ 个数，按位考虑。

对于每一位 $b$ 倒着枚举，如果这一位要填 1，就尽量多填。

怎么多填？每次 $n = \min(n - m * 2^b, n \mod 2^b )$ ，最多填 $m$ 个，否则只能填 $\frac {n} {2 ^ m}$ 个。

AC Code

if __name__ == '__main__':
    T = int(input())
    for x in range (T):
        n, m = map(int, raw_input().split()) #Python 2 的写法
        ans = (int)(0)
        cnt = 0
        ret = (int)(1)
        for i in range(10000):
                if ret * m - m >= n:
                        break
                ret = ret * 2
        while n > 0:
                # print("n = ",n,", ret = ",ret,", ans = ",ans)
                while (ret - 1) * m >= n:
                        ret = ret // 2
                ans = ans | ret
                if ret * m < n:
                        n -= ret * m
                else:
                        n = n % ret
        print(ans)
    exit(0)

本文标题:ZOJ 3987

文章作者:Babydragon

发布时间:2018-10-27, 23:20:00

最后更新:2018-10-28, 00:18:43

原始链接:http://baolintian.github.io/2018/10/27/ZOJ-3987/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。