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));
}
}
}

最后

以上就是优秀荔枝为你收集整理的17 南宁区域赛 F - The Chosen One 【规律】的全部内容，希望文章能够帮你解决17 南宁区域赛 F - The Chosen One 【规律】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。