MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1225 - Digit Counting
AOAPC II

UVaOJ 1225 - Digit Counting

Chai
2021-11-24 0:00:00在线评测阅读 236

问题描述

p1225

原题链接:UVaOJ 1225 - Digit Counting

相关说明:本题为《算法竞赛入门经典(第2版)》习题 3-3

解法一:模拟(预处理)

可以提前打表 cnt 存储好所有的情况,一维索引表示输入数字 n ,二维索引范围为 0~9 的数位。

C++
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;
}
Python
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 " ")
AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz