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

UVaOJ 1583 - Digit Generator

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

问题描述

p1583

原题链接:UVaOJ 1583 - Digit Generator

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

解法一:暴力(缩小范围)

由于 $1 \leq N \leq 10000$, 能够得到的最大数字和为 MAX_SUM = digit_sum(99999) = 45, 因此可从 $N-45$ 开始枚举(注意边界),计算当前数字是否是最小生成元,而不用每次都从头开始。由于枚举顺序,第一个找到的生成元就是最小生成元。

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
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  const int MAX_SUM = 45;
  int t, n;
  cin >> t;
  while (t--) {
    int res = 0;
    cin >> n;
    for (int i = max(1, n - MAX_SUM); i < n; ++i) {
      int digit_sum = 0, cur = i;
      while (cur) {
        digit_sum += cur % 10;
        cur /= 10;
      }
      if (i + digit_sum == n) {
        res = i;
        break;
      }
    }
    cout << res << endl;
  }
  return 0;
}
Python (注意会 TLE)
1
2
3
4
5
6
7
8
9
10
11
MAX_SUM = 45
t = int(input())
for _ in range(t):
    res = 0
    n = int(input())
    for cur in range(max(1, n - MAX_SUM), n):
        digit_sum = sum([int(x) for x in str(cur)])
        if cur + digit_sum == n:
            res = cur
            break
    print(res)

这里的 MAX_SUM 可以进一步优化,动态地获取 MAX_SUM = 9 * min(len(str(n)), 5).

解法二:暴力(预处理)

分析一下时间复杂度,解法一的时间复杂度为 $O(T * \text{max_sum})$,当 $T$ 的值非常非常大时,使用 Python 是有可能超时的。因此还有进一步优化的做法,即根据输入用例的范围,提前将所有对应的结果计算出来,存储在可查询的数据结构中,这种做法又叫 “预处理“ 或 “打表“。时间复杂度为构造表的时间加上查询表的时间 $O(N+T)$. 对于 $T$ 比较大的情况,能带来指数级别( MAX_SUM )的效率提升。

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
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  const int MAX_SUM = 45, RANGE = 100100;
  array<int, RANGE> ans = {0};
  for (int i = 1; i <= RANGE - MAX_SUM; ++i) {
    int digit_sum = 0, cur = i;
    while (cur) {
      digit_sum += cur % 10;
      cur /= 10;
    }
    if (!ans[i + digit_sum] || i < ans[i + digit_sum]) ans[i + digit_sum] = i;
  }
 
  int t, n;
  cin >> t;
  while (t--) {
    cin >> n;
    cout << ans[n] << endl;
  }
  return 0;
}
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from collections import defaultdict
 
RANGE = 100100
 
ans = defaultdict(int)
for cur in range(1, RANGE):
    digit_sum = sum([int(x) for x in str(cur)])
    if not ans[cur + digit_sum] or cur < ans[cur + digit_sum]:
        ans[cur + digit_sum] = cur
 
t = int(input())
for _ in range(t):
    n = int(input())
    print(ans[n])
AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz