企业官网建设流程全解析

前几天整理题单，翻到一道题号叫 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个1

3.1 朴素构造的局限

如果只靠0^a 1^b这种一段0加一段1的结构，我们能把k表示成a * b，然后希望a + b不超过n。但问题在于：不是所有k都能写成两个都比较小的整数乘积。

举个具体例子，n = 9，k = 19。0^19 1^1能贡献19，但长度是20，远超n；0^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的要求。

1. 读入n、k。
2. 特判k = 0：直接输出n个'0'，因为全0串没有任何'1'，01子序列数量为0，长度为n。
3. 枚举b，从1到n - 1：
   • 计算a = k // b，r = 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'。
   • 输出构造结果，程序结束。
4. 如果所有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串：没有1，01子序列数量为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，如果r>0还要插入一个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串：没有1，01子序列数量为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，如果r>0还要插入一个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 样例手算验证

空口无凭，手动验几个例子：

注意第四行，n=9时最大01子序列数是floor(9/2) * ceil(9/2) = 4 * 5 = 20，k=20正好顶到上限，也能构造出来。这说明我们的块状构造在边界上也很稳。

5. 正确性与边界：为什么枚举b够用，什么时候无解

5.1 最大01子序列数的一个快速认知

长度为n的01串，什么时候01子序列数量最大？直观想，'0'在前面、'1'在后面时，每个'0'都会被后面的'1'利用到。如果'0'和'1'都太偏，贡献就会被浪费。最优情况是0和1尽量均匀：0的个数约等于n/2，1的个数约等于n/2，最大数量是floor(n/2) * ceil(n/2)。

比如n=8，最大是4 * 4 = 16；n=9，最大是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趋于0，cost又回升。所以cost一定存在一个最低点，大致在b接近sqrt(k)的位置。如果k没超过上面的max_cnt，这个最低点处的cost几乎总是能压进n以内的。实际做题时，直接暴力枚举b，第一次遇到cost ≤ n就break，非常稳定。

这不是严格的数学证明，但作为竞赛里“暴力枚举+检查”的解题策略已经足够可靠。如果你想要更保险，还可以在枚举之前就把b限定在1到n-1，并且加上k ≤ max_cnt的提前判断，双保险。

5.3 k=0的特判为什么不能省

当k=0时，如果还在循环里枚举b，b=1时a=0、r=0，cost=1，构造出来会是一串'1'，看起来也没问题。但如果n=1，b只能取到1？其实b < n意味着没有合法的b，最终会输出-1，但k=0明明有解。所以k=0还是特判最干净。直接输出n个'0'，简单直接，不用进循环。

顺带一提，如果题目允许全0串或全1串，k=0的答案有很多种。我习惯输出全0，因为一眼就能看出来确实没有'1'，不会有01子序列。

5.4 无解分支必须写清楚

构造题和普通计算题还不一样，普通题无解时通常RE或WA，构造题则明确要求输出-1。如果漏掉else分支，编译器可能会返回一个未初始化的字符串，或者输出空串，都是WA。

无解的情况主要有两种：

• k超过了理论最大值max_cnt；
• n太小，连核心构造都放不下（比如n=1，k=1，一个字符不可能同时出现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，卡在n=5、k=5这种看似简单但a、b凑不进来的数据上。a=5、b=1虽然贡献是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没有意义；k=0又必须提前特判。所以循环一定是从b=1开始，到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的结构把整道题从“瞎凑”变成了“按公式生成”。刷题刷到后面你会慢慢发现，很多所谓的构造题，本质上就是让你把目标值写成一个更容易控制的算术表达式，剩下的就是枚举、整除、取余这类基本功。希望这篇复盘能让你也体会到这种“公式一旦写对，答案自己会走出来”的感觉。