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:
代码语言：javascript复制12Sample Output:
代码语言：javascript复制5题目大意：给出一个数字n，求1~n的所有数字里面出现1的个数 分析：这是一道数学问题。从第一位（个位）到最高位，设now为当前位的数字，left为now左边的所有数字构成的数字，right是now右边的所有数字构成的数字。只需要一次次累加对于当前位now来说可能出现1的个数，然后把它们累加即可。i表示当前now的位权 1.now=1时，ans =left*i right 1
2.now>1,ans =(left 1)*i
3.now=0,ans =left*i
至于为啥，你举个例子就懂了
比如5012 先枚举到2这一位，left=573，right=0，i=1;当枚举到的这位为1时，right只能=0，而left可以有000,001...到501总共502种变化，和我们给出的第二条相符
接着枚举到十位1这一位，left=50，right=2，i=10;当枚举到的这位为1时，与刚刚所不同的是r多了一点情况，right在left=50时可以为0,1,2多了right 1=3中情况，而left可以有00,01...到49(注意是56，想想为什么)总共50*i=500(此时i=10,因为此时每一种right都有0~9 10种变化)，你可以算算，和我们给出的第1条相符
接着枚举到百位0这一位，left=5，right=12，i=100;当枚举到的这位为1时，只能是left取0~4，right就不管因为都是0~9总共5*100=500种，自然是和我们给出的第3条相符的
最后枚举到千位5这一位，left=0，right=12,i=1000;运用第二条,ans =(0 1)*1000
所以答案是2505
至于怎么得到每一步的left和right，就留着给看官当思考题吧，也很简单~
代码语言：javascript复制#include<bits/stdc .h>
#define ll long long
#define rg register ll
using namespace std;
ll n,ans;
int main()
{
cin>>n;
ll now=n,left=n/10,right=0;
for(rg i=1;right<n;i*=10)
{
if(now>1)ans =(left 1)*i;
else if(now==1)ans =left*i right 1;
else if(!now)ans =left*i;
right=now*i right;
now=left;
left/=10;
//cout<<right<<" "<<ans<<endl;
}
cout<<ans<<endl;
//while(1)getchar();
return 0;
}
