蓝桥杯第1593题——二进制问题

2024-04-02 19:20
文章标签 问题 蓝桥 二进制 1593

本文主要是介绍蓝桥杯第1593题——二进制问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

小蓝最近在学习二进制。他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗?

输入描述

输入一行包含两个整数 N 和 K。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

7 2

输出

3

评测用例规模与约定

对于 30% 的评测用例,1 ≤ N ≤ 10^6,1 ≤ K ≤ 10。

对于 60% 的评测用例,1 ≤ N ≤ 2×10^9,1 ≤ K ≤ 30。

对于所有评测用例,1 ≤ N ≤ 10^18,1 ≤ K ≤ 50。

解题思路

这道题大致的问题就是给定一排位置,填或者不填的问题,我们可以考虑使用数位dp的思想。

对于n个位置填k个1的方案数量是典型的排列组合,虽然K的值最高只有50,计算排列组合C_{m}^{n}也是可以实现的,但这里我们综合考虑使用帕斯卡公式,即C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}

于是我们可以定义dp[i][j]:在长度为 i 的二进制序列中填 j 个 1 的组合数。

帕斯卡公式的证明就是这道题的原理,即n个数中取m个元素的组合数——包含第一个数不取,在剩下的n-1个数中取m个数;和第一个数取,在剩下n-1个数中取m-1个数的总和。

题目要求统计包含K个1的二进制数的数量,以N的二进制为1011,取k=3为例,我们可以将1011分解为以下几个区间考虑:0000~0111、1000~1001、1010~1010、1011。

这样分的理由是,第一个数不填1,考虑剩下3个位置填3个1的方法总数,这不就正好是在000~111这个长度为3的二进制序列中填3个1的排列总数吗,即dp[3][3]。

那么比111更大的数即代表着第一个数一定填1,在第二个区间中,我们是在第一个数填1的情况下,考虑第三个数不填1的排列数,即剩下1个位置填2个1满足要求——dp[1][2]。

第三个区间考虑在第一个位置和第三个位置都填1的情况下,第四个位置不填1的情况,那么就要加上在剩下0个位置填1个1的组合数——dp[0][1]。

最后还剩一个单独的1011,其目的是要留着特判,因为我们前面一直都是在遇到1的情况下考虑这个位置不填1有多少种满足要求的可能性,那么我们就会漏掉最后一个位置填1的情况没有计算,在最后一个位置填1,并且刚好满足k个1的时候,就需要增加一种组合数。

根据上述逻辑,此数据的答案即为:dp[3][3] + dp[1][2] + dp[0][1] + 1  =  1 + 0 + 0 + 1  =  2种

import java.util.*;
import java.io.*;public class Main {static long n;static int k;static long[][] dp;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextLong();k = sc.nextInt();init();System.out.println(solve(n));}public static long solve(long n) {char[] s = Long.toBinaryString(n).toCharArray();long ans = 0;// ones 用于记录已经填的1的数量int ones = 0;for (int i = 0; i < s.length; i++) {int po = s.length - i;if (s[i] == '1') {// 先考虑位置po不填1的可能性ans += dp[po - 1][k - ones];// 然后填上一个1并记录ones++;// 由于在ones等于k的时候还有一次后续什么都不填的可能性,即dp[xxx][0] = 1// 所以只在填超了以后才breakif (ones > k) {break;}}// 如果最后一位刚好填够k个1,会漏计算1种情况,需要补上if (po == 1 && ones == k) {ans++;}}return ans;}public static void init() {dp = new long[65][65];dp[0][0] = 1;for (int i = 1; i < 65; i++) {for (int j = 0; j <= i; j++) {if (j == 0) {dp[i][j] = 1;} else {dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];}}}}
}

这篇关于蓝桥杯第1593题——二进制问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/870841

相关文章

VS配置好Qt环境之后但无法打开ui界面的问题解决

《VS配置好Qt环境之后但无法打开ui界面的问题解决》本文主要介绍了VS配置好Qt环境之后但无法打开ui界面的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 目UKeLvb录找到Qt安装目录中designer.UKeLvBexe的路径找到vs中的解决方案资源

MySQL启动报错:InnoDB表空间丢失问题及解决方法

《MySQL启动报错:InnoDB表空间丢失问题及解决方法》在启动MySQL时,遇到了InnoDB:Tablespace5975wasnotfound,该错误表明MySQL在启动过程中无法找到指定的s... 目录mysql 启动报错:InnoDB 表空间丢失问题及解决方法错误分析解决方案1. 启用 inno

Java使用MethodHandle来替代反射,提高性能问题

《Java使用MethodHandle来替代反射,提高性能问题》:本文主要介绍Java使用MethodHandle来替代反射,提高性能问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录一、认识MethodHandle1、简介2、使用方式3、与反射的区别二、示例1、基本使用2、(重要)

电脑蓝牙连不上怎么办? 5 招教你轻松修复Mac蓝牙连接问题的技巧

《电脑蓝牙连不上怎么办?5招教你轻松修复Mac蓝牙连接问题的技巧》蓝牙连接问题是一些Mac用户经常遇到的常见问题之一,在本文章中,我们将提供一些有用的提示和技巧,帮助您解决可能出现的蓝牙连接问... 蓝牙作为一种流行的无线技术,已经成为我们连接各种设备的重要工具。在 MAC 上,你可以根据自己的需求,轻松地

Java 中的跨域问题解决方法

《Java中的跨域问题解决方法》跨域问题本质上是浏览器的一种安全机制,与Java本身无关,但Java后端开发者需要理解其来源以便正确解决,下面给大家介绍Java中的跨域问题解决方法,感兴趣的朋友一起... 目录1、Java 中跨域问题的来源1.1. 浏览器同源策略(Same-Origin Policy)1.

如何清理MySQL中的binlog问题

《如何清理MySQL中的binlog问题》:本文主要介绍清理MySQL中的binlog问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目http://www.chinasem.cn录清理mysql中的binlog1.查看binlog过期时间2. 修改binlog过期

如何解决yum无法安装epel-release的问题

《如何解决yum无法安装epel-release的问题》:本文主要介绍如何解决yum无法安装epel-release的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录yum无法安装epel-release尝试了第一种方法第二种方法(我就是用这种方法解决的)总结yum

IDEA下"File is read-only"可能原因分析及"找不到或无法加载主类"的问题

《IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题》:本文主要介绍IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题,具有很好的参... 目录1.File is read-only”可能原因2.“找不到或无法加载主类”问题的解决总结1.File

idea中project的显示问题及解决

《idea中project的显示问题及解决》:本文主要介绍idea中project的显示问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录idea中project的显示问题清除配置重China编程新生成配置总结idea中project的显示问题新建空的pr

redis在spring boot中异常退出的问题解决方案

《redis在springboot中异常退出的问题解决方案》:本文主要介绍redis在springboot中异常退出的问题解决方案,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴... 目录问题:解决 问题根源️ 解决方案1. 异步处理 + 提前ACK(关键步骤)2. 调整Redis消费者组