欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

相关标签: 规律