P6661 [POI 2019] Pomniejszenie

POI 合集。

阴间模拟题。考虑求出使得 $A, B$ 不同的第一个位置 $p$，有如下限制：

• 需要修改的位置数量不能超过 $k$。
• 没有考虑到的位置数量不能小于还需要修改的位数。

具体地，对于每一位 $i$，求出 $s$ 表示在第 $i$ 位之前有多少 $A\neq B$ 的位置。$i$ 合法的必要条件是 $B_i \neq 0$，先判掉。由于上述限制要求修改位置数量既不能太小，也不能太大，所以需要考虑当前位是否修改：

• 若 $A_i < B_i$，说明可以不修改。此时若 $s \leq k$ 且 $n - i \geq k - s$ 则 $i$ 合法。
• 若 $B_i > 1$ 或 $A_i > 0$，说明可以 强制 修改（因为当 $A_i = 0, B_i = 1$ 时不能修改）。此时若 $s + 1\leq k$ 且 $n - i \geq k - s - 1$ 则合法。

若找不到合法的 $p$ 则无解。输出答案的过程时刻维护 $k$ 表示还需要修改的位数：

• 若当前位 $i$ 小于 $p$，输出 $B_i$。
• 若当前位 $i$ 等于 $p$，此时当 $n - i + 1 = k$ 且 $A_i + 1 = B_i$ 时输出 $B_i - 2$，否则输出 $B_i - 1$，前者因为这一位必须修改（否则将导致剩余位数小于要修改位数，不合法）。
• 若当前位 $i$ 大于 $p$，此时当 $n - i + 1 = k$ 且 $A_i = 9$ 时输出 $8$，否则输出 $9$。
• 注意点：若输出的数码与 $A_i$ 不同，则令 $k$ 自减 $1$。
• 注意点：任何时刻若 $k = 0$，则输出 $A_i$。

时间复杂度线性。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, k, p;
char s[N], t[N];
void solve() {
	scanf("%s %s %d", s + 1, t + 1, &k), n = strlen(s + 1), p = 0;
	for(int i = 1, pr = 0; i <= n; i++) {
		if(t[i] - '0') {
			if(s[i] < t[i] && pr <= k && n - i >= k - pr) p = i;
			if((t[i] > '1' || s[i] > '0') && pr + 1 <= k && n - i >= k - pr - 1) p = i;
		} pr += s[i] != t[i];
	} if(!p) return puts("-1"), void();
	for(int i = 1, out; i <= n; i++) {
		if(i < p) out = t[i];
		else if(!k) out = s[i];
		else if(i == p) out = t[i] - 1 - (s[i] + 1 == t[i] && n - i + 1 == k);
		else out = '9' - (n - i + 1 == k && s[i] == '9');
		putchar(out), k -= out != s[i];
	} cout << endl;
}
int main() {
	int T; cin >> T; while(T--) solve();
	return 0;
}