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的个数肯定是会超时的，仔细观察就可以发现其中的规律。我们可以从每一位开始计算1的个数。
以40123位例。从个位到万位进行计算。
个位：
个位数3，左边4012右边0。个位3可以取到1，左边0000到4012，有4013个数，4013乘以10的0次方。
十位：
十位数2，左边401，右边3。左边000到401.右边可以取到0到9。十位取1时可以表示为0001x到4011x。总共有402*10个数。
百位：
百位数1，左边40，右边23。
1、左边00到39，右边xx。40*10的2次方个。注意为什么不能取到40。如果取了40后面就不能取到99。
2、左边取40，百位1，，右边可以去00到23.共23+1=24个。
千位
千位0，左边4，右边123。01xxx到31xxx，4乘以10的三次方。
万位
万位4，左边0，右边0123，1xxxx，1*10的四次方个。
下面是具体的计算规则：
以ans表示1的个数，从低位到高位依次枚举每一位，其中给出a表示后面的位数。
设当前位的数位数字为now，左边的数位l,右边的数位r;
根据now的值分三种情况讨论：
1、now等于0 ans+=l*a
2、now等于1 ans+=l*a+r+1;
3、now大于1 ans+=(l+1)*a;
下面是具体代码：
#include<iostream> using namespace std; int main(){ int n; int a = 1,ans = 0; int l,r,now; scanf("%d",&n); while(n/a != 0){ l = n/(a*10); now = n/a; r = n%a; if(now == 0){ ans += l*a; }else if(now == 1){ ans += l*a+r+1; }else ans += (l+1)*a; a *= 10; printf("%d\n",ans); } printf("%d\n",ans); return 0; }
