MdOIR5-A Python 验题人做法

· · 题解

考虑到这道题是简单题，读者仍然会比较依赖代码，因此不同的语言是必须的。

本文将仅提供 Python 3 代码。

做法

看到每次跳 2 的整数次幂，不难想到二进制。再想想它和二进制之间的联系。

每一步向左或向右太麻烦，不如我们先强制向右 2^k 步，然后允许不记步数地向左 2^{k+1} 步。不难发现这和原来说的是一回事。

向左跳的总长度可以是 2,4,8,\ldots 的任意组合，显然可以组成所有自然数中的偶数。

向右跳 k 秒可以跳 2^{k+1}-1 步，因此如果 2^{k+1}-1\ge n，并且 2^{k+1}-1-n 是个偶数，那么 k 就一定是合法的。

实现

多测的实现：用 int(input()) 读入 T 后，使用 for i in range 生成一个循环。你不必担心 int(input()) 被调用多次，因为第一次输入 T 后，这个 range 就确定了。

接下来求最小的 k 使得 2^{k+1}-1\ge n。我们发现这个问题相当于问 n 的二进制是几位数。

注意到 Python 3 自带 bin 函数，返回一个有 0b 前缀的字符串。因此，如果 s=bin(int(input()))，那么减去 3 就是所需的 k。

最后判断它是不是偶数。我的写法将要输出的 -1 或 len(s)-3 写进列表，看二进制末位是不是 0，并将布尔值转为下标取出对应的结果。

把上面三句话连在一起，就得到了本题代码：

for i in range(int(input())):
    s=bin(int(input()))
    print([-1,len(s)-3][s[-1]!='0'])

如果你的 Python 还不熟练，你可以不压行，将上面每个功能拆开写，更容易理解。