前导
果然是我想多了,这道题和基础课中的模板题很像,就用数位统计DP做了,看了y总的代码后悔不已....
算法详解
$Q:$问题1:求$[a,b]$中$2$出现的次数
$A:$问题转化:实现一个函数$count(n,x)$,$1-n$中$x$出现的次数
那么[a,b]中2出现的次数就转化为了求$count(b,x) - count(a-1,x)$,$x$等于$2$
$Q:$问题2:我们如何实现$count$函数,也就是如何求x在1~n中每一位出现的次数
$A:$问题分解:求x在一个数中每一位出现的次数,我们相加就可以求出1~n中每一位出现的次数
解决方案:分情况讨论
设当前数字为$abcdefg$,求1在第4位出现的次数,$xxx1yyy$,和n的每一位进行比较
$1 <= xxx1yyy <= abcdefg == n$
1:$xxx < abc,xxx = 000 ~ abc - 1$,$yyy = 000 ~ 999$,方案数为$1000 * abc$
2:$xxx = abc$
- d < 1,abc1yyy > abc0efg,说明超过了n的范围,就不在我们的考虑范围之内了 ,方案数为0
- d = 1,yyy = 000~efg,方案数为efg + 1
- d > 1,abc1yyy < abcdefg,yyy = 000 ~ 999,abc1yyy方案数为1000
因为x == 2,所以不用考虑边界问题了
java代码
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int l = in.nextInt();
int r = in.nextInt();
System.out.print(count(r, 2) - count(l - 1, 2));
}
private static int count(int n, int x) //返回1~n中x出现的总次数
{
if(n == 0) return 0;
List<Integer> list = new ArrayList<>(); //取出n的每一位
while(n != 0)
{
list.add(n % 10);
n /= 10;
}
n = list.size();
int res = 0;
for(int i = n - 1; i >= 0; i --) //枚举位数
{
if(i < n - 1)
{
res += get(list,n - 1, i + 1) * Math.pow(10, i);
}
if(list.get(i) == x) res += get(list, i - 1, 0) + 1;
else if(list.get(i) > x) res += Math.pow(10, i);
}
return res;
}
private static int get(List<Integer> list, int l , int r)
{
int res = 0;
for(int i = l; i >= r; i --)
{
res = res * 10 + list.get(i);
}
return res;
}
}
2021.2.12.8.55 祝大家新年快乐呀!