pat1049. Counting Ones (30)

1049. Counting Ones (30)

時間限制

10 ms

內存限制

65536 kB

代碼長度限制

16000 B

判題程序

Standard

作者

CHEN, Yue

The task is simple: given any positive integer N, you are supposed to count the total number of 1's in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1's in 1, 10, 11, and 12.

Input Specification:

Each input file contains one test case which gives the positive N (<=2³⁰).

Output Specification:

For each test case, print the number of 1's in one line.

Sample Input:

Sample Output:

提交代碼

思路：

統計每位的1的貢獻。

對于k位（k>=1）：

1.Ak=0，count+=AnAn-1....Ak+1AkAk-1....A1*10^(k-1)

2.Ak=1，count+=AnAn-1....Ak+1AkAk-1....A1*10^(k-1)+Ak-1Ak-2...A1+1

3.Ak>=2，count+=(AnAn-1....Ak+1AkAk-1....A1+1)*10^(k-1)

 1 #include<cstdio>
 2 #include<stack>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<stack>
 6 #include<set>
 7 #include<map>
 8 using namespace std;
 9 //count的最大值是1036019223
10 int main(){
11     int n;
12     scanf("%d",&n);
13     long long base=1;
14     long long count=0;
15     int frpart,afpart,a;
16     while(n>=base){
17         a=n/base%10;
18         frpart=n/(10*base);
19         afpart=n%base;
20         count+=frpart*base;
21         if(a==1){
22             count+=afpart+1;
23         }
24         else if(a>1){
25             count+=base;
26         }
27         base*=10;
28     }
29     printf("%lld\n",count);
30     return 0;
31 }

轉載于:https://www.cnblogs.com/Deribs4/p/4776672.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/374547.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/374547.shtml
英文地址，請注明出處：http://en.pswp.cn/news/374547.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！