P6661 [POI 2019] Pomniejszenie

Alex_Wei · 2022-02-01 18:15:08 · 题解

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;
}