最小字典序

GitHub跳转原题关系图返回列表

逐位贪心试字符,配一趟按最后逗号位置递推的可达性判定,每个位置只留左端最小数即可判定能否补全。

OJ: roj

题目 ID: 1682

难度:提高

标签:贪心动态规划字符串python

创建: 2026-10-07 15:33

更新: 2026-10-07 15:33

形式化题目

给定一个长度为 nn 的字符串 SS,字符只可能来自 {0..9, ’,’, ’?’}\{\texttt{0..9},\ \texttt{','},\ \texttt{'?'}\}, 其中 ’?’\texttt{'?'} 是通配符。要求把每个 ’?’\texttt{'?'} 替换成数字或逗号, 得到一个不含问号的串 TT,满足:

  1. TT 只含数字和逗号;
  2. 逗号把 TT 切成若干个非空数字段,首尾都不是逗号;
  3. 每个数字段首位不为 0(即每个数都是无前导零的正整数);
  4. 各数字段表示的整数序列严格递增。

在全部合法 TT 中取字典序最小者输出(按 ASCII,, << 0 << 1 <⋯<< \cdots < 9, 所以 "1,2""1,2" 比 "12""12" 小);无解输出 impossible。多组数据,TT 组数 ⩽10\leqslant 10,n⩽50n \leqslant 50。

样例第三组的 ?????????,9 答案为 1,2,3,4,5,9:把第 00、22、44、66、88 个问号 各留作数字(1、2、3、4、5),其余问号都换成逗号,得到 5 个数后接末尾固定的 9。 注意 1,2,3,4,5,9 的第 1 个字符是逗号,比任何以数字开头的可行串都小, 这正是"逗号优先级最高"的体现。

正解

思路

本题是"逐位定字符"的结构,不是"逐段定数字"的结构。 一个常见的错想是: 先在脑子里把串切成数字段,再对每段填最小数。但字典序最小是按字符比较的, 判题只认最终字符串,所以正确的做法是从左往右逐位确定字符: 对每个 ?,按 ASCII 从小到大依次试 , 0 1 … 9, 留下第一个"仍然能补全成合法串"的字符,之后的 ? 再继续处理。 这是标准的字典序贪心模板——只要"能否补全"这个判定是精确的, 逐位贪心得到的就是字典序最小解(每一位都取到当前能取得的最小值, 且不影响前面已定的前缀)。

剩下的全部难点都在判定:给定一个前缀已定、后缀还是 ? 的模式串,能否补全成合法串?

判定:按"最后一个逗号位置"递推。 合法串由一串数字段构成, 段与段之间由逗号分隔,所以一个自然的状态是"逗号落在哪里"。 设 cc 为某个逗号的位置(虚拟起点记 c=−1c = -1,表示还没有任何数字), f(c)f(c) = 当逗号落在 cc 时,它左侧最后一个数字段的最小可能取值。 这个值之所以够用,是因为下一段数字 vv 只受一个约束:v>f(c)v > f(c)—— 比它更左边的数字(如倒数第二个数)对 vv 没有任何直接约束。 因此同一位置只需要保留最小的 f(c)f(c),其余取值更差的路径一律可以丢掉, 判定不会因此变松。

于是转移很直接:从状态 cc 出发,枚举下一段的结束位置 ee(段是 S[c+1,e)S[c+1, e)):

  • 位置 ee 若 e<ne < n,它必须是逗号位,即 S[e]∈{’,’,’?’}S[e] \in \{\texttt{','}, \texttt{'?'}\}; e=ne = n 时这一段收尾,串结束,直接判定成功。
  • 段内要能填出一个首位非 00、不含固定逗号、且数值 >f(c)> f(c) 的数字; 取其中最小的那个,作为新状态 f(e)f(e) 的候选。
  • 走到 ee 后新逗号位置是 ee,记入 g(e+1)g(e+1)(下标 c+1c+1 是为了让 −1-1 能存进数组)。

一层层从左往右推进,任一状态能读到最后一段就可行。因为每个状态只留最小值, 状态数 O(n)O(n)、每个状态枚举 O(n)O(n) 个结束位置,一次判定是 O(n2)O(n^2) 级别 (唯一的额外代价是 O(n)O(n) 位的数字串比较,见「复杂度」一节)。

子问题:在 S[s,e)S[s, e) 上填出"最小的、>lower> lower"的数字。 记 L=e−sL = e - s:

  1. 先构造忽略下界的最小匹配数字 base:? 首位填 1、其余填 0, 固定数字必须原样接受;出现固定逗号、或首位被固定成 0,这一段就废了。
  2. 若 base 的位数 ≠\neq lowerlower 的位数,位数多则 base 一定更大,位数少则一定不可能更大。 同位数时若 base > lower,base 就是答案。
  3. 否则必须"在某个位置 jj 上超过 lowerlower":jj 之前与 lowerlower 完全相同, 第 jj 位取比 lower[j]lower[j] 大的最小可行数字,jj 之后取最小。jj 越靠右,得到的数越小, 所以从右往左扫第一个可行的 jj。

第 3 步是常见的"构造恰好大于某数的最小串"的技巧,扫一遍 O(L)O(L) 个位置即可。 下面是样例第三组 ?????????,9 的贪心追踪, 每行的"尝试序列"是这一位按 , 0 1 … 9 试下来、判定返回的可达性序列, 第一个 True 就是留下的字符:

位置 该位尝试与判定结果 留下的字符
0 , ✗,0 ✗,1 ✓ 1
1 , ✓ ,
2 , ✗,0 ✗,1 ✗,2 ✓ 2
3 , ✓ ,
4 ,0 1 2 全 ✗,3 ✓ 3
5 , ✓ ,
6 ,0 1 2 3 全 ✗,4 ✓ 4
7 , ✓ ,
8 ,0 1 2 3 4 全 ✗,5 ✓ 5

观察重点有两处。第一,位置 0 试 , 会直接失败,因为串首不能是逗号;试 0 也不行,因为数字段首位不能是 0; 奇数位置试探逗号时立刻成功,因为逗号总是让后面的段更短、更容易满足递增。 第二,偶数位置试 , 也失败:它前面的奇数位置已经是逗号,再放一个就是空数字段; 而试 0 同样失败(这一位正是某个数字段的首位,会出现前导 0)。 剩下第一个能成功的字符就是这一位的最小值:位置 2 试 1 时, 这一段夹在两个逗号之间只有一位,必须 >1> 1,所以只能升到 2; 位置 4、6、8 同理依次升到 3、4、5。 整个过程与它要填的数值大小无关,纯粹是"先占逗号,占不下才升为数字"。

不可行与边界。 判定返回假时输出 impossible(判定本身已覆盖了"必须递增"与 "无前导 0"两个硬约束,所以不必额外特判)。全问号短串可以直接手算感受贪心的取舍: ????? 的答案是 1,100 而不是段数更多的 1,2,3——两者第 3 个字符分别是 1 与 2, 位置 2 处 ,(空段)和 0(前导 0)都不可行,而 1 已经可行,贪心就停在这里; ?? 的答案是 10 而非 1,因为长度是硬性的:填成 1, 会以逗号结尾。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:18
# update_at: 2026-10-07 15:33

import sys

COMMA_FIRST = ",0123456789"  # '?' 的候选字符:',' 的 ASCII 是 44,小于所有数字,所以排在最前


def rank(num: str) -> tuple[int, str]:
    """无前导 0 的数字串的比较键:先比位数,再比字典序。"""
    return (len(num), num)


def minimal_number(pat: str, start: int, stop: int, lower: str) -> str:
    """把 pat[start:stop] 填成一个合法数字并尽量小:首位非 0、段内不含固定逗号、
    数值严格大于 lower(lower 为空串表示无下界);填不出数字时返回空串。
    """
    length = stop - start
    if length <= 0:
        return ""
    base = "".join(                    # base = 忽略下界时这一段的"最小匹配数字"
        pat[i] if pat[i] != "?" else ("1" if i == start else "0") for i in range(start, stop)
    )
    if "," in base or base[0] == "0":
        return ""                      # 段内被固定逗号截断,或这一位只能放 0(前导 0 / 空数字)
    if rank(base) > rank(lower):
        return base                    # 已经比下界大,且是同位数里最小的
    if len(base) < len(lower):
        return ""                      # 位数比下界少,这一段的任何填法都不够大

    # 同位数且 base <= lower:任何更大的数都在"第一个超过 lower 的位置 j"上变大,
    # 前缀与 lower 相同、第 j 位放大、后面取最小;j 越靠右结果越小,所以从右往左找。
    for j in range(length - 1, -1, -1):
        if any(pat[start + i] not in ("?", lower[i]) for i in range(j)):
            continue                   # 前缀与 lower 冲突,这一段无法在 j 处变大
        pick = next((c for c in "123456789" if c > lower[j] and pat[start + j] in ("?", c)), "")
        if not pick:
            continue
        tail = "".join("0" if pat[i] == "?" else pat[i] for i in range(start + j + 1, stop))
        return lower[:j] + pick + tail
    return ""


def completable(pat: str) -> bool:
    """pat 里剩下的 '?' 还能否补成合法串。

    按"最后一个逗号的位置"从左往右递推:每个位置只保留左侧最后一个数最小的那条路径,
    因为下界更小对后面只会更宽松,丢掉别的路径不会丢解。
    """
    n = len(pat)
    best: list[str | None] = [None] * (n + 2)  # best[c + 1] = 逗号落在 c 时左端最后一个数的最小值
    best[0] = ""                               # 虚拟起点(逗号位置 -1):还没有数字,无下界
    farthest = 0                               # 已被点亮的最大状态下标

    for c in range(-1, n):
        lower = best[c + 1]
        if lower is None:
            if c + 1 > farthest:
                break                          # 转移只向右,右侧没有点亮的状态,后面永远断线
            continue                           # 这个逗号位置走不到
        for stop in range(c + 2, n + 1):       # 当前数字段是 pat[c + 1:stop]
            if stop < n and pat[stop] not in "?,":
                continue                       # 段后面必须能放逗号(或这一段到串尾)
            value = minimal_number(pat, c + 1, stop, lower)
            if not value:
                continue
            if stop == n:
                return True                    # 最后一段也填出了合法数字,整体可行
            old = best[stop + 1]
            if old is None or rank(value) < rank(old):
                best[stop + 1] = value         # 逗号落在 stop,位置 stop + 1 即状态下标
                farthest = max(farthest, stop + 1)
    return False


def restore(pat: str) -> str:
    """把 pat 还原成字典序最小的合法串;无解时返回 'impossible'。

    先判定整体可不可行,再逐位贪心:每个 '?' 留下第一个仍能补全的字符。
    """
    if not completable(pat):
        return "impossible"
    chars = list(pat)
    for i, ch in enumerate(chars):
        if ch != "?":
            continue                           # 题目固定的字符必须原样保留
        for c in COMMA_FIRST:
            chars[i] = c
            candidate = "".join(chars)         # 这一位取 c 之后的候选串
            if completable(candidate):
                break
            chars[i] = "?"
    return "".join(chars)


def solve() -> None:
    data = iter(sys.stdin.read().split())
    T = int(next(data))
    out: list[str] = []

    for _ in range(T):
        out.append(restore(next(data)))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:18
 * update_at: 2026-10-07 15:33
 */
// main.cpp:把含 '?' 的模式串补成字典序最小的合法整数序列(',' 的 ASCII 小于所有数字)。
// 做法是"逐位贪心 + 可达性判定":每位 '?' 依次试 ',' 与 '0'..'9',取第一个还能补全的字符;
// 判定用一趟按"上一个逗号位置"的状态 DP 完成,每个位置只留"左侧最后一个数最小"的那条路径。

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

typedef long long ll;

const int MAXLEN = 55;                  // 串长上界 50,留一点余量

// 贪心时每个 '?' 的尝试顺序:','(ASCII 44)小于所有数字(ASCII 48~57)
const string TRY_ORDER = ",0123456789";

// 逗号位置 c 上的状态:逗号落在位置 c 时,它左侧最后一个数的最小可能取值是多少。
// c = -1 是虚拟起点(还没有任何数字),value 为空串表示"无下界"。
struct State {
    bool reach;   // 这个逗号位置是否可达
    string value; // 可达时,左侧最后一个数的最小取值
};
State state[MAXLEN + 2];

string pat; // 当前模式串,'?' 表示这一位还没定
string ans; // 本组数据的答案
ll n;       // 模式串长度

// 比较两个无前导 0 的十进制数字串:先比位数,再比字典序。
ll cmpNumber(const string &a, const string &b) {
    if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
    if (a == b) return 0;
    return a < b ? -1 : 1;
}

// 在 pat[start, stop) 上填出一个数字(首位非 0)并让它尽可能小;
// lower 为空串表示没有下界,否则要求数值严格大于 lower。填不出数字时返回空串。
string minNumber(ll start, ll stop, const string &lower) {
    ll length = stop - start;
    if (length <= 0) return "";

    string base(length, '0'); // base:忽略下界时的最小匹配数字
    for (ll i = 0; i < length; i++) {
        char c = pat[start + i];
        if (c == '?') {
            base[i] = (i == 0) ? '1' : '0';
        } else if (c == ',') {
            return ""; // 这一段中间被固定逗号截断,放不下一个数字
        } else {
            if (i == 0 && c == '0') return ""; // 前导 0,非法
            base[i] = c;
        }
    }

    ll lowerLen = lower.size();  // size() 是 size_t,赋给 ll 即可,不需要强制转换
    if (lower.empty() || length > lowerLen) return base; // 位数更多必然更大
    if (length < lowerLen) return "";                    // 位数更少不可能更大
    if (cmpNumber(base, lower) > 0) return base;

    // 同位数且 base <= lower:枚举"第一个超过 lower 的位置 j",前缀与 lower 相同、
    // 第 j 位放大、后面取最小。j 越靠右得到的数越小,所以从右往左找第一个可行位置。
    for (ll j = length - 1; j >= 0; j--) {
        bool prefixOk = true;
        for (ll i = 0; i < j; i++) {
            if (pat[start + i] != '?' && pat[start + i] != lower[i]) {
                prefixOk = false;
                break;
            }
        }
        if (!prefixOk) continue;

        ll pick = -1;
        for (ll d = (lower[j] - '0') + 1; d <= 9; d++) {
            if (j == 0 && d == 0) continue; // 首位不能是 0
            if (pat[start + j] != '?' && pat[start + j] - '0' != d) continue;
            pick = d;
            break;
        }
        if (pick < 0) continue;

        string t = lower.substr(0, j);
        t += "0123456789"[pick]; // 直接取数字字符,省掉整型到字符的转换
        for (ll i = j + 1; i < length; i++) t += (pat[start + i] == '?') ? '0' : pat[start + i];
        return t;
    }
    return "";
}

// 当前 pat(前缀已固定)还能不能补全成合法串。
// 按逗号位置从左往右推进:同一位置只保留"左侧最后一个数最小"的路径,
// 因为上界更小对后面只会更宽松,丢掉别的路径不会丢解。
bool feasible() {
    for (ll i = 0; i <= n + 1; i++) {
        state[i].reach = false;
        state[i].value.clear();
    }
    state[0].reach = true; // 虚拟逗号位置 -1:还没有数字,无下界

    for (ll c = -1; c < n; c++) {
        if (!state[c + 1].reach) continue;
        ll start = c + 1; // 当前这一段数字从 start 开始
        for (ll stop = start + 1; stop <= n; stop++) {
            if (stop < n && pat[stop] != '?' && pat[stop] != ',') continue; // 段后要能放逗号
            string value = minNumber(start, stop, state[c + 1].value);
            if (value.empty()) continue;
            if (stop == n) return true; // 最后一段也填出了数字,整体可行
            ll nxt = stop + 1;          // 新逗号落在位置 stop
            if (!state[nxt].reach || cmpNumber(value, state[nxt].value) < 0) {
                state[nxt].reach = true;
                state[nxt].value = value;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll T;
    if (!(cin >> T)) return 0;

    while (T--) {
        cin >> pat;
        n = pat.size();

        if (!feasible()) {
            cout << "impossible\n";
            continue;
        }

        ans = pat;
        ll orderLen = TRY_ORDER.size();
        for (ll i = 0; i < n; i++) {
            if (pat[i] != '?') continue; // 题目固定给出的字符必须原样保留
            for (ll k = 0; k < orderLen; k++) {
                pat[i] = TRY_ORDER[k];
                if (feasible()) {        // 这一位取 TRY_ORDER[k] 后仍能补全
                    ans[i] = TRY_ORDER[k];
                    break;               // 留下这个字符继续处理后面的 '?'
                }
                pat[i] = '?';
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

复杂度

  • 时间:设串长 nn。每次判定按逗号位置递推,O(n)O(n) 个状态、每个状态枚举 O(n)O(n) 个段终点, 段内填数 O(n)O(n),数字串比较 O(n)O(n),故单次判定 O(n2)O(n^2)。贪心要试 nn 个 ?、 每个至多试 11 个字符,总复杂度 O(n3⋅11)O(n^3 \cdot 11);n⩽50n \leqslant 50、T⩽10T \leqslant 10 时 单个数据点毫秒级完成(C++ 实测 10 个数据点全部 ⩽0.01\leqslant 0.01 s,限时 1000 ms)。
  • 空间:状态数组存 O(n)O(n) 个长度 O(n)O(n) 的串,加上模式串与答案串,O(n2)O(n^2) 字符; 实测峰值内存 8.4 MB(限时 128 MB)。
  • Python 侧:同一算法的 CPython 实测最慢数据点 0.16 s(T=10T = 10、串长 50 全问号), 距离 1 s 限时安全,不存在 TLE 风险。

总结

  • 按位贪心而不是按段构造:字典序最小由最终字符串逐位决定, 逗号比所有数字小,所以每个 ? 的候选顺序必须是 , 0 1 … 9, 不能按"把某个数写小一点"的直觉去调。
  • 贪心的正确性完全依赖判定的精确性:逐位贪心本身是平凡的, 这道题的思维量在"能否补全"这一问上;判定错一点,整串就会错。
  • 状态只需记住一个值:合法串的约束是"相邻两段递增", 所以走到某个逗号位置时,只有"左侧最后一个数最小是多少"会影响未来, 其余路径一律被支配。这是"只留最优值做可行性判定"的典型用法。
  • “恰好大于某数的最小数字串”:构造 base、比位数、 再枚举"第一个变大的位置并从右往左取最靠右者",三步都是 O(n)O(n) 级别的技巧, 在各类字典序 / 数位构造题里反复出现。
  • 边界由判定统一处理:首尾逗号、前导 0、空数字段、连续逗号、段内固定逗号, 全部在 minNumber 与转移的合法性检查里自然被排除,不需要额外特判。