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

A

问题

给定一个长度为 $100$ 的数组，数组元素为数字 $0$ 到 $9$。数组内容如下：

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

需要找到所有长度为 $8$ 的子序列，这些子序列可以组成一个 yyyymmdd 格式的日期，其中 yyyy 表示年份（只能为 $2023$），mm 表示月份（$01$ 至 $12$），dd 表示天数（$2023$ 年不是闰年则 $2$ 月有 $28$ 天）。子序列元素必须保持数组中的下标顺序（但不一定连续），且相同日期只统计一次。

思路

先将年份固定为 $2023$：子序列的前四个数字必须依次为 $2$、$0$、$2$、$3$，且下标递增。因此，先找到所有满足 $a_i = 2$、$a_{i + 1} = 0$、$a_{i + 2} = 2$、$a_{i + 3} = 3$ 且 $i < i + 1 < i + 2 < i + 3$ 的四元组 $f(i, i + 1, i + 2, i + 3)$。

对于每个年份结束位置 $i + 3$，从 $i + 4$ 开始，寻找后续两个数字作为月份，再寻找两个数字作为日期，要求下标严格递增：$i + 3 < i + 4 < i + 5 < i + 6 < i + 7$，其中：

• $a_{i + 4}$ 和 $a_{i + 5}$ 组成有效的月份（$01$ 至 $12$）。
• $a_{i + 6}$ 和 $a_{i + 7}$ 组成有效的日期（根据月份）：
  • 月份 $01$、$03$、$05$、$07$、$08$、$10$、$12$：日期 $01$ 至 $31$；
  • 月份 $04$、$06$、$09$、$11$：日期 $01$ 至 $30$；
  • 月份 $02$：日期 $01$ 至 $28$。

去重我们可以考虑使用 set<int> s; 记录所有有效的 (mm, dd) 对，避免重复日期（这里不用管 yyyy 是因为 yyyy 只能为 $2023$，为其他日期的在前面的步骤就已经筛掉了）。

对于优化，由于数组长度固定，可以预处理数字位置。年份部分只有特定的结束位置 $i + 3$（请注意 $i + 3$ 表示的是下标，不是数值。只有 $i + 3 = 58$ 或 $59$ 可行，因为其他 $i + 3$ 后位置不足）。然后枚举月份十位（必须是 $0$ 或 $1$）和个位（根据十位确定范围），再枚举日期十位和个位（根据月份确定范围），检查下标顺序。

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int arr[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};
set<pair<int, int>> st;

bool vd(int m, int d)
{
    if (d < 1)
        return 0;
    if (m == 2)
        return d <= 28;
    if (m == 4 || m == 6 || m == 9 || m == 11)
        return d <= 30;
    return d <= 31;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int yei[2] = {58, 59}; // 年份结束的下标
    for (int idx = 0; idx < 2; idx++)
    {
        int i_3 = yei[idx];
        for (int i_4 = i_3 + 1; i_4 < 100; i_4++)
        {
            if (arr[i_4] != 0 && arr[i_4] != 1)
                continue;
            for (int i_5 = i_4 + 1; i_5 < 100; i_5++)
            {
                int m = arr[i_4] * 10 + arr[i_5];
                if (m < 1 || m > 12)
                    continue;
                for (int i_6 = i_5 + 1; i_6 < 100; i_6++)
                {
                    if (arr[i_6] < 0 || arr[i_6] > 3)
                        continue;
                    for (int i_7 = i_6 + 1; i_7 < 100; i_7++)
                    {
                        int d = arr[i_6] * 10 + arr[i_7];
                        if (vd(m, d))
                            st.insert(make_pair(m, d));
                    }
                }
            }
        }
    }
    cout << st.size() << endl;
    return 0;
}

答案

答案为 $235$。

B

问题

题目要求计算一个长度为 $23333333$ 的 $01$ 串中 $0$ 出现的次数，已知信息熵为 $11625907.5798$ 且 $0$ 的个数少于 $1$ 的个数。香农信息熵的公式为：

$$
H(S) = -\sum_{i=1}^{n} p(x_i) \log_2 p(x_i)
$$

其中 $p(0)$ 和 $p(1)$ 分别是 $0$ 和 $1$ 在串中的占比。设 $0$ 的个数为 $i$，则 $1$ 的个数为 $j = 23333333 - i$。信息熵可简化为：

$$
H(S) = -\left[ i \cdot \frac{i}{n} \log_2 \left(\frac{i}{n}\right) + j \cdot \frac{j}{n} \log_2 \left(\frac{j}{n}\right) \right]
$$

其中 $n = 23333333$。由于 $0$ 的个数少于 $1$ 的个数，$i$ 的范围为 $1 \leq i \leq \lfloor \frac{n}{2} \rfloor$。

思路

我们采用两种策略结合的方法：

• 遍历 $i$ 时，一旦找到满足精度要求 $|H - \text{target}| < 0.01$ 的解，立即输出；
• 同时记录全局最小误差的解，确保最终输出的是精度差最小的答案。

步骤

1. 初始化：

   • 总长度 $n = 23333333$；
   • 目标信息熵 $\text{target} = 11625907.5798$；
   • 最小误差初始化为极大值 $\text{min_diff} = \infty$；
   • 最优解 $\text{ans} = 0$。

2. 枚举 $0$ 的个数 $i$：

   • 遍历范围：$i$ 从 1 到 $\lfloor \frac{n}{2} \rfloor$；
   • 计算 1 的个数 $j = n - i$。

3. 计算信息熵：

   • 计算概率：$p0 = \frac{i}{n}$, $p1 = \frac{j}{n}$；
   • 计算熵值：$H = -\left[ i \cdot p0 \cdot \log_2(p0) + j \cdot p1 \cdot \log_2(p1) \right]$。

4. 检查精度：

   • 计算绝对误差 $\text{diff} = |H - \text{target}|$；
   • 若 $\text{diff} < 0.01$，输出 $i$ 并立即终止程序；
   • 同时记录最小误差解：若 $\text{diff} < \text{min_diff}$，更新 $\text{min_diff}$ 和 $\text{ans}$。

5. 输出结果：

   • 若找到精确匹配则已退出；
   • 否则输出全局最小误差解 $\text{ans}$。

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 23333333;
const double T = 11625907.5798;

int main()
{
    double md = 1e18;
    int a = 0;
    for (int i = 1; i <= N / 2; i++)
    {
        int j = N - i;
        double p0 = 1.0 * i / N;
        double p1 = 1.0 * j / N;
        double h = -(i * p0 * log2(p0) + j * p1 * log2(p1));
        double d = fabs(h - T);
        if (d < 0.01)
        {
            cout << i;
            return 0;
        }
        if (d < md)
        {
            md = d;
            a = i;
        }
    }
    cout << a << endl;
    return 0;
}

验证

答案为 $11027421$，验证如下：

• $0$ 的个数：$i = 11027421$；

• $1$ 的个数：$j = 23333333 - 11027421 = 12305912$；

• 概率计算：

  $$
  p0 = \frac{11027421}{23333333} \approx 0.4727
  $$

  $$
  p1 = \frac{12305912}{23333333} \approx 0.5273
  $$

• 信息熵计算：

  $$
  H \approx 11625907.5798 \quad (\text{误差} < 10^{-5})
  $$

答案

答案为 $11027421$。

代码

#include<iostream>
#include<string>
using namespace std;
int main() {
    string ans [] = {
        "235", // 试题 A 答案
        "11027421", // 试题 B 答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}