UVaOJ 1583 - Digit Generator

问题描述

解法一：暴力（缩小范围）

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

#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;
}

#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;

}

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 = 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 ）的效率提升。

#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;
}

#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;

}

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])

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 字符串