nyoj-648-数字1的数量

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 using namespace std;
 6 bool cmp(int a,int b)
 7 {
 8     return a>b;
 9 }
10 int main()
11 {
12     int record1(int n);
13     int n;
14     while(scanf("%d",&n)!=EOF)
15     {
16         printf("%d
",record1(n));
17     }
18     return 0;
19 }
20 int record1(int n)
21 {
22     int lnum,rnum,num,sum=0,flag=1;
23     while(n/flag!=0)
24     {
25         rnum=n-(n/flag)*flag;
26         num=(n/flag)%10;
27         lnum=n/(flag*10);
28         switch(num)
29         {
30             case 0: sum+=lnum*flag; break;
31             case 1: sum+=lnum*flag+rnum+1; break;
32             default :sum+=(lnum+1)*flag; break;
33         }
34         flag*=10;
35     }
36     return sum;
37 }

编程之美上讲的方法：本位如果为0，则出现1的个数为这位左边的数*位数

如果为1 ，则出现1的个数为这位左边的数*位数+右边的+1

大于1，则出现1的个数为（这位左边的数+1）*位数

效率提高40000倍

其实就是找规律