逐位贪心试字符,配一趟按最后逗号位置递推的可达性判定,每个位置只留左端最小数即可判定能否补全。
OJ: roj
题目 ID: 1682
难度:提高
标签:贪心动态规划字符串python
创建: 2026-10-07 15:33
更新: 2026-10-07 15:33
形式化题目
给定一个长度为
只含数字和逗号; - 逗号把
切成若干个非空数字段,首尾都不是逗号; - 每个数字段首位不为
0(即每个数都是无前导零的正整数); - 各数字段表示的整数序列严格递增。
在全部合法 , 0 1 9,
所以 impossible。多组数据,
样例第三组的 ?????????,9 答案为 1,2,3,4,5,9:把第 9。
注意 1,2,3,4,5,9 的第 1 个字符是逗号,比任何以数字开头的可行串都小,
这正是"逗号优先级最高"的体现。
正解
思路
本题是"逐位定字符"的结构,不是"逐段定数字"的结构。 一个常见的错想是:
先在脑子里把串切成数字段,再对每段填最小数。但字典序最小是按字符比较的,
判题只认最终字符串,所以正确的做法是从左往右逐位确定字符:
对每个 ?,按 ASCII 从小到大依次试 , 0 1 … 9,
留下第一个"仍然能补全成合法串"的字符,之后的 ? 再继续处理。
这是标准的字典序贪心模板——只要"能否补全"这个判定是精确的,
逐位贪心得到的就是字典序最小解(每一位都取到当前能取得的最小值,
且不影响前面已定的前缀)。
剩下的全部难点都在判定:给定一个前缀已定、后缀还是 ? 的模式串,能否补全成合法串?
判定:按"最后一个逗号位置"递推。 合法串由一串数字段构成,
段与段之间由逗号分隔,所以一个自然的状态是"逗号落在哪里"。
设
于是转移很直接:从状态
- 位置
若 ,它必须是逗号位,即 ; 时这一段收尾,串结束,直接判定成功。 - 段内要能填出一个首位非
、不含固定逗号、且数值 的数字; 取其中最小的那个,作为新状态 的候选。 - 走到
后新逗号位置是 ,记入 (下标 是为了让 能存进数组)。
一层层从左往右推进,任一状态能读到最后一段就可行。因为每个状态只留最小值,
状态数
子问题:在
- 先构造忽略下界的最小匹配数字
base:?首位填1、其余填0, 固定数字必须原样接受;出现固定逗号、或首位被固定成0,这一段就废了。 - 若
base的位数的位数,位数多则 base一定更大,位数少则一定不可能更大。 同位数时若base > lower,base就是答案。 - 否则必须"在某个位置
上超过 ": 之前与 完全相同, 第 位取比 大的最小可行数字, 之后取最小。 越靠右,得到的数越小, 所以从右往左扫第一个可行的 。
第 3 步是常见的"构造恰好大于某数的最小串"的技巧,扫一遍 ?????????,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 时,
这一段夹在两个逗号之间只有一位,必须 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 版:
#!/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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:设串长
。每次判定按逗号位置递推, 个状态、每个状态枚举 个段终点, 段内填数 ,数字串比较 ,故单次判定 。贪心要试 个 ?、 每个至多试 11 个字符,总复杂度; 、 时 单个数据点毫秒级完成(C++ 实测 10 个数据点全部 s,限时 1000 ms)。 - 空间:状态数组存
个长度 的串,加上模式串与答案串, 字符; 实测峰值内存 8.4 MB(限时 128 MB)。 - Python 侧:同一算法的 CPython 实测最慢数据点 0.16 s(
、串长 50 全问号), 距离 1 s 限时安全,不存在 TLE 风险。
总结
- 按位贪心而不是按段构造:字典序最小由最终字符串逐位决定,
逗号比所有数字小,所以每个
?的候选顺序必须是, 0 1 … 9, 不能按"把某个数写小一点"的直觉去调。 - 贪心的正确性完全依赖判定的精确性:逐位贪心本身是平凡的, 这道题的思维量在"能否补全"这一问上;判定错一点,整串就会错。
- 状态只需记住一个值:合法串的约束是"相邻两段递增", 所以走到某个逗号位置时,只有"左侧最后一个数最小是多少"会影响未来, 其余路径一律被支配。这是"只留最优值做可行性判定"的典型用法。
- “恰好大于某数的最小数字串”:构造
base、比位数、 再枚举"第一个变大的位置并从右往左取最靠右者",三步都是级别的技巧, 在各类字典序 / 数位构造题里反复出现。 - 边界由判定统一处理:首尾逗号、前导
0、空数字段、连续逗号、段内固定逗号, 全部在minNumber与转移的合法性检查里自然被排除,不需要额外特判。