不含101的数

不含101的数

真题目录: 点击去查看

E 卷 200分题型

题目描述

小明在学习二进制时，发现了一类不含101的数：

将数字用二进制表示，不能出现 101 。

现在给定一个整数区间 [l,r] ，请问这个区间包含了多少个不含 101 的数？

输入描述

输入的唯一一行包含两个正整数 l， r（ 1 ≤ l ≤ r ≤ 10^9）。

输出描述

输出的唯一一行包含一个整数，表示在 [l,r] 区间内一共有几个不含 101 的数。

用例1

输入

1 10

输出

8

说明

区间 [1,10] 内， 5 的二进制表示为 101 ，10的二进制表示为 1010 ，因此区间 [ 1 , 10 ] 内有 10−2=8 个不含 101的数。

用例2

输入

10 20

输出

7

说明

区间 [10,20] 内，满足条件的数字有 [12,14,15,16,17,18,19] 因此答案为 7。

题解

思路：

采用数组dp算法 + 记忆化搜索剪枝实现：

• dfs(int p, boolean limit, int[] [] f, Integer[] arr, int pre, int prepre)： p 当前位置，limit之前的是否为最大值? 会限制当前的取值范围, f 记忆化数组防止重复计算. pre前一位的值，prepre前两位的值

c++

#include <stdio.h>
#include <string.h>
#include<iostream>
#define MAX_LEN 32  // 假设 int 最大 32 位

int dp[MAX_LEN][2][2];
int binary[MAX_LEN];  // 存储二进制数，从高位到低位

// 递归计算
int dfs(int pos, int limit, int pre, int prepre, int len) {
    if (pos == len) return 1;  // 递归到末尾，找到一个有效方案

    if (!limit && dp[pos][pre][prepre] != -1) return dp[pos][pre][prepre];

    int maxDigit = limit ? binary[pos] : 1;  // **存储高位到低位，所以直接用 pos**
    int count = 0;

    for (int i = 0; i <= maxDigit; i++) {
        if (i == 1 && pre == 0 && prepre == 1) continue;  // 跳过非法情况
        count += dfs(pos + 1, limit && (i == maxDigit), i, pre, len);
    }

    if (!limit) dp[pos][pre][prepre] = count;  // 记忆化存储
    return count;
}

// 计算 0~num 内的合法数字个数
int digitSearch(int num) {
    int len = 0;
    memset(dp, -1, sizeof(dp));

    // **高位到低位存储二进制数**
    for (int i = 31; i >= 0; i--) {
        if (num & (1 << i)) {
            binary[len++] = 1;
        } else if (len > 0) {  // 遇到第一个1后才开始存储
            binary[len++] = 0;
        }
    }

    return dfs(0, 1, 0, 0, len);
}

int main() {
    int L, R;
    scanf("%d %d", &L, &R);
    int count = digitSearch(R) - digitSearch(L - 1);
    printf("%d\n", count);
    return 0;
}

JAVA

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

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int L = sc.nextInt();
    int R = sc.nextInt();
    int count = digitSearch(R) - digitSearch(L - 1);
    System.out.println(count);
  }

  public static int digitSearch(int num) {
    Integer[] arr =
        Arrays.stream(Integer.toBinaryString(num).split(""))
            .map(Integer::parseInt)
            .toArray(Integer[]::new);

    int[][][] f = new int[arr.length][2][2];

    return dfs(0, true, f, arr, 0, 0);
  }

  public static int dfs(int p, boolean limit, int[][][] f, Integer[] arr, int pre, int prepre) {
    if (p == arr.length) return 1;

    if (!limit && f[p][pre][prepre] != 0) return f[p][pre][prepre];

    int max = limit ? arr[p] : 1;
    int count = 0;

    for (int i = 0; i <= max; i++) {
      if (i == 1 && pre == 0 && prepre == 1) continue;
      count += dfs(p + 1, limit && i == max, f, arr, i, pre);
    }

    if (!limit) f[p][pre][prepre] = count;

    return count;
  }
}

Python

# 算法实现
def dfs(p, limit, f, arr, pre, prepre):
    if p == len(arr):
        return 1

    if not limit and f[p][pre][prepre] > 0:
        return f[p][pre][prepre]

    maxV = arr[p] if limit else 1
    count = 0

    for i in range(maxV + 1):
        if i == 1 and pre == 0 and prepre == 1:
            continue
        count += dfs(p + 1, limit and i == maxV, f, arr, i, pre)

    if not limit:
        f[p][pre][prepre] = count

    return count


def digitSearch(num):
    arr = list(map(int, list(format(num, 'b'))))
    f = [[[0 for k in range(2)] for j in range(2)] for i in range(len(arr))]
    return dfs(0, True, f, arr, 0, 0)


# 输入获取
L, R = map(int, input().split())

# 算法调用
print(digitSearch(R) - digitSearch(L - 1))

JavaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const times = (await readline()).split(",").map(Number);
  const m = parseInt(await readline());

  // T的初始取值范围
  let low = 0;
  let high = times.reduce((a, b) => a + b) - Math.max(...times);

  // 二分
  while (low <= high) {
    // 取中间值尝试
    let mid = (low + high) >> 1;

    if (check(mid)) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  console.log(low);

  function check(t) {
    // 今天总耗时
    let sum_cost = 0;
    // 今天耗时最多的题目的耗时
    let max_cost = 0;
    // 今天是否可以申请帮助
    let canHelp = true;

    // 第几天
    let day = 1;

    let i = 0;
    while (i < times.length) {
      sum_cost += times[i];
      max_cost = Math.max(max_cost, times[i]);

      if (sum_cost > t) {
        // 如果做完times[i]，总耗时超过了t
        if (canHelp) {
          // 如果可以申请帮助，那么就看耗时最长的题目的答案
          sum_cost -= max_cost;
          // 今天申请帮助的机会用完了
          canHelp = false;
          // 下面继续做下一题
          i++;
        } else {
          // 如果不能申请帮助，则今天做不了times[i]题目，只能放到明天做
          // 进入明天
          day++;
          // 重置总耗时，最大耗时题目，以及申请帮助机会
          sum_cost = 0;
          max_cost = 0;
          canHelp = true;
        }
      } else {
        // 如果做完times[i]，总耗时没有超过t，则继续做下面的题目
        i++;
      }
    }

    return day <= m;
  }
})();

Go

package main

import (
	"fmt"
)

const MaxLen = 32 // 最大二进制位数

var dp [MaxLen][2][2]int
var binary []int

// 递归计算
func dfs(pos int, limit bool, pre int, prepre int, length int) int {
	if pos == length {
		return 1 // 递归到末尾，找到一个有效方案
	}

	if !limit && dp[pos][pre][prepre] != -1 {
		return dp[pos][pre][prepre]
	}

	maxDigit := 1
	if limit {
		maxDigit = binary[pos] // 访问当前位
	}

	count := 0
	for i := 0; i <= maxDigit; i++ {
		if i == 1 && pre == 0 && prepre == 1 {
			continue // 跳过非法情况
		}
		count += dfs(pos+1, limit && (i == maxDigit), i, pre, length)
	}

	if !limit {
		dp[pos][pre][prepre] = count // 记忆化存储
	}

	return count
}

// 计算 0~num 内的合法数字个数
func digitSearch(num int) int {
	binary = []int{}
	started := false // 标记是否遇到了第一个 1

	// **高位到低位存储二进制数**
	for i := 31; i >= 0; i-- {
		if num&(1<<i) > 0 {
			binary = append(binary, 1)
			started = true
		} else if started { // 遇到第一个 1 后才开始存储后续 0
			binary = append(binary, 0)
		}
	}

	length := len(binary) // 记录二进制长度

	// 初始化 dp 数组
	for i := range dp {
		for j := range dp[i] {
			for k := range dp[i][j] {
				dp[i][j][k] = -1
			}
		}
	}

	return dfs(0, true, 0, 0, length)
}

func main() {
	var L, R int
	fmt.Scan(&L, &R)
	count := digitSearch(R) - digitSearch(L-1)
	fmt.Println(count)
}