1049. Counting Ones (30)

The task is simple: given any positive integer N, you are supposed to count the total number of 1's in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1's in 1, 10, 11, and 12.

Input Specification:

Each input file contains one test case which gives the positive N (<=2³⁰).

Output Specification:

For each test case, print the number of 1's in one line.

Sample Input:

12

Sample Output:

5 题目意思很好理解，数小于等于n的1的个数，注意不要漏掉11中的两个1，有几个1都要算上 本题使用动态规划结题，分析可知，给定第一个数，剩下的就可以递推得到了，例如 n = 623 可知， 比623小的数中，可以是0， 1， 2， 3， 4， 5开头，其中0开头也就是比23小的数字 6开头： 由于百位不会出现比1了，所以答案就是f(99) 5开头： 同理，f(99) . . . 1开头： 这个要注意除了f(99)外，还需要加上100个开头的1 0开头： f(99) 所有加和就是答案，综合分析可知，如果n首位first大于1， 除去首位后的数字是k， f(n) = first * f(99..9) + f(k) + 10..00 若n首位等于1， 除去首位数字是k， f(n) = f(k) + f(99..9) + k + 1 上代码：

#include 
      
       #include 
       
        #include 
        
         using namespace std;long long ex[100]; //计算n的最高10次幂， 比如123 最高为100， 也就是 10 ^ 2,  e = 2int exp(long long n){    int e = 0;    while(n  > 0)    {        e += 1;        n /= 10;    }    return e - 1;} //不知道为什么，cmath自带的函数pow（10, 2） = 99 所以自己写了一个pow函数long long pow(int n){    int prod = 1;    for(int i = 0; i < n; i++)    {        prod *= 10;    }    return prod;}long long f(long long n){    if(n == 0)        return 0;    if(n < 10)        return 1;    int e = exp(n);    long long e10 = pow(e);　　　 　　//如果是除了首位全都是0， 那么直接返回计算过的结果    if(n % e10 == 0)        return ex[e] + 1;    int first = n / e10;    if(first == 1)        return f(n % e10) + (n % e10 + 1) + ex[e];    return f(n % e10) + e10 + first * ex[e];}int main(){    long long n;    scanf("%d", &n);    int e = exp(n);    ex[1] = 1; 　　//预先算出f(99..9)的数组，以后不需要重新计算    for(int i = 2; i <= e; i++)    {        ex[i] = 10 * (ex[i - 1]) + pow(i - 1);    }    printf("%d", f(n));    return 0;}
        
       
      

此题知道， PAT不能使用%I64d读入，否则会出格式错误， 也不能使用__int64的类型，以后要注意大数使用 long long