第十四届蓝桥杯填空题：日期统计 01串熵

这道题我们选择暴力搜索，剪枝

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int a[] = { 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 };
vector<int> path;
int cnt;
int day[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

void dfs(int pos) {
    if (path.size() == 8) {
        if (path[0] == 2 && path[1] == 0 && path[2] == 2 && path[3] == 3) {
            int mm = path[4] * 10 + path[5];
            if (mm >= 1 && mm <= 12) {
                int dd = path[6] * 10 + path[7];
                if (dd >= 1 && dd <= day[mm]) {
                    cnt++;
                }
            }
        }
        return;
    }
    unordered_set<int> mp;
    for (int i = pos; i < 100; i++) {
        if(mp.find(a[i])!=mp.end())
            continue;
        mp.insert(a[i]);
        path.push_back(a[i]);
        dfs(i + 1);
        path.pop_back();
    }
}

int main() {
    dfs(0);
    cout << cnt << endl;
    return 0;
}

这道题，我们要求0出现了多少次，我们就枚举0的个数，找到符合要求的0的个数，输出即可

#include <iostream>
#include <algorithm>
#include <cctype>
#include <cmath>
using namespace std;
const int N = 23333333;

double calc(double cnt0, double cnt1)
{
	double p0 = cnt0 / (cnt0 + cnt1);
	double p1 = cnt1 / (cnt0 + cnt1);
	return -cnt0 * (p0 * log2(p0)) - cnt1 * (p1 * log2(p1));
}
const double M = 11625907.5798;
int main()
{
	for (int i = 1; i <= N; i++)
	{
		if (fabs(calc(i, N - i) - M) < 0.0001)
		{
			cout << i << endl;
			break;
		}
	}






	return 0;
}