[数据结构与算法]蓝桥杯2021年第十二届国赛真题-二进制问题（数位DP）

时间限制: 1Sec 内存限制: 128MB 提交: 1802 解决: 272

题目描述

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

输入

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

输出

输出一个整数表示答案。

样例输入

7 2

样例输出

3

提示

【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ N ≤ 106, 1 ≤ K ≤ 10。
对于 60% 的评测用例，1 ≤ N ≤ 2 × 109, 1 ≤ K ≤ 30。
对于所有评测用例，1 ≤ N ≤ 1018, 1 ≤ K ≤ 50。

解题思路：

数位dp求解；求N的二进制表示，然后在每一个二进制位上填0或1，暴力出所有的结果，然后进行记忆化搜索，对一些重复计算进行减枝操作，这样就能够降低时间复杂度。

?如果要求[L,R]上满足某个条件的数的个数，一般就是使用数位dp求解，可以利用数位dp求出[0,R]上满足条件的数的个数，然后减去[0,L]上满足条件的数的个数。

import java.util.Arrays;
import java.util.Scanner;

/*
 * 二进制问题
 */
public class BinAry_12 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		long n = in.nextLong();
		int k = in.nextInt();

		int[] a = new int[63];
		int num = 0;
		while (n != 0) {
			a[num++] = (int) (n % 2);
			n /= 2;
		}
		long[][] dp = new long[num][k + 1];
		for (int i = 0; i < num; i++) {
			for (int j = 0; j <= k; j++) {
				dp[i][j] = -1;
			}
		}
		System.out.println(recur(a, num - 1, k, true, dp));
	}

	// 数位dp
	static long recur(int[] a, int p, int k, boolean limit, long[][] dp) {
		if (p < 0) {
			if (k == 0) {
				return 1;
			} else {
				return 0;
			}
		}

		// limit为true的情况需要单独处理，每一位上的limit都为true时，即是判断最大值n是否符合题中的条件
		if (!limit && dp[p][k] != -1)
			return dp[p][k];// p k 位置的结果已经计算过了

		int up = limit ? a[p] : 1;// a包括了每一位上的约束条件， 如果上一位选择了约束条件中的值，则这一位最大也只能选择约束条件中的值

		long res = 0;
		for (int i = 0; i <= up; i++) {
			if (i == 1) {
				if (k - 1 < 0) {
					continue;
				}
				res += recur(a, p - 1, k - 1, limit && i == up, dp);
			} else {
				res += recur(a, p - 1, k, limit && i == up, dp);
			}
		}
		dp[p][k] = res;
		return res;
	}

}

时间复杂度：O(longN)。