1049 Counting Ones (30 point(s))
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 (≤230).
Output Specification:
For each test case, print the number of 1’s in one line.
Sample Input:
12
Sample Output:
5
Code1:
//计数dp
#include <bits/stdc++.h>
using namespace std;
int main()
{int n;cin >> n;int now, left, right;int a = 1;int ans = 0;while (n / a){left = n / (a * 10);now = n / a % 10;right = n % a;if (now == 0)ans += left * a;else if (now == 1)ans += left * a + right + 1;elseans += (left + 1) * a;a = a * 10;}cout << ans;return 0;
}
Code2(通解)：
#include <bits/stdc++.h>
using namespace std;int get(vector<int> &num, int l, int r)
{int res = 0;for (int i = l; i >= r; i--)res = res * 10 + num[i];return res;
}int count(int n, int x)
{if (!n)return 0;vector<int> num;while (n){num.push_back(n % 10);n /= 10;}n = num.size();int res = 0;// 最高位不能是0for (int i = n - 1 - !x; i >= 0; i--){// i == n -1 无左边if (i < n - 1){res += get(num, n - 1, i + 1) * pow(10, i);if (!x)res -= pow(10, i);}if (num[i] == x)res += get(num, i - 1, 0) + 1;else if (num[i] > x)res += pow(10, i);}return res;
}int main()
{int n;cin >> n;cout << count(n, 1);return 0;
}