題目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 ||//剪枝，前四位必須是2023pos == 4 && (0 <= a[x] && a[x] <= 1) || //剪枝，月份第一位不可能超過1pos == 5 && (0 <= a[x] && a[x] <= 9) ||pos == 6 && (0 <= a[x] && a[x] <= 3) ||//日期的第一位不可能超過3pos == 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題解析