蓝桥杯真题训练-2023年省赛B组

2023年省赛题目B组

炼冶金属：

  • 描述：根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

  • 思路：根据情况很顺利地推导出逻辑，代码实现即可

  • 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;
int n, A, B, l = -INF, r = INF; 
int main()
{
	cin>>n;
	while(n--){
		cin>>A>>B;
		l = max(l, A/(B + 1) + 1);
		r = min(r, A/B);
	}
	cout<<l<<" "<<r<<endl;
	
	return 0;
}
  • 总结：并不难，主要是INF这里掌握不足，需要记住。

飞机降落：

  • 描述：请你判断 N 架飞机是否可以全部安全降落。
  • 思路：刚开始尝试贪心但是发现怎么都调不出来所有飞机的顺序，故而采取dfs遍历所有飞机的顺序，时间复杂度为O(N^2),主要注意book每次都要重置为0，不然会影响后面的使用。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int T, n, book[15]; 
struct node{
	int t;
	int d;
	int l;
}p[N];
int dfs(int step, int tim){
	if(step > n) return 1;
	for(int i = 1; i <= n; i++){
		if(book[i] == 1 ) continue;
		if(p[i].t + p[i].d < tim) return 0;
		book[i] = 1;
		if(dfs(step + 1, max(tim, p[i].t) + p[i].l)){
			return 1;
		}
		book[i] = 0;
	}
	return 0;
}
int main()
{
	cin>>T;
	while(T--){
		cin>>n;
		for(int i = 1; i <= n; i++){
			cin>>p[i].t>>p[i].d>>p[i].l;
		}
		memset(book,0,sizeof(book));
		if(dfs(1, 0)) cout<<"YES"<<endl;
		else cout<<"NO"<<endl; 
	}
	
	return 0;
}
  • 总结：for遍历dfs这种形式其实比较常见，注意要恢复现场，多多考虑清楚细节问题。

接龙数列：

  • 描述：给定一个数组，判断最少去掉多少个元素可以使剩余数列为接龙数列
  • 思路：最少不太好判断，可以转化一下思路，把解决的问题变为在原数组找最长的接龙子序列，那么就是一个线性dp问题了，把每个数字都当作字符串存储更容易使用。dp[c]表示以c为结尾的最长接龙子序列的长度，那么从头开始遍历序列,当前的字符串是s, dp[s[m-1] - 48] = max(dp[s[m-1] - 48], dp[s[0] - 48] + 1)。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
string s;
int dp[15], ans, n; 
int main()
{
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>s;
		int m = s.length();
		dp[s[m-1] - 48] = max(dp[s[m-1] - 48], dp[s[0] - 48] + 1);
	}
	for(int i = 0; i <= 9; i++){
		ans = max(ans, dp[i]);
	}
	cout<<n-ans<<endl;
	
	return 0;
}
  • 总结：还是觉得很神奇的线性DP,从头开始遍历竟然就可以逐步解决子序列的求解，太简洁有力了~

抓娃娃：

  • 描述：套圈，给取多个区间，多条线段，线段覆盖区间一半以上算是套中，问每个线段可以套中几个
  • 思路：套中其实相等于区间的中点在线段之内，那么求出所有的区间中点再前缀和一下，就可以O(1)求出套中的区间个数了。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int N = 1000050;
int n, m, mp[N]; 
int main()
{
	cin>>n>>m;
	for(int i = 1,l,r; i <= n; i++){
		cin>>l>>r;
		mp[l+r]++;
	}
	for(int i = 1; i <= N; i++){
		mp[i] = mp[i-1] + mp[i];
	}
	int l, r;
	while(m--){
		cin>>l>>r;
		l *= 2;
		r *= 2;
		cout<<mp[r] - mp[l-1]<<endl;  
	}
	
	return 0;
}
  • 总结：转化一下思路即可，注意求中点可能出现小数，最好都乘2来避免，这点已经不止一次遇到了。

子串简写：

  • 描述：子串Kubernetes可以简写成 K8s，我们规定长度大于等于 K 的字符串都可以采用这种简写方法。长度小于 K 的字符串不允许使用这种简写。给定一个字符串 S 和两个字符 c1 和 c2。请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写？
  • 思路：其实就是找对应的c1,c2组数，然后距离要大于等于k,为了降低时间复杂度，对c1的位置进行存储，然后找出最大的符合当前c2位置要求的位置。时间复杂度应当是NlogN。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define int long long
int k, ans;
string s;
char c1,c2;
vector<int> pc1;
signed main()
{
	cin>>k>>s>>c1>>c2;
	for(int i = 0; i < s.size(); i++){
		if(s[i] == c1){
			pc1.push_back(i);
		}
		if(s[i] == c2){
			if(i - k + 1 < 0 || pc1.size() == 0) continue;
			int l = 0, r = pc1.size() - 1;
			while(l < r){
				int mid = (l + r + 1)>>1;
				if(pc1[mid] <= i - k + 1) l = mid;
				else r = mid - 1;
			}
			if(pc1[l] <= i - k + 1){
				ans += l + 1;
			}
		}
	}
	cout<<ans<<endl;
	
	return 0;
}
  • 总结：通过二分很有效地降低了时间复杂度，而且很简洁明了。关于二分的题目还是要重视，其要求就是存在一个临界点，找出这个临界点。另外，发现题目必须开long long才能过。所以比赛的时候不管三七二十一，最好都写上#define int long long，这样子会避免失去不必要失去的分数。

01串的熵

  • 描述：对于一个长度为23333333 的 01 串，如果其信息熵为 11625907.5798，且 0 出现次数比 1 少，那么这个01 串中 0 出现了多少次？
  • 思路：模拟即可，0的个数0开始遍历，直到结果求出与所给的值一致
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n = 23333333;
	for(int i = 0; i <= n/2; i++){
		double x = (-1.0)*(1.0*i/n)*log2(1.0*i/n)*i;
		double y = (-1.0)*(n-i)/n*log2(1.0*(n-i)/n)*(n-i);
		if(x + y >= 11625907.5798 && x + y <= 11625907.5799){
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}
  • 总结：模拟并不困难，关键要注意整数型在进行除法运算时必须加入1.0这样的浮点数，否则会精度缺失；另外，最终的浮点数结果的判定也要选取x + y >= 11625907.5798 && x + y <= 11625907.5799这样的合理范围。

景区导游：

  • 描述：某景区一共有 N 个景点，编号 1 到 N。
    景点之间共有 N − 1 条双向的摆渡车线路相连，形成一棵树状结构。
    在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
    小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K 个景点：A1, A2, … , AK。 今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K − 1 个景点。
    具体来说，如果小明选择跳过 Ai，那么他会按顺序带游客游览A1, A2, … , Ai−1, Ai+1, … , AK; (1 ≤ i ≤ K)。
    请你对任意一个 Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

解法一：暴力求树上两点距离

  • 思路：通过dfs来求树上两点之间的距离，求出总的路线的sum，再遍历去掉每一个点，sum进行简单的加减。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int n, k, a[N], sum;
vector<PII> e[N];
map<PII, int> st;
bool dfs(int s, int cur, int last, int v, int sum){
	if(cur == v){
		st[{s, v}] = sum;
		st[{v, s}] = sum;
		return true;
	}
	for(int i = 0; i < e[cur].size(); i++){
		int x = e[cur][i].first;
		if(x == last) continue;
		int y = e[cur][i].second;
		if(dfs(s, x, cur, v, sum + y)){
			return true;
		}
	}
	return false;
}
signed main()
{
	cin>>n>>k;
	for(int i = 0,u,v,t; i < n - 1;i++){
		cin>>u>>v>>t;
		e[u].push_back({v, t});
		e[v].push_back({u, t});
	}
	for(int i = 0; i < k; i++) cin>>a[i];
	for(int i = 0; i < k - 1; i++){
		dfs(a[i], a[i], -1, a[i + 1], 0);
		sum += st[{a[i], a[i + 1]}];
	}
	int res;
	for(int i = 0; i < k; i++){
		if(i == 0){
			//dfs(a[i], a[i], -1, a[i + 1], 0);
			res = sum - st[{a[i], a[i + 1]}];
		}else if(i == k - 1){
			//dfs(a[i-1], a[i-1], -1, a[i], 0);
			res = sum - st[{a[i-1], a[i]}];
		}else{
			dfs(a[i-1], a[i-1], -1, a[i+1], 0);
			res = sum - st[{a[i-1],a[i]}] - st[{a[i], a[i+1]}] + st[{a[i-1], a[i+1]}];
		}
		cout<<res<<endl;
	}
	
	
	return 0;
}
  • 总结：是一种暴力解法，关键在于树上两点距离的dfs求解，其实这类题目的套路基本已经很熟悉了，还是要勇敢去做，去尝试。这是一道很棒的练手题~

解法二：树上前缀和+LCA

  • 思路：暴力的时间复杂度只要体现在每次都要dfs来求两点之间距离，可以利用树上前缀和，先预处理每个点到根节点的距离，那么两点间距离=sum[u]+sum[v]- 2*sum[lca(u,v)]。时间复杂度变为O(N)+O(logN)
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
int n, k, a[N], sum[N];
vector<PII> e[N];
int siz[N], dep[N], top[N], fa[N], son[N];
void dfs1(int u ,int father){//(1,0)
	siz[u] = 1;
	dep[u] = dep[father] + 1;
	fa[u] = father;
	for(int i = 0; i < e[u].size(); i++){
		int s = e[u][i].first;
		if(s == fa[u]) continue;
		dfs1(s, u);
		siz[u] += siz[s];
		if(siz[son[u]] < siz[s]){
			son[u] = s;
		}
	}
}
void dfs2(int u ,int t){//(1,1)
	top[u] = t;
	if(son[u] == 0) return;
	dfs2(son[u], t);
	for(int i = 0; i < e[u].size(); i++){
		int s = e[u][i].first;
		if(s == fa[u] || s == son[u]) continue;
		dfs2(s, s);
	}
}
int lca(int x, int y){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]){
			swap(x, y);
		}
		x = fa[top[x]];
	}
	return dep[x] < dep[y]? x : y;
}
void cal_sum(int u){
	for(int i = 0; i < e[u].size(); i++){
		int x = e[u][i].first;
		if(x == fa[u]) continue;
		int y = e[u][i].second;
		sum[x] = sum[u] + y;
		cal_sum(x);
	}
}

signed main()
{
	cin>>n>>k;
	for(int i = 0, u, v, t; i < n - 1; i++){
		cin>>u>>v>>t;
		e[u].push_back({v, t});
		e[v].push_back({u, t});
	}
	for(int i = 1; i <= k; i++){
		cin>>a[i];
	}
	dfs1(1, 0);
	dfs2(1, 1);
	
	cal_sum(1);
	
	int ans = 0;
	for(int i = 1; i <= k - 1; i++){
		int u = a[i], v = a[i + 1];
		int cost = sum[u] + sum[v] - 2*sum[lca(u,v)];
		ans += cost;
	}
	for(int i = 1; i <= k; i++){
		int tmp = ans, w = a[i - 1], u = a[i], v = a[i + 1];
		if(i == 1){
			tmp -= sum[u] + sum[v] - 2*sum[lca(u,v)]; 
		}else if(i == k){
			tmp -= sum[w] + sum[u] - 2*sum[lca(u,w)];
		}else{
			tmp = tmp - (sum[u] + sum[v] - 2*sum[lca(u,v)])-(sum[w] + sum[u] - 2*sum[lca(u,w)])
			+(sum[v] + sum[w] - 2*sum[lca(w,v)]);
		}
		cout<<tmp<<" ";
	}
	
	return 0;
}
  • 总结：看来lca的用途还是很广的，可以再多多联系以达到熟练的程度。可以和砍树这道题联合起来看。关键在于lca的板子熟练，目前基本可以敲下来了，还需要不时的练习。

整数删除：

  • 描述：给定一个长度为 N 的整数数列：A1, A2, … , AN。你要重复以下操作 K 次：
    每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。
    并把与它相邻的整数加上被删除的数值。
    输出 K 次操作后的序列

解法一：暴力模拟

  • 思路：直接对过程进行模拟，能拿到20%的分数，主要是相邻的数相加这里要考虑存在删除了的数，再加两个循环遍历。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f
const int N = 5e5 + 10;
int n, k, a[N], vis[N];
signed main()
{
	cin>>n>>k;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
	}
	while(k--){
		int minn = INF, pos = -1;
		for(int i = 1; i <= n; i++){
			if(vis[i]==0 && a[i] < minn){
				minn = a[i];
				pos = i;
			}
		}
		vis[pos] = 1;
		for(int j = pos - 1; j >= 0; j --)
		{
			if(!vis[j])
			{
				a[j] += minn;
				break;
			}
		}

		for(int j = pos + 1; j < n; j ++)
		{
			if(!vis[j])
			{
				a[j] += minn;
				break;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(vis[i] == 0){
			cout<<a[i]<<" ";
		}
	} 
	
	return 0;
}
  • 总结：能直接模拟出来快速拿到部分分也是个不错的选择，至少是个保底，当然能正确模拟也是很重要的。

解法二：链表+优先队列

  • 思路：暴力解法的时间复杂度主要体现在寻找最小值以及找未被删除的相邻节点，可以使用小根堆（优先队列）降低寻找最小值的时间复杂度为O(logN)，再用双向队列（两个数组）维护相邻节点。

  • 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 5e5 + 10;
int n, k, a[N], st[N], l[N], r[N]; 
signed main()
{
	cin>>n>>k;
	priority_queue<pii, vector<pii>, greater<pii>> q;
	for(int i = 0; i < n; i++){
		cin>>a[i];
		q.push({a[i], i});
		st[i] = a[i];
		l[i] = i - 1;
		r[i] = i + 1;
		if(i == n - 1) r[i] = -1;
	}
	
	while(k){
		pii t = q.top();
		q.pop();
		if(t.first != st[t.second]){
			q.push({st[t.second], t.second});
			continue;
		}
		k--;
		int pos = t.second;
		if(l[pos] >= 0) st[l[pos]] += t.first;
		if(r[pos] >= 0) st[r[pos]] += t.first;
		
		if(l[pos] >= 0) r[l[pos]] = r[pos];
		if(r[pos] >= 0) l[r[pos]] = l[pos];
		st[pos] = -1;
	}
	for(int i = 0; i < n; i++){
		if(st[i] != -1){
			cout<<st[i]<<" ";
		}
	}
	return 0;
}
  • 总结：一些细节问题可以学习，比如修改值，就是先取，发现值有了更新就加上放回去再重新取，直到没有改变多了，再k–,这点很巧妙。这是由于小根堆的特点，取最小值比较快。不能直接找出那个要加的值，取出再放回，那么小根堆就失去优势了。

砍树：

解法一：暴力53%

  • 描述：给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对(a1, b1), (a2, b2), … , (am, bm)，其中 ai 互不相同，bi 互不相同，ai ≠ bj(1 ≤ i, j ≤ m)。
    小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai, bi) 满足 ai 和bi 不连通。
    如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开始），否则输出-1。
  • 思路：根据描述，对于每一对序号，找到它们的公共边即可实现，那怎么找呢？可以dfs每对序号，从一端找到另一端，在dfs的过程中标记走过的边，最终边的权重为m的就是在删除范围内的边了，再找到编号最大的即可。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int ,int> PII;
const int N = 1e5 + 10; 
int n, m, w[N];
vector<int> e[N];
map<PII, int> id;
bool dfs(int s, int u, int father, int v){
	if(u == v) return true;
	for(int i = 0; i < e[u].size(); i++){
		int cur = e[u][i];
		if(cur == father) continue;
		if(dfs(s, cur, u, v)){
			int ID = id[{cur, u}];
			w[ID]++;
			return true;
		}
	}
	return false;
}
signed main()
{
	cin>>n>>m;
	for(int i = 0, u, v; i < n-1; i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
		id[{u,v}] = i;
		id[{v,u}] = i;
	}
	for(int i = 0, u, v; i < m; i++){
		cin>>u>>v;
		dfs(u,u,-1,v); 
	}
	int ans = -1;
	for(int i = n-1; i>=0; i--){
		if(w[i] == m){
			ans = i + 1;
			break;
		}
	}
	cout<<ans<<endl;
	return 0;
}
  • 总结：思路并不难，但是一遇到树就容易犯怵，一点想法也没有，其实刚开始不要给自己太大压力，就慢慢一步一步地想，去模拟样例是怎么实现的，再去和dfs联系起来，熟能生巧叭~

解法二：lca+树上差分

  • 思路：优化给边打标记的过程，先边权转化为点权，对于一对序号，对它的两个端点序号++，它们的公共祖先序号-2，最后对每个点点权进行累计为它为根的所在子树的权重即可，边就是这个点上面的一条边。使用树链剖分来实现lca。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
int n, m, w[N];
vector<int> e[N];
map<pii, int> id;

int siz[N], top[N], dep[N], fa[N], son[N];
void dfs1(int u, int father)
{
	siz[u] = 1, dep[u] = dep[father] + 1;
	fa[u] = father;
	for(int i = 0; i < e[u].size(); i ++)
	{
		int s = e[u][i];
		if(s == fa[u])
			continue;
		dfs1(s, u);
		siz[u] += siz[s];
		if(siz[son[u]] < siz[s])
			son[u] = s;
	}
}

void dfs2(int u, int t)
{
	top[u] = t;
	if(son[u] == 0)
		return;
	dfs2(son[u], t);
	for(int i = 0; i < e[u].size(); i ++)
	{
		int s = e[u][i];
		if(s == fa[u] || s == son[u])
			continue;
		dfs2(s, s);
	}
}

int lca(int x, int y)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]])
			swap(x, y);

		x = fa[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}

void cal_sum(int u, int father)
{
	for(int i = 0; i < e[u].size(); i ++)
	{
		int son = e[u][i];
		if(son == father)
			continue;
		cal_sum(son, u);
		w[u] += w[son];
	}
}

signed main()
{
	cin>>n>>m;
	for(int i = 1; i <= n - 1; i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
		id[{x,y}] = id[{y,x}] = i;
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for(int i = 0; i < m; i++){
		int a,b;
		cin>>a>>b;
		w[a]++;
		w[b]++;
		w[lca(a,b)] -= 2;
	}
	cal_sum(1, 0);
	int ans = -1;
	for(int i = 1; i <= n; i++){
		if(w[i] == m){
			int ID = id[{i, fa[i]}];
			ans = max(ID, ans);
		}
	}
	cout<<ans<<endl;
	return 0;
}
  • 总结：一个是lca,一个是树上差分，树上差分主要用于树上一段路径的+1，需要熟悉模板以及解决问题的思路是怎么推出来的，很有挑战的一道题目，但是可以理解的。模板要尽可能地熟练。
算法
#蓝桥杯
蓝桥杯真题训练-2023年省赛B组
http://example.com/2024/03/11/蓝桥杯省赛备赛/蓝桥杯真题训练-2023年省赛B组/
作者
jhxxxxx
发布于
2024年3月11日
许可协议