17 南宁区域赛F - The Chosen One【规律】

题目链接

https://nanti.jisuanke.com/t/19972

题意

给出一个n 然后将 n 个数 标号为 1 -> n

按顺序排列 每次抽掉 奇数位的数 然后求最后剩下那个数字的编号

思路

可以模拟一下过程 就可以发现规律

比如 n = 9

那么

1 2 3 4 5 6 7 8 9

抽掉后 就是

2 4 6 8

我们可以把这四个数字 / 2

就是

1 2 3 4

然后 可以发现 其实是递归的子问题 这个是n = 4 的情况

抽掉后 可以发现 留下

2 4 再 做除法 剩下

1 2

也是 递归的子问题

最后那个数字 就是2

可以发现规律就是 1 -> n 的数字当中 那个 能够被2整除次数最多的那个数字 就是答案

很显然 就是 <= n 的 2的幂次数

AC代码

import java.math.BigInteger; import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int t = cin.nextInt(); while (t-- != 0) { BigInteger n = cin.nextBigInteger(); BigInteger ans = new BigInteger("2"); System.out.println(ans = ans.pow(n.bitLength() - 1)); } } }

转载于:https://www.cnblogs.com/Dup4/p/9433061.html