-
[1475] Bachelor
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
-
炎热的暑期集训就要结束了，在这短短的20天，大家都很努力，因为很多都是光棍嘛。balabala
所以 Marknoon 先森一直耿耿于怀，毕竟他也是单身嘛。
有一天，Marknoon 先森看着一串数字，发现了那个跟他同命相连的数字1，所以他就开始无聊起来，想知道从数字1到数字N，一共出现了几个1。
例如N=12，则1的个数为5，出现1的数字分别为1,10,11,12。
- 输入
-
输入一个数N(1 <= N <= 2147483647)。
- 输出
-
输出从1到N中所有数字里出现 1 的个数。
- 样例输入
-
3
13
123
- 样例输出
-
1
6
57
- 提示
-
无
- 来源
-
Hungar
按位置计算，即分别计算个位，十位，百位，千位 。。。的 1 出现的次数，然后将他们的个数和输出
这里以 2145 为例进行说明： 个位为 1 的情况 ： _ _ _ 1 横线部分 可以是 000 到 214 的任意数字 所以个位 一共有 215个 1 ------- （214 + 1）
十位为 1 的情况： _ _ 1 _ 横线部分 可以是 000 到 219 的任意数字 十位 一共有 220 个 1 ------- （21 +1）*10
百位为 1 的情况： _ 1 _ _ 横线部分 可以是 000 到 245 的任意数字 百位 一共有 246 个 1 ------ 2 * 100 +45 +1
千位为 1 的情况： 1 _ _ _ 横线部分 可以是 000 到 999 的任意数字 千位 一共有 1000 个 1 ------ （0 + 1）* 1000
当然 还有 为 0 的情况 如果是 2105 的话 则 有 21* 10 ---- 十位 有 210 个 1
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[20];
int digit[20];
long long Zero[20]={1,10,100,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12};
int cal(int l,int r){ //得到digit数组里面[i,j]区间构成的数
int ans=0;
for(int i=l;i<=r;i++)
ans=ans*10+digit[i];
return ans;
}
int main(){
//freopen("input.txt","r",stdin);
while(~scanf("%s",str)){
int len=strlen(str);
for(int i=0;i<len;i++)
digit[i]=str[i]-'0';
long long ans=0;
int l,r;
for(int i=0;i<len;i++){
l=cal(0,i-1);
if(digit[i]>1) //如果数字大于1 则用左边 digit[0,i-1] 构成的数 加1 乘上 10的（右边位数）次方
ans+=(l+1)*Zero[len-1-i];
else if(digit[i]==1){ //如果数字等于1 则用左边 digit[0,i-1] 构成的数 乘上 10的（右边位数）次方 后 加上 右边digit[i,len-1] 构成的数 再加上1
r=cal(i+1,len-1);
ans+=l*Zero[len-1-i]+r+1;
}else if(digit[i]==0) //如果数字等于0 则用左边digit[0,i-1] 构成的数 直接乘上 10的（右边位数）次方
ans+=l*Zero[len-1-i];
}
cout<<ans<<endl;
}
return 0;
}