17 南宁区域赛 F - The Chosen One 【规律】
程序员文章站
2022-04-03 08:21:07
...
题目链接
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));
}
}
}