蓝桥杯 2023 年省赛 C++ 组 B 组填空题（日期统计与 01 串的熵）题解

C++ b 组：

A 题：

答案：235

思路：

暴力搜索题，但是要注意剪枝。 2100 爆搜一年都跑不完。

首先年 2023 是确定的，考虑用 a 、 b 、 c 、 d 分别枚举 2、0、2、3。 a 不是 2 就不继续枚举 b ， b 不是 0 就不继续枚举 c ， d 同理。消去指数级别的复杂度。

用 e 、 f 分别枚举月的十位与个位， e 为 0 时 f 不能取 0， e 为 1 时 f  2 。

用 g 、 h 分别枚举日的十位与个位，注意 g 为 0 时 f 不能取 0，其他时候不用特判，因为循环最后一层不会造成时间复杂度的变化。

然后就可以打出一个月份对应的日期表，注意 2023 年为平年。之后检查一下日期是否合法，如合法就可以把日期从数字拼接成字符串，使用 unordered_set 维护日期是否出现，常数会更好看一点。（因为这些数字范围都很紧凑）

完整代码如下：

//
//  main.cpp
//  日期统计
//
//  Created by SkyWave Sun on 2023/4/8.
//

#include <iostream>
#include <unordered_set>
using namespace std;
const int nums[] = {0, 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};
const int n = 100;
const int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
unordered_set<string> st;
int main(int argc, const char * argv[]) {
    int sum = 0;
    for (int a = 1; a <= n; ++a) {//year
        if (nums[a] == 2) {
            for (int b = a + 1; b <= n; ++b) {//year
                if (nums[b] == 0) {
                    for (int c = b + 1; c <= n; ++c) {//year
                        if (nums[c] == 2) {
                            for (int d = c + 1; d <= n; ++d) {//year
                                if (nums[d] == 3) {
                                    for (int e = d + 1; e <= n; ++e) {//month
                                        if (nums[e] == 0 || nums[e] == 1) {
                                            for (int f = e + 1; f <= n; ++f) {//month
                                                if ((nums[e] == 0 && nums[f] != 0) || (nums[e] == 1 && nums[f] <= 2)) {
                                                    for (int g = f + 1; g <= n; ++g) {//day
                                                        if (nums[g] <= 3) {
                                                            for (int h = g + 1; h <= n; ++h) {//day
                                                                if (nums[g] == 0 && nums[h] == 0) {
                                                                    continue;
                                                                }
                                                                string str = "2023";
                                                                int month = nums[e] * 10 + nums[f];
                                                                int day = nums[g] * 10 + nums[h];
                                                                str += to_string(nums[e]) + to_string(nums[f]);
                                                                str += to_string(nums[g]) + to_string(nums[h]);
                                                                if (day <= days[month]) {
                                                                    if (st.count(str)) {
                                                                        continue;
                                                                    }
                                                                    st.insert(str);
                                                                    puts(str.c_str());
                                                                    ++sum;
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    printf("%d\n",sum);
    return 0;
}

时间复杂度为小常数 

B 题：

答案：11027421

思路：朴素的暴力枚举 0 的个数（时间复杂度 ​​​​​​​ ）​​​​​​​ 暴力计算贡献（时间复杂度  ）肯定吃不消。枚举 0 的个数的线性不可避免，考虑优化式子，发现 01 在串里的顺序不影响最终贡献，因为贡献的计算中只有 0 和 1 的数量的参与。于是可以把循环优化成乘法，记 0 在串中数量为 sum0 ，1 在串中数量为 sum1 ，其他参数与原式相同，则式子变为 ，于是可以线性求得答案。

又观察到信息熵大概是长度的一半少一点，于是可以凭感觉从长度的一半往前枚举。注意，因为浮点数是不能等于的，并且在此题中因无限循环小数参与过多，导致误差会相差很大，所以建议将浮点数的偏移量设置成 。

代码：

//
//  main.cpp
//  01 串的熵
//
//  Created by SkyWave Sun on 2023/4/8.
//

#include <iostream>
#include <cmath>
using namespace std;
const double eps = 1e-4;
const double ans = 11625907.5798;
const int n = 23333333;
double f(int sum1, int sum0) {
    double ans = 0.0;
    double p1 = (double)sum1 / (double)n;
    double p0 = (double)sum0 / (double)n;
    ans += sum1 * p1 * log2(p1);
    ans += sum0 * p0 * log2(p0);
    return ans;
}
int main(int argc, const char * argv[]) {
    for (int i = n >> 1; i >= 0; --i) {
        double tmp = -f(n - i, i);
        if (fabs(tmp - ans) <= eps) {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}