联系 - 题目列表

形式化题目

给定一个长度为 $L$ 的 01 序列 $S$ 以及整数参数 $A, B, N$ （满足 $1 \le A \le B \le 12$ ， $1 \le N < 50$ ）。

定义合法子串为长度 $k \in [A, B]$ 的连续子串。统计所有至少出现一次的合法子串在 $S$ 中的出现频次（重叠子串均计入）。

选出出现频次最高的前 $N$ 种频次（若存在的频次种类不足 $N$ ，则选出所有存在的频次），按频次降序排列。对于每个频次：

先输出该频次数值；
再输出拥有该频次的所有子串，子串先按长度升序排序，长度相同时按二进制字典序升序排序；每行最多输出 6 个子串，空格分隔。

正解：滑动窗口统计与多级排序

思路

本题参数规模具有显著特征：子串长度上限 $B \le 12$ 非常小，但 01 序列长度 $L$ 可达 $200,000$ 。

状态空间与规模分析：
- 长度在 $[A, B]$ 之间的二进制模式串总数上限为 $\sum_{k=A}^B 2^k \le 2^1 + 2^2 + \dots + 2^{12} = 8190$ 种。
- 这意味着无论原序列多长，互不相同的模式串最多只有 8190 种，完全可以直接用哈希表/字典统计频次。
滑动窗口计数：
- 外层遍历所有待统计的目标长度 $len \in [A, B]$ ；
- 内层遍历起始位置 $i \in [0, L - len]$ ，截取子串 $S[i : i+len]$ 并在计数器中累加频次。
- 总截取与哈希插入操作次数约为 $(B - A + 1) \cdot L \le 12 \times 200,000 = 2.4 \times 10^6$ ，在常数极小的字符串切片操作下可瞬时完成。
分桶与排序规则：
- 将所有出现过的模式串按出现频次归类到一个以频次为键的桶中。
- 频次按从大到小降序排序，取前 $N$ 个频次。
- 相同频次内的模式串按 (len(s), s) 排序：由于 Python 字符串比较按字符 ASCII 字典序进行，而 '0' < '1'，因此直接比较字符串天然等价于二进制字典序。
格式化输出：
- 遍历前 $N$ 个频次及其对应的排序后列表；
- 先单独输出频次数值；
- 模式串列表按步长 6 切块并用空格连接，每行最多输出 6 个。

图示解析

以样例 A=2, B=4, N=10，输入片段 01010010... 为例：

flowchart TD
    A["输入 01 序列 (长达 200,000)"] --> B["滑动窗口切片 (长度 len ∈ [2, 4])"]
    B --> C["哈希表计数 Counter (至多 8190 种模式串)"]
    C --> D["按频次分桶 (频次 freq 降序)"]
    D --> E["组内多关键字排序: (长度升序, 二进制字典序升序)"]
    E --> F["格式化输出: 单独行频次 + 每行最多 6 个模式串"]

频次	包含的模式串（排序后）	行格式化效果
23	`00`	`23` `00`
15	`01`, `10`	`15` `01 10`
12	`100`	`12` `100`
11	`11`, `000`, `001`	`11` `11 000 001`
5	`011`, `110`, `1000`	`5` `011 110 1000`

代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#!/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-03-31 10:00
# update_at: 2026-03-31 10:00

import sys
from collections import Counter, defaultdict


def count_patterns(seq: str, min_len: int, max_len: int) -> Counter[str]:
    """统计字符串中所有长度在 [min_len, max_len] 之间的连续子串频次。"""
    n = len(seq)
    counts: Counter[str] = Counter()
    for length in range(min_len, max_len + 1):
        if length > n:
            break
        for i in range(n - length + 1):
            counts[seq[i : i + length]] += 1
    return counts


def group_and_sort_patterns(counts: Counter[str]) -> list[tuple[int, list[str]]]:
    """将子串按出现频次降序分桶，同一频次内按长度升序、二进制字典序升序排序。"""
    freq_map: defaultdict[int, list[str]] = defaultdict(list)
    for pattern, freq in counts.items():
        freq_map[freq].append(pattern)

    # 频次从大到小排序；同频次内：长度递增、二进制字典序（'0' < '1'）递增
    return [
        (freq, sorted(patterns, key=lambda s: (len(s), s)))
        for freq, patterns in sorted(freq_map.items(), key=lambda item: -item[0])
    ]


def format_frequency_groups(groups: list[tuple[int, list[str]]], top_n: int) -> list[str]:
    """将前 top_n 个频次组按每行最多 6 个模式串的规则格式化为输出行。"""
    lines: list[str] = []
    for freq, patterns in groups[:top_n]:
        lines.append(str(freq))
        for i in range(0, len(patterns), 6):
            lines.append(" ".join(patterns[i : i + 6]))
    return lines


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())

    a = int(next(data))
    b = int(next(data))
    n = int(next(data))
    seq = "".join(token.decode() for token in data)

    counts = count_patterns(seq, a, b)
    groups = group_and_sort_patterns(counts)
    lines = format_frequency_groups(groups, n)

    print("\n".join(lines))


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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116/**
 * 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:41
 * update_at: 2026-10-06 09:41
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAX_SEQ = 200005;          // 输入 01 序列的最大长度
const int MAX_B = 12;                // 子串长度上限 B <= 12
const int VALUE_SPACE = 1 << MAX_B;  // 单个长度下模式串的数值上界 2^12

char seq[MAX_SEQ];                    // 输入的 01 序列
int cnt[MAX_B + 1][VALUE_SPACE];      // cnt[len][value]：定长 len 的模式串出现次数

struct Pattern {
    int freq;   // 该模式串的出现次数
    int len;    // 模式串长度
    int value;  // 模式串二进制对应的数值，定长时数值顺序即二进制字典序
};

Pattern pats[1 << (MAX_B + 1)];  // 不同模式串最多 sum(2^len) < 8192 个

// 排序规则：频次降序，其次长度升序，同长度按二进制字典序（数值）升序
bool cmp(const Pattern &a, const Pattern &b) {
    if (a.freq != b.freq) return a.freq > b.freq;
    if (a.len != b.len) return a.len < b.len;
    return a.value < b.value;
}

// 按定长输出模式串的二进制形式，高位不足补 0
void print_pattern(int value, int len) {
    char buf[MAX_B + 1];
    for (int i = 0; i < len; i++) {
        int bit = (value >> (len - 1 - i)) & 1;
        buf[i] = bit ? '1' : '0';
    }
    buf[len] = '\0';
    printf("%s", buf);
}

int main() {
    int A, B, N;
    if (scanf("%d %d %d", &A, &B, &N) != 3) return 0;

    // 读入序列：可能分成多行，直接拼接所有 0/1 字符
    int seq_len = 0;
    char token[1024];
    while (scanf("%1023s", token) == 1) {
        for (int i = 0; token[i] != '\0'; i++) {
            seq[seq_len] = token[i];
            seq_len++;
        }
    }

    // 对每个目标长度做滑动窗口，累计各模式串出现次数
    for (int len = A; len <= B; len++) {
        if (len > seq_len) break;
        int mask = (1 << len) - 1;
        int value = 0;
        for (int i = 0; i < len; i++) {
            value = (value << 1) | (seq[i] - '0');
        }
        cnt[len][value]++;
        for (int i = len; i < seq_len; i++) {
            value = ((value << 1) | (seq[i] - '0')) & mask;
            cnt[len][value]++;
        }
    }

    // 收集所有出现过的模式串
    int m = 0;
    for (int len = A; len <= B; len++) {
        if (len > seq_len) break;
        int total = 1 << len;
        for (int value = 0; value < total; value++) {
            if (cnt[len][value] > 0) {
                pats[m].freq = cnt[len][value];
                pats[m].len = len;
                pats[m].value = value;
                m++;
            }
        }
    }

    sort(pats, pats + m, cmp);

    // 按频次分组输出，最多输出前 N 种频次，每组内每行最多 6 个模式串
    int printed_freq = 0;
    int i = 0;
    while (i < m && printed_freq < N) {
        int freq = pats[i].freq;
        printf("%d\n", freq);
        int idx = 0;
        int j = i;
        while (j < m && pats[j].freq == freq) {
            if (idx > 0) {
                if (idx % 6 == 0) printf("\n");
                else printf(" ");
            }
            print_pattern(pats[j].value, pats[j].len);
            idx++;
            j++;
        }
        printf("\n");
        printed_freq++;
        i = j;
    }

    return 0;
}

复杂度

时间复杂度： $\mathcal{O}((B - A + 1) \cdot L + M \log M)$ ，其中 $L \le 200,000$ ， $B \le 12$ ， $M \le 8190$ 为不同模式串的种类上限。字符串滑动窗口切片和哈希计数开销约为 $12 \times 200,000 = 2.4 \times 10^6$ 次操作，耗时约 $0.05\text{s}$ ，排序与输出开销微秒级，远低于时限 1.0s。
空间复杂度： $\mathcal{O}(L + 2^B)$ 。存储输入序列需要约 $200\text{KB}$ ，哈希表与分桶列表最多存储 $8190$ 个小字符串，内存占用 $\le 1\text{MB}$ ，远低于 128MB 限制。

总结

核心突破口在于注意到模式串的最大长度 $B \le 12$ 极小，二进制模式串的总数被限制在 8190 之内。
借助滑动窗口与哈希表直接统计连续子串频次，再结合 Python 的多关键字排序 (len(s), s) 和步长切片 patterns[i:i+6]，能够简洁而严谨地满足复杂的排版要求。

联系

目录

形式化题目

正解：滑动窗口统计与多级排序

思路

图示解析

代码

复杂度

总结