1 条题解

  • 0
    @ 2026-11-15 21:09:44

    题目分析

    考虑求出使得 A,BA, B 不同的第一个位置 pp,有如下限制:

    • 需要修改的位置数量不能超过 kk。

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

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

    • 若 Ai<BiA_i < B_i,说明可以不修改。此时若 s≤ks \le k 且 n−i≥k−sn - i \ge k - s,则 ii 合法。

    • 若 Bi>1B_i > 1 或 Ai>0A_i > 0,说明可以强制修改(因为当 Ai=0,Bi=1A_i = 0, B_i = 1 时不能修改)。此时若 s+1≤ks + 1 \le k 且 n−i≥k−s−1n - i \ge k - s - 1,则 ii 合法。

    若找不到合法的 pp 则无解。

    输出答案的过程中时刻维护变量 kk,表示还需要修改的位置数:

    • 若当前位 i<pi < p,输出 BiB_i。

    • 若当前位 i=pi = p,若 n−i+1=kn - i + 1 = k 且 Ai+1=BiA_i + 1 = B_i,输出 Bi−2B_i - 2,否则输出 Bi−1B_i - 1,前者因为这一位必须修改(否则将导致剩余位数小于要修改位数,不合法)。

    • 若当前位 i>pi > p,若 n−i+1=kn - i + 1 = k 且 Ai=9A_i = 9输出 8 ,否则输出 9 。

    • 若输出的数字与 AiA_i 不同,则令 kk 自减 11。

    • 若 k=0k = 0,则输出 AiA_i。

    时间复杂度线性。

    • 1

    信息

    ID
    195
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者