1049 Counting Ones （30 分)

2019-03-27

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

Output Specification:

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

Sample Input:

Sample Output:

作者: CHEN, Yue

单位: 浙江大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

给一个数N，统计从1到N的数中，数字1出现的个数

分析

直接暴力，会有两个测试点超时。网上有一种数学方法，比较巧妙。思路如下：

分析N上各个位数字，统计各位上出现1的次数。记当前位数为cur（个位，百位等），当前位上的数字为curn（0-9），分为如下几种情况：

curn为0。例如12035，百位为0。那么百位上出现1的数字为100-199,1100-1199,…11100-11199。共计12*100个，即为百位左边数*位数。
curn为1。例如12135。百位上出现1的数字为100-199,…,11100-11199,12100-12135。即为百位左边数*位数+百位右边数+1。
curn>=2。例如12235。百位上出现1的数字为100-199,…,12100-12199,即为(百位左边数+1)*位数。

从个位计算到最高位，将各位上出现1的次数相加即可。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include<sstream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int c = 0;
    int cur = 1;
    while (cur <= n) {
        int left = n / cur / 10;
        int right = n % cur;
        int curn = n / cur % 10;
        if (curn == 0)
            c += left * cur;
        else if (curn == 1) {
            c += left * cur;
            c += right + 1;
        } else {
            c += (left + 1) * cur;
        }
        cur *= 10;
    }
    cout << c << endl;
    return 0;
}

其他

这题是《编程之美》上的一个题，如果我写的还不够明白，可以去书中看解析