Loner John 的博客
0%

csuoj-算法-Counting_Ones

发表于 更新于 分类于 Valine：

题目

解题思路

N<2^30 ,计算1~N中1出现的的次数M。使用暴力遍历时间肯定是不够的。
这里使用另一种方法计算：令N是k位十进制数，设第i位1出现的次数为mi。则M=m1+m2+m3+···+mk。所以现在的目标是求mi。
设第i位的数为ci。求mi时根据ci的不同分三种情况讨论。
以N=13105为例：
1.当i=4时，ci=3大于1，则m4=(N/10^i+1) ×10^(i-1) =(13105/10^4+1) ×105
2.当i=3时，ci=1等于1，则m3=N/10^i×10^(i-1)+N%10^(i-1)+1 =13105/10^3×10^2+13105%10^2+1
3.当i=2时，ci=0小于1，则m2=N/10^i×10^(i-1) =13105/100×10

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long N=scanner.nextLong();
        String S= String.valueOf(N);
        int nm=S.length();
        long ans= 0L;
        for (long f = 1,i=1, b = 1; i <= nm; i++) {
            f *=10;
            long flag=N/b%10;
            if (flag>1){
                ans+=(N/f+1)*b;
            }else if (flag==1){
                ans+=N/f*b+N%b+1;
            }else {
                ans+=N/f*b;
            }
            b *=10;
        }
        System.out.println(ans);
    }
}