题目

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(≤230).

Output Specification:
For each test case, print the number of 1’s in one line.

Sample Input:

12

Sample Output:

5

解题思路

　　题目大意： 给一个数N，统计从1到N的所有数字中1出现的次数。
　　解题思路： 这道题是《编程之美》上面的一道题（第2.4节），需要通过分析来总结规律，然后总结出公式，如果暴力去“数”1的个数，显然会超时。但如果通过公式来算的话，时间复杂度就直接降到O(1)。具体分析过程比较复杂，详情参见《编程之美》2.4节“1的数目”，这里只给出结论——
　　

/*
** @Brief:No.1049 of PAT advanced level.
** @Author:Jason.Lee
** @Date:2018-12-20
** @Solution: Accepted!
*/
#include<iostream>
#include<algorithm>
using namespace std;
int ans;
int main()
{
    int n;
    scanf(\"%d\", &n);
    int a = 1, left, right;
    while (n / a)
    {
        int now = n / a % 10;
        left = n / (a * 10);
        right = n%a;
        if (now == 0)ans += left*a;
        else if (now == 1)ans += left*a + 1 + right;
        else if (now > 1)ans += (left + 1)*a;
        a *= 10;
        cin.get();
    }
    printf(\"%d\", ans);
    return 0;
}

总结

　　这道题还是挺变态的，如果之前没有遇到过类似的题目，那么想凭借自己的临场发挥做出这道题，我只能说，你数学真的很强。但数学不强也不用着急，至少暴力的手段也能得到23分，10分钟的时间拿到23分，某种意义上讲，也算是一道“送分题”了吧。