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

忘是亡心i 2023-09-30 22:34 4阅读 0赞

#### 目录 ####

*  试题 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.  子序列的长度为  8 8 8；
 *  1.  . 这个子序列可以按照下标顺序组成一个  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.模板代码 ###

## 试题 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.模板代码 ###

## 试题 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.模板代码 ###

## 试题 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.模板代码 ###

## 试题 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.模板代码 ###

## 试题 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;
    }