目录
试题 A. 日期统计1.题目描述2.解题思路3.模板代码 试题 B.01 串的熵1.题目描述2.解题思路3.模板代码 试题 C. 冶炼金属1.题目描述2. 解题思路3.模板代码 试题 D. 飞机降落1.题目描述2. 解题思路3.模板代码 试题 E. 接龙数列1.题目描述2. 解题思路3.模板代码 试题 F. 岛屿个数1.题目描述2. 解题思路3.模板代码 试题 G. 子串简写1.题目描述2. 解题思路3.模板代码 试题 H.整数删除1.题目描述2. 解题思路3.模板代码 试题 I. 景区旅游1.题目描述2. 解题思路3.模板代码 试题 J. 砍树1.题目描述2. 解题思路3. 模板代码
目前除 B、F题未补，其余题均已更完，经非官方数据测试均可AC。欢迎交流
试题 A. 日期统计
1.题目描述
小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的
范围之内。数组中的元素从左至右如下所示：
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
现在他想要从这个数组中寻找一些满足以下条件的子序列：
子序列的长度为 8 8 8； . 这个子序列可以按照下标顺序组成一个 y y y y m m d d yyyymmdd yyyymmdd 格式的日期，并且要求这个日期是 2023 2023 2023 年中的某一天的日期，例如 20230902 ， 20231223 20230902，20231223 20230902，20231223。
y y y y yyyy yyyy 表示年份， m m mm mm 表示月份， d d dd dd 表示天数，当月份或者天数的长度只
有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同 的 2023 年的日期。
对于相同的日期你只需要统计一次即可。
2.解题思路
考虑八层循环枚举一下，中间需要进行减枝加快搜索步骤，不建议写 dfs，不然就像我一样在考场写烂，注意答案需要去重，答案为235。
3.模板代码
暂更
试题 B.01 串的熵
1.题目描述
没学过数学，暂更
2.解题思路
3.模板代码
试题 C. 冶炼金属
1.题目描述
小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个
炉子有一个称作转换率的属性 V V V， V V V 是一个正整数，这意味着消耗 V V V 个普通金
属 O O O 恰好可以冶炼出一个特殊金属 X X X，当普通金属 O O O 的数目不足 V V V 时，无法
继续冶炼。
现在给出了 N N N 条冶炼记录，每条记录中包含两个整数 A A A 和 B B B，这表示本次投入了 A A A 个普通金属 O O O，最终冶炼出了 B B B 个特殊金属 X X X。每条记录都是独立
的，这意味着上一次没消耗完的普通金属 O O O 不会累加到下一次的冶炼当中。
根据这 N N N 条冶炼记录，请你推测出转换率 V V V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。
2. 解题思路
如果看过样例的话，显然答案两个上下界都是可以直接二分出来的。因为式子的结构都是 A C = B \frac{A}{C} = B CA=B。 A A A 是不变的，我们先考虑二分求最小的 C C C，因为需要保证所有式子的 B B B 都不变，如果 C C C 太小，显然会有某一组的 B B B 增大，所以需要保证每一组都符合a[i]/x <= b[i]。反过来考虑求最大的 C C C, 如果 C C C 太大，显然会有某一组的 B B B 变小，需要保证每一组都符合 a[i]/x >= B。
3.模板代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n;int a[N], b[N];bool check(LL x) {for (int i = 1; i <= n; ++i) {if (a[i] / x > b[i]) return false;}return true;}bool check2(LL x) {for (int i = 1; i <= n; ++i) {if (a[i] / x < b[i]) return false;}return true;}void solve(){cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];LL l = 1, r = 1e9;while (l < r) {LL mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}int s = r;l = 1, r = 1e9;while (l < r) {LL mid = l + r + 1 >> 1;if (check2(mid)) l = mid;else r = mid - 1;}cout << s << " " << r << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}试题 D. 飞机降落
1.题目描述
N N N 架飞机准备降落到某个只有一条跑道的机场。其中第 i i i 架飞机在 T i Ti Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 D i Di Di 个单位时间，即它最早
可以于 T i Ti Ti 时刻开始降落，最晚可以于 T i + D i Ti + Di Ti+Di 时刻开始降落。降落过程需要 L i Li Li
个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不
能在前一架飞机完成降落前开始降落。
请你判断 N N N 架飞机是否可以全部安全降落。
2. 解题思路
看 N N N 最大为10，T最大也为10，考虑全排列枚举所有的降落情况，只要有一种符合的情况即可，大概计算一下复杂度为 10 ! × 10 × 10 10 ! \times10\times10 10!×10×10 等于3e8，理论可过 。
3.模板代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n;int a[N], b[N], c[N];void solve(){cin >> n;for (int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i];std::vector<int> d(n);auto check = [&]() {int v = 0;for (int i = 0; i < n; ++i) {int x = d[i];if (i == 0) {v = a[x] + c[x];} else {if (a[x] + b[x] < v) return false;v = max(v, a[x]) + c[x];}}return true;};iota(all(d), 0);bool f = false;do {if (check()) {f = true;break;}} while (next_permutation(all(d)));if (f) cout << "YES" << '\n';else cout << "NO" << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;}试题 E. 接龙数列
1.题目描述
对于一个长度为 K K K 的整数数列： A 1 , A 2 , . . . , A K A_1, A_2, . . . , A_K A1,A2,...,AK，我们称之为接龙数列当且仅当 A i A_i Ai 的首位数字恰好等于 A i − 1 A_{i-1} Ai−1 的末位数字 ( 2 ≤ i ≤ K ) (2 ≤ i ≤ K) (2≤i≤K)。
例如 12 , 23 , 35 , 56 , 61 , 11 12, 23, 35, 56, 61, 11 12,23,35,56,61,11 是接龙数列； 12 , 23 , 34 , 56 12, 23, 34, 56 12,23,34,56 不是接龙数列，因为 56 56 56 的首位数字不等于 34 34 34 的末位数字。所有长度为 1 1 1 的整数数列都是接龙数列。
现在给定一个长度为 N N N 的数列 A 1 , A 2 , . . . , A N A_1, A_2, . . . , A_N A1,A2,...,AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
2. 解题思路
考场读完题的时候感觉有点奇怪，发现思路还是比较简单的。首先一个数我们只需要关注其首位数字和末位数字，定以 f [ i ] f[i] f[i] 为以数字 i i i 结尾的最长接龙序列的长度， i i i 的范围是 [ 0 , 9 ] [0,9] [0,9]。对于每个数字设其首位数字为 a a a ，末尾数字为 b b b，则有转移方程：
f [ b ] = m a x ( f [ b ] , f [ a ] + 1 ) f[b]=max(f[b],f[a]+1) f[b]=max(f[b],f[a]+1)
最后在 f [ 0 ] 、 f [ 1 ] . . . f [ 9 ] f[0]、f[1]...f[9] f[0]、f[1]...f[9] 取一个最大值 a n s ans ans，答案则为 n − a n s n-ans n−ans。
3.模板代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n;int a[N], b[N];int f[10];void solve(){cin >> n;for (int i = 1; i <= n; ++i) {int x;cin >> x;b[i] = x % 10;string s = to_string(x);a[i] = s[0] - '0';}for (int i = 1; i <= n; ++i) {f[b[i]] = max(f[b[i]], f[a[i]] + 1);}int ans = 0;for (int i = 0; i <= 9; ++i) ans = max(ans, f[i]);cout << n - ans << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}试题 F. 岛屿个数
1.题目描述
暂更，感觉不好写
2. 解题思路
3.模板代码
试题 G. 子串简写
1.题目描述
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 i n t e r n a t i o n − a l i z a t i o n internation-alization internation−alization 简写成 i 18 n i18n i18n， K u b e r n e t e s Kubernetes Kubernetes （注意连字符不是字符串的一部分）简写成 K 8 s , L a n q i a o K8s, Lanqiao K8s,Lanqiao 简写成 L 5 o L5o L5o等。
在本题中，我们规定长度大于等于 K K K 的字符串都可以采用这种简写方法（长度小于 K K K 的字符串不配使用这种简写）。
给定一个字符串 S S S 和两个字符 c 1 c1 c1 和 c 2 c2 c2，请你计算 S S S 有多少个以 c 1 c1 c1 开头 c 2 c2 c2 结尾的子串可以采用这种简写？
2. 解题思路
这道题放在 G 题感觉更奇怪了，一道前缀和模板题。假设下标为 i i i 的字符为 c 1 c1 c1，那我们只需要统计在区间 [ i + k − 1 , n ] [i+k-1,n] [i+k−1,n]有多少个 c 2 c2 c2 即可，前缀和预处理一下 c 2 c2 c2 字符，直接累加答案即可，注意答案会爆int，复杂度 O ( n ) O(n) O(n)
3.模板代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 500010;int k;string s;char c1, c2;int a[N];void solve(){cin >> k >> s >> c1 >> c2;int n = s.size();s = '?' + s;for (int i = 1; i <= n; ++i) {a[i] = (s[i] == c2);a[i] += a[i - 1];}LL ans = 0;for (int i = 1; i + k - 2 < n; ++i) {if (s[i] == c1) ans += a[n] - a[i + k - 2];}cout << ans << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}试题 H.整数删除
1.题目描述
给定一个长度为 N N N 的整数数列： A 1 , A 2 , . . . , A N A_1, A_2, . . . , A_N A1,A2,...,AN。你要重复以下操作 K K K 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
输出 K K K 次操作后的序列。
2. 解题思路
感觉是比较典的题目，用优先队列维护，存入值和下标，再用一个数组cnt累计每个下标增加的和，当弹出最小的值下标为 i 时，如果此时cnt[i]不等于0，说明它实际的值需要加上cnt[i]，我们将其增加后再放回优先对列，注意需要清空cnt[i]。如果此时cnt[i]等于0，那我们就成功弹出当前最小元素，这时需要将其前一个元素和后一个元素值增加，我们需要模拟链表去记录每个元素的前后元素是谁，pre[i]表示下标为i的上一个元素是谁，ne[i]表示下标为 i 的下一个元素是谁，直到堆的元素个数只剩n-k时结束循环。不难想象，堆元素的出入次数是线性的。
3.模板代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 500010;int n, k;int pre[N], ne[N];LL cnt[N];void solve(){cin >> n >> k;priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>> >q;for (int i = 1; i <= n; ++i) {LL v;cin >> v;q.push({v, i});pre[i] = i - 1;ne[i] = i + 1;}int g = n - k;while (q.size() > g) {auto p = q.top(); q.pop();LL v = p.first, ix = p.second;if (cnt[ix]) {q.push({v + cnt[ix], ix});cnt[ix] = 0;} else {int l = pre[ix], r = ne[ix];cnt[l] += v;cnt[r] += v;ne[l] = r;pre[r] = l;}}std::vector<LL> a(n + 1);for (int i = 0; i < g; ++i) {auto p = q.top(); q.pop();a[p.second] = p.first + cnt[p.second];}for (int i = 1; i <= n; ++i) {if (a[i]) cout << a[i] << " ";}}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}试题 I. 景区旅游
1.题目描述
某景区一共有 N N N 个景点，编号 1 1 1 到 N N N。景点之间共有 N − 1 N − 1 N−1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K K K 个景点： A 1 , A 2 , . . . , A K A_1, A_2, . . . , A_K A1,A2,...,AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K − 1 K − 1 K−1 个景点。具体来说，如果小明选择跳过 A i A_i Ai，那么他会按顺序带游客游览 A 1 , A 2 , . . . , A i − 1 , A i + 1 , . . . , A K , ( 1 ≤ i ≤ K ) A_1, A_2, . . . , A_{i−1}, A_{i+1}, . . . , A_K, (1 ≤ i ≤ K) A1,A2,...,Ai−1,Ai+1,...,AK,(1≤i≤K)。
请你对任意一个 A i Ai Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？
2. 解题思路
L C A LCA LCA 模板题（问题是比赛写不出板子呢），首先肯定需要考虑求树上任意两点的距离。设点 u , v u,v u,v 的最近公共祖先为 z z z，定义 f [ i ] f[i] f[i] 为点 i i i 到根节点的距离，那么则有公式:
d i s t ( u , v ) = f [ u ] + f [ v ] − 2 ∗ f [ z ] dist(u,v)=f[u]+f[v]-2*f[z] dist(u,v)=f[u]+f[v]−2∗f[z]
先求出不跳过任何的点时需要走的距离为ans以及任意相邻两个跳点的距离。假设我们跳过四个点分别为 a , b , c , d a,b,c,d a,b,c,d。当跳过的点为 a a a 时，我们只需要用ans减去 a a a到 b b b的距离，当跳过的点为 d d d 时，我们只需要用ans减去 c c c 到 d d d 的距离，这是首尾两个点的情况。
那么当跳过的点为中间点呢？比如我们跳过的是 b b b，那么则需要用ans减去 a a a到 b b b以及 b b b到 c c c的距离，并且还需要加上 a a a到 c c c的距离，其余的中间点处理同理。
3.模板代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s)#define SZ(s) ((int)s.size())#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n, m;std::vector<pair<int, LL>> e[N];int depth[N], fa[N][32];LL f[N];int root;void bfs(int root){ memset(depth, 0x3f, sizeof depth); depth[0] = 0, depth[root] = 1; queue<int> q; q.push(root); while (!q.empty()) { auto t = q.front(); q.pop(); for (auto [j, c] : e[t]) { if (depth[j] > depth[t] + 1) { depth[j] = depth[t] + 1; q.push(j); fa[j][0] = t; for (int k = 1; k <= 20; k++) { fa[j][k] = fa[fa[j][k - 1]][k - 1]; } } } }}void dfs(int u, int fa) { for (auto [v, c] : e[u]) { if (v == fa) continue; f[v] = f[u] + c; dfs(v, u); }}int lca(int a, int b) { if (depth[a] < depth[b]) swap(a, b); for (int k = 20; k >= 0; k--) { if (depth[fa[a][k]] >= depth[b]) { a = fa[a][k]; } } if (a == b) return a; for (int k = 20; k >= 0; --k) { if (fa[a][k] != fa[b][k]) { a = fa[a][k]; b = fa[b][k]; } } return fa[a][0];}LL calc(int u, int v) { int z = lca(u, v); return f[u] + f[v] - 2 * f[z];}void solve(){ cin >> n >> m; for (int i = 0; i < n - 1; ++i) { int u, v , c; cin >> u >> v >> c; e[u].push_back({v, c}); e[v].push_back({u, c}); } bfs(1); dfs(1, -1); std::vector<LL> g(m + 1); for (int i = 1; i <= m; ++i) cin >> g[i]; LL ans = 0; for (int i = 1; i < m; ++i) { ans += calc(g[i], g[i + 1]); } for (int i = 1; i <= m; ++i) { if (i == 1) cout << ans - calc(g[i], g[i + 1]) << " "; else if (i == m) cout << ans - calc(g[i - 1], g[i]) << " "; else { LL res = ans - calc(g[i], g[i + 1]) - calc(g[i - 1], g[i]) + calc(g[i - 1], g[i + 1]); cout << res << " "; } }}signed main(){ ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while (t--) { solve(); } return 0;}试题 J. 砍树
1.题目描述
给定一棵由 n n n 个结点组成的树以及 m m m 个不重复的无序数对 ( a 1 , b 1 ) , ( a 2 , b 2 ) , . . . , ( a m , b m ) (a1, b1), (a_2, b_2),. . . , (a_m, b_m) (a1,b1),(a2,b2),...,(am,bm)，其中 a i ai ai 互不相同， b i b_i bi 互不相同， a i , b j ( 1 ≤ i , j ≤ m ) a_i , b_j(1 ≤ i, j ≤ m) ai,bj(1≤i,j≤m)。
小明想知道是否能够选择一条树上的边砍断，使得对于每个 ( a i , b i ) (ai , bi) (ai,bi) 满足 a i ai ai和 b i bi bi 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 1 1 开始），否则输出 − 1 -1 −1。
2. 解题思路
又是 L C A LCA LCA 模板题啊，但我之前没做过（反正也写不出 L C A LCA LCA）。考虑一对无序数对的点 x x x 和 y y y ，如果我们砍掉某条边可以让这两个点不连通，那么这条边一定是从 x x x 到 y y y 路径上的一点，我们可以让从 x x x 到 y y y 路径的边权值都加1。这个操作我们可以使用树上差分。 对于 m m m 个无序数对我们都如此操作，最后如果某条边的权值为 m m m 则说明它符合条件，我们选出符合条件编号最大的那条边就是答案，如果没有权值为 m m m 的边则说明无解。
3. 模板代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n, m;std::vector<int> e[N];int depth[N], fa[N][32];int f[N];int root;int ans;map<PII, int> mp;void bfs(int root){ms(depth, 0x3f);depth[0] = 0, depth[root] = 1;queue<int> q;q.push(root);while (!q.empty()) {auto t = q.front();q.pop();for (int j : e[t]) {if (depth[j] > depth[t] + 1) {depth[j] = depth[t] + 1;q.push(j);fa[j][0] = t;for (int k = 1; k <= 15; k++) {fa[j][k] = fa[fa[j][k - 1]][k - 1];}}}}}int lca(int a, int b) {if (depth[a] < depth[b]) swap(a, b);for (int k = 15; k >= 0; k--) {if (depth[fa[a][k]] >= depth[b]) {a = fa[a][k];}}if (a == b) return a;for (int k = 15; k >= 0; --k) {if (fa[a][k] != fa[b][k]) {a = fa[a][k];b = fa[b][k];}}return fa[a][0];}int dfs(int u, int fa) {int res = f[u];for (auto v : e[u]) {if (v == fa) continue;int g = dfs(v, u);if (g == m) {ans = max(ans, mp[ {v, u}]);}res += g;}return res;}void solve(){cin >> n >> m;for (int i = 0; i < n - 1; ++i) {int u, v;cin >> u >> v;mp[ {u, v}] = mp[ {v, u}] = i + 1;e[u].push_back(v);e[v].push_back(u);}bfs(1);for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;int z = lca(u, v);f[u]++;f[v]++;f[z] -= 2;}dfs(1, -1);cout << (ans == 0 ? -1 : ans) << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}
