-
[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
按位置计算，即分别计算个位，十位，百位，千位 。。。的 出现的次数，然后将他们的个数和输出
这里以 为例进行说明： 个位为 的情况 ： _ _ _ 横线部分 可以是 到 的任意数字 所以个位 一共有 215个 ------- （ + ）
十位为 的情况： _ _ _ 横线部分 可以是 到 的任意数字 十位 一共有 个 ------- （ +）*
百位为 的情况： _ _ _ 横线部分 可以是 到 的任意数字 百位 一共有 个 ------ * + +
千位为 的情况： _ _ _ 横线部分 可以是 到 的任意数字 千位 一共有 个 ------ （ + ）*
当然 还有 为 的情况 如果是 的话 则 有 * ---- 十位 有 个
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[];
int digit[];
long long Zero[]={,,,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12};
int cal(int l,int r){ //得到digit数组里面[i,j]区间构成的数
int ans=;
for(int i=l;i<=r;i++)
ans=ans*+digit[i];
return ans;
}
int main(){
//freopen("input.txt","r",stdin);
while(~scanf("%s",str)){
int len=strlen(str);
for(int i=;i<len;i++)
digit[i]=str[i]-'';
long long ans=;
int l,r;
for(int i=;i<len;i++){
l=cal(,i-);
if(digit[i]>) //如果数字大于1 则用左边 digit[0,i-1] 构成的数 加1 乘上 10的（右边位数）次方
ans+=(l+)*Zero[len--i];
else if(digit[i]==){ //如果数字等于1 则用左边 digit[0,i-1] 构成的数 乘上 10的（右边位数）次方 后 加上 右边digit[i,len-1] 构成的数 再加上1
r=cal(i+,len-);
ans+=l*Zero[len--i]+r+;
}else if(digit[i]==) //如果数字等于0 则用左边digit[0,i-1] 构成的数 直接乘上 10的（右边位数）次方
ans+=l*Zero[len--i];
}
cout<<ans<<endl;
}
return ;
}