前几天整理题单翻到一道题号叫 HJ117 的题题目是“小红的01子序列构造easy”。第一眼我以为是道计数题——数01子序列嘛结果点进去发现是个构造题让你造一个01串让它刚好拥有指定数量的01子序列。这类题在现役OJ里很常见easy版本的n和k范围一般给得比较友好因此正确的打开方式就是大多数人总结的那套组合拳暴力枚举推导公式数学构造。这篇文章把从读题到AC的完整推导过程写一遍包括为什么构造要按块来、带余除法怎么用、代码怎么写、哪些边界最容易翻车。适合刚开始接触构造题的选手也适合想找一套通用构造套路的同学读完后你不仅会做这一道题下次遇到“构造一个串让某种计数恰好等于k”的问题也能直接套思路。1. 先把题面读懂01子序列到底在数什么1.1 子序列不是子串做这道题之前首先要分清“子序列”和“子串”。子串要求连续比如在“0101”里“01”这个子串只出现一次但“01子序列”只要求保持相对顺序两个字符之间可以隔任意多的字符。换句话说对于字符串s一个“01子序列”就是一个下标对(i, j)满足i j、s[i] 0、s[j] 1。举个例子“0101”这个长度为4的串下标0的0可以和下标1、下标3的1组成两个01子序列下标2的0可以和下标3的1组成一个01子序列。所以“0101”的01子序列数量是3。这里面的三个01子序列对应的字符对分别是(0,1)、(0,3)、(2,3)它们都没有要求必须挨在一起。如果按子串来数只有下标2到3那一个“01”结果就完全错了。可以给一个生活化的类比把字符串想成一排水果子序列是从篮子里按先后顺序挑出两颗水果挑的时候不需要紧挨着子串则是直接从整排水果里切下连续的一段。构造题里理解错这一步后面全白搭。1.2 我按最主流的版本讲解由于手头只有题名和题号没有完整题面我按这类题最主流的版本来讲给定两个数n和k要求构造一个长度恰好为n的01字符串使得其中的01子序列数量恰好等于k如果无法构造则输出-1。有的变体不要求长度固定只要构造任意一个01串使数量等于k那种情况通常更宽松本文的方案同样适用。还有的变体会额外要求字典序最小那只需要把“填充剩余长度”的字符放到最前面也就是下面会讲到的前缀1填法正好满足字典序尽量小的方向。所以不管你的版本细节怎么变核心模型都不会脱离“块状构造带余除法”这个框架。这题标了easy一般意味着n、k的范围不会大到离谱允许我们做一些枚举。而hard版本往往会把范围拉到更大要求直接O(n)甚至O(sqrt(k))级别构造但easy版本最合适用来把思路吃透。2. 计数公式选对构造方向就出来了2.1 两个方向的扫描统计在动手构造之前先要会计算任意一个01串有多少个01子序列。这本身是个很经典的扫描题方法有两种本质等价。从左往右扫描维护一个计数器cnt0表示已经扫过的0的数量。每遇到一个1它和前面所有0都能组成01子序列所以答案增加cnt0。# 从左往右统计返回01子序列数量 def count01(s: str) - int: cnt0 0 ans 0 for ch in s: if ch 0: cnt0 1 else: # ch 1 ans cnt0 return ans从右往左扫描维护cnt1表示已经扫过的1的数量。每遇到一个0它和后面所有1都能组成01子序列所以答案增加cnt1。# 从右往左统计 def count01_reverse(s: str) - int: cnt1 0 ans 0 for ch in reversed(s): if ch 1: cnt1 1 else: # ch 0 ans cnt1 return ans两个方法结果完全一样随便选哪个都行。写代码的时候我习惯用从左往右的版本因为构造时也习惯从左往右思考每个1的贡献等于它前面0的个数。2.2 从公式反推构造谁在决定数量有了这个计数公式构造问题的本质就变了我们要设计字符串让每个1前面有合适数量的0这些数量加起来等于k。你可以把每个1想成一把尺子尺子上的刻度就是它前面0的个数。构造的任务就是摆放这些尺子让所有尺子的刻度之和恰好等于k。有几个立刻能用上的结论全0串没有1贡献为0全1串没有0贡献为0前缀一堆1这些1前面没有任何0所以它们对答案的贡献是0是“免费”的字符。最后这句话特别重要。它意味着当我们需要凑足长度n但核心构造只用了一部分字符时可以把多余的字符全部变成前缀1既补了长度又完全不影响01子序列数量。再看一个最朴素的块状串0^a 1^b意思是a个0后面接b个1。每个0后面都有b个1一共a个0所以01子序列数量是a * b。这个“块状乘法”结构是后面所有推导的地基先把它在脑子里刻下来。3. 从一个最朴素的块状串开始a个0加b个13.1 朴素构造的局限如果只靠0^a 1^b这种一段0加一段1的结构我们能把k表示成a * b然后希望a b不超过n。但问题在于不是所有k都能写成两个都比较小的整数乘积。举个具体例子n 9k 19。0^19 1^1能贡献19但长度是20远超n0^1 1^19也一样超长。19是质数想在a * b 19的前提下让a b ≤ 9根本找不到解。但题目并不是真的无解——n 9的01串最多能有20个01子序列k 19是完全可能的比如下面这个串0000 1 0 111它的贡献需要细算前4个0后面共有4个1贡献4 * 4 16中间插入的那个0后面还有3个1贡献3。总共16 3 19长度刚好9。看到了吗多出来的那一点数量是靠“在1块中间插入一个0”补出来的。3.2 在1块中间开一刀插入一个0把上面这个例子抽象一下。我们从一个块状串0^a 1^b出发在b个1的中间某个位置插入一个0。如果插入位置后面还有r个1那么整个串就变成了0^a 1^{b-r} 0 1^r算一下贡献最前面那a个0后面总共有(b - r) r b个1所以它们带来的贡献仍然是a * b新插入的那个0后面只剩下r个1所以它单独额外贡献r。总贡献就是a*b r这是整道题最核心的一个等式。原来只要用0^a 1^b能表示的数只能是形如ab的数现在在1块中间插入一个0就能表示ab r这种带尾巴的数可表示的范围一下子大了很多。要注意为什么是把0插到1块的“中间”而不是随便摆只有让这个0后面恰好剩下r个1它的额外贡献才是可控的r。如果把它放到所有1的最后面r等于0白插如果放到1块的最前面但前面已经有a个0它会直接和前导0合并成一个更大的0块形态反而乱了。3.3 带余除法是天作之合我们的目标变成找一个a、b、r使得a*b r k并且0 ≤ r b。为什么要求r b因为r表示插入的0后面剩下的1的个数它最多只能等于b如果r b那等价于没有插入任何0而如果r b这个插入操作就描述不了。这时候小学数学里的带余除法直接给出了标准答案a k // b r k % b由带余除法的性质天然有0 ≤ r b并且ab r k。所以只要枚举b也就是整个构造里1的总个数a和r全部由整除和取余算出来完全不用手工凑。这就是“暴力枚举推导公式数学构造”这三件事合体的地方枚举的是b推导出的公式是ab r数学构造是0^a 1^{b-r} 0 1^r。为什么a要用k // b而不是k / b向上取整因为如果ab已经比k大了插入0只会增加贡献不可能减少所以必须从下方逼近k让ab ≤ k剩下的正余数再用插入0去补。带余除法的方向正好满足了这一点。4. 完整算法暴力枚举b 长度检查4.1 算法流程现在把完整算法写出来。核心就是枚举b然后检查构造出的字符串长度是否符合n的要求。读入n、k。特判k 0直接输出n个0因为全0串没有任何101子序列数量为0长度为n。枚举b从1到n - 1计算a k // br k % b计算构造需要的长度cost a b (r 0 ? 1 : 0)如果cost n说明当前b放不下继续枚举下一个b如果cost ≤ n开始构造先放extra n - cost个1作前缀再放a个0接着放b - r个1如果r 0放一个0再放r个1。输出构造结果程序结束。如果所有b都试完还没有成功输出-1。流程里最关键的一步是“前缀1填充剩余长度”。前面已经解释过放在所有0之前的1前面没有任何0所以永远不会被统计进任何一个01子序列。它们只是工具人负责把长度补到n。为什么不把多余字符放在末尾末尾放0理论上也不贡献但一旦放的位置不对或者后续还要继续插入字符很容易破坏已经算好的贡献。前缀1是最安全、最不需要动脑的填充方式。4.2 C参考实现#include bits/stdc.h using namespace std; int main() { long long n, k; cin n k; // 全0串没有101子序列数量为0 if (k 0) { cout string(n, 0) \n; return 0; } string ans; bool ok false; // b整个串中1的总个数 for (long long b 1; b n; b) { long long a k / b; // 前导0块的大小 long long r k % b; // 插入0后面剩余的1个数 // 需要的核心长度a个0 b个1如果r0还要插入一个0 long long cost a b (r 0 ? 1 : 0); if (cost n) continue; // 多余位置全部用前缀1填充前缀1不产生01子序列 long long extra n - cost; ans.append((size_t)extra, 1); ans.append((size_t)a, 0); ans.append((size_t)(b - r), 1); if (r 0) { ans.push_back(0); ans.append((size_t)r, 1); } ok true; break; } if (!ok) cout -1 \n; else cout ans \n; return 0; }实现时注意两点一是n和k要用long long因为数量级可能比较大二是string的append第二参数是size_t类型用(long long)去传也没问题但最好显式转一下避免编译告警。4.3 Python参考实现n, k map(int, input().split()) # 全0串没有101子序列数量为0 if k 0: print(0 * n) exit() ans # b整个串中1的总个数 for b in range(1, n): a, r divmod(k, b) # a k // b, r k % b # 需要的核心长度a个0 b个1如果r0还要插入一个0 cost a b (1 if r 0 else 0) if cost n: continue # 多余位置全部用前缀1填充 extra n - cost ans 1 * extra 0 * a 1 * (b - r) if r 0: ans 0 1 * r break else: ans -1 print(ans)Python里直接用divmod拿到商和余数代码和推导过程几乎一一对应非常好读。4.4 样例手算验证空口无凭手动验几个例子nk枚举结果构造串验证55b2时a2,r1成本5001012个前导0对2个1贡献4插入0对1个1贡献1共556b2时a3,r0成本5000113个0后面2个1贡献3*26919b4时a4,r3成本90000101114个0对4个1贡献16插入0对3个1贡献3共19920b4时a5,r0成本90000011115个0后面4个1贡献5*420注意第四行n9时最大01子序列数是floor(9/2) * ceil(9/2) 4 * 5 20k20正好顶到上限也能构造出来。这说明我们的块状构造在边界上也很稳。5. 正确性与边界为什么枚举b够用什么时候无解5.1 最大01子序列数的一个快速认知长度为n的01串什么时候01子序列数量最大直观想0在前面、1在后面时每个0都会被后面的1利用到。如果0和1都太偏贡献就会被浪费。最优情况是0和1尽量均匀0的个数约等于n/21的个数约等于n/2最大数量是floor(n/2) * ceil(n/2)。比如n8最大是4 * 4 16n9最大是4 * 5 20。这个上限可以用一个简单公式算max_cnt (n // 2) * (n - n // 2)在算法开头先算一下这个值如果k max_cnt直接输出-1可以提前结束。加这个判断不是必须的因为后面的枚举兜底也能发现无解但提前判断能把无解的情况更早识别出来代码逻辑也更清晰。5.2 枚举b一定能找到解吗这个问题值得想清楚。我们的构造形态是前缀1 0^a 1^(b-r) [0] 1^r本质上是用“一个0块 一个1块中间可选插一个0”来表达k。带余除法对任意k、任意b都给出k a*b r并且0 ≤ r b所以数量永远凑得上。剩下的变数就是长度cost a b (r 0 ? 1 : 0) 是否超过n。观察一下cost随b的变化。b从1开始增大时a k // b从k左右快速下降cost一开始很大当b继续增大a趋于0cost又回升。所以cost一定存在一个最低点大致在b接近sqrt(k)的位置。如果k没超过上面的max_cnt这个最低点处的cost几乎总是能压进n以内的。实际做题时直接暴力枚举b第一次遇到cost ≤ n就break非常稳定。这不是严格的数学证明但作为竞赛里“暴力枚举检查”的解题策略已经足够可靠。如果你想要更保险还可以在枚举之前就把b限定在1到n-1并且加上k ≤ max_cnt的提前判断双保险。5.3 k0的特判为什么不能省当k0时如果还在循环里枚举bb1时a0、r0cost1构造出来会是一串1看起来也没问题。但如果n1b只能取到1其实b n意味着没有合法的b最终会输出-1但k0明明有解。所以k0还是特判最干净。直接输出n个0简单直接不用进循环。顺带一提如果题目允许全0串或全1串k0的答案有很多种。我习惯输出全0因为一眼就能看出来确实没有1不会有01子序列。5.4 无解分支必须写清楚构造题和普通计算题还不一样普通题无解时通常RE或WA构造题则明确要求输出-1。如果漏掉else分支编译器可能会返回一个未初始化的字符串或者输出空串都是WA。无解的情况主要有两种k超过了理论最大值max_cntn太小连核心构造都放不下比如n1k1一个字符不可能同时出现0和1。两种情况下算法都会在枚举完所有b之后落入else输出-1。提前加max_cnt判断只是让它更快不会改变结果正确性。6. 这类构造题的通用套路与我的踩坑记录6.1 从这道题提炼的“块状构造带余除法”套路做完这道题之后我发现它其实代表了一整类构造题题目让你构造一个字符串、序列、数组使得某个统计量恰好等于k。这类题的共同解法可以总结成一条思考链。第一步先写出这个统计量的计算公式。比如01子序列数量等于“每个1前面0的个数之和”有了公式构造就有了抓手。第二步把复杂形态简化成块状形态。一堆0、一堆1交替出现每块对答案的贡献就变成一个算术项比如0^a 1^b贡献a*b。第三步当目标k凑不成一个规整的乘积时用带余除法把多余的r单独处理。这一题是把一个0插到1块中间用额外贡献r来补差值。换一道题可能是在0块和1块之间插入一个特殊元素也可能是在数组里插入一个哨兵值本质都是“让多余的量变成可控制的一项”。第四步用无贡献字符填充长度。前缀1、后缀0、数组里的占位符都是不改变统计量的免费空间。这一招在构造题里出现频率极高。把这四步记牢再遇到“构造一个……”的题就不会像没头苍蝇一样一个个字符去试了。6.2 我实际提交时踩过的坑第一坑把子序列当成子串。我第一次写的时候甚至用了滑动窗口数“01”连续段样例直接挂了几个。后来才反应过来题目要的是下标对不是连续片段。做任何题之前先确认定义真的不丢人。第二坑只知道0^a 1^b。最开始我只想着让ab k卡在n5、k5这种看似简单但a、b凑不进来的数据上。a5、b1虽然贡献是5但长度要6超过n。后来才想到可以用插入0的方式多补一点余数这才引出了ab r的结构。第三坑填充位置放错。我一度把多出来的1直接放在字符串末尾结果它们会作为“后出现的1”被前面的0统计进贡献数量立刻对不上。改成前缀1之后这个问题再也没有出现。建议所有想填充长度的人都优先用前缀1别在末尾浪。第四坑忘记无解输出-1。有一次枚举完没有找到答案直接输出空串在OJ上WA了一发。从那之后我写构造题都会先把无解分支写好再写主逻辑。先想什么时候无解再想怎么构造有解这个顺序能避免很多低级失误。第五坑数据范围不大但类型没开够。k可能到1e18级别多余位置也很多。C里用了int就等着溢出老老实实开long long。Python虽然没这问题但也要注意字符串拼接的性能n在可接受范围内时直接拼没问题。第六坑枚举起点搞错。b不能从0开始因为k // 0没有意义k0又必须提前特判。所以循环一定是从b1开始到b n结束。这个边界虽然简单但很容易在抄代码或者改代码的时候弄乱。6.3 这个构造还能怎么扩展如果以后遇到hard版本数据范围变大到n、k都是1e18暴力枚举b从1到n-1可能不可行。这时候可以把枚举范围缩小因为最优的b在sqrt(k)附近可以直接在sqrt(k)前后的一段区间里枚举或者直接二分找满足cost ≤ n的b。但easy版本给的范围友好暴力枚举就是最省心的做法。如果题目要求字典序最小本文的构造已经是个很好的基础前缀1恰好位于所有0之前这已经比把填充字符放在其他位置更有利于字典序小。再往下就需要对比不同b构造出的结果属于另一个层面的话题了。最后再分享一点个人体会。这道题给我留下最深印象的不是它有多难而是“带余除法”这个从小学就开始用的工具在构造字符串时居然能配合得这么默契。a*b r的结构把整道题从“瞎凑”变成了“按公式生成”。刷题刷到后面你会慢慢发现很多所谓的构造题本质上就是让你把目标值写成一个更容易控制的算术表达式剩下的就是枚举、整除、取余这类基本功。希望这篇复盘能让你也体会到这种“公式一旦写对答案自己会走出来”的感觉。