题目A：日期统计
思路分析：
本题的题目比较繁琐，我们采用暴力加DFS剪枝的方式去做，我们在DFS中按照8位日期的每一个位的要求进行初步剪枝找出所有的八位子串，但是还是会存在19月的情况，为此还需要在CHECK函数中进一步剪枝，使得月份天数都符合条件
作者题解：
#include<iostream>
using namespace std;
int a[105], ans;
bool vis[20240000];
bool check(int date)//进一步剪枝，判断日期是否合法
{
if (vis[date])return false;
vis[date] = 1;//标记是否访问过
int mm = date / 100 % 100;//取出月份判断是否合法
int dd = date % 100;//取出天数判断是否合法
if (mm < 1 || mm > 12)return false;//月份小于1大于12都不合法
if (mm == 1 || mm == 3 || mm == 5 || mm == 7 || mm == 8 || mm == 10 || mm == 12)
{
if (1 <= dd && dd <= 31)return true;//大月如果是31天表示合法
}
else if (mm == 2)
{
if (1 <= dd && dd <= 28)return true;//如果是2月不超过28天表示合法
}
else if (1 <= dd && dd <= 30)return true;//不是2月也不是大月不超过30天表示合法
else return false;
}
void dfs(int x, int pos, int date)
{
if (x == 100)return;
if (pos == 8)
{
if (check(date))++ans;
return;
}
if (pos == 0 && a[x] == 2 ||
pos == 1 && a[x] == 0 ||
pos == 2 && a[x] == 2 ||
pos == 3 && a[x] == 3 ||//剪枝，前四位必须是2023
pos == 4 && (0 <= a[x] && a[x] <= 1) || //剪枝，月份第一位不可能超过1
pos == 5 && (0 <= a[x] && a[x] <= 9) ||
pos == 6 && (0 <= a[x] && a[x] <= 3) ||//日期的第一位不可能超过3
pos == 7 && (0 <= a[x] && a[x] <= 9))
dfs(x + 1, pos + 1, date * 10 + a[x]);
dfs(x + 1, pos, date);//合法才继续往后搜索
}
int main()
{
ios::sync_with_stdio,cin.tie(0), cout.tie(0);
for (int i = 0; i < 100; i++)cin >> a[i];
dfs(0, 0, 0);
cout << ans;
return 0;
}
运行结果：
有235个这样的合法子序列
题目B：01串的熵
思路分析：
这道题我们不要被它的定义吓唬住，仔细分析我们设串中的1的个数为u,串长为N，则v的个数为N-u，我们可以得到如下图的递推公式：
然后就是由于题中给出的是浮点数，我们要考率精度的问题，误差在给定的范围内即可认为是同一个浮点数，给定的数有几位小数，我们的精度就设为10的几次方
作者题解：
#include<iostream>
using namespace std;
using db = long double;
const int N = 23333333;//定义字符串长度
const db ans = 11625907.5798, eps = 1e-4;//由于题目中的数据是四位小数，所以我们要定义一个误差精度eps，在误差内表示是同一个数
int main()
{
for (int v = 0; v <= N / 2; ++v)
{
int u = N - v;
db res = -1.0 * u * u / N * log2(1.0 * u / N) - 1.0 * v * v / N * log2(1.0 * v / N);
if (fabs(res - ans) < eps)
{
cout << v;
return 0;
}
}
return 0;
}
运行结果：
题目C：冶炼金属
思路分析：
如图所示，我们通过数轴的方式分析，Ai/Vmin=Bi，那么我们如果要找Vmin那么Vmin逐渐增大，对应的Bi会逐渐变小，也就是说，Vmin左侧的Bi应该都比Vmin的Bi大，同理，Vmax右侧的Bi应该都比Vmax的Bi小，所以我们使用两次二分法，二分答案，以Bi的值作为检验函数，就可以求出最大和最小的V
作者题解：
#include<iostream>
using namespace std;
const int MAX_N = 1e4 + 1;
int N, A[MAX_N], B[MAX_N];
int V_min,V_max;
bool check_min(int V)
{
for (int i = 1; i <= N; ++i)
if (A[i] / V > B[i])return false;//查找最小值时都应该比bi小
return true;
}
bool check_max(int V)
{
for (int i = 1; i <= N; ++i)
if (A[i] / V < B[i])return false;//查找最大值时都应该比bi小
return true;
}
int main()
{
ios::sync_with_stdio, cin.tie(0), cout.tie(0);
cin >> N;
for (int i = 1; i <= N; i++)cin >> A[i] >> B[i];
int L = 1, R = 1e9;
while (L <= R)
{
int mid = L + R >> 1;
if (check_min(mid))
{
V_min = mid;
R = mid - 1;//查找最小值缩右边界
}
else L = mid + 1;
}
L = 1, R = 1e9;
while (L <= R)
{
int mid = L + R >> 1;
if (check_max(mid))
{
V_max = mid;
L = mid + 1;//查找最大值缩左边界
}
else R = mid - 1;
}
cout << V_min << " " << V_max << endl;
return 0;
}
运行结果：
题目D：飞机降落
思路分析：
这道题如果我们直接采用全排列可能会超时，所以我们还是采用DFS剪枝的策略，核心思想在于该架飞机的到达时间加上盘旋时间大于此前所有飞机的降落时间时才可以安全降落，我们采用一个used数组来维护飞机是否可以安全降落，最后递归的出口如果X==N即所有飞机完成降落我们就输出YES
作者题解：
#include<iostream>
using namespace std;
const int MAX_N = 11;
int N, T[MAX_N], D[MAX_N], L[MAX_N];
bool used[MAX_N], have_answer;//use标志飞机是否安全降落
void dfs(int x, int tim) //tim表示此前所有飞机降落所需的单位时间
{
if (have_answer)return;
if (x == N)
{
have_answer = 1;
return;//存在解则退出搜索
}
for (int i = 1; i <= N; i++)
{
if (!used[i] && tim <= T[i] + D[i])
{
used[i] = 1;
dfs(x + 1, max(T[i], tim) + L[i]);//如果此前所有的飞机的降落时间小于下一架飞机的最早降落时间可以等一等
if (have_answer)return;
else used[i] = 0;//回溯
}
}
}
void solve()
{
have_answer = 0;
cin >> N;
for (int i = 1; i <= N; ++i)
{
cin >> T[i] >> D[i] >> L[i];
used[i] = 0;
}
dfs(0, 0);
if (have_answer)cout << "YES\n";
else cout << "NO\n";
}
int main()
{
ios::sync_with_stdio, cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
运行结果：
下期预告：E，F，G题解析