基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题
给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。
例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。
Input
输入N(1 <= N <= 10^9)
Output
输出包含1的个数
Input示例
12
Output示例
5
注意数据规模，只好找规律了。
代码实现：
1 #include<cstdio> 2 int n,a=1,ans; 3 int main(){ 4 scanf("%d",&n); 5 while(n>=a){ 6 ans+=n/(10*a)*a; 7 if(n/a%10>1) ans+=a; 8 if(n/a%10==1) ans+=n%a+1; 9 a*=10; 10 } 11 printf("%d\n",ans); 12 return 0; 13 }
有人说是数位DP什么的。
题目来源：51Nod