AcWing 1085. 不要62
原题链接
中等
作者:
dannywang
,
2021-05-07 11:28:40
,
所有人可见
,
阅读 220
import java.util.*;
public class Main{
static int l, r;
static int[][] f = new int[11][10]; // f[i][j]表示数位个数为i、且最高位为j的数字个数
// 通过简单DP,预处理出数组f
public static void init(){
// 初始化
for(int i = 0; i <= 9; i ++){
if(i == 4) f[1][i] = 0;
else f[1][i] = 1;
}
// 状态计算
for(int i = 2; i <= 10; i ++)
for(int j = 0; j <= 9; j ++)
if(j == 4) f[i][j] = 0; // 出现数字“4”
else{
for(int k = 0; k <= 9; k ++){
if(j == 6 && k == 2) continue; // 出现“62”整体
else f[i][j] += f[i - 1][k];
}
}
}
public static int dp(int num){
if(num == 0) return 1;
List<Integer> nums = new ArrayList<>();
while(num > 0){
nums.add(num % 10);
num /= 10;
}
int res = 0;
int last = 0;
for(int i = nums.size() - 1; i >= 0; i --){
int x = nums.get(i);
// 左边分支
if(x > 0){
for(int j = 0; j < x; j ++){
if((last == 6 && j == 2) || j == 4) continue;
else res += f[i + 1][j];
}
}
if(x == 4 || (last == 6 && x == 2)) break;
else last = x;
// 右边分支
if(i == 0) res ++;
}
return res;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
init();
while(sc.hasNext()){
l = sc.nextInt();
r = sc.nextInt();
if(l + r == 0) break;
System.out.println(dp(r) - dp(l - 1));
}
}
}