noj [1475] Bachelor (找1的个数)

http://ac.nbutoj.com/Problem/view.xhtml?id=1475

[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
规律应该可以找到了吧！！！

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <string.h>
 5 #include <vector>
 6 
 7 using namespace std;
 8 
 9 int getNum(int *a,int i,int j)   //得到a数组里面[i,j]区间构成的数
10 {
11     int sum=0;
12     for(;i<=j;i++)   sum=10*sum+a[i];
13     return sum;
14 }
15 
16 int main()
17 {
18     char str[20];
19     int a[20];
20     __int64 p[]={1,10,100,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12};
21     while(~scanf("%s",str))
22     {
23         int len = strlen(str);
24         int i,left,right;
25         for(i=0;i<len;i++)   a[i]=str[i]-'0';
26         __int64 sum = 0;
27         for(i=0;i<len;i++)
28         {
29             left = getNum(a,0,i-1);;
30             if(a[i]>1)
31             {
32                 sum+=(left+1)*p[len-1-i];  //如果数字大于1 则用左边 a[0,i-1] 构成的数 加1 乘上 10的（右边位数）次方
33             }
34             else if(a[i]==1)
35             {
36                 right = getNum(a,i+1,len-1);
37                 sum+=left*p[len-1-i]+right+1;   //如果数字等于1 则用左边 a[0,i-1] 构成的数 乘上 10的（右边位数）次方  后 加上 右边a[i,len-1] 构成的数 再加上1
38             }
39             else if(a[i]==0)
40             {
41                 sum+=left*p[len-1-i];    //如果数字等于0 则用左边 a[0,i-1] 构成的数 直接乘上 10的（右边位数）次方
42             }
43         }
44         printf("%I64d
",sum);
45 
46     }
47     return 0;
48 }

解法二：先写断暴力代码测试用：

找到规律输 9：1
99：20
999：300

9999：4000

- 99999 : 50000

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<stdio.h>
 4 #include<math.h>
 5 #include<string.h>
 6 using namespace std;
 7 int main()
 8 {
 9     int i;
10     __int64 a[30]={0,1};
11     int b[100]={0};
12     char str[1000];
13     a[2]=20;
14     for(i=1;i<100;i++)
15     {
16         int cnt=0;
17         if(i%10==1)
18             cnt++;
19         if(i/10==1)
20             cnt++;
21         b[i]+=b[i-1]+cnt;
22     }
23     __int64 temp=20;
24 
25     __int64 pow[]={1,10,100,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12};
26 
27     for(i=3;i<=10;i++)
28     {
29         a[i]=i*pow[i-1];
30     }
31 
32     while(~scanf("%s",str))
33     {
34         int len=strlen(str);
35         __int64 s=0;
36         for(i=0;i<len;i++)
37         {
38             temp = str[i] - '0';
39             s=10*s+temp;
40         }
41         __int64 sum=0;
42         for(i=0;i<len-2;i++)
43             if(str[i]!='0')
44             {
45                 int p=len-i;
46                 if(str[i]=='1')
47                 {
48                     s=s%pow[p-1];
49                     sum+=a[p-1]+s+1;
50                 }
51                 else
52                     sum+=pow[p-1]+a[p-1]*(str[i]-'0');
53             }
54         sum+=b[s%100];
55         printf("%I64d
",sum);
56     }
57     return 0;
58 }