[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- 思路：
解法1：按位置计算，即分别计算个位，十位，百位，千位 。。。的 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 <stdio.h>
#include <math.h>
#include <string.h>
#include <vector> using namespace std; int getNum(int *a,int i,int j) //得到a数组里面[i,j]区间构成的数
{
int sum=;
for(;i<=j;i++) sum=*sum+a[i];
return sum;
} int main()
{
char str[];
int a[];
__int64 p[]={,,,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12};
while(~scanf("%s",str))
{
int len = strlen(str);
int i,left,right;
for(i=;i<len;i++) a[i]=str[i]-'';
__int64 sum = ;
for(i=;i<len;i++)
{
left = getNum(a,,i-);;
if(a[i]>)
{
sum+=(left+)*p[len--i]; //如果数字大于1 则用左边 a[0,i-1] 构成的数 加1 乘上 10的（右边位数）次方
}
else if(a[i]==)
{
right = getNum(a,i+,len-);
sum+=left*p[len--i]+right+; //如果数字等于1 则用左边 a[0,i-1] 构成的数 乘上 10的（右边位数）次方 后 加上 右边a[i,len-1] 构成的数 再加上1
}
else if(a[i]==)
{
sum+=left*p[len--i]; //如果数字等于0 则用左边 a[0,i-1] 构成的数 直接乘上 10的（右边位数）次方
}
}
printf("%I64d\n",sum); }
return ;
}解法二：先写断暴力代码测试用：
- 找到规律输 9：1
- 99：20
- 999：300
- 9999：4000
- 99999 : 50000
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<string.h>
using namespace std;
int main()
{
int i;
__int64 a[]={,};
int b[]={};
char str[];
a[]=;
for(i=;i<;i++)
{
int cnt=;
if(i%==)
cnt++;
if(i/==)
cnt++;
b[i]+=b[i-]+cnt;
}
__int64 temp=; __int64 pow[]={,,,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12}; for(i=;i<=;i++)
{
a[i]=i*pow[i-];
} while(~scanf("%s",str))
{
int len=strlen(str);
__int64 s=;
for(i=;i<len;i++)
{
temp = str[i] - '';
s=*s+temp;
}
__int64 sum=;
for(i=;i<len-;i++)
if(str[i]!='')
{
int p=len-i;
if(str[i]=='')
{
s=s%pow[p-];
sum+=a[p-]+s+;
}
else
sum+=pow[p-]+a[p-]*(str[i]-'');
}
sum+=b[s%];
printf("%I64d\n",sum);
}
return ;
}
noj [1475] Bachelor (找1的个数)
http://ac.nbutoj.com/Problem/view.xhtml?id=1475