51Nod 1009 数字1的数量

1009 数字1的数量

1 秒 131,072 KB 80 分 5 级题

题目描述

给定一个十进制正整数N,写下从1开始,到N的所有正数,计算出其中出现所有1的个数。
例如:n = 12,包含了5个1。1,10,12共包含3个1,11包含2个1,总共5个1。

输入

输入N(1 <= N <= 10^9)

输出

输出包含1的个数

输入样例

12

输出样例

5

解析:
这题有点难受,我自己是不会做的。百度了,大家都说是数学逻辑或则数位dp。看了篇博客,得出自己的理解
大佬的链接

个人理解:
  看了大佬的博客,在做dp的时候是在打表,首先把一个10进制数分不同位来确定第i 位为数j 所包含的1的数量。dp[i][j] 即表示第i 位为数j 所包含的1的数量
    例如:假设我现在是第2位为1,即dp[2][1] ,它就表示19及以前的所有数包含的1的数目
    再如:假设是第3位为2,即dp[3][2] ,它表示299及以前的所有数中1的数量。
  总之,dp[i][j] 表示的是第 i 位为数 j的最大的数及之前的所有数中1的数量。

  生成dp[][]的公式:(不知道怎么写公式,就直接加代码了)

	if(j==0) {//j表示这个数是几
		dp[i][j] = dp[i-1][9];			
	} else {
		dp[i][j] = dp[i-1][9] + dp[i][j-1] + (int)Math.pow((j==1?1:0) * 10, i-1); 
		//另外在这里有个问题,今天写了个bug
		//上面的 (j==1?1:0) * 10,这样写是做了三目运算之后再乘10
		//如果写成了 j==1?1 : 0 * 10,就是先0*10,再做三目运算
		//三目运算符的两个运算符所分割的三个部分,每个部分单独成为三目运算的一部分,如果要把结果用在其他的运算中,必须打括号。
	}

  在计算1的个数的时候还需要考虑到一个问题,假设我们的数是255,一次对每一位数进行处理。首先处理2,因为上面说到了dp存的数据计算方式,所以先加dp[3][1] ,(因为dp[3][2] 表示的是1-299之间的1的数量,所以加的是dp[3][1]),然后依次处理的剩下的位数。
  当处理的某一位数是1时,需要加上比他位数低的数组成的数。例如:135,在加了dp[3][0], dp[2][2], dp[1][5] 之后,我们会忽略一部分,100-135中作为百位的1没有计算,所以还要加上(35+1)。

完整AC代码:(在看大佬博客的时候,不知道为什么他会使用long long, 后来把dp全部输出之后才发现,结果会超出int的数据范围,所以设置为long long, 但是下面的代码过题却是没问题的)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		Scanner input = new Scanner(System.in);
		
		int[][] dp = new int[11][11];
		for(int i=1; i<=9; i++) {
			dp[1][i] = 1; 
		}
		
		for(int i=2; i<=10; i++) {
			for(int j=0; j<=9; j++) {
				if(j==0) {
					dp[i][j] = dp[i-1][9];
				}
				else {
					dp[i][j] = dp[i-1][9] + dp[i][j-1] + (int)Math.pow((j==1?1:0) * 10, i-1); 
				}
				
			}
		}

		int n = input.nextInt();
		int m = n;
		
		int[] pos = new int[11];
		int index = 0;
		while(n>0) {
			pos[++index] = n%10;
			n /= 10;
		}
		
		int[] add = new int[11];
		for(int i=index; i>=1; i--) {
			int tmp = (int)Math.pow(10, i-1);
			add[i] = m%tmp; 
		}
		
		int ans = 0;
		for(int i=index; i>=1; i--) {
			if(i>1) {
				ans += pos[i]>0 ? dp[i][pos[i]-1] : 0;
				System.out.print((pos[i]>0 ? dp[i][pos[i]-1] : 0) + " ");
			} else {
				ans += dp[i][pos[i]];
				System.out.print(dp[i][pos[i]]+ " ");
			}
			if(pos[i]==1 && i>1) {
				ans += add[i]+1;
				System.out.print(add[i]+1 + " ");
			}
		}
		System.out.println(ans);
	}
}

上一篇:51nod 237 最大公约数之和 V3 杜教筛


下一篇:51nod 1781 Pinball(线段树)