做了这么多年的算法题，我对“构造”这类题目一直保持警惕：它不像普通模拟题那样照流程跑一遍就行，也不像DP题靠状态转移推到底，而是要先读懂题目想让你构造什么，再用数学规律把答案“算”出来。HJ117“小红的01子序列构造（easy）”就是很典型的例子，看起来只是生成一个01字符串，实际上一旦你把01子序列的计数公式想清楚，代码不到20行，真正的难点全在推导。
这篇博文我会从题目解读、公式推导、构造思路、代码实现、边界情况到通用套路逐步展开，把这道easy题讲透，也把这类构造题的方法论给你提炼出来。
1. 题目到底在问什么：不是数子序列，是造子序列
1.1 先搞清楚什么是“01子序列”
很多人看到“子序列”就会和“子串”混淆。子串必须是连续的，比如字符串0101的子串有010、101，但001就不是子串；子序列则允许跳跃选取，只要保持相对顺序就行。所以0101里选第1个字符0和第3个字符0，再选第4个字符1，组成的001就是一个子序列。
而“01子序列”专门指：选取两个位置i < j，满足i位置是0、j位置是1。换句话说，数一数整个字符串里有多少个“前面是0、后面是1”的无序对。
举个例子：
010- 位置1和位置2：
0和1，构成01子序列。 - 位置1和位置3：
0和0，不行。 - 位置2和位置3：
1和0，顺序反了，不行。
所以010的01子序列数量是1。
再看0011：
- 第1个0：后面有2个1，贡献2个。
- 第2个0：后面有2个1，贡献2个。
- 总数是4。
这个“每个0数后面有几个1再求和”的理解方式非常关键，后面所有推导都从它出发。
1.2 HJ117的题意还原
HJ117的题面用“小红”做主角，属于牛客网常见的命名风格。虽然题目标注了easy，但它不是让你写一个暴力统计函数，而是给你长度为n和目标值k，要求构造一个长度为n的01字符串，让它包含的01子序列数量恰好等于k。构造不出来就输出-1。
这里“构造”是核心：字符串本身不是唯一的，可能有无数种答案，你只需要输出任何一种合法解。
注意：这里的
k通常不会给得太大。如果k超过了长度为n的01串能产生的最大01子序列数量，那无论怎么摆都没有解。这个“最大值”是第一个要算的数学规律。
2. 核心思路：把字符串看成“0的累加器”
2.1 关键公式：答案等于每个1前面的0的个数之和
上面我们已经有了一个统计方式：逐个数每个0后面有几个1。但其实更顺手的统计方式是从左往右扫描：
维护一个变量cnt0表示当前已经扫过的0的个数。每遇到一个1，这个1会和前面所有0组成01子序列，所以答案累加cnt0；每遇到一个0，cnt0加1。
用010验证：
- 遇到
0，cnt0=1。 - 遇到
1，答案+=1。 - 遇到
0，cnt0=2。 - 答案=1，正确。
这个视角等价于：假设最终构造的字符串里有b个1，从左到右编号为第1个、第2个、…、第b个1，记c_i为第i个1前面出现的0的个数，那么：
答案 = c_1 + c_2 + ... + c_b这个式子看起来简单，但它揭示了一个重要性质：c_1 <= c_2 <= ... <= c_b。因为扫描到越靠后的1时，前面的0只会更多，不可能变少。这个非递减单调性，是构造算法的根基。
2.2 最大值和界限：为什么k太大就无解
如果a个0全部排在b个1的前面，那么每个1前面的0数量都等于a，答案达到最大值a*b。
在固定总长度n = a + b的前提下，a*b的最大值是初等数学里的经典结论：两个数和固定，乘积最大化在两者接近相等时取得。所以：
max = floor(n / 2) * ceil(n / 2)比如n=5时，a=2, b=3或a=3, b=2，最大都是6。所以如果k > 6，直接无解。
这个上限判断虽然简单，但在代码里必须写，否则边界数据会直接卡死后面的构造逻辑。
3. 数学构造：用“分组平均数”的思路精确命中k
3.1 平均分配的直觉来源
有了答案 = c_1 + c_2 + ... + c_b，问题就变成了：构造一个非递减的非负整数序列c_i，让它的总和等于k，并且最终能用01串实现。
如果直接让所有c_i都等于某个数q，那么总和是b*q，只能表示b的倍数，覆盖不了所有k。但我们可以退一步：
设：
q = k // b r = k % b也就是说，把k拆成b份，平均每份q，还余下r。那么一种自然的非递减序列就是：
前 b-r 个 c_i 等于 q 后 r 个 c_i 等于 q+1这个序列显然是满足非递减的。举个例子，k=8, b=3时：
q = 2, r = 2 c = [2, 3, 3]总和2+3+3=8。
3.2 如何把这个序列翻译成01字符串
现在的问题变成了：怎么构造一个01串，让第1个1前面有q个0，第2个1前面还是q个0，直到第b-r个1前面都是q个0，然后从第b-r+1个1开始，每个1前面多1个0？
做法非常简洁：
若 r == 0： 0^q + 1^b + 0^(a-q) 若 r > 0： 0^q + 1^(b-r) + 0^1 + 1^r + 0^(a-q-1)解释一下这个分段：
0^q：提供前面公用的q个0，让所有1都有q个前缀0。1^(b-r)：和前面的q个0配对，每个1贡献q，一共贡献(b-r)*q。- 紧接着的一个
0：它只影响后面的r个1，让它们每个都多一个前缀0。 1^r：后面的r个1，每个贡献q+1，一共贡献r*(q+1)。0^(a-q-1)：多余的0全部放在最后面。它们不会出现在任何1的前面，因此对答案没有任何影响。
这样总贡献就是(b-r)*q + r*(q+1) = b*q + r = k，精确命中。
来看一个完整的例子：n=5, k=5。
选b=3, a=2：
q = 5 // 3 = 1 r = 5 % 3 = 2因为r>0，构造：
0^1 + 1^(3-2=1) + 0^1 + 1^2 + 0^(2-1-1=0) = "0" + "1" + "0" + "11" = "01011"验证：第1个1前面有1个0，贡献1；第2个1前面有1+1=2个0，贡献2；第3个1前面也有2个0，贡献2。总数1+2+2=5，完全正确。
3.3 构造条件：不是随便选b都能成功
刚才的例子比较顺利，但如果你选的b不合适，公式里会出现负数指数。比如n=5, k=5时选b=1, a=4：
q = 5 // 1 = 5 r = 5 % 1 = 0构造0^5 + 1^1 + 0^(4-5)，最后一段指数是-1，显然不合法。
原因在于：a=4个0根本不够给那个唯一的1凑出5个前缀0。所以构造之前必须检查两个条件：
第一个条件是总量足够，即a*b >= k。这是保证把k平均分给b个1后不会超过可能的最大贡献。
第二个条件是0的数量足够分配，即：
r == 0 时：a >= q r > 0 时：a >= q + 1这个条件可以统一写成a >= q + (1 if r > 0 else 0)。
逻辑很直白：r==0时需要在1的前面放q个0，末尾放a-q个0，要求a-q >= 0；r>0时除了前面放q个0，中间还要放1个0，要求a - q - 1 >= 0。
4. 代码实现：暴力枚举b，简单又稳妥
4.1 C++实现
写代码时我的习惯是：不要试图一开始就推导出最优的b公式，直接枚举b从0到n，遇到第一个合法方案就输出。因为n一般不会很大，O(n)枚举完全够用，而且跳过繁琐的证明，极大降低写错概率。
#include <bits/stdc++.h> using namespace std; int main() { int n; long long k; cin >> n >> k; // 无解：超过理论最大值 long long maxK = 1LL * (n / 2) * (n - n / 2); if (k > maxK) { cout << -1 << '\n'; return 0; } // 特判 k = 0，全0串一定满足 if (k == 0) { for (int i = 0; i < n; i++) cout << '0'; cout << '\n'; return 0; } for (int b = 1; b <= n; b++) { int a = n - b; if (a * 1LL * b < k) continue; long long q = k / b; long long r = k % b; int need = (int)q + (r > 0 ? 1 : 0); if (a < need) continue; string ans; // 公共前缀0 ans.append(q, '0'); if (r == 0) { ans.append(b, '1'); ans.append(a - q, '0'); } else { ans.append(b - r, '1'); ans.push_back('0'); ans.append(r, '1'); ans.append(a - q - 1, '0'); } if ((int)ans.size() != n) { // 理论推到这里不会发生，但保留一个保护 continue; } cout << ans << '\n'; return 0; } cout << -1 << '\n'; return 0; }代码里maxK的计算用1LL防止整型溢出，这个习惯值得强调：算法竞赛中一旦出现n*n级别的乘法，永远要用long long。
4.2 Python实现
Python写起来更短，逻辑完全一样：
n, k = map(int, input().split()) max_k = (n // 2) * (n - n // 2) if k > max_k: print(-1) exit() if k == 0: print('0' * n) exit() for b in range(1, n + 1): a = n - b if a * b < k: continue q, r = divmod(k, b) # q = k//b, r = k%b need = q + (1 if r > 0 else 0) if a < need: continue if r == 0: ans = '0' * q + '1' * b + '0' * (a - q) else: ans = '0' * q + '1' * (b - r) + '0' + '1' * r + '0' * (a - q - 1) print(ans) exit() print(-1)这里divmod是Python的一个小技巧，一次拿到商和余数，配合后面的条件判断非常顺手。
4.3 为什么枚举b一定找得到解
理论上，只要k <= maxK，上面的枚举必定能找到一个合法b。我从两个层面理解这件事。
在直觉层面，b从1到n遍历时，其实是在尝试所有可能的“1的个数”。如果b太小，a*b < k，说明1太少无法产生足够的01子序列；如果b太大导致a太小，a < need，说明0太少无法给每个1配够前缀0。最大值floor(n^2/4)恰好说明存在一个均衡的b让两种情况同时满足，而枚举从b=1开始逐个试，总会在到达均衡点前后命中。
在构造层面，我们给出的分段公式把所有0分成了三块：公共前缀0、中间分隔0、末尾填充0。只要0的总数多于“公共前缀0+中间分隔0”，就能成功。这个余量由a - need保证非负。
所以这段枚举代码不是“碰运气”，而是把存在性证明转化为一个非常简单的循环。
5. 常见问题与边界情况：这些坑我都踩过
5.1 k=0的情况必须单独处理
一开始我写代码时没有对k=0单独特判，直接走进枚举循环。然后发现当b=1时：
q = 0, r = 0确实可以构造出0^0 + 1^1 + 0^(a)，也就是末尾一个1加一堆0的串，比如010？不对，0^(a)会在1前面放0？让我们验证：n=3, k=0，枚举b=1, a=2，q=0, r=0，need=0，构造"" + "1" + "00" = "100"，这个串的01子序列数量确实是0，因为0都在1后面。所以不特判也能过。
但更稳妥、更清晰的做法是一开始就特判k=0直接输出全0。原因有两个：
- 全0串永远合法，不需要走后续的数学分支。
- 即使后续分支能覆盖
k=0，它依赖1在0前面的排列，容易让自己绕晕。
5.2 小心“子序列”和“子串”的混淆
如果你把01子序列理解成01连续子串，整个推导就全错了。比如001的子串中只有最后两个字符01算一个，但按子序列算，第1个0和第2个0都能和最后的1配对，答案是2。
我建议你在草稿纸上先把0011这种简单串的子序列数手算一遍，再开始推公式。这个基础打不牢，后面所有构造技巧都是空中楼阁。
5.3 当输出串长度不对时发生了什么
我在第一次实现r>0分支时，写成了：
0^q + 1^(b-r) + 0 + 1^r + 0^a忘记减去末尾的0数量。结果总长度变成a+q+1，比n多了q+1个字符。当时调试了半天，最后逐段打印每段的长度才发现问题。
所以强烈建议在你的代码里加一个断言：
assert len(ans) == n如果构造串长度不等于n，说明公式用错了。在正式提交时可以去掉，但调试阶段能救你一命。
5.4 数据范围再小也要用long long
n看着不大，但k可能接近1e10，如果你在C++里用int存k，读入就会爆掉。更隐蔽的是a * b在判断时也可能溢出，一定要写1LL * a * b或者直接全部用long long。Python没有这个问题，但C++选手要格外小心。
5.5 k特别大时，b应该选多少
当k很接近maxK时，比如n=1000, k=250000，最优的b一定在500附近。枚举依然能处理，因为循环从1到1000最多跑1000次。
如果你想知道一个手动选b的快速方法：让a和b尽量接近sqrt(k)附近，同时满足a+b=n。比如n=1000, k=250000，取a=b=500最合适。但为了代码的通用性和简洁性，暴力枚举是性价比最高的方案。
6. 从这道easy题延伸出去的构造题套路
6.1 把任意目标值拆成“贡献序列”
“构造一个对象，使其某个统计量恰好等于k”是算法题里非常常见的一类。解决它们的通用步骤是：
- 找出这个统计量的累加公式，最好是整理成若干个整数相加的形式。
- 把目标值
k拆分到这若干个整数上，通常用整除、取余、二进制分解等手法。 - 设计一个物理结构（字符串、数组、图等），让这些整数变成真实存在的贡献项。
这道题里，统计量01子序列数量恰好等于每个1前面0数量的累加，于是问题退化为“构造非递减整数序列使其和为k”。如果题目改成“10子序列”，思路完全对称；如果改成“010子序列”，就需要用组合数展开，但方法论是一致的。
6.2 这一类题目的常见变体
我自己遇到过的变体至少有三种：
第一种，目标值变成了“01子序列数量等于k且长度最短”。这种题不需要固定n，你可以无限加0或1。处理方式是用贪心：不断追加1直到前缀0的数量不够就直接追加0累加前缀，本质上还是累加器思路。
第二种，目标值变成了“两种子序列的数量差恰好为k”。这种题会把01子序列和10子序列都算出来，然后利用对称性构造。比如先构造一个答案，再通过翻转部分字符调整差值。
第三种，目标值的限制变成了“不能被表示成某个形式”。这通常更偏数学构造，需要用到二进制拆分甚至数论知识。
6.3 一个可以继续刷的练习思路
做完HJ117之后，你可以尝试自己改造题目：把“01子序列”改成“010子序列”，同样给定n和k，尝试构造。你会发现统计公式从一次累加变成了二次前缀和，需要维护两个前缀变量，代码复杂度立刻上升，但底层思路一模一样。
先把easy的累加器模型吃透，再挑战多层统计量。这是构造题能力的正道。
这类构造题做多了以后，我最大的感受是：擅长的人往往不是手速快，而是能快速把题目里的“恰好等于k”翻译成一个数学表达式，然后找一个最简单的结构去实现这个表达式。HJ117恰好是个极好的训练样本，希望你也能从这道题里找到这种“翻译”的快感。
