pat1049. Counting Ones (30)
1049. Counting Ones (30)
時間限制 10 ms 內(nèi)存限制 65536 kB 代碼長度限制 16000 B 判題程序 Standard 作者 CHEN, YueThe 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 (<=230).
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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 递推DP UVA 590 Always
- 下一篇: Ubuntu Linux系统下的SVN客