学习目标
- 用 FIFO 队列按数值顺序生成二进制字符串。
- 对每个已输出字符串依次追加
0与1，维持层序。 - 根据输出长度分析时间、空间与判题器输出上限。
前置知识与环境
建议先学习第 2 章栈与队列。使用 ISO C++17；开始前可在本目录运行 make doctor。
任务
将字符串 "1" 入队。每次取出队头作为下一个答案，再把它后面追加 0 和 1 得到的两个字符串按此顺序入队。这样依次得到十进制数 1..n 的无前导零二进制表示。
输入格式
一行正整数 n。
输出格式
输出 1..n 的二进制表示，各表示以空格分隔，末尾换行。例如 n=5 输出 1 10 11 100 101；不输出十进制数 0。
数据范围与限制
- 输入规模不超过
200000，除题面另有说明外整数使用 64 位有符号范围。 1 <= n <= 200000；输出总字符数为O(n log n)，算法时间和输出规模同阶，辅助队列空间为O(n log n)。- 标准输出只保留题目要求的结果；调试信息写入标准错误。
- 目标算法时间和输出规模同阶（
O(n log n)），辅助队列空间为O(n log n)。
边界与验收重点
n=1、跨过二进制位数变化的n=2,4,8。- 先入队
当前串+0，再入队当前串+1，不能反转。 n=200000时输出超过 1 MiB；判题输出上限为 8 MiB，覆盖合法最大答案。
如何验证
powershell
make doctor
make run
make score未安装 Make 时，在仓库根目录运行：
powershell
pnpm lab:validate -- labs/chapter-02/exercise/E-02-16-binary-number-queue
pnpm lab:run -- labs/chapter-02/exercise/E-02-16-binary-number-queue
pnpm lab:score -- labs/chapter-02/exercise/E-02-16-binary-number-queue思考与复盘
- 若先入队
当前串+1，前四个答案会变成什么？ - 为什么不能只按生成的字符串数
n估算输出字节数？
思考题参考
- 会得到
1 11 10 111，不再对应数值顺序。 - 每个答案有
Θ(log n)位，还包含分隔符，总输出是Θ(n log n)字节。
题解
点击查看题解
思路与不变量
队列按层保存尚未输出的二进制字符串。队头字符串对应当前最小的未输出整数；取出 s 后，按 s+"0"、s+"1" 的顺序入队，下一层就会继续按数值顺序产生。
算法步骤
- 将字符串
"1"入队； - 重复
n次：取出队头并输出，再把它加上0和1后依次入队； - 用空格分隔输出，最后换行。
正确性说明
对任意已输出的无前导零二进制串 s，s0 和 s1 分别是该层的两个连续后继。队列的先进先出顺序先处理较短层，再按父串顺序处理同层节点，因此第 i 次取出的字符串正好是十进制 i+1 的二进制表示。
复杂度分析
- 时间复杂度：
O(n log n)，总处理量与输出字符数同阶； - 额外空间：
O(n log n)，队列中保存的字符串总长度与输出规模同阶。
边界注意
- 不输出十进制 0，也不产生前导零；
- 必须先入队
s0再入队s1，否则顺序会错； - 需要按输出规模估算缓冲和判题器上限，而不能只看字符串个数。