2023年蓝桥杯B组C++题解

A 日期统计 5分

小蓝现在有一个长度为 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

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

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

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

思路

这一届的填空题比去年要难上一些, 手算挺容易出错, 还是来写个代码整吧。8层for循环枚举年月日即可。注意闰月和2月的特殊处理, 2023年并不是闰年, 故2月共28天。

通常是用一个数组来表示月份对应天数：

int day[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

去重的话直接用 月份* 100 + 天数 手动hash, 配合 unordered_set。

答案为 235。

枚举代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_set>
#define _for(i, n, m) for (int i = n; i < m; i++)
using namespace std;
int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int a[110];
 
int main()
{
	int n = 100;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	unordered_set<int> S;
 
	_for(y1, 0, n)
	{
		if (a[y1] != 2)
			continue;
		_for(y2, y1 + 1, n)
		{
			if (a[y2] != 0)
				continue;
			_for(y3, y2 + 1, n)
			{
				if (a[y3] != 2)
					continue;
				_for(y4, y3 + 1, n)
				{
					if (a[y4] != 3)
						continue;
 
					_for(m1, y4 + 1, n)
					{
						if (a[m1] > 1)
							continue;
						_for(m2, m1 + 1, n)
						{
							int m = a[m1] * 10 + a[m2];
							if (m > 12 || !m)
								continue;
							_for(d1, m2 + 1, n)
							{
								if (a[d1] > 3)
									continue;
								_for(d2, d1 + 1, n)
								{
									int d = a[d1] * 10 + a[d2];
									if (d > day[m] || !d)
										continue;
									if (!S.count(m * 100 + d))
										S.insert(m * 100 + d);
									// cout << a[y1] << a[y2] << a[y3] << a[y4] << "-" << m << "-" << d << endl;
								}
							}
						}
					}
				}
			}
		}
	}
	cout << S.size() << endl;
	return 0;
}

B 01 串的熵

对于一个长度为 $n$ 的 $01$ 串 $S=x_1{x}_2{x}_{3\dots }{x}_n$，香农信息熵的定义为 $H(S)=-{\Sigma }_1^{n}p(x_i)log2(p(x_i))$，其中 $p(0),p(1)$ 表示在这个 $01$ 串中 $0$ 和 $1$ 出现的占比。

比如，对于 $S=100$ 来说，信息熵 $H(S)=-\frac{1}{3}log2(\frac{1}{3})-\frac{2}{3}log2(\frac{2}{3})-\frac{2}{3}log2(\frac{2}{3})=1.3083$。

对于一个长度为 $23333333$ 的 $01$ 串，如果其信息熵为 $11625907.5798$， 且 $0$ 出现次数比 $1$ 少，那么这个 $01$ 串中 $0$ 出现了多少次？

思路

很难通过信息熵来逆推出现的次数（不懂信息熵

故根据暴力杯传统, 直接枚举所有长度为 23333333 的01串可能, 计算他们每一个的信息熵, 如果等于 $11625907.5798$, 且 $0$ 出现的次数比 $1$ 少, 就输出当前串。

math库中有一个求以2为底的log函数：（比赛时候查帮助文档没找到）

log2()

直接按照公式枚举1的个数即可：

// https://www.cnblogs.com/kiddingma/p/17299464.html
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
double eps = 1E-4;
 
int main()
{
    auto get = [&](int x, int y)
    {
        double one = 1.0 * x / (1.0 * (x + y));
        double zero = 1.0 * y / (1.0 * (x + y));
        return -(x * one * log2(one) + y * zero * log2(zero));
    };
    for (int i = 0; i <= 23333333; i++)
    {
        if (abs(get(i, 23333333 - i) - 11625907.5798) <= eps)
        {
            cout << i << endl;
            break;
        }
    }
 
    return 0;
}

C 冶炼金属

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。

现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式

第一行一个整数 $N$，表示冶炼记录的数目。 接下来输入 $N$ 行，每行两个整数 $A、B$，含义如题目所述。

输出格式

输出两个整数，分别表示 $V$ 可能的最小值和最大值，中间用空格分开。

样例输入

3
75 3
53 2
59 2

样例输出

20 25

数据范围

对于 $30\%$ 的评测用例，$1\le N\le 10^2$。 对于 $60\%$ 的评测用例，$1\le N\le 10^3$。 对于 $100\%$ 的评测用例，$1\le N\le 10^4，1\le B\le A\le 10^9$。

思路