[蓝桥杯 2023 省 B] 填空问题

GitHub跳转原题关系图返回列表

日期统计用贪心找最靠左落点判断子序列，01 串的熵用单调性二分定位峰值附近的两个候选，两问都只需常数级计算。

OJ: luogu

题目 ID: P9239

难度:普及-

标签:枚举贪心二分数学思维

创建: 2026-10-03 11:29

更新: 2026-10-03 11:33

形式化题目

输入一个大写字母，表示要回答下面哪一问。

试题 A（日期统计）：给定一个长度为 $100$ 的序列 $a_1,a_2,\dots,a_{100}$ ，每个 $a_i\in\{0,1,\dots,9\}$ 。统计有多少个字符串 $d$ 满足：

$d$ 形如 yyyymmdd，且表示的日期属于 2023 年；
$d$ 的 $8$ 位数字按顺序作为 $a$ 的子序列出现（即存在下标 $i_1<i_2<\dots<i_8$ ，使得 $a_{i_k}$ 等于 $d$ 的第 $k$ 位数字）。

试题 B（01 串的熵）：设长度 $n=23333333$ 的 01 串中 $0$ 出现 $c_0$ 次、 $1$ 出现 $c_1=n-c_0$ 次，占比分别为 $p_0=c_0/n$ 、 $p_1=c_1/n$ 。信息熵定义为

H(c_0)=-\sum_{i=1}^{n}p(x_i)\log_2\bigl(p(x_i)\bigr) =-c_0p_0\log_2 p_0-c_1p_1\log_2 p_1 .

已知 $H$ 的小数形式为 $11625907.5798$ ，且 $0$ 出现次数比 $1$ 少（即 $c_0<n/2$ ），求 $c_0$ 。

暴力解法

思路

两问的规模都不大，可以先把“题目字面要求”直接翻译成程序，作为正确性基线。

试题 A：枚举 2023 年的每一天，得到 365 个日期串。对每个日期串，把 $8$ 位数字的落点当作一串决策，递归枚举所有可能的下标组合：第 $k$ 位在当前起点之后任选一个等于该位数字的位置，递归匹配下一位。只要存在一组下标走到底，这个日期就合法。
试题 B： $c_0$ 只有 $0\sim n/2$ 种可能，逐个代入熵公式算出 $H(c_0)$ ，记录与目标值差距最小的 $c_0$ 。

暴力不利用任何结构，A 题枚举组合、B 题线性扫描，正确性一眼可见。

代码

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/**
 * 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-03 11:29
 * update_at: 2026-10-03 11:29
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// A 题枚举每个日期串的所有可能匹配位置组合；B 题扫描全部 c0 取值取最近的一个。
// 两道小问的规模都是固定的，暴力只用来独立验证正解的贪心/单调性结论。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

// 试题 A 给定的 100 个数字。
int a[MAXN];

// 当前正在匹配的 8 位日期串。
string target_date;

// 递归的层数：正在决定日期串第几位的落点。
// 返回是否找到一组下标，使日期串成为 a[] 的子序列。
// brute 不使用“最靠左落点最优”的贪心结论，而是把所有下标组合都试一遍。
bool dfs_A(int digit, int start) {
    if (digit == 8) {
        return true;
    }
    int want = target_date[digit] - '0';
    for (int i = start; i < 100; i++) {
        if (a[i] == want) {
            if (dfs_A(digit + 1, i + 1)) {
                return true;
            }
        }
    }
    return false;
}

// 每个月的天数，2023 不是闰年。
int month_day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 试题 A：枚举 2023 年的每一天，用 dfs_A 判断这一天能否被拼出来。
int solve_A() {
    int ans = 0;
    for (int m = 1; m <= 12; m++) {
        for (int d = 1; d <= month_day[m]; d++) {
            char buf[16];
            snprintf(buf, sizeof(buf), "2023%02d%02d", m, d);
            target_date = buf;
            if (dfs_A(0, 0)) {
                ans++;
            }
        }
    }
    return ans;
}

// 试题 B：暴力枚举 0 的个数 c0，直接用熵公式算出 H(c0)，
// 记录与题目给定熵值差距最小的那个 c0。
// 不利用 H(c0) 的单调性，也不提前退出，遍历全部 n/2 + 1 个取值。
int solve_B() {
    const int n = 23333333;
    const double target = 11625907.5798;
    double best_diff = 1e18;
    int best_c0 = -1;
    for (int c0 = 0; c0 <= n / 2; c0++) {
        int c1 = n - c0;
        double p0 = (double)c0 / n;
        double p1 = (double)c1 / n;
        double h = 0.0;
        // c0 或 c1 为 0 时该项占比为 0，熵的贡献记 0，不对 log2(0) 求值。
        if (c0 > 0) {
            h -= (double)c0 * p0 * log2(p0);
        }
        if (c1 > 0) {
            h -= (double)c1 * p1 * log2(p1);
        }
        double diff = fabs(h - target);
        if (diff < best_diff) {
            best_diff = diff;
            best_c0 = c0;
        }
    }
    return best_c0;
}

int main() {
    int given[100] = {
        5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7,
        5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,
        2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3,
        8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6,
        1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3,
    };
    for (int i = 0; i < 100; i++) {
        a[i] = given[i];
    }

    char type;
    if (!(cin >> type)) {
        return 0;
    }
    if (type == 'A') {
        printf("%d\n", solve_A());
    } else if (type == 'B') {
        printf("%d\n", solve_B());
    }
    return 0;
}

复杂度

试题 A 对每个日期做一次 $O(100^8)$ 上限的搜索（实际因起点递增远小于该上界），试题 B 线性扫描 $O(n)$ 次浮点运算。

瓶颈

暴力能算出答案，但没有回答“为什么是这两个数”：

A 题枚举下标组合是指数级的，数据稍大就不可行，而且它没有解释子序列匹配的判定为什么可以更快。
B 题虽然能在 $O(n)$ 内算完，但要遍历 $1.1\times10^7$ 个取值，且完全没有利用 $H(c_0)$ 的单调结构——这正是正解要回答的问题。

正解

思路

试题 A：贪心取最靠左落点。

判断一个日期串能否作为子序列出现，有一个标准结论：让每一位尽量取靠左的位置，不会让后面的匹配变难。设 pos[k] 表示贪心匹配完前 $k$ 位后，第 $k$ 位落在 $a$ 中的下标。那么

pos[k]=\min\{\,i>pos[k-1]\mid a_i=d_k\,\},

其中 $pos[0]=-1$ （下标从 $0$ 开始）。只要 $pos[1]\dots pos[8]$ 都存在，这个日期就合法。

正确性来自交换论证：若存在任意一组可行下标 $i_1<\dots<i_8$ ，则 $pos[1]\leqslant i_1$ ；归纳地， $pos[k]\leqslant i_k$ 恒成立，所以贪心在第 $k$ 位用的下标永远不比可行解更靠右，贪心失败时也一定不存在可行解。因此这个判定是充要的。

有了判定后，枚举日期本身而不是枚举子序列：遍历 2023 年的 365 天（2023 不是闰年，2 月 28 天），每个日期天然只被检查一次，所以相同日期不可能重复计数，无需额外去重。每一天的判定只需扫一遍长度为 $100$ 的数组。

试题 B：利用 $c_0$ 的单调性二分。

把熵写成只含 $c_0$ 的函数：

H(c_0)=-c_0p_0\log_2 p_0-c_1p_1\log_2 p_1 .

由最大熵原理， $H$ 在 $c_0=c_1=n/2$ 处取最大值，在 $[0,n/2]$ 上随 $c_0$ 严格单调递增。原因是一个简单的对称性论证：把 0 和 1 互换， $H$ 不变，所以 $H(c_0)=H(n-c_0)$ ；函数 $t\mapsto -t\log_2 t$ 在 $[0,n/2]$ 上递增，两部分贡献合起来使 $H$ 在 $[0,n/2]$ 上单调不减，且在该区间内严格递增。

于是“与目标值最近”的 $c_0$ 一定紧贴在 $H$ 穿过目标值的位置两侧。做法是先二分出最大的满足 $H(c_0)\leqslant 11625907.5798$ 的下标（记为 below），再比较 below 与 below + 1 中哪个的熵更接近目标值，返回更近的那个。

这一步是必要的：题面给的是四位小数，不能指望某个整数 $c_0$ 的熵恰好等于它。下表是目标值附近几个 $c_0$ 的真实熵，可以看到最小差距出现在 $c_0$ 略大于穿越点的一侧：

$c_0$	$H(c_0)$	与 $11625907.5798$ 的差
$11027420$	$11625907.4523$	$0.1275$
$11027421$	$11625907.5798$	$0.0000145$
$11027422$	$11625907.7073$	$0.1275$

因此正确答案是 $11027421$ ，它的熵比目标值略大。这提醒我们：如果只取“第一个 $H(c_0)\leqslant$ 目标值”的下标，会得到 $11027420$ ，差了一步。

代码

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142/**
 * 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-03 11:29
 * update_at: 2026-10-03 11:29
 */
// main.cpp：P9239 填空问题正解。
// 两道小问的输入都只是题面写死的常量（A 题的 100 个数字、B 题的 n 和熵值），
// 所以这里把“答案是怎么算出来的”完整写出来，而不是直接 printf 两个数字。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

// 试题 A 给定的 100 个数字，每个都在 0..9 之间。
int a[MAXN];

// pos[L] = 贪心匹配日期串前 L 位后，第 L 位落在 a[] 中的最小下标。
// pos[0] 用 -1 表示“还没有匹配任何字符”。
int pos[10];

// 每个月的天数，2023 不是闰年，2 月按 28 天算。
int month_day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int LEN_B = 23333333;              // 试题 B 的 01 串长度 n
const double ENTROPY_B = 11625907.5798;  // 试题 B 给定的信息熵

// 判断 8 位日期串 d 能否作为 a[] 的子序列出现。
// 思路：第 L 位取在 pos[L-1] 之后最靠左的位置，不会让后面的匹配变难。
bool can_form(const string & d) {
    for (int L = 0; L <= 8; L++) {
        pos[L] = 1000000;
    }
    pos[0] = -1;
    for (int L = 1; L <= 8; L++) {
        int want = d[L - 1] - '0';
        // 从上一个落点的右边开始，找第一个等于 want 的数字。
        for (int i = pos[L - 1] + 1; i < 100; i++) {
            if (a[i] == want) {
                pos[L] = i;
                break;
            }
        }
        if (pos[L] == 1000000) {
            return false;
        }
    }
    return true;
}

// 试题 A：枚举 2023 年的 365 个日期，逐个判断是不是 a[] 的子序列。
// 直接枚举日期本身，同一个日期天然只被统计一次。
int solve_a() {
    int ans = 0;
    for (int m = 1; m <= 12; m++) {
        for (int d = 1; d <= month_day[m]; d++) {
            char buf[16];
            snprintf(buf, sizeof(buf), "2023%02d%02d", m, d);
            string date = buf;
            if (can_form(date)) {
                ans++;
            }
        }
    }
    return ans;
}

// 计算 0 出现 c0 次、1 出现 c1 = n - c0 次时的信息熵：
// H = -c0 * p0 * log2(p0) - c1 * p1 * log2(p1)，其中 p0 = c0/n，p1 = c1/n。
// 某一类出现 0 次时规定它贡献 0（不取 log2(0)）。
double entropy_of(int c0, int n) {
    int c1 = n - c0;
    double p0 = (double)c0 / n;
    double p1 = (double)c1 / n;
    double h = 0.0;
    if (c0 > 0) {
        h -= (double)c0 * p0 * log2(p0);
    }
    if (c1 > 0) {
        h -= (double)c1 * p1 * log2(p1);
    }
    return h;
}

// 试题 B：H(c0) 关于 c0 在 [0, n/2] 上单调递增（峰值在 c0 = n/2），
// 所以“离目标熵最近”的 c0 一定在 H 穿过目标值的那个位置附近。
// 先二分出最大的、满足 H(c0) <= 目标值的 c0，再和它的右邻居比一比距离即可。
int solve_b() {
    int n = LEN_B;
    double target = ENTROPY_B;

    // 二分：H(0) = 0 <= target，且 H(n/2) 远大于 target，区间内一定有解。
    int left = 0, right = n / 2;
    int below = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (entropy_of(mid, n) <= target) {
            below = mid;   // mid 还在目标值下方，可能还能更大
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    int best = below;
    int next = below + 1;
    if (next <= n / 2) {
        double diff_best = fabs(entropy_of(best, n) - target);
        double diff_next = fabs(entropy_of(next, n) - target);
        if (diff_next < diff_best) {
            best = next;
        }
    }
    return best;
}

int main() {
    char type;
    if (!(cin >> type)) {
        return 0;
    }

    // 题面写死的 100 个数字。
    int given[100] = {
        5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7,
        5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,
        2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3,
        8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6,
        1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3,
    };
    for (int i = 0; i < 100; i++) {
        a[i] = given[i];
    }

    if (type == 'A') {
        printf("%d\n", solve_a());
    } else if (type == 'B') {
        printf("%d\n", solve_b());
    }
    return 0;
}

复杂度

试题 A：日期数 $365$ 乘以每次判定 $O(100)$ ，即 $O(365\cdot 100)$ ，是常数级计算。试题 B：每次求熵是 $O(1)$ ，二分 $O(\log n)$ ，总复杂度 $O(\log n)$ 。

总结

这道题的两问看似无关，但都在考同一件事：先用结构把搜索空间压小，再在压缩后的空间里枚举或二分。

子序列匹配的贪心性质把“枚举所有下标组合”压成了“每层只取最靠左的落点”，正确性用交换论证保证。
熵函数的对称性 $H(c_0)=H(n-c_0)$ 把搜索区间砍半，单调性又把线性扫描压成了二分。

两个结论都值得记住：子序列存在性判定用贪心取最左是最常用的子序列技巧；先找穿越点、再比较相邻候选是处理“给定浮点目标求最近整数”这类填空问题的通用写法，因为浮点误差使“恰好等于”几乎不可能发生。

P9239 [蓝桥杯 2023 省 B] 填空问题

题目描述

试题 A：日期统计

【问题描述】

小蓝现在有一个长度为 $100$ 的数组，数组中的每个元素的值都在 $0$ 到 $9$ 的范围之内。数组中的元素从左至右如下所示:

text

15 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3

现在他想要从这个数组中寻找一些满足以下条件的子序列：

子序列的长度为 $8$ ;
这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且要求这个日期是 2023 年中的某一天的日期，例如 $20230902$ ， $20231223$ 。yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。

请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。对于相同的日期你只需要统计一次即可。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 B：01 串的熵

【问题描述】

对于一个长度为 $n$ 的 01 串 $S=x_{1} x_{2} x_{3} \ldots x_{n}$ ，香农信息熵的定义为 $H(S)=-\sum_{i=1}^{n} p\left(x_{i}\right) \log_{2}\left(p\left(x_{i}\right)\right)$ ，其中 $p(0),p(1)$ 表示在这个 01 串中 0 和 1 出现的占比。

比如，对于 $S=100$ 来说，信息熵 $H(S)=-\frac{1}{3}\log _{2}\left(\frac{1}{3}\right)-\frac{2}{3} \log _{2}\left(\frac{2}{3}\right)-\frac{2}{3} \log _{2}\left(\frac{2}{3}\right)=1.3083$ 。对于一个长度为 $23333333$ 的 01 串，如果其信息熵为 $11625907.5798$ ，且 0 出现次数比 1 少，那么这个 01 串中 0 出现了多少次？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输入格式

输入格式输入一个大写字母，表示第几个问题。

输出格式

根据所输入的问题编号，输出对应问题的答案。

说明/提示

答题模板，可供参考。

cpp

1
2
3
4
5
6
7
8
9
10
11
12#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of task A", // 双引号中替换为 A 题的答案
        "The answer of task B", // 双引号中替换为 B 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}

[蓝桥杯 2023 省 B] 填空问题

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

代码

复杂度

总结