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:
12
Sample Output:
5
题意
给定一个正整数 N(<=230)，要求计算所有小于 N 的正整数的各个位置上，1 出现的次数之和。
分析
比较有思维难度的一题，核心在于找规律。10ms 的时间限制表明了不能用常规的循环遍历来解决。需要从简单的 case 找规律，逐步扩大到常规的情况。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
//规律0~9有1个1；0~99有20个1；0~999有300个1...
using namespace std;
#define UP 10
int a[UP] = {};
void mka(){
for (int i=; i<UP; i++) {
double tmp = pow(, i-);
a[i] = tmp * i;
}
}
int getD(int n) {//得出几位数，123是3位数
int cnt = ;
while (n!=) {
n/=;
cnt++;
}
return cnt;
} int main()
{
mka();
int N;
scanf("%d", &N);
int sum = ;
while (N != ) {//每次循环处理最高位
if (N< && N>=) {
sum += ;
break;
}
int d = getD(N);//d位数
double tmp = pow(, d-); int t = tmp;
int x = N / t;//最高位的数字
if (x ==) {
sum += N - x*t + ;
}
else if (x>) {
sum += t;
}
sum += x*a[d-];
N -= x*t;//去掉最高位，处理后面的数
}
printf("%d", sum); return ;
}