1049 Counting Ones (30 分)
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.
Each input file contains one test case which gives the positive N (≤).
Output Specification:
For each test case, print the number of 1's in one line.
12
Sample Output:
530分的题确实比其他分的好很多，这种题就比较锻炼思维。找1的个数，这个是一定不能暴力的，肯定超时。可能就只能骗分。
1 #include <bits/stdc++.h>
2 #define ll long long int
3 using namespace std;
4 int n;
5 string s;
6 int getstr(
string s){
7 int num =
0;
8 for(
int i =
0; i < s.length(); i++
)
9 num = num*
10 + s[i]-
'0';
10 return num;
11 }
12
13 ll pow(
int x){
14 int num =
1;
15 while(x--
){
16 num *=
10;
17 }
18 return num;
19 }
20 int main(){
21 cin >>
s;
22 int len =
s.length();
23 n =
getstr(s);
24 ll sum =
0;
25 ll mod = pow(len-
1), left =
0, right =
0;
26 for(
int i =
0; i < len; i++
){
27 right = n%
mod;
28 if(s[i] ==
'1'){
29 sum += (right+
1);
30 sum += left*
mod;
31 }
else if(s[i] ==
'0'){
32 sum += left*
mod;
33 }
else{
34 sum += (left+
1)*
mod;
35 }
36 left = left*
10 + s[i]-
'0';
37 mod /=
10;
38 }
39 cout << sum <<
endl;
40 return 0;
41 }
转载于:https://www.cnblogs.com/zllwxm123/p/11185301.html
