题解：P6661 [POI 2019/2020 R1] Pomniejszenie / 削减

_VerteX_ · 2026-08-11 18:31:19 · 题解

为了让构造出来的数 A' 在小于 B 的情况下最大化，我们可以通过几次操作让 A' 在某个数位 pos 前都与 B 相同，然后让后缀小于 B 的后缀即可。

我们可以先处理出 pre_{i}=\sum^{i}_{j=1}[A_{j} \ne B_{j}]，pre_{pos} 就是使得 pos 前的 A' 和 B 各数位相同的操作数。

若 pre_{pos}>k，那这一个 pos 肯定不合法。

计算出剩余操作数 r=k-pre_{pos}，由于一定要消耗完操作数，如果 r>n-pos+1，则我们没法在保持前缀相同的情况下消耗这 r 次操作，直接判非法。

如果计算出的 r=0，那接下来就不能操作了，我们比较 A 和 B 的后缀即可。

后缀的比较结果也预处理即可。设 suf_i=1 表示 A 的后缀严格小于 B 的后缀，初始化 suf_{n+1}=0，递推方法为

如果 r>0，我们首先考虑将 A_{pos} 变成 B_{pos}-1。

这时若 B_{pos}=0，我们最多只能让 A_{pos}=B_{pos}=0，然后调整后面来判断可行性。但这与我们最开始的想法不符，我们的 pos 是 A' 和 B 第一个对应数位不同的地方，让其上的数字相同会增加我们的考虑，而且为了让 A'<B，总会有一个位置满足 A'_{pos} \ne B_{pos} 的，所以这里我们直接将 B_{pos}=0 看作不合法即可。

当 B_{pos}>0 时，我们令 A'_{pos}=B_{pos}-1，便能最大化合法的 A'。

但这时我们又会发现冲突，即当 A'_{pos}=A_{pos} 时，这个所谓的操作不算数，r 不会减少，这可能导致后面的剩余位数哪怕全部被操作都无法消耗完 r，合法判断根据为 r<=n-pos。

若是不操作 pos 就不合法，我们就不得不再让一步，令 A'_{pos}=A_{pos}-1。当然，若 A_{pos}=0，判断为非法。

实现很简单，考虑清楚即可。

void process_pre_and_suf() {
  pre[0] = 0;
  for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + (a[i] != b[i]);
  }
  suf[n + 1] = 0;
  for (int i = n; i; i--) {
    if (a[i] > b[i])
      suf[i] = 0;
    else if (a[i] < b[i])
      suf[i] = 1;
    else
      suf[i] = suf[i + 1];
  }
}

bool check(int pos) {
  if (pre[pos - 1] > k)
    return 0;
  int remain = k - pre[pos - 1];
  if (remain > n - pos + 1)
    return 0;
  if (remain == 0) {
    if (suf[pos])
      return 1;
    return 0;
  }
  if (a[pos] == b[pos] - 1) {
    if (remain <= n - pos)
      return 1;
    if (a[pos] == '0')
      return 0;
  }
  if (b[pos] == '0')
    return 0;
  return 1;
}

同样合法的情况，让 A' 在较小位时小于 B 肯定更优，故我们从后往前枚举 pos。

int get_pos() {
  for (int i = n; i; i--) {
    if (check(i))
      return i;
  }
  return 0;
}

根据对应情况，我们只要注意 pos 上不同情形带来的差异即可。

当 A' 在 pos 上小于 B 后，后面部分不管怎么搞都行，所以我们将其最大化。

从高位到低位，所有数位能变成 9 就变，当然原来就是 9 的数位先保持不动，就这样操作直到 r 耗尽或完成剩余部分的遍历。若有剩余，则从低位往高位，将原来是 9 的数位变为 8，直到 r 耗尽。

void process_string(string &c, int pos, int remain) {
  for (int i = pos; i <= n; i++) {
    c[i] = a[i];
    if (a[i] == '9')
      continue;
    if (remain > 0) {
      c[i] = '9';
      remain--;
    }
  }
  if (remain == 0)
    return;
  for (int i = n; i >= pos; i--) {
    if (a[i] == '9') {
      c[i] = '8';
      remain--;
      if (remain == 0)
        return;
    }
  }
  assert(remain > 0);
}

string construst_ans(int pos) {
  string c = b;
  int remain = k - pre[pos - 1];
  if (remain == 0) {
    assert(suf[pos]);
    for (int i = pos; i <= n; i++) {
      c[i] = a[i];
    }
    return c;
  }
  if (a[pos] == b[pos] - 1) {
    if (remain <= n - pos) {
      c[pos] = a[pos];
      process_string(c, pos + 1, remain);
      return c;
    }
    assert(a[pos] != '0');
    c[pos] = a[pos] - 1;
    remain--;
    process_string(c, pos + 1, remain);
    return c;
  }
  assert(b[pos] != '0');
  c[pos] = b[pos] - 1;
  remain--;
  process_string(c, pos + 1, remain);
  return c;
}

单次时间复杂度为 O(n)。

Code

#include <iostream>
#include <cassert>
#include <string>
using namespace std;
const int N = 1e5 + 5;
int t;
string a, b;
int n, k;

void read() {
  cin >> a >> b;
  cin >> k;
  n = a.size();
  a = '?' + a;
  b = '?' + b;
}

int pre[N];
bool suf[N];

void process_pre_and_suf() {
  pre[0] = 0;
  for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + (a[i] != b[i]);
  }
  suf[n + 1] = 0;
  for (int i = n; i; i--) {
    if (a[i] > b[i])
      suf[i] = 0;
    else if (a[i] < b[i])
      suf[i] = 1;
    else
      suf[i] = suf[i + 1];
  }
}

bool check(int pos) {
  if (pre[pos - 1] > k)
    return 0;
  int remain = k - pre[pos - 1];
  if (remain > n - pos + 1)
    return 0;
  if (remain == 0) {
    if (suf[pos])
      return 1;
    return 0;
  }
  if (a[pos] == b[pos] - 1) {
    if (remain <= n - pos)
      return 1;
    if (a[pos] == '0')
      return 0;
  }
  if (b[pos] == '0')
    return 0;
  return 1;
}

int get_pos() {
  for (int i = n; i; i--) {
    if (check(i))
      return i;
  }
  return 0;
}

void process_string(string &c, int pos, int remain) {
  for (int i = pos; i <= n; i++) {
    c[i] = a[i];
    if (a[i] == '9')
      continue;
    if (remain > 0) {
      c[i] = '9';
      remain--;
    }
  }
  if (remain == 0)
    return;
  for (int i = n; i >= pos; i--) {
    if (a[i] == '9') {
      c[i] = '8';
      remain--;
      if (remain == 0)
        return;
    }
  }
  assert(remain > 0);
}

string construst_ans(int pos) {
  string c = b;
  int remain = k - pre[pos - 1];
  if (remain == 0) {
    assert(suf[pos]);
    for (int i = pos; i <= n; i++) {
      c[i] = a[i];
    }
    return c;
  }
  if (a[pos] == b[pos] - 1) {
    if (remain <= n - pos) {
      c[pos] = a[pos];
      process_string(c, pos + 1, remain);
      return c;
    }
    assert(a[pos] != '0');
    c[pos] = a[pos] - 1;
    remain--;
    process_string(c, pos + 1, remain);
    return c;
  }
  assert(b[pos] != '0');
  c[pos] = b[pos] - 1;
  remain--;
  process_string(c, pos + 1, remain);
  return c;
}

int main() {
  cin >> t;
  while (t--) {
    read();
    process_pre_and_suf();
    int pos = get_pos();
    if (!pos) {
      cout << "-1\n";
      continue;
    }
    string ans = construst_ans(pos);
    for (int i = 1; i <= n; i++)
      cout << ans[i];
    cout << '\n';
  }
  return 0;
}