没记错的话第一次见到“HJ119 小红的01子序列构造hard”是在某次线上模拟赛的压轴位。当时我花了大半个小时在暴力枚举上死磕样例都跑不对一度怀疑自己连子序列定义都没搞明白。后来真正卡住我的是“本质不同”这四个字——等我把去重这件事想透了这题的骨架其实非常干净一个去重计数 DP配合逐位构造的字典序贪心就能漂亮地把第 K 小答案抠出来。这篇文章写给两类人一是准备算法竞赛、想系统掌握“第 K 小构造类题目”套路的选手二是对字符串子序列计数感兴趣、想搞懂为什么不能简单枚举的学习者。我会把题面拆开把 hard 点、去重原理、DP 设计、边界坑完整走一遍最后给出可复现代码和几组测试用例。下面的推导不依赖任何平台上的原题细节只要题目符合“本质不同子序列 字典序第 K 小”的设定思路就能直接用。1. 先把题目拆明白小红要的子序列到底怎么算1.1 题面还原与约定我拿到的题面大概是这样一个版本给定一个长度为 n 的 01 串 s再给两个参数 k 和 K。小红想知道s 的所有长度为 k 的子序列中字典序第 K 小的那个是什么。如果长度为 k 的子序列根本不存在或者 K 超过了本质不同子序列的总数输出 -1。数据范围方面n 可以到 2×10^5k 在 1 到 n 之间K 最大能到 10^18。这里有三个非常容易理解偏的约定子序列不需要连续但字符顺序必须保持原串中的相对顺序。两个不同的位置选择方式如果得到完全相同的字符串只能算同一种子序列。这一步是整道题的分水岭。字典序按字符比较0 小于 1。先比第 1 位再比第 2 位依此类推。为了后续讨论统一我先把参数表列出来参数含义范围n原串长度≤ 2×10^5s01 串下标从 1 开始长度 nk需要构造的子序列长度1 ≤ k ≤ nK字典序排名第 K 小1 ≤ K ≤ 10^18输出第 K 小的本质不同子序列不存在则输出 -1这里的 K 是 64 位整数级别的不是 int 能装下的。后面所有中间计数都得用 long long甚至要做截断处理否则还没开始构造就溢出了。1.2 这个 hard 到底难在哪有人可能会说既然只要长度为 k 的子序列枚举所有 C(n,k) 种选法排序后取第 K 个不就行了问题是数量。当 n30 时C(30,15) 已经超过 1.5 亿n 一旦到 2×10^5组合数直接超过任何整数类型能表达的范围更别说逐条枚举了。但组合爆炸只是“硬”的基础真正让这道题配得上 hard 标签的有三个点要能快速数出某个前缀能引出多少种本质不同的子序列。这样才能在每一步决定第 K 小落到“填 0”分支还是“填 1”分支。计数必须去重。如果不去重同一个字符串会被多个位置组合重复统计K 的语义就错了后面的构造全部失真。每一步的计数结果要扛得住 10^18 量级的 K。不能溢出也不能因为状态太多而超时。第 1 点和第 3 点是很多“第 K 小构造题”的共性第 2 点是 01 串特有问题也是整道题最容易翻车的地方。理解了这三点后面思路就顺了。2. 暴力枚举为什么想都别想重复解是最大的坑2.1 组合爆炸的规模感受一下先说最朴素的思路长度为 n子序列长度为 k位置选法就是 C(n,k)。当 n2×10^5、k10^5 时这个数比宇宙中的原子数量还大好几个量级。不要说枚举光是“生成一个字符串再比较一次”的复杂度就已经无法接受了。更麻烦的是即便 K 很小比如 K2我们依然不能“只枚举前几个”。因为字典序第 K 小和位置选法的顺序没有任何关系你无法知道第 2 小的字符串出现在第几次枚举里除非把所有结果都生成出来再排序。退一步说假设我们用了某种剪枝只生成“一部分”候选但子序列的字典序不是按生成顺序排列的剪枝很容易剪掉正确答案。所以暴力枚举这条路在第一步设计上就走死了。2.2 同样一个子序列原串里可能有一百种选法我去重这个问题的真正顿悟是在一个极端的例子上。s “0000”k2。从 4 个位置里选 2 个有 C(4,2)6 种选法但得到的子序列全都是 “00”。本质不同只有 1 种。如果题目不做去重那“第 2 小”在哪直接不存在。这个例子很夸张但它说明了核心矛盾位置选法的数量和本质不同字符串的数量完全是两套计数体系。去重的标准做法是给每一种字符串规定唯一的一组“代表位置”。最常见也最自然的规则是构造字符串时每次添加一个字符都选择该字符在当前扫描位置之后第一次出现的位置。为什么这样能去重因为对于任意一个能在 s 中作为子序列出现的字符串 t用“每次选择字符第一次出现位置”的贪心方式去选得到的 t 只对应一组位置反过来任意一组位置也唯一确定一个字符串。于是“本质不同的子序列集合”和“按首次位置规则选出的序列集合”形成了一一对应。这个一一对应关系是整个去重 DP 的地基。我最初没想通这一点直接写了一个“枚举每个位置选或不选”的 DP数组里的数字大得离谱调试了半天不知道错在哪。后来把状态改成“只关心下一个 0 在哪、下一个 1 在哪”一切才豁然开朗。2.3 我踩的第一个坑把方案数当成了本质不同数量这个坑在题目里特别隐蔽。如果你曾经刷过“统计一个字符串的所有不同子序列个数”的题会知道那里也有一个去重套路dp[i] 2*dp[i-1] - dp[last[s[i]]-1]。很多选手会试图把那套公式直接搬到这题上来但这里子序列长度是固定的 k不是任意长度而且还要支持“从某个位置之后开始计数”的查询直接套公式会让状态设计变得很别扭。我当时犯的错更基础我统计的是“从 i 开始能选出多少条位置路径”而不是“能选出多少种字符串”。路径数量天然是组合数的叠加重复率极高。直到我把“首次位置规则”画出来才发现正确的状态里根本不需要记录“具体选了哪些位置”只需要记录“第一个 0/1 落在哪”。3. 核心思路从“找第 K 小”变成“逐位决定填空”3.1 字典序的本质第 i 位越小字典序越小想想我们平时怎么比较两个字符串。从左往右看遇到第一个不同的字符0 那边就比 1 那边小。所以找字典序第 K 小的子序列完全可以逐位确定先定第 1 位是 0 还是 1再定第 2 位依此类推。这就像翻字典找单词。你先确定第一个字母再确定第二个字母每步都把候选集一分为二。关键在于你必须知道一个数如果这一位填 0后面还能接出多少种长度为剩余量的本质不同子序列。这个数如果大于等于 K说明答案第 1 位是 0否则把 K 减去这个数答案第 1 位就是 1。这个“提前数数”的过程决定了效率。因为每一步只做一次“填 0 还是填 1”的判断总步数就是 k只要能在常数时间得到计数整体算法就是 O(n·k) 量级——这已经比枚举所有子序列不知道快了多少个量级。3.2 决定走 0 还是走 1需要“提前数数”假设当前我们从原串的某个位置 pos 之后继续选还剩下 rem 个字符要填。先尝试填 0设 nxt0 为 s 在 pos 之后第一个 0 出现的位置如果 nxt0 存在在 nxt0 之后还要选出 rem-1 个字符组成剩余部分这个剩余部分的本质不同数量记为 cnt0。如果 K ≤ cnt0这一位确定为 0下一轮从 nxt0 之后重新开始rem 减 1。如果 K cnt0说明第 K 小的子序列这一位是 1K 先减去 cnt0跨过所有以 0 开头的候选再走 1 分支。这里有一种边界情况pos 之后根本没有 0那 cnt00自然直接落到 1 分支如果连 1 也没有说明当前已经无法继续构造应该输出 -1。于是核心子问题变成给定一个起点 p 和一个长度 len问 s[p..n] 能构造出多少种本质不同的长度为 len 的子序列。这个子问题用 DP 解决下面就是最关键的推导。3.3 DP 去重计数只看每个字符最近出现的位置定义 dp[i][j] 表示从位置 i 开始包含 is[i..n] 能构造出的长度为 j 的本质不同子序列数量。因为只有 0 和 1 两种字符转移只需要两支dp[i][j] dp[nxt0(i) 1][j - 1] dp[nxt1(i) 1][j - 1]其中 nxt0(i) 表示 s[i..n] 中第一个 0 的位置nxt1(i) 表示第一个 1 的位置。如果某个字符不存在对应分支就是 0。初值 dp[i][0] 1表示空串有 1 种。这个转移看起来简单但正确性完全建立在 2.2 节的“首次位置规则”上。每一个从 i 开始的子序列第一个字符要么是 0 且落在 nxt0(i)要么是 1 且落在 nxt1(i)两个分支互不重叠因为第一个字符是确定的。而每个子序列只会被计数一次因为后续字符的选取同样强制走“首次出现位置”。用序列自动机的视角看会更直观把每个位置看成一个状态每个状态有两条出边一条指向下一个 0一条指向下一个 1。任何一个子序列都对应一条路径而“每个字符只从首次出现位置走”相当于把所有平行边折叠成一条边路径数量恰好等于本质不同子序列数量。dp 就是这张 DAG 上的路径计数。4. 代码实操next 数组、去重 DP 与构造器4.1 预处理 next0 和 next1实现时我统一用 1-based 下标s 前面加一个占位空格。nxt0[i] 表示 s[i..n] 中第一个 0 的位置如果不存在设为 n1。倒着扫一遍就能预处理出来#include bits/stdc.h using namespace std; using ll long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; ll K; cin n k K; string s; cin s; s s; // 转成 1-based vectorint nxt0(n 2, n 1), nxt1(n 2, n 1); int p0 n 1, p1 n 1; // 哨兵不存在的位置 for (int i n; i 1; --i) { if (s[i] 0) p0 i; else p1 i; nxt0[i] p0; nxt1[i] p1; }注意这里我是在更新 p0/p1 之后再记录 nxt所以 nxt0[i] 是“从 i 开始第一个 0”包含了 i 本身。这个语义必须和 DP 状态保持一致。4.2 计数 DP 的写法与 K 截断dp[i][j] 从 i 倒序计算因为转移用到的 nxt0[i]1 一定大于 i所以后面的状态会先算好。初值方面dp[i][0]1 对所有合法 i 成立dp[n1][j] 对 j0 应该全是 0。// dp[i][j]: s[i..n] 中长度为 j 的本质不同子序列数量 vectorvectorll dp(n 2, vectorll(k 1, 0)); for (int i 0; i n 1; i) dp[i][0] 1; for (int i n; i 1; --i) { for (int j 1; j k; j) { ll cnt 0; if (nxt0[i] ! n 1) cnt dp[nxt0[i] 1][j - 1]; if (nxt1[i] ! n 1) cnt dp[nxt1[i] 1][j - 1]; if (cnt K) cnt K; // 截断避免溢出 dp[i][j] cnt; } }这里有一个非常容易写错的地方dp[n1][0] 的值。哨兵 n1 表示“空后缀”它不应该贡献任何非空子序列。上面的初值循环会把 dp[n1][0] 设为 1而 dp[n1][j0] 保持 0这是正确的。但如果你顺手把 dp 初始化成全部为 1或者用了 dp[n2][0]1 这种多余的状态转移时就会发现空后缀也能“变出”长度为 1 的序列样例直接崩掉。边界哨兵只保留一个不要画蛇添足。4.3 最后一步按 K 的值逐位构造子序列构造过程需要一个当前扫描位置 pre初始 pre0表示从 s[pre1..n] 这些位置里继续选。每次先定位从 pre1 开始的第一个 0 和第一个 1然后利用 DP 计数决定填哪个字符。int pre 0, rem k; string ans; while (rem 0) { int st pre 1; if (nxt0[st] n 1 nxt1[st] n 1) { cout -1 \n; return 0; } int a nxt0[st]; // 之后第一个 0 int b nxt1[st]; // 之后第一个 1 ll cnt0 0; if (a ! n 1) cnt0 dp[a 1][rem - 1]; if (K cnt0) { ans.push_back(0); pre a; rem--; } else { K - cnt0; if (b n 1) { // 理论上不会发生但保留判断更稳 cout -1 \n; return 0; } ans.push_back(1); pre b; rem--; } } cout ans \n;为什么要用 dp[a 1][rem - 1] 而不是 dp[st][rem] 之类的东西因为 dp[a1] 表示从选中 a 位置之后开始选正好排除掉已经用掉的 a同时 a 是 st 之后第一个 0正是“首次位置规则”规定的代表位置。看向 dp[st][rem] 会把所有没有明确首位字符的空串情况也卷进来计数语义就错了。5. 边界测试与踩坑记录几个差点送走的 case5.1 K 的起点问题第 0 小是什么大部分题面里 K 从 1 开始这个约定很重要。因为在构造过程中每一步的判断都是 K ≤ cnt0K 的最小值是 1正好对应“取当前分支里第一个候选”。如果题目变体允许 K0那意味着要输出“字典序第 0 小”通常等价于某种空串/特判需要在构造前单独处理。我建议写代码前先确认 K 的下界省得构造做到最后还是错的。还有一点如果输入给的 K 是 1而长度为 k 的本质不同子序列至少有 1 种那么答案永远是“所有长度为 k 的候选里字典序最小的那个”。这个最小的候选很好猜尽量让前面的字符都填 0。用我们的构造逻辑跑一遍会发现每一步 cnt0 都足够大永远走 0 分支最终输出一串尽量靠前的 0 和必要时的 1结果完全正确。5.2 填 0 分支计数为 0但填 1 可行构造时如果 K cnt0说明所有以 0 开头的候选都被跨过了。这时 K 要减去 cnt0再进入填 1 分支。很多人会在这里少写 K - cnt0 这一行导致后面所有判断全部偏移。另一种情况更隐蔽cnt0 是 0K 是 1直接 Kcnt0于是填 1。这没问题。但如果 K 很大比如 10^9而 0 分支和 1 分支的总数都不足 K理论上应该在某个时刻发现走不下去。由于 DP 被 K 截断过这里不会出现“错误地认为足够”的问题吗答案是安全。设初始 K 为 K0预处理时我们做的截断是 min(真实值, K0)。构造过程中 K 只会保持不变或减小永远不会超过 K0。如果一个分支的真实数量小于当前 K那么它也小于 K0DP 里保留的就是真实值判断正确如果一个分支的真实数量不小于当前 K那么它可能被截断为 K0但只要真实值 ≥ 当前 K截断后的值一定也 ≥ 当前 K判断依然正确。这个“只截不断错”的性质是 K 截断能用在这类题里的根本原因。5.3 全 0、全 1 与大量重复字符极端数据是检验去重 DP 是否写对的好工具。我用几组测试验证过输入输出说明s0000, k2, K100本质不同只有 1 种s111, k2, K211全 1同样只有 1 种s0101, k2, K201所有长度为 2 的子序列00,01,10,11s1010, k2, K5-1本质不同只有 00,01,10,11s01, k3, K1-1长度不足无解全 0 和全 1 这种串长度 k 的子序列无论怎么选结果都只有一种。如果 DP 写成了路径计数这里会输出一个大于 1 的数字K2 时就会错误地进入某个分支最后构造出乱七八糟的东西。能用这组用例跑通说明去重逻辑基本没问题。5.4 性能观察n×k 打满怎么办说句实话最坏情况下 O(n×k) 在 n 和 k 都拉满到 2×10^5 时无论是时间还是空间都扛不住。这也是这题被标 hard 的另一个原因。刷题时常见的应对方式有几种当 K 比较小时比如 K ≤ 10^6大量 dp 状态会被截断成 K实际运算量远小于 n×k跑起来飞快。当 k 接近 n 时可以考虑“反向删除”长度为 k 的子序列等价于原串删掉 dn-k 个字符。如果 d 很小可以反过来做删除方案的构造复杂度和 O(n·d) 相关而不是 O(n·k)。空间上 dp 可以滚动因为 dp[i][j] 只依赖 j-1 层的状态按 j 从 1 到 k 逐层计算只需要两个长度为 n 的数组滚动使用。我个人的经验是先按 O(n×k)截断写一版能过大部分子任务和中等数据如果题目明确给极限数据再针对 k 和 n-k 的较小值选择正反方向。比赛里“能拿部分分 快速换方向”往往比死磕一个满分做法更划算。6. 套路沉淀这类“第 K 小构造题”的通用解法模型6.1 和经典第 K 小子序列题的异同如果你刷过“第 K 小子串”“第 K 小排列”这类题目会发现核心套路是一样的先做计数再逐位构造。计数环节负责回答“以某个前缀开头的候选有多少个”构造环节负责根据 K 的大小不断二分候选集。不同的是“子串”天然不会有位置重复问题而“子序列”必须处理同一字符串由不同位置组合造成重复计数的问题。这就是为什么子串题可以用后缀自动机或前缀和直接数子序列题却要引入“首次位置规则”来做去重。理解了这一层很多变体题都能看出共性只要计数逻辑能去重剩下的逐位构造框架可以原封不动地搬过去。6.2 换题不换骨从 01 串推广到字符集更大的题如果题目把 01 串换成小写字母串思路完全一样只是转移从 2 个分支变成 26 个分支。dp[i][j] Σ dp[nxt_c(i)1][j-1]其中 nxt_c(i) 表示 s[i..n] 中字符 c 第一次出现的位置。复杂度会乘以字符集大小但只要字符集不大依然可行。如果题目要求“字典序第 K 大”同样简单把比较方向反过来构造时先尝试填 1 分支即可。如果题目要求输出所有本质不同子序列那 DP 去重计数可以直接用于回溯生成只是数量多了会爆炸。6.3 一点提速与调试建议最后分享几个我实操中积累的小技巧预处理 next 数组时哨兵统一用 n1。这样“不存在”和“空后缀”是同一个值判断分支会非常干净。DP 数组的初值只对 dp[i][0] 设 1不要给非法状态随便设值。一个多余的哨兵会让错误发生得非常隐蔽。构造答案时手动维护 pre 而不是在 DP 表里记录位置。因为 DP 表是按长度和起点组织的构造时需要在原串上跳跃直接维护一个位置变量最直观。调试时先跑全 0、全 1 样例再跑有多个重复 0/1 的样例。这两类数据能快速暴露“是否真的去重了”的本质问题。这套模型我后来在好几道变体题里都直接套用过包括字符集 26 的“第 K 小子序列”、带循环节的“周期串子序列”等。只要计数去重这一关过了逐位构造的代码几乎不用改直接就是稳定输出。
