题目大意：给出整数N，要求求出从1到N的十进制数中位数是1的个数之和。
思路：题目可以转化为求当每一位是1的时候，总共有多少种情况。
例如30710，我们从右向左遍历。
- 首先是0，那么它的右边的数为3071，如果我们假设它不是0而是1，那么前面的数可以取0-3070，3071不可以，因为30711 > 30710 ， 所以总共有3071种情况。
- 接下来是1，那么当左边的数取0-306的时候，右边的数可以随便取（0-9），左边的数取307的时候，右边只能取原来的数，所以共有307*10+1种。
- 然后是7，假设此位是1而不是7，那么左边的数可以取0-30，右边的数随便取（0-99），所以共有（30+1）*100种。
- 然后是0，假设是1，那么左边可以取0-2，右边随便取（0-999），所以有3*1000种。
- 最后是3，假设是1，那么右边随便取，共有（0+1）* 10000种。
规律：
- 当前位数字 == 0时，那么此位为1时有 左边数 * 当前位数；
- 当前位数字 == 1时，那么此位为1时有 左边数 * 当前位数 + 右边数 + 1；
- 当前位数字 > 1时，那么此位为1时有 （左边数+1） * 当前位数；
反思：求所有位数为1的个数，那么我们可以一位一位求，因为我们求这一位是1的情况的时候，虽然和求另外一位是1的情况的时候是有会重复数字，但是这不影响求总的1的个数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#include<iostream>
using namespace std;
int main()
{
int n, a=1, ans = 0;
int left, loc, right;
scanf("%d", &n);
while(n/a!=0)
{
left = n/(a*10);
loc = n/a%10;
right = n%a;
if(loc == 0) ans += left*a;
else if(loc==1) ans += left *a + right + 1;
else ans += (left + 1)*a;
a *= 10;
}
printf("%d", ans);
return 0;
}