【UVA – 1225】Digit Counting【紫书】

【UVA – 1225】Digit Counting【紫书】

问题链接:https://vjudge.net/problem/UVA-1225

udebug测试数据:https://www.udebug.com/UVa/1225

核心思路:

N最大为10000,可以提前离线存储将每个N对应的0~9出现的次数都存储到一个数组中。对于每个\(N\),其0~9数字出现次数为\(N – 1\)对应0~9出现次数加上N中各位数出现次数。

Solution:

#include <iostream>

using namespace std;

const int LIM = 10000 + 1;
int table[LIM][10];

void build() {
    for (int i = 1; i < LIM; i++) {
        for (int j = 0; j < 10; j++)
            table[i][j] = table[i - 1][j];
        int t = i;
        while (t) {
            table[i][t % 10]++;
            t /= 10;
        }
    }
}

int main(void) {
    build();
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < 10; i++) {
            if (i) putchar(' ');
            printf("%d", table[n][i]);
        }
        putchar('\n');
    }
    return 0;
}

 

相关阅读:

《算法竞赛入门经典》(紫书)全AC代码