AT_abc443_f Non-Increasing Number 题解
属于是看上去是模板，实际上有点小巧思的题目。
考虑我们如何比较两个方案大小。可以先比位数然后比字典序。因此我们只需要先求出最小位数然后再构造最小字典序方案即可。
和数位以及倍数相关容易想到同余最短路（和这题很像）。我们拆成
考虑每次往后拼一位。对于每个
接下来是构造方案。容易想到建出最短路径树然后直接贪心选择即可。
到这里其实没啥思维难度。
接下来是实现部分。首先暴力连边是
但是题解有一个非常巧妙的不用显式建图的方法。显然最短路不只一条，我们希望找到最短的那条。我们将代价设置为
我们依旧考虑一次扩展，每次扩展都是往后加一个字符，根据字典序的比较方法，如果如果前面
实际上我们也不需要
参考代码： 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
namespace numbers {
template <typename T>
T inf() {
assert(false);
}
template <>
int inf<int>() {
return 0x3f3f3f3f;
}
template <>
uint inf<uint>() {
return 0x3f3f3f3f;
}
template <>
ll inf<ll>() {
return 0x3f3f3f3f3f3f3f3f;
}
template <>
ull inf<ull>() {
return 0x3f3f3f3f3f3f3f3f;
}
} // namespace numbers
namespace graph {
const auto index = [](uint mod, uint last_digit) {
return mod * 10 + last_digit;
};
constexpr const uint npos = static_cast<uint>(-1);
struct graph {
uint n;
std::vector<uint> dis;
std::vector<uint> prev_point;
void bfs() {
std::fill(dis.begin(), dis.end(), numbers::inf<uint>());
std::fill(prev_point.begin(), prev_point.end(), npos);
std::vector<bool> vis(n);
std::deque<uint> q;
uint real_n = n / 10;
for (size_t i = 1; i < 10; i++) {
q.push_back(index(i % real_n, i));
dis[index(i % real_n, i)] = 0;
}
while (!q.empty()) {
auto f = q.front();
q.pop_front();
if (vis[f]) {
continue;
}
vis[f] = true;
uint mod = f / 10, digit = f % 10;
{
/**
* 填一个数
*/
uint nxt = (mod * 10 + digit) % real_n;
uint dest = index(nxt, digit);
if (!vis[dest] && dis[dest] > dis[f] + 1) {
dis[dest] = dis[f] + 1;
prev_point[dest] = f;
q.push_back(dest);
}
}
if (digit != 9) {
/**
* 换。
*/
uint nxt_digit = digit + 1;
uint dest = index(mod, nxt_digit);
if (!vis[dest] && dis[dest] >= dis[f]) {
/**
* 实际上和直接双端队列 bfs 记录前驱
* 相比只在这里多了一个 = 而已。
*/
dis[dest] = dis[f];
prev_point[dest] = f;
q.push_front(dest);
}
}
}
return;
}
graph(uint _n) : n(_n), dis(_n), prev_point(_n) {}
};
} // namespace graph
int main() {
uint n;
std::cin >> n;
graph::graph g(n * 10);
g.bfs();
auto min_digit = g.dis[graph::index(0, 9)];
if (min_digit == numbers::inf<uint>()) {
std::cout << -1 << std::endl;
return 0;
}
std::string s;
s.reserve(min_digit);
uint cur_pos = graph::index(0, 9);
for (uint j = 0; j < min_digit; j++) {
while (g.prev_point[cur_pos] / 10 == cur_pos / 10) {
cur_pos = g.prev_point[cur_pos];
}
assert(cur_pos % 10 == g.prev_point[cur_pos] % 10);
s.push_back((cur_pos % 10) + '0');
cur_pos = g.prev_point[cur_pos];
}
while (g.prev_point[cur_pos] != graph::npos) {
cur_pos = g.prev_point[cur_pos];
}
s.push_back((cur_pos % 10) + '0');
std::reverse(s.begin(), s.end());
std::cout << s << std::endl;
return 0;
}