Java 蓝桥杯 算法训练 二进制数数
程序员文章站
2024-02-21 18:58:22
...
试题 算法训练 二进制数数
资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
给定L,R。统计[L,R]区间内的所有数在二进制下包含的“1”的个数之和。
如5的二进制为101,包含2个“1”。
输入格式
第一行包含2个数L,R
输出格式
一个数S,表示[L,R]区间内的所有数在二进制下包含的“1”的个数之和。
样例输入
2 3
样例输出
3
数据规模和约定
L<=R<=100000;
本来是使用穷举法做的,后来列了一遍二进制数 1 10 11 100 101……发现了数数字1有规律,用递推做出来了,穷举:140ms,递推:93ms
穷举:
递推:
二进制数数1规律:
二进制数—1的个数
长度为1:1—1
长度为2:10—1 11—2
长度为3:100—1 101—2 110—2 111—3
可以发现从长度为2开始
前半部分二进制数1的个数会是上一个长度的二进制数1的个数
后半部分为前半部分1的个数+1
比如:100 101的1的个数 1、2 是长度为2的1的个数1、2 ,
110 111 的1的个数 2、3 是前半部分1的个数 1+1=2、2+1=3。后面以此类推
import java.util.Scanner;
public class Main {
//用来存储每个二进制数中1的个数 0-1 1-2...
static int bNum[];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int L=sc.nextInt();
int R=sc.nextInt();
//获取最大数的长度
int length=Integer.toBinaryString(R).length();
//获取从1到最大长度的二进制数个数
int i=(int)Math.pow(2,length)-1;
bNum=new int[i];、
//bNum初始化
bNum[0]=1;
//获取每个长度的二进制数中1的个数 从长度2开始
for(int x=2;x<=length;x++)
add(x);
//计算从L到R的二进制中1的个数
int sum=0;
for(int x=L-1;x<=R-1;x++)
sum+=bNum[x];
System.out.println(sum);
}
public static void add(int le) {
//每个长度开始的下标 比如:长度2 开始下标为1
int s=(int)Math.pow(2,le-1)-1;
//每个长度结束的下标 比如:长度2 结束下标为3
int e=(int)Math.pow(2,le)-1;
//上一个长度开始的下标 比如:长度2时 bs获取长度1的开始下标为0
int bs=(int)Math.pow(2,le-2)-1;
//每个长度前半部分的赋值
for(int x=s;x<s+(e-s)/2;x++)
bNum[x]=bNum[bs++];
//每个长度后半部分的赋值
for(int x=s+(e-s)/2;x<e;x++)
bNum[x]=bNum[s++]+1;
}
}