【构造】【P9215】扶苏与 1
一扶苏一
·
·
题解
【构造】【P9215】扶苏与 1
Description
给出一个数字串 x，求一个长度不超过 x 长度的数字串 y，使得 x + y 的竖式计算有恰好 k 个进位，或报告无解。
## Analysis
接下来我们称 $x$ 的最高位是第 $1$ 位，最低位是第 $n$ 位。『第 $i$ 位』指的是从左到右数第 $i$ 个位置。
首先能观察到一个简单的事实：如果第 $k$ 位不为 $0$，那么可以简单地构造一个前 $k$ 位是 $9$、后 $n - k$ 位是 $0$ 的数字 $y$ 来做到恰好 $k$ 个进位。例如，若 $x = 10101$，$k = 3$，那么构造 $y = 99900$ 可以在第 $1,2,3$ 位上构造出进位。
**证明**：
首先第 $k$ 位之后都是 $0$，这些位置不会有进位。
$x$ 的第 $k$ 位不为 $0$，加上 $9$ 一定会有 $1$ 的进位；
假设第 $i$ 位（$1 < i \leq k$）产生了 $1$ 的进位，考虑 $y$ 的第 $i$ 位是 $9$，加上进上来的 $1$，再加上 $x$ 对应位的原数，得数一定不小于 $10$，所以一定会产生 $1$ 的进位。
根据归纳假设，第 $1 \sim k$ 位都会产生进位，$k + 1\sim n$ 位没有进位，得证。
接下来考虑第 $k$ 位为 $0$ 时应该如何构造：
找到第 $k$ 位之前最后一个不为 $0$ 的位置 $p$（显然存在），然后根据上面的方法我们可以构造 $p$ 个进位。考虑构造剩下的 $k - p$ 个进位。
找到第 $k$ 位之后第一个不为 $0$ 的位置 $q$。如果这样的 $q$ 不存在，说明我们不能构造更多的进位，此时显然无解。
如果 $q$ 存在，我们来证明 $[p + 1, q - 1]$ 这段区间（显然这段区间里全部都是 $0$）的长度不小于 $k - p$。：
这段区间的长度是 $q - 1 - (p + 1) + 1 = q - p - 1$。因为 $q > k$，所以 $q - p > k - p$。所以 $q - p - 1 \geq k - p$。
我们从第 $q$ 位起，向前填充 $k - p$ 个 $9$。也就是给 $[q - (k - p) + 1, q]$ 这段区间填充上 $9$。且给 $q - (k - p)$ 这个位置填充上 $0$。我们来证明这样构造出了 $k - p$ 个进位：
因为 $x$ 第 $q$ 位不为 $0$，加上 $9$ 一定不小于 $10$，产生了一个进位。再用与前面类似的归纳，假设下一位产生了进位，那么加上 $y$ 这一位的 $9$，一定有进位。因为一共有 $k - p$ 个 $9$，所以一共构造出来了 $k - p$ 个进位。特别的，$q - (k - p) = p + (q - k) \geq p + 1 \in [p + 1, q - 1]$，所以 $x$ 第 $q - (k - p)$ 位也是 $0$，$y$ 的这一位也是 $0$，加上第 $q - (k - p) + 1$ 位的进位也不会有新的进位。所以我们恰好构造了 $k - p$ 个进位。
这样，我们在 $[1, p]$ 区间上构造了 $p$ 个进位，$[q - (k - p) + 1, q]$ 区间上构造了 $k - p$ 个进位。一共构造出了 $k$ 个进位。其他位置上全填充 $0$，不会产生新的进位。
以下两张图分别是 $k = 5$ 和 $k = 8$ 的例子，可以结合图片来理解构造方法。
## Code
在实现上，因为字符串下标是从 $0$ 开始的，所以一些位置有减去 $1$ 的操作。
```cpp
#include <assert.h>
#include <string>
#include <iostream>
#include <algorithm>
int T;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
for (std::cin >> T; T; --T) {
int k;
std::string s; std::cin >> s >> k;
if (s == "0") {
std::cout << "-1\n";
continue;
}
std::string ans;
assert(k <= s.length());
int endp = k - 1;
while (s[endp] == '0') --endp;
for (int i = 0; i <= endp; ++i) {
ans.push_back('9');
}
if (endp != k - 1) {
int q = k - 1;
while (q < s.size() && s[q] == '0') ++q;
if (q == s.size()) {
std::cout << "-1\n";
continue;
}
int p = k - endp - 1;
p = q - p + 1;
for (int i = endp + 1; i < p; ++i) ans.push_back('0');
for (int i = p; i <= q; ++i) ans.push_back('9');
}
while(s.size() > ans.size()) ans.push_back('0');
std::cout << ans << '\n';
}
}
```