第十四届蓝桥杯填空题:日期统计 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;
}