Skip to content

51Nod 1009 数字1的数量#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description#

给定一个十进制正整数，写下从1开始，到的所有正数，计算出其中出现所有1的个数。

例如：，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。

1.3. Input#

输入

1.4. Output#

输出包含1的个数

1.5. Sample Input#

12

1.6. Sample Output#

5

1.7. Source#

51Nod 1009 数字1的数量

2. 解读#

从低位到高位，依次考虑每一数位为1时，其他的数位能够取多少种情况。

定义以下符号：

pos: 数位 posNum: 数位上的数字 posScale: 当前数位代表的数量级， left: 左边的数位 right: 右边的数位 current: 当前计数 ans: 累计计数

判断有多少种情况的方法如下：

  1. 若当前数位大于1，则将当前数位设置为1时
    • 左边的数位可以取 共 种情况
    • 右边的数位可以取 共 种情况
    • 当前的情况计数为
  2. 若当前数位等于0，则将当前数位设置为1时
    • 左边的数位可以取 共 种情况
    • 右边的数位同上，共 种情况
    • 当前的情况计数为
  3. 若当前数位等于1，则将当前数位设置为1时
    • 左边的数位同上，共 种情况
    • 右边的数位同上，共 种情况
    • 还要加上左边数位取 ，当前数位取1，右边的数位取 的情况
    • 如计算123时，要考虑 这里的24种情况
    • 当前的情况计数为

以为例

pos posNum posScale left right current ans
0 3 1 12 0 13 13
1 2 10 1 3 20 33
2 1 100 0 23 24 57

得到的答案为57

3. 代码#

#include <iostream>
using namespace std;
int Cal(int n)
{
    // 存储计数
    int ans = 0;
    // 取数位，从个位开始取到最高位
    int pos = 0;
    // 当前数位代表的数量级，posScale = 10^pos
    int posScale = 1;
    int posNum = 0, left = 0, right = 0;
    while (n / posScale) {
        // posNum，当前数位的数字
        posNum = (n / posScale) % 10;
        // 当前数位左边所有数位上的数字
        left = n / (posScale * 10);
        // 当前数位右边所有数位上的数字
        right = n % posScale;
        // 判断当前数位上的值
        if (posNum > 1) {
            // 若大于1，则将当前数位设置为1时
            // 左边的数位可以取 [0, left] 共 (left + 1) 种情况
            // 右边的数位可以取 [0, 10^pos - 1] 共 posScale 种情况
            ans += (left + 1) * posScale;
        } else if (posNum == 0) {
            // 若等于0，则将当前数位设置为1时
            // 左边的数位可以取 [0, left) 共 (left) 种情况
            // 右边的数位同上，posScale 种情况
            ans += left * posScale;
        } else if (posNum == 1) {
            // 若等于1，则将当前数位设置为1时
            // 左边的数位同上，left种情况
            // 右边的数位同上，posScale 种情况
            // 还要加上左边数位取left，当前数位取1，右边的数位取[0, right]的情况
            // 如计算123时，要考虑[100, 123]这里的24种情况
            ans += left * posScale + right + 1;
        }
        // 取下一个数位
        pos++;
        posScale *= 10;
    }
    return ans;
}
int main()
{
    int n;
    while (cin >> n) {
        cout << Cal(n) << endl;
    }
    return 0;
}

还有一种动态规划方法，参考自另一位博主的博客

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn = 20;
ll dp[maxn][maxn], a[maxn];

ll dfs(int pos, int num, int limit)
{
    if(pos == -1) return num;
    if(!limit && dp[pos][num] != -1) return dp[pos][num];
    int up = limit ? a[pos] : 9;
    ll tmp = 0;
    for(int i = 0; i <= up; i++)
        tmp += dfs(pos-1, num+(i==1), limit && i == a[pos]);
    if(!limit) dp[pos][num] = tmp;
    return tmp;
}

ll solve(ll x)
{
    int pos = 0;
    while(x)
    {
        a[pos++] = x%10;
        x /= 10;
    }
    return dfs(pos-1, 0,  1);
}

int main(void)
{
    ll n;
    memset(dp, -1, sizeof(dp));
    while(cin >> n)
        printf("%lld\n", solve(n));
    return 0;
}

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。

Back to top