1049. Counting Ones (30)

時間限制 10 ms 內(nèi)存限制 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: 12 Sample Output: 5

---

提交代碼

?

?

思路：

統(tǒng)計每位的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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Deribs4/p/4776672.html

總結

以上是生活随笔為你收集整理的pat1049. Counting Ones (30)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。