usaco-3.2.2 二进制数01串

形式化题目

给定正整数 $N, L, I$ ：在由所有长度为 $N$ 且字符 1 的出现次数不超过 $L$ 的二进制 01 串按字典序（数值升序）构成的序列中，求第 $I$ 个（从 $1$ 开始计数）二进制 01 串。

正解

思路

对于长度固定的二进制串，字典序的大小完全由从高到低的位权决定：高位填 0 的串严格排在高位填 1 的串之前。因此，我们可以从最高位到最低位逐位确定该位置应当填 0 还是 1。

1. 组合计数状态定义

定义 $f(i, j)$ 表示：长度为 $i$ 且含 1 的个数不超过 $j$ 的二进制串总数。

考虑最高位放 0 还是放 1：

若最高位填 0：剩余的 $i-1$ 位至多还可以包含 $j$ 个 1，方案数为 $f(i-1, j)$ ；
若最高位填 1：用掉了一个 1 的配额，剩余 $i-1$ 位至多还可以包含 $j-1$ 个 1，方案数为 $f(i-1, j-1)$ 。

因此得到状态转移方程：

f(i, j) = f(i-1, j) + f(i-1, j-1)

边界条件：

当剩余长度 $i = 0$ 时，空串是一种合法方案： $f(0, j) = 1$ ；
当剩余配额 $j = 0$ 时，剩余位置只能全部填 0： $f(i, 0) = 1$ 。

2. 逐位试填决策

设当前正在决策从高到低的第 $i$ 个位置（剩余未决定的位数为 $i$ ），剩余允许的 1 的最大数量为 $rem$ ：

计算若当前位填 0，后续子树中包含的合法串数量 $C = f(i-1, rem)$ 。
比较目标排名 $I$ 与 $C$ ：
- 若 $I \le C$ ：说明第 $I$ 个数必定落在当前位填 0 的这组串中。当前位填 0， $rem$ 保持不变；
- 若 $I > C$ ：说明第 $I$ 个数已经超过了当前位填 0 的全部方案，必定落在当前位填 1 的组中。当前位填 1，同时跳过填 0 的所有方案（令 $I \leftarrow I - C$ ），并消耗一次配额（令 $rem \leftarrow rem - 1$ ）。

重复上述过程 $N$ 轮，即可自高向低逐位拼出完整的二进制答案串。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-10-04 13:13

import sys
from functools import cache


@cache
def count_valid(length: int, ones: int) -> int:
    """计算长度为 length 且含 1 个数不超过 ones 的二进制串总数。"""
    if length == 0 or ones == 0:
        return 1
    # 最高位放 0 则剩余有 count_valid(length - 1, ones) 个；放 1 则有 count_valid(length - 1, ones - 1) 个
    return count_valid(length - 1, ones) + count_valid(length - 1, ones - 1)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, l, rank = next(data), next(data), next(data)

    bits: list[str] = []
    rem_ones = l
    for i in range(n, 0, -1):
        # 当前最高位填 0 时，后续满足条件的串总数
        zeros_branch = count_valid(i - 1, rem_ones)
        if rank <= zeros_branch:
            bits.append("0")
        else:
            bits.append("1")
            rank -= zeros_branch
            rem_ones -= 1

    print("".join(bits))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:46
 * update_at: 2026-10-06 09:46
 */
// roj 2047 usaco-3.2.2 二进制数01串
// 数位计数 + 字典序逐位试填：先算出当前位填 0 的分支规模，再决定这一位填 0 还是填 1。

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 40;

ll f[MAXN][MAXN]; // f[i][j] 表示长度为 i 且其中 1 的个数不超过 j 的二进制串总数

int main() {
    ll n, l, rank_id;
    cin >> n >> l >> rank_id;

    // 边界：空串算一种方案；没有 1 的配额时剩余位只能全填 0
    for (int j = 0; j <= l; j++) {
        f[0][j] = 1;
    }
    for (int i = 0; i <= n; i++) {
        f[i][0] = 1;
    }

    // f[i][j] = 最高位填 0 的方案数 + 最高位填 1 的方案数
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= l; j++) {
            f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
        }
    }

    // 自高向低逐位试填：branch_zero 是当前位填 0 时后续子树的合法串数量
    ll left_ones = l;
    for (int i = n; i >= 1; i--) {
        ll branch_zero = f[i - 1][left_ones];
        if (rank_id <= branch_zero) {
            cout << '0';
        } else {
            cout << '1';
            rank_id -= branch_zero;
            left_ones--;
        }
    }
    cout << '\n';

    return 0;
}

复杂度

时间复杂度：状态数至多为 $(N+1) \times (L+1)$ ，记忆化搜索与递推计算耗时为 $O(N \times L)$ ；逐位试填共进行 $N$ 次分支判断，耗时为 $O(N)$ 。在 $N \le 31$ 时总计算步数在千次以内，耗时小于 $0.02\text{s}$ 。
空间复杂度：记忆化缓存表与递归栈深度均为 $O(N \times L)$ ，整体额外空间远小于题目限制。

总结

这是一道经典的“数位计数 + 字典序逐位试填”模型。核心观察在于将字典序排名问题转化为树形搜索树上的分支定位：高位为 0 的分支在字典序上整体排在高位为 1 的分支之前；只需先计算出左分支的规模，便可通过一次大小比较决定走向左分支还是扣除左分支大小后走向右分支。

图示解析

以样例 $N=5, L=3, I=19$ 为例，试填过程对应的搜索二叉树路径决策如下：

graph TD
    Root["根: 待定 5 位, L=3, I=19"] -->|最高位填 0: C=f(4,3)=15| Left1["左子树规模 15 < 19"]
    Root -->|最高位填 1| Node1["选择填 1! (I 变为 19-15=4, 剩余配额 L=2)"]

    Node1 -->|第 2 位填 0: C=f(3,2)=7| Node2["选择填 0! (4 <= 7, I=4, 剩余配额 L=2)"]
    Node1 -.->|第 2 位填 1| Right2["右子树 (不选)"]

    Node2 -->|第 3 位填 0: C=f(2,2)=4| Node3["选择填 0! (4 <= 4, I=4, 剩余配额 L=2)"]
    Node2 -.->|第 3 位填 1| Right3["右子树 (不选)"]

    Node3 -->|第 4 位填 0: C=f(1,2)=2| Left4["左子树规模 2 < 4"]
    Node3 -->|第 4 位填 1| Node4["选择填 1! (I 变为 4-2=2, 剩余配额 L=1)"]

    Node4 -->|第 5 位填 0: C=f(0,1)=1| Left5["左子树规模 1 < 2"]
    Node4 -->|第 5 位填 1| Node5["选择填 1! (I 变为 2-1=1, 剩余配额 L=0)"]

    style Node1 fill:#d4edda,stroke:#28a745
    style Node2 fill:#d4edda,stroke:#28a745
    style Node3 fill:#d4edda,stroke:#28a745
    style Node4 fill:#d4edda,stroke:#28a745
    style Node5 fill:#d4edda,stroke:#28a745

由此依次确定的各位字符为 1、0、0、1、1，得到最终二进制串 10011。