[数据结构与算法]2022十三届蓝桥杯国赛题解

						**特此声明，本文仅为参考文档，标准答案请参考官方文档**

试题A

该题是一道背包dp题，我的思路是定义三维dp，第一维表示第i个数，第二维表示前i个数的总和为j，第三维表示前i个数，总和为j,第i个数为z的方案数。

首先观察这个题的性质，要求互不相同，首先我们需要找一个严格递增的序列，并且序列的总和为2022
刚开始我也是想到的一个O(n³)的dp 状态转移，但是我们发现其中一维可以通过优化去掉变成O(n²)dp，然后成功算出答案。
需要注意的是需要开$longlong$因为答案太大爆int

然后推出方程式：
$$if(k>z)continue;//表明当前总和装不下当前项$$
$$if(kandz>=k)//我们可以给当前枚举项加一构造新的方案$$
$$f[i][z][k]+=f[i?1][z?k][k?1];$$
$$if(zandk)//表明我们选的当前项必须比上一项严格大$$
$$f[i][z][k]+=f[i][z?1][k?1];$$

代码如下

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std ;

long long ans ;
long long f[20][3000][3000] ; // 个数 总和 上一项

int main(void){
	f[0][0][0] = 1 ;
	for(int i = 1 ; i <= 10 ; i ++)
		for(int z = 0 ; z <= 2022 ; z ++)
			for(int k = 0 ; k <= 2022 ; k ++){
				if(k > z) continue ;
				if(k && z >= k)
					f[i][z][k] += f[i - 1][z - k][k - 1] ;
				if(z && k)
					f[i][z][k] += f[i][z - 1][k - 1] ;
			}
	for(int i = 0 ; i <= 2022 ; i ++)
		ans += f[10][2022][i] ;
	cout << ans << endl ;
}

答案为

379187662194355221

试题B

这道题首先我们可以观察到，这是一道枚举题目，暴力枚举即可。
主要注意的地方有，时针转一周的过程中，每经过$1s$转动的角度是$360?(1/(60?60?12))$,我们需要把每秒转动的角度也要算出来。分针转一周的过程中，每经过$1s$转动的角度是 $360?(1/(60?60))$ , 秒钟则是 $360?(1/60)$ 。

于是我们可以很愉快的运行我的代码 , 发现结果只有两个，一个是$0,0,0$ , 一个是$4,48,0$。[$，$代表空格]
于是我们得到的答案是

4 48 0

代码如下

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std ;

const double eps = 1e-8 ;

double get(int a , int b , int c){
	return 360.0 * (a * 3600 + b * 60 + c) / (3600 * 12) ;
}

double get(int b , int c){
	return 360.0 * (b * 60 + c) / 3600 ;
}

double get(int c){
	return 360.0 * c / 60 ;
}

int main(void){
	// cout << get(30 , 0) << endl ;
	for(int i = 0 ; i <= 6 ; i ++)
		for(int j = 0 ; j <= 59 ; j ++)
			for(int z = 0 ; z <= 59 ; z ++){
				double a = get(i , j , z) ;
				double b = get(j , z) ;
				double c = get(z) ;
				double x = abs(a - b) ;
				double y = abs(c - b) ;
				if(x > 180) x = 360 - x ;
				if(y > 180) y = 360 - y ;
				if(fabs(x - 2 * y) < eps){
					cout << i << " " << j << " " << z << endl ;
				}
			}
}

试题C

首先观察这个题目，我们可以发现这是类似于贪心的思想。
我们肯定先把最小的坑填满，类似于灌水一样，然后慢慢的统计层数。
我们第一个策略是先排序，按照大小从小到大排序。
但是题目中加了一给数组b限制，我们不能简单的去求解答案。
但是我们如何去利用数组b呢，我们发现ai + bi是该列最多能摆放的层数。
于是我们先求
$$min(ai+bi)i为[1,n]$$
这是答案的最大值

然后我们先排序好之后，我们开始我们的模拟过程，因为排好序之后是递增的，所以我们就按照高度顺序一个一个递增地去模拟灌溉过程。最后算出来的答案$ans$要加上$a[1]$表示当前仅灌溉能够获得的最大高度。

然后最后的结果就是$min(ans+a[1],ans1)$
当考虑到数据又2e5的时候，用快读会明显提升代码运行速度。

代码如下

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std; 

typedef long long LL ;

const int N = 2e5 + 10 ;
const int Inf = 1e9 + 10 ;

int a[N] , b[N] ;

int read(){
	int res = 0 , flag = 1 ;
	char c = getchar() ;
	while(!isdigit(c)){
		if(c == '-') flag = -1 ;
		c = getchar() ;
	}
	while(isdigit(c)){
		res = (res << 1) + (res << 3) + (c ^ 48) ;
		c = getchar() ;
	}
	return res * flag ; 
}

int main(void){
	int n ;
	LL m ;
	scanf("%d%lld" , &n , &m) ;
	for(int i = 1 ; i <= n ; i ++) a[i] = read() ; 
	for(int i = 1 ; i <= n ; i ++) b[i] = read() ;
	int ans = a[1] + b[1] ;
	for(int i = 2 ; i <= n ; i ++)
		ans = min(ans , a[i] + b[i]) ;
	sort(a + 1 , a + 1 + n) ;
	int ans1 = 0 ; 
	a[n + 1] = Inf ; 
	for(int i = 1 ; i <= n ; i ++){
		int j = i ;
		while(j <= n && a[i] == a[j]) j ++ ;
		j -- ;
		long long tot = (a[j + 1] - a[j]) * 1ll * j ;
		if(m >= tot) {
			ans1 += a[j + 1] - a[j] ;
			 m -= tot ;
		} 
		else {
			ans1 += m / j ; 
			break ;
		}
		i = j ; 
	}
	printf("%d\n" , min(ans , ans1 + a[1])) ;	
	return 0 ;	
}

试题D

这道题应该是一道比较隐晦的背包dp 。
思路如下
首先我们先找出背包dp所需的两种条件，一个是花费$w$，一个是价值$v$
首先我们可以观察到这个题目的两个方法是$加$和$减$,我们可以把这个看成分组背包模型，然后代价是到某一个数所需的最少次数。
计算方式如下

int get(int x , int mod){
	return (x % mod + mod) % mod ;
}

for(int p = 0 ; p <= 9 ; p ++)
{
	int t = s[i] - '0' ;
	int x = get(p - t , 10) ;
	int y = get(t - p , 10) ;
}

p是我们枚举当前位置的放的数字，然后我们开始讨论价值，首先把数放在首部的价值是，我们把整个数的长度为n , 第一个数的价值就为10 ^n-1 * p 。 剩下的数字的价值以此类推。

于是一道不是很明显的背包dp的代码如下
注意：本题需要开long long

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std ;

const int N = 20 ;
const int M = 110 ;

typedef long long LL ;

LL f[N][M][M] ;
char s[N] ;
int a , b ;
long long f10[20] ;

int get(int x , int mod){
	return (x % mod + mod) % mod ;
}
int main(void){
	scanf("%s" , s + 1) ;
	scanf("%d%d" , &a , &b) ;
	f10[0] = 1 ;
	for(int i = 1 ; i <= 18 ; i ++)
		f10[i] = f10[i - 1] * 10 ;
	int n = strlen(s + 1) ;
	for(int i = 1 ; i <= n ; i ++)
		for(int p = 0 ; p <= 9 ; p ++)
		{
			int t = s[i] - '0' ;
			int x = get(p - t , 10) ;
			int y = get(t - p , 10) ;
			for(int j = 0 ; j <= a ; j ++)
				for(int k = 0 ; k <= b ; k ++){
					if(j >= x) f[i][j][k] = max(f[i][j][k] , f[i - 1][j - x][k] + f10[n - i] * p) ;
					if(k >= y) f[i][j][k] = max(f[i][j][k] , f[i - 1][j][k - y] + f10[n - i] * p) ;
				}
		}
	printf("%lld" , f[n][a][b]) ;
	return 0 ;
}

试题E

首先题目的描述中我们已经可以观察到该题是一道裸的单源最短路问题，但是加了一个隔离时间的限制，我们需要改变单源最短路的一些变量去满足题目要求，首先我们观察到边的价值改变了，从i - j 的代价我们应该是道路的代价+j的隔离时间，然后这样逐渐转移我们可以通过当前的图去跑最短路求出解，不过边的代价如果是一个点走到终点$n$的花费不再是边权加上当前的隔离时间，因为我们不需要从终点隔离走向下一点。
加边过程

	for(int i = 1 ; i <= m ; i ++){
		int a , b , c; 
		scanf("%d%d%d" , &a , &b , &c) ;
		if(b != n)
			add(a , b , c + ci[b]) ;
		else 
			add(a , b , c) ;
		if(a != n)
			add(b , a , c + ci[a]) ;
		else 
			add(b , a , c) ;
	}

代码如下

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>

#define x first
#define y second 

using namespace std ;

const int N = 1e5 + 10 ;
const int M = 2 * N ;
typedef pair<int , int> PII ;

int h[N] , e[M] , ne[M] , idx ;
int w[M] , ci[N] ;
bool st[N] ;
int dist[N] ;

int read(){
	int res = 0 , flag = 1 ;
	char c = getchar() ;
	while(!isdigit(c)){
		if(c == '-') flag = -1 ;
		c = getchar() ;
	}
	while(isdigit(c)){
		res = (res << 1) + (res << 3) + (c ^ 48) ;
		c = getchar() ;
	}
	return res * flag ; 
}

void add(int a , int b , int c) {
	e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++ ; 
}

int main(){
	memset(h , -1 , sizeof h) ;
	int n , m ;
	scanf("%d%d" , &n , &m) ;
	for(int i = 1 ; i <= n ; i ++) ci[i] = read() ;
	for(int i = 1 ; i <= m ; i ++){
		int a , b , c; 
		scanf("%d%d%d" , &a , &b , &c) ;
		if(b != n)
			add(a , b , c + ci[b]) ;
		else 
			add(a , b , c) ;
		if(a != n)
			add(b , a , c + ci[a]) ;
		else 
			add(b , a , c) ;
	}
	memset(dist , 0x3f ,sizeof dist) ;
	priority_queue<PII , vector<PII> , greater<PII>> q ;
	dist[1] = 0 ;
	q.push({0 , 1}) ;
	PII t ;
	while(q.size()){
		t = q.top() ;
		q.pop() ;
		int d = t.x , ver = t.y ;
		if(st[ver]) continue ;
		st[ver] = true ;
		for(int i = h[ver] ; ~i ; i = ne[i]){
			int j = e[i] ;
			if(dist[ver] + w[i] < dist[j]){
				dist[j] = dist[ver] + w[i] ;
				q.push({dist[j] , j}) ;
			}
		}
	}
	printf("%d" , dist[n]) ;
	return 0 ;
}

试题F

这是一道非常显眼的背包dp。
这是一种类似于判断背包dp，判断是否能组成某一个数之类的dp。
定义两维dp ， 表示前i个能否组成j。
状态转移方程为
$$if(i>=kandj>=cost[cnt].y)f[i][j]|=f[i?k][j?cost[cnt].y];$$
$$elseif(i<kandj==cost[cnt].y)$$
$$f[i][j]|=true;$$
需要注意的细节是从后往前枚举最接近m的答案。

于是代码如下

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

#define x first
#define y second 

using namespace std ;

const int N = 20 ;
const int M = 8010 ;
const int K = 1010 ;
const int Inf = 1e9 + 10 ;

typedef pair<int , int> PII ;

int day[N] = {0 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31} ;

PII cost[M] ; 
int f[K][M] ;

int get(int a , int b){
	return day[a - 1] + b ;
}

int main(void){
	for(int i = 1 ; i <= 12 ; i ++){
		day[i] += day[i - 1] ;
	}
	int n , m , k ;
	scanf("%d%d%d" , &n , &m , &k) ;
	for(int i = 1 ; i <= n ; i ++){
		int mi , di , vi ;
		scanf("%d%d%d" , &mi , &di , &vi) ;
		cost[i] = {get(mi , di) , vi} ;
	}
	sort(cost + 1 , cost + 1 + n) ;
	int cnt = 1 ;
	f[0][0] = 1 ;
	for(int i = 1 ; i <= 365 ; i ++){
		for(int j = 0 ; j < M ; j ++) f[i][j] |= f[i - 1][j] ;
		while(cnt <= n && cost[cnt].x == i){
			for(int j = 0 ; j < M ; j ++){
				if(i >= k && j >= cost[cnt].y) f[i][j] |= f[i - k][j - cost[cnt].y] ;
				else if(i < k && j == cost[cnt].y){
					f[i][j] |= true ;
				}
			}
			++ cnt ;
 		}
	}
	int Min = Inf ;
	int ans ;
	for(int i = M - 1 ; i >= 0 ; i --)
		if(f[365][i] && abs(i - m) < Min){
			Min = abs(i - m) ;
			ans = i ;
		}
	printf("%d" , ans) ;
	return 0 ;
}

试题G


这道题的描述可能有问题，我重新定义新的描述(仅为我的理解)，首先第一行应该表示为若发生故障为$i$的概率为$pi$ ，然后每一行每一列同题意。

然后我们这道题应该是一道条件概率的题目，首先我们要算出所有会出现故障的情况，然后除以条件概率即可。

首先我们算出如果a出现故障，而且只出现在第三列的概率为
$$0.3?1?0.5?0.33?0.75?1.0$$
除了第三列剩下的全为$1?pi$
剩下的几行方法一致
注意的是如果不存在直接输出结果，否则会出现浮点错误

代码如下

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

#define x first
#define y second 

using namespace std ;

typedef pair<long double ,int> PII ;

const int N = 50 + 10 ;
const double eps = 1e-8 ;

int pi[N] ;
int pij[N][N] ;
long double ans[N] ;
bool st[N] ;
PII tt[N] ;

bool cmp(PII a , PII b){
	if(fabs(a.x - b.x) > eps) return a.x > b.x ;
	return a.y < b.y ;
}
int main(void){
	// double a = 0.3 * 0.33 * 0.5 * 0.75;
	// double b = 0.2 * 0.35 * 0.7 ;
	// cout << a << " " << b << endl ;
	// cout << b / (a + b) << endl ;
	int n , m ;
	scanf("%d%d" , &n , &m) ;
	for(int i = 1 ; i <= n ; i ++) scanf("%d" , &pi[i]) ;
	for(int i = 1 ; i <= n ; i ++) 
		for(int j = 1 ; j <= m ; j ++)
			scanf("%d" , &pij[i][j]) ;
	int k ;
	scanf("%d" , &k) ;
	for(int i = 1 ; i <= k ; i ++){
		int x ;
		scanf("%d" , &x) ;
		st[x] = true ;
	}
	for(int i = 1 ; i <= n ; i ++){
		ans[i] = 1 ;
		for(int j = 1 ; j <= m ; j ++)
			if(st[j])
				ans[i] = ans[i] * pij[i][j] / 100 ;
			else 
				ans[i] = ans[i] * (100 - pij[i][j]) / 100 ;
		ans[i] = ans[i] * pi[i] / 100 ;
	}
	double tot = 0 ;
	for(int i = 1 ; i <= n ; i ++) tot += ans[i] ;
	if(fabs(tot) < eps){
		for(int i = 1 ; i <= n ; i ++){
			printf("%d 0.00\n" , i) ;
		}
		return 0 ;
	}
	for(int i = 1 ; i <= n ; i ++) ans[i] = ans[i] * 100 / tot ;
	for(int i = 1 ; i <= n ; i ++) tt[i] = {ans[i] , i} ;
	sort(tt + 1 , tt + 1 + n , cmp) ;
	for(int i = 1 ; i <= n ; i ++){
		printf("%d %.2Lf\n" , tt[i].y , tt[i].x) ;
	}
	return 0 ;
}

试题H

这道题目偏套路，这是一个类似于树的前缀的一道题目。
首先我们假定1为根，然后维护从节点i到根的路径节点所有的度数之和。我们假设为数组g
然后答案为
$$g[a]+g[b]?2?g[lca(a,b)]+d[lca(a,b)]$$
需要注意的是如果当前$a==b$我们直接输出1即可
用倍增维护lca即可
代码如下

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std; 

const int N = 1e5 + 10 ;
const int K = 20 ;
const int M = 2 * N ;

int f[N][K] ;
int sz[N] ;
int h[N] , e[M] , ne[M] , idx ;
long long g[N] ;
int dep[N] ;
int d[N] ;

void add(int a , int b){
	e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}

int lca(int a , int b){
	if(dep[a] < dep[b]) 
		swap(a , b) ;
	for(int k = K - 1 ; k >= 0 ; k --)
		if(dep[f[a][k]] >= dep[b]){
			a = f[a][k] ;
		}
	if(a == b) {
		return a ;
	}
	for(int k = K - 1 ; k >= 0 ; k --)
		if(f[a][k] != f[b][k]){
			a = f[a][k] ;
			b = f[b][k] ;
		}
	return f[a][0] ;
}

void dfs(int u , int v){
	sz[u] = 1 ;
	dep[u] = dep[v] + 1 ;
	g[u] = d[u] + g[v] ;
	for(int i = h[u] ; ~i ; i = ne[i]){
		int j = e[i] ;
		if(j == v) continue ;
		f[j][0] = u ;
		for(int k = 1 ; k < K ; k ++)
			f[j][k] = f[f[j][k - 1]][k - 1] ;
		dfs(j , u) ;
	}
}

int main(){
	memset(h , -1 , sizeof h) ;
	int n , m ;
	scanf("%d%d" , &n , &m) ;
	for(int i = 1 ; i < n ; i ++){
		int a , b ;
		scanf("%d%d" ,&a , &b) ;
		add(a , b) ;
		add(b , a) ; 
		d[a] ++ , d[b] ++ ;
	}
	dfs(1 , 1) ;
	for(int i = 1 ; i <= m ; i ++){
		int a , b; 
		scanf("%d%d" , &a , &b) ;
		int c = lca(a , b) ;
		if(a != b)
			printf("%lld\n" , g[a] + g[b] - 2 * g[c] + d[c]) ;
		else 
			printf("1\n") ;
	}
	
	
	return 0 ;
}

试题i

这是一道比较偏套路的一道题。
其实大部分同学在观察完题目之后，应该可以发现的规律时最后转速之比一定为首项/末项
为什么呢
首先我们观察样例，样例为

2   3  3   4
- * - * - *  =  2 
3   3   4  1

我们也可以转换为，消除第i的分母和i + 1的分子，然后消完之后最后为首项/末项
这道题就转换为找两个数，他们数的商能否组成我们查询的数
这道题套路性的想到了用筛法的性质，筛法本身时对一个数和一个数的因子的筛。
然后筛法还有非常优秀的时间复杂度为$O(nlogn)$
于是筛法做法出来了，该题解法为

void init(){
	for(int i = 1 ; i < N ; i ++){
		if(Hash[i]){
			for(int j = i ; j < N ; j += i)
				if(Hash[j])
					ans[j / i] = true ;
		}
	}
}

代码如下

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm> 

using namespace std; 

const int N = 2e5 + 10 ;

bool Hash[N] ;
bool ans[N] ;

void init(){
	for(int i = 1 ; i < N ; i ++){
		if(Hash[i]){
			for(int j = i ; j < N ; j += i)
				if(Hash[j])
					ans[j / i] = true ;
		}
	}
}

int main(void){
	int n , m ;
	scanf("%d%d" ,&n , &m) ;
	for(int i = 1 ; i <= n ; i ++){
		int x ;
		scanf("%d" , &x) ;
		Hash[x] = true ;
	}
	init() ;
	for(int i = 1 ; i <= m ; i ++){
		int x ;
		scanf("%d" , &x) ;
		if(ans[x]) puts("YES") ;
		else puts("NO") ;
	}
	return 0 ;
}

试题J

这道题也是一道隐晦的背包dp
首先我们观察一下题目，我们如果要是价值最大，我们肯定要把价值小的放在前面，并且价值相同的时候。
首先我们推式子
i表示前面部分，j表示后面部分

	wi + si <= vj
	wj + si <= vi 

我们很难发现规律
转换一下

	wi - vj <= si 
	wj - vi <= si

我们可以发现，相邻的两个wi - vj的值越小越好。于是重写cmp

bool cmp(PII a , PII b){
	int t = a.x - b.y ;
	int t1 = b.x - a.y ;
	return t < t1 ;
}

然后我们排好序之后，我们可以显然的发现这是一道裸的背包dp，然后我们直接对其dp即可。
题目要求当前价值一定大于重量总和，我们在状态转移时加一个判断即可。

$$f[i][j]=f[i?1][j];$$
$$if(j>=wandv>=j?w)$$
$$f[i][j]=max(f[i][j],f[i?1][j?w]+v);$$

最后代码如下

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

#define x first
#define y second 

using namespace std ;

const int N = 1010 ;
const int M = 2e4 + 10 ;

typedef pair<int , int> PII ;

int f[N][M] ;
PII cost[N] ;

bool cmp(PII a , PII b){
	int t = a.x - b.y ;
	int t1 = b.x - a.y ;
	return t < t1 ;
}
int main(){
	int n ;
	scanf("%d" , &n) ;
	for(int i = 1 ; i <= n ; i ++){
		int a , b ;
		scanf("%d%d" , &a , &b) ;
		cost[i] = {a , b} ;		
	} 
	sort(cost + 1 , cost + 1 + n , cmp) ;
 	for(int i = 1 ; i <= n ; i ++){
		int w = cost[i].x ;
		int v = cost[i].y ;
		for(int j = 0 ; j < M ; j ++){
			f[i][j] = f[i - 1][j] ;
			if(j >= w && v >= j - w){
				f[i][j] = max(f[i][j] , f[i - 1][j - w] + v) ;
			}
		}
	}
	int ans = 0 ;
	for(int i = 0 ; i < M ; i ++)
		ans = max(ans , f[n][i]) ;
	printf("%d" , ans) ;
	return 0 ;
}