1049 Counting Ones 甲级 xp_xht123

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

解题思路：

首先，可以想到的一定是暴力的手段，对于每一个数截取出每一位的数字，统计1的个数，如果这样写的话4 和 6测试点会过不了，因为n的范围最大可以到max_int，因此这样的作法并不是最终解法。

 因此，需要寻找结果和给定的n之间的关系

如果一个数是abcdefg

if d == 0 
abc可以的取值是000～(abc - 1)
efg可以的取值000～999
总共方案数 abc * 10^3

if d == 1
    if abc在000～(abc - 1)
    总方案数abc * 10^3
    if abc取abc
    总方案数efg + 1
    综上 abc * 10^3 + efg + 1
    
if d > 1
方案数(abc + 1) * 10^3

综上所述

错误代码

#include
#include
 
using namespace std;
 
int n;
 
int main()
{
    cin >> n;
    int res = 0;
    for(int i = 1;i <= n;i ++)
    {
        int j = i;
        while(j) 
        {
            if(j % 10 == 1) res ++;
            j /= 10;
        }
    }
    cout << res;
}

 正确代码

#include
#include
 
using namespace std;
 
int n;
 
int cal()
{
    vector<int>v;
    while(n) v.push_back(n % 10) , n /= 10;
    
    int res = 0;
    for(int i = v.size() - 1;i >= 0;i --)
    {
        int x = v[i];
        int right = 0 , left = 0 , pow = 1;
        //计算左边 (efg)
        for(int j = v.size() - 1;j > i;j --) left = left * 10 + v[j];
        //计算右边 (abc)
        for(int j = i - 1;j >= 0;j --)
        {
            right = right * 10 + v[j];
            pow *= 10;
        }
        if(x == 0) res += left * pow;
        else if(x == 1) res += left * pow + right + 1;
        else res += (left + 1) * pow;
    }
    return res;
}
 
int main()
{
    cin >> n;
    cout << cal() << endl;
    return 0;
}