第十四届蓝桥杯大赛软件赛省赛（C/C++B组）

---

部分题暂更补代码，欢迎评论区交流

---

试题 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. 子序列的长度为 $8$；
• 2. . 这个子序列可以按照下标顺序组成一个 $yyyymmdd$ 格式的日期，并且
     要求这个日期是 $2023$ 年中的某一天的日期，例如 $20230902，20231223$。
     $yyyy$ 表示年份，$mm$ 表示月份，$dd$ 表示天数，当月份或者天数的长度只
     有一位时需要一个前导零补充。

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

2.解题思路

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

3.模板代码

  暂更

试题 B.01 串的熵

1.题目描述

  没学过数学，暂更

2.解题思路

3.模板代码

试题 C. 冶炼金属

1.题目描述

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

2. 解题思路

  如果看过样例的话，显然答案两个上下界都是可以直接二分出来的。因为式子的结构都是 $\frac{A}{C}=B$。$A$ 是不变的，我们先考虑二分求最小的 $C$，因为需要保证所有式子的 $B$ 都不变，如果 $C$ 太小，显然会有某一组的 $B$ 增大，所以需要保证每一组都符合a[i]/x <= b[i]。反过来考虑求最大的 $C$, 如果 $C$ 太大，显然会有某一组的 $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$ 架飞机准备降落到某个只有一条跑道的机场。其中第 $i$ 架飞机在 $Ti$ 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 $Di$ 个单位时间，即它最早
可以于 $Ti$ 时刻开始降落，最晚可以于 $Ti+Di$ 时刻开始降落。降落过程需要 $Li$
个单位时间。
  一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不
能在前一架飞机完成降落前开始降落。
  请你判断 $N$ 架飞机是否可以全部安全降落。

2. 解题思路

   看 $N$ 最大为10，写了个全排列，T组数据复杂度还是炸了，暂更吧 。

3.模板代码

试题 E. 接龙数列

1.题目描述

   对于一个长度为 $K$ 的整数数列：$A_1,A_2,...,A_K$，我们称之为接龙数列当且仅当 $A_i$ 的首位数字恰好等于 $A_{i-1}$ 的末位数字 $(2\le i\le K)$。
   例如 $12,23,35,56,61,11$ 是接龙数列；$12,23,34,56$ 不是接龙数列，因为 $56$ 的首位数字不等于 $34$ 的末位数字。所有长度为 $1$ 的整数数列都是接龙数列。
   现在给定一个长度为 $N$ 的数列 $A_1,A_2,...,A_N$，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

2. 解题思路

   考场读完题的时候感觉有点奇怪，发现思路还是比较简单的。首先一个数我们只需要关注其首位数字和末位数字，定以 $f[i]$ 为以数字 $i$ 结尾的最长接龙序列的长度，$i$ 的范围是 $[0,9]$。对于每个数字设其首位数字为 $a$ ，末尾数字为 $b$，则有转移方程：
$$f[b]=max(f[b],f[a]+1)$$
   最后在 $f[0]、f[1]...f[9]$ 取一个最大值 $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.题目描述

   程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 $internation-alization$ 简写成 $i18n$，$Kubernetes$ （注意连字符不是字符串的一部分）简写成 $K8s,Lanqiao$ 简写成 $L5o$等。
   在本题中，我们规定长度大于等于 $K$ 的字符串都可以采用这种简写方法（长度小于 $K$ 的字符串不配使用这种简写）。
   给定一个字符串 $S$ 和两个字符 $c1$ 和 $c2$，请你计算 $S$ 有多少个以 $c1$ 开头 $c2$ 结尾的子串可以采用这种简写？

2. 解题思路

   这道题放在 G 题感觉更奇怪了，一道前缀和模板题。假设下标为 $i$ 的字符为 $c1$，那我们只需要统计在区间 $[i+k-1,n]$有多少个 $c2$ 即可，前缀和预处理一下 $c2$ 字符，直接累加答案即可，注意答案会爆int，复杂度 $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$ 的整数数列：$A_1,A_2,...,A_N$。你要重复以下操作 $K$ 次：
   每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
   输出 $K$ 次操作后的序列。

2. 解题思路

   感觉是比较典的题目，但是这题好像卡常，我的代码在非官方数据TLE了大半。用优先队列维护，存入值和下标，再用一个数组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$ 个景点，编号 $1$ 到 $N$。景点之间共有 $N-1$ 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
   小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 $K$ 个景点：$A_1,A_2,...,A_K$。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 $K-1$ 个景点。具体来说，如果小明选择跳过 $A_i$，那么他会按顺序带游客游览 $A_1,A_2,...,A_{i-1},A_{i+1},...,A_K,(1\le i\le K)$。
   请你对任意一个 $Ai$，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

2. 解题思路

   $LCA$ 模板题（问题是比赛写不出板子呢），首先肯定需要考虑求树上任意两点的距离。设点 $u,v$ 的最近公共祖先为 $z$，定义$f[i]$ 为点 $i$ 到根节点的距离，那么则有公式:
$$dist(u,v)=f[u]+f[v]-2\ast f[z]$$
   先求出不跳过任何的点时需要走的距离为ans以及任意相邻两个跳点的距离。假设我们跳过四个点分别为 $a,b,c,d$。当跳过的点为 $a$ 时，我们只需要用ans减去$a$到$b$的距离，当跳过的点为 $d$ 时，我们只需要用ans减去 $c$ 到 $d$ 的距离，这是首尾两个点的情况。
   那么当跳过的点为中间点呢？比如我们跳过的是 $b$，那么则需要用ans减去$a$到$b$以及$b$到$c$的距离，并且还需要加上$a$到$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<PII> 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 <= 15; 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 = 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];
}
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), w(m + 1);for (int i = 1; i <= m; ++i) cin >> g[i];LL ans = 0;for (int i = 1; i < m; ++i) {int u = g[i], v = g[i + 1];int z = lca(u, v);w[i] = f[u] + f[v] - 2 * f[z];ans += w[i];}for (int i = 1; i <= m; ++i) {if (i == 1) cout << ans - w[1] << " ";else if (i == m) cout << ans - w[m - 1] << " ";else {LL res = ans - w[i] - w[i - 1];int u = g[i - 1], v = g[i + 1];int z = lca(u, v);res += f[u] + f[v] - 2 * f[z];cout << res << " ";}}
}
int main()
{ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;
}

试题 J. 砍树

1.题目描述

   给定一棵由 $n$ 个结点组成的树以及 $m$ 个不重复的无序数对 $(a1,b1),(a_2,b_2),...,(a_m,b_m)$，其中 $ai$ 互不相同，$b_i$ 互不相同，$a_i,b_j(1\le i,j\le m)$。
   小明想知道是否能够选择一条树上的边砍断，使得对于每个 $(ai,bi)$ 满足 $ai$和 $bi$ 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 $1$ 开始），否则输出 $-1$。

2. 解题思路

   又是 $LCA$ 模板题啊，但我之前没做过（反正也写不出 $LCA$）。考虑一对无序数对的点 $x$ 和 $y$ ，如果我们砍掉某条边可以让这两个点不连通，那么这条边一定是从 $x$ 到 $y$ 路径上的一点，我们可以让从 $x$ 到 $y$ 路径的边权值都加1。这个操作我们可以使用树上差分。 对于 $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;
}