题解：P17216 [ICPC 2017 Nanning R] The Chosen One

· · 题解

P17216 [ICPC 2017 Nanning R] The Chosen One

观察样例，获得答案。

题意

有 n 个人站成一排，编号从 1 到 n。每一轮删除所有当前奇数位置的人，剩下的人重新从 1 开始编号，继续删除奇数位置。求最后剩下的人的原始编号。

思路分析

观察规律：

可以发现，答案总是不超过 n 的最大的 2 的幂次。

证明

每一轮删除奇数位置，相当于将所有偶数位置保留，且它们的新编号等于原编号除以 2。经过 k 轮后，保留的是原始编号能被 2^k 整除的那些人。当剩余人数为 1 时，该人的原始编号就是最大的 2^k \le n。

因此，答案即为 2^{\lfloor \log_2 n \rfloor}。

使用高精度即可，复杂度 O(T\log n)（乘法视为 O(1)）。

code

既然是高精度那为什么不用 python 呢？

import sys
def solve():
    data = sys.stdin.read().split()
    t = int(data[0])
    ans = []
    for i in range(1, t + 1):
        n = int(data[i])
        res = 1 << (n.bit_length() - 1)
        ans.append(str(res))
    sys.stdout.write("\n".join(ans))
if __name__ == "__main__":
    solve()