2023蓝桥杯省赛 B01串的熵

数学模拟 枚举 T2

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;
}