谨以此题解纪念我的20次提交。
题目大意
给一个整数 \(x\) 和 进位次数 \(k\)，求一个数 \(y\) 使得列竖式计算 \(x+y\) 时正好产生 \(k\) 次进位。
思路
（最开始是想正着搞的，但是怎么也调不出来）提供一种倒着做的做法。
首先有几个结论：
-
产生进位 \(=\) 给前一位 \(+1\)。
-
对于 \(99...999\)，当最后一位发生进位时，会引发连环进位，总进位次数为连续 \(9\) 的个数。
-
\(0\) 无法产生进位。
应该挺显然的吧（）。
然后从后往前每一位考虑。
-
如果这一位是 \(0\)。
无论如何它都不会产生进位，所以随便丢个数字给它。 -
如果这一位不是 \(0\)。
也就是它可以产生进位。这时候就要抉择它要不要进位了。
肯定是能进位就进位，但什么时候不能进位呢？
如果它进位引发的连环进位总次数超过了剩下的进位次数 \(k'\)，那么它不可以进位。
由于 \(x\) 的位数不会超过 \(10^4\)， 所以可以暴力进位。
代码
const int N = 10010;
int t, n, k, ans[N], a[N];
int p[N]; //连续 9 的个数
char s[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for (int I = 1; I <= t; I++) {
cin >> s + 1;
n = strlen(s + 1);
for (int i = 1; i <= n; i++) ans[i] = 0;
for (int i = 1; i <= n; i++) a[i] = s[i] ^ 48;
for (int i = 1; i <= n; i++) //统计连续 9 的个数
if (a[i] == 9) p[i] = p[i - 1] + 1;
else p[i] = 0;
cin >> k;
for (int i = n; i >= 1; i--) {
if (a[i] == 0) {
ans[i] = 0;
continue;
}
if (p[i - 1] + 1 > k) ans[i] = 0; //i 位进位会导致的一连串进位数量超过 k
else {
ans[i] = 10 - a[i]; //加上任意一个大于等于 (10-a[i]) 的数都可以
a[i] += ans[i];
int l = i;
while (a[l] > 9) { //进行连环进位
a[l - 1] += a[l] / 10, a[l--] %= 10, k--; l++;
if (a[l] == 9) p[l] = p[l - 1] + 1; //新产生的 9 要加进连续 9 的计数中
}
i = l; //一串 9 连环进位以后会变成一串 0, 显然都不会产生贡献, 直接跳掉就可以了 (这个优化不加也能过)
}
}
if (k) cout << "-1\n";
else {
int l = 1;
while (ans[l] == 0 && l <= n) l++;
for (int i = l; i <= n; i++) cout << ans[i];
cout << '\n';
}
}
return 0;
}