目录

  • 试题 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

现在他想要从这个数组中寻找一些满足以下条件的子序列:

    1. 子序列的长度为 88 8
    1. . 这个子序列可以按照下标顺序组成一个 yyyymmddyyyymmdd yyyymmdd 格式的日期,并且
      要求这个日期是 20232023 2023 年中的某一天的日期,例如 20230902,2023122320230902,20231223 2023090220231223
      yyyyyyyy yyyy 表示年份,mmmm mm 表示月份,dddd dd 表示天数,当月份或者天数的长度只
      有一位时需要一个前导零补充。

  请你帮小蓝计算下按上述条件一共能找到多少个不同 的 2023 年的日期。
对于相同的日期你只需要统计一次即可。

2.解题思路

  考虑八层循环枚举一下,中间需要进行减枝加快搜索步骤,不建议写 dfs,不然就像我一样在考场写烂,注意答案需要去重,答案为235

3.模板代码

  暂更

试题 B.01 串的熵

1.题目描述

  没学过数学,暂更

2.解题思路

3.模板代码

试题 C. 冶炼金属

1.题目描述

  小蓝有一个神奇的炉子用于将普通金属 OOO 冶炼成为一种特殊金属 XXX。这个
炉子有一个称作转换率的属性 VVV VVV 是一个正整数,这意味着消耗 VVV 个普通金
OOO 恰好可以冶炼出一个特殊金属 XXX,当普通金属 OOO 的数目不足 VVV 时,无法
继续冶炼。
 现在给出了 NNN 条冶炼记录,每条记录中包含两个整数 AAA BBB,这表示本次投入了 AAA 个普通金属 OOO,最终冶炼出了 BBB 个特殊金属 XXX。每条记录都是独立
的,这意味着上一次没消耗完的普通金属 OOO 不会累加到下一次的冶炼当中。
 根据这 NNN 条冶炼记录,请你推测出转换率 VVV 的最小值和最大值分别可能是多少,题目保证评测数据不存在无解的情况。

2. 解题思路

  如果看过样例的话,显然答案两个上下界都是可以直接二分出来的。因为式子的结构都是 AC= B\frac{A}{C} = BCA=B AAA 是不变的,我们先考虑二分求最小的 CCC,因为需要保证所有式子的 BBB 都不变,如果 CCC 太小,显然会有某一组的 BBB 增大,所以需要保证每一组都符合a[i]/x <= b[i]。反过来考虑求最大的 CCC, 如果 CCC 太大,显然会有某一组的 BBB 变小,需要保证每一组都符合 a[i]/x >= B

3.模板代码

#includeusing 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.题目描述

   NNN 架飞机准备降落到某个只有一条跑道的机场。其中第 iii 架飞机在 T iTiTi 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 D iDiDi 个单位时间,即它最早
可以于 T iTiTi 时刻开始降落,最晚可以于 T i + D iTi + DiTi+Di 时刻开始降落。降落过程需要 L iLiLi
个单位时间。
 一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不
能在前一架飞机完成降落前开始降落。
 请你判断 NNN 架飞机是否可以全部安全降落。

2. 解题思路

   看 NNN 最大为10T最大也为10,考虑全排列枚举所有的降落情况,只要有一种符合的情况即可,大概计算一下复杂度为 10 ! × 10 × 1010 ! \times10\times1010!×10×10 等于3e8,理论可过 。

3.模板代码

#includeusing 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.题目描述

   对于一个长度为 KKK 的整数数列: A1, A2, . . . , AK A_1, A_2, . . . , A_KA1,A2,,AK,我们称之为接龙数列当且仅当 Ai A_iAi 的首位数字恰好等于 A i − 1 A_{i-1}Ai1 的末位数字 ( 2 ≤ i ≤ K )(2 ≤ i ≤ K)(2iK)
  例如 12 , 23 , 35 , 56 , 61 , 1112, 23, 35, 56, 61, 1112,23,35,56,61,11 是接龙数列; 12 , 23 , 34 , 5612, 23, 34, 5612,23,34,56 不是接龙数列,因为 565656 的首位数字不等于 343434 的末位数字。所有长度为 111 的整数数列都是接龙数列。
  现在给定一个长度为 NNN 的数列 A1, A2, . . . , AN A_1, A_2, . . . , A_NA1,A2,,AN,请你计算最少从中删除多少个数,可以使剩下的序列是接龙序列?

2. 解题思路

   考场读完题的时候感觉有点奇怪,发现思路还是比较简单的。首先一个数我们只需要关注其首位数字和末位数字,定以 f [ i ]f[i]f[i] 为以数字 iii 结尾的最长接龙序列的长度, iii 的范围是 [ 0 , 9 ][0,9][0,9]。对于每个数字设其首位数字为 aaa ,末尾数字为 bbb,则有转移方程:
f[b]=max(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 sansans,答案则为 n − a n sn-ansnans

3.模板代码

#includeusing 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 ninternation-alizationinternationalization 简写成 i 18 ni18ni18n K u b e r n e t e sKubernetesKubernetes (注意连字符不是字符串的一部分)简写成 K 8 s , L a n q i a oK8s, LanqiaoK8s,Lanqiao 简写成 L 5 oL5oL5o等。
  在本题中,我们规定长度大于等于 KKK 的字符串都可以采用这种简写方法(长度小于 KKK 的字符串不配使用这种简写)。
  给定一个字符串 SSS 和两个字符 c 1c1c1 c 2c2c2,请你计算 SSS 有多少个以 c 1c1c1 开头 c 2c2c2 结尾的子串可以采用这种简写?

2. 解题思路

   这道题放在 G 题感觉更奇怪了,一道前缀和模板题。假设下标为 iii 的字符为 c 1c1c1,那我们只需要统计在区间 [ i + k − 1 , n ][i+k-1,n][i+k1,n]有多少个 c 2c2c2 即可,前缀和预处理一下 c 2c2c2 字符,直接累加答案即可,注意答案会爆int,复杂度 O ( n )O(n)O(n)

3.模板代码

#includeusing 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.题目描述

   给定一个长度为 NNN 的整数数列: A1, A2, . . . , AN A_1, A_2, . . . , A_NA1,A2,,AN。你要重复以下操作 KKK 次:
  每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除。并把与它相邻的整数加上被删除的数值。
  输出 KKK 次操作后的序列。

2. 解题思路

   感觉是比较典的题目,用优先队列维护,存入值和下标,再用一个数组cnt累计每个下标增加的和,当弹出最小的值下标为 i 时,如果此时cnt[i]不等于0,说明它实际的值需要加上cnt[i],我们将其增加后再放回优先对列,注意需要清空cnt[i]。如果此时cnt[i]等于0,那我们就成功弹出当前最小元素,这时需要将其前一个元素和后一个元素值增加,我们需要模拟链表去记录每个元素的前后元素是谁,pre[i]表示下标为i的上一个元素是谁,ne[i]表示下标为 i 的下一个元素是谁,直到堆的元素个数只剩n-k时结束循环。不难想象,堆元素的出入次数是线性的。


3.模板代码

#includeusing 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.题目描述

   某景区一共有 NNN 个景点,编号 111 NNN。景点之间共有 N − 1N − 1N1 条双向的摆渡车线路相连,形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行,需要花费一定的时间。
  小明是这个景区的资深导游,他每天都要按固定顺序带客人游览其中 KKK 个景点: A1, A2, . . . , AK A_1, A_2, . . . , A_KA1,A2,,AK。今天由于时间原因,小明决定跳过其中一个景点,只带游客按顺序游览其中 K − 1K − 1K1 个景点。具体来说,如果小明选择跳过 Ai A_iAi,那么他会按顺序带游客游览 A1, A2, . . . , A i − 1, A i + 1, . . . , AK, ( 1 ≤ i ≤ K )A_1, A_2, . . . , A_{i−1}, A_{i+1}, . . . , A_K, (1 ≤ i ≤ K)A1,A2,,Ai1,Ai+1,,AK,(1iK)
  请你对任意一个 A iAiAi,计算如果跳过这个景点,小明需要花费多少时间在景点之间的摆渡车上?

2. 解题思路

   L C ALCALCA 模板题(问题是比赛写不出板子呢),首先肯定需要考虑求树上任意两点的距离。设点 u , vu,vu,v 的最近公共祖先为 zzz,定义 f [ i ]f[i]f[i] 为点 iii 到根节点的距离,那么则有公式:
dist(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]2f[z]
  先求出不跳过任何的点时需要走的距离为ans以及任意相邻两个跳点的距离。假设我们跳过四个点分别为 a , b , c , da,b,c,da,b,c,d。当跳过的点为 aaa 时,我们只需要用ans减去 aaa bbb的距离,当跳过的点为 ddd 时,我们只需要用ans减去 ccc ddd 的距离,这是首尾两个点的情况。
  那么当跳过的点为中间点呢?比如我们跳过的是 bbb,那么则需要用ans减去 aaa bbb以及 bbb ccc的距离,并且还需要加上 aaa ccc的距离,其余的中间点处理同理。

3.模板代码

#includeusing 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 intmod = 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.题目描述

   给定一棵由 nnn 个结点组成的树以及 mmm 个不重复的无序数对 ( a 1 , b 1 ) , ( a2, b2) , . . . , ( am, bm)(a1, b1), (a_2, b_2),. . . , (a_m, b_m)(a1,b1),(a2,b2),,(am,bm),其中 a iaiai 互不相同, bi b_ibi 互不相同, ai, bj( 1 ≤ i , j ≤ m )a_i , b_j(1 ≤ i, j ≤ m)ai,bj(1i,jm)
  小明想知道是否能够选择一条树上的边砍断,使得对于每个 ( a i , b i )(ai , bi)(ai,bi) 满足 a iaiai b ibibi 不连通,如果可以则输出应该断掉的边的编号(编号按输入顺序从 111 开始),否则输出 − 1-11

2. 解题思路

   又是 L C ALCALCA 模板题啊,但我之前没做过(反正也写不出 L C ALCALCA)。考虑一对无序数对的点 xxx yyy ,如果我们砍掉某条边可以让这两个点不连通,那么这条边一定是从 xxx yyy 路径上的一点,我们可以让从 xxx yyy 路径的边权值都加1。这个操作我们可以使用树上差分。 对于 mmm 个无序数对我们都如此操作,最后如果某条边的权值为 mmm 则说明它符合条件,我们选出符合条件编号最大的那条边就是答案,如果没有权值为 mmm 的边则说明无解。

3. 模板代码

#includeusing 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;}