问题描述
p1225原题链接:UVaOJ 1225 - Digit Counting
相关说明:本题为《算法竞赛入门经典(第2版)》习题 3-3
解法一:模拟(预处理)
可以提前打表 cnt 存储好所有的情况,一维索引表示输入数字 n ,二维索引范围为 0~9 的数位。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <bits/stdc++.h> using namespace std; int main() { const int MAX_VALUE = 10000, DIGIT_RANGE = 10; array<array<int, DIGIT_RANGE>, MAX_VALUE> cnt = {0}; for (int i = 1; i < MAX_VALUE; ++i) { if (i > 1) cnt[i] = cnt[i - 1]; int cur = i, digit; while (cur) { digit = cur % 10; cnt[i][digit]++; cur /= 10; } } int t, n; cin >> t; while (t--) { cin >> n; for (int i = 0; i < DIGIT_RANGE; ++i) cout << (i ? " " : "") << cnt[n][i]; cout << endl; } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
MAX_VALUE = 10000 DIGIT_RANGE = 10 cnt = [[0] * DIGIT_RANGE] * 2 for i in range(1, MAX_VALUE): if i > 1: cnt.append(cnt[i - 1].copy()) cur = i while cur: digit = cur % 10 cnt[i][digit] += 1 cur //= 10 t = int(input()) for _ in range(t): n = int(input()) for i in range(DIGIT_RANGE): print(cnt[n][i], end="\n" if i == 9 else " ") |