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: 12 Sample Output: 5

---

提交代码

 

 

思路：

统计每位的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

总结

以上是生活随笔为你收集整理的pat1049. Counting Ones (30)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。