給一個有$n$位的正整數$s$，再給一個根$R$。
把整數各位數加起來，得到新整數，再把那個新整數的各個位數加起來…直到該整數只剩一位。
插入單個數字到該整數中，使得最後那一位整數剛好等於根。
由小到大輸出所有可能的結果，且忽略最小及最大。
$2\le n\le 29, 0\le R\le 9$
其實就是一個實作題，只要枚舉$n+1$個空格，再枚舉10個數字，然後檢查。
因為$30\times 9=270$，所以只要不超過3次操作就能讓數字變到剩一位。
但是可能會有重複的(ex. $s=333$，且再插入3，不管插在哪都是一樣的)。
只要排序後再unique就好了。
複雜度似乎是$\mathcal{O}(n^3)$或$\mathcal{O}(n^2logn)$，不過在這題複雜度其實沒有很重要就是了。
實作上，使用accumulate函式可以很漂亮的解決操作過程><
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
signed main() { EmiliaMyWife
string s;
int n, k;
cin >> n >> k >> s;
n--;
auto proc = [&] (const string &s) {
return accumulate(s.begin(), s.end(), 0, [&] (int a, char c) { return a + (c ^ 48); });
};
vector<string> ans;
for(int i = 0; i <= n; i++) {
for(char c = '0'; c <= '9'; c++) {
string owo = (i ? s.substr(0, i) : "") + c + (i < n ? s.substr(i, n - i) : "");
int w = proc(owo);
while(w > 9)
w = proc(to_string(w));
if(w == k)
ans.push_back(owo);
}
}
sort(ans.begin(), ans.end()); ans.erase(unique(ans.begin(), ans.end()), ans.end());
for(int i = 1; i + 1 < ans.size(); i++)
cout << ans[i] << '\n';
}
|