C/C++教程

第十三届蓝桥杯c++b组国赛题解(还在持续更新中...)

本文主要是介绍第十三届蓝桥杯c++b组国赛题解(还在持续更新中...),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

试题A:2022

解题思路:

 有2022个物品,它们的编号分别是1到2022,它们的价值分别等于它们的编号。也就是说,有2022种物品,物品价值等于物品编号。

从2022个物品种选取10个物品,满足10个物品的价值之和为2022,用f[i][j][k]表示前i个物品里选择j个物品,价值之和为k的方案数 则对于前i种物品,有两种选择,选或者不选 f[i][j][k]=f[i-1][j][k] 不选 f[i][j][k]=f[i-1][j-1][k-i] 选 (为什么是k-i,因为第i个物品的体积就是i)

最后的答案是:379187662194355221

注意:本题记得开long long,不然真见祖宗了,hh

代码实现:

三维未优化空间(此代码只能在本地跑结果,直接交蓝桥杯官网测评会爆空间)

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=2500;
//dp[i][j][k]表示从前i件物品中选,每件物品的价值等于其编号,且当前选了j件物品,且当前价值为k的所有选法数 
int dp[N][15][N];
signed main(){
	//因为价值k为0,所以只有一种选法:就是啥也不选 
	for(int i=0;i<N;i++)dp[i][0][0]=1;
	for(int i=1;i<=2022;i++){
		for(int j=1;j<=10;j++){
			for(int k=1;k<=2022;k++){
				//不选第i个物品 
				dp[i][j][k]=dp[i-1][j][k];
				//选第i个物品 
				if(k>=i)dp[i][j][k]+=dp[i-1][j-1][k-i];
			}
		}
	}
	cout<<dp[2022][10][2022]<<endl;
	return 0;
}

二维优化空间:

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=2500;
int dp[15][N];
signed main(){
	dp[0][0]=1;
	for(int i=1;i<=2022;i++){
		for(int j=10;j>=1;j--){
			for(int k=i;k<=2022;k++){
				//不选第i个物品和不选第i个物品 
				dp[j][k]=dp[j][k]+dp[j-1][k-i];
			}
		}
	}
	cout<<dp[10][2022]<<endl;
	return 0;
}

试题B:钟表

解题思路:

for循环枚举时针(i)、分针(j)、秒针位置(k),计算三个针的角度

秒针的角度就是:s=360*k/60

分针的角度就是:m=360*j/60+s/60,因为秒针也会为分针贡献角度

时针的角度就是:h=360*i/12+m/12,因为分针也会为时针贡献角度

然后计算分针和时针的夹角A,分针的夹角B,为了让夹角A和夹角B能够处于同一个方向,A和B都取较小的半角

最后通过A-2B是否相等判断是否满足条件

注意:

1)double相减存在误差,最好不要直接判断相等

2)当 时、分、秒都为0时虽然也满足条件,但是题目要求找出的是一个0 时 0 分 0 秒以外的解,故时、分、秒同时为0的情况需要跳过

代码实现:

#include<bits/stdc++.h>
using namespace std;

int main() 
{
    for(int s=0;s<=6;++s){
        for(int f=0;f<60;++f){
            for(int m=0;m<60;++m){
                if(s==0&&f==0&&m==0) continue;
                double dm=360*m/60;
                double df=360*f/60+dm/60;
                double ds=360*s/12+df/12;
                double A=abs(df-ds),B=abs(df-dm);
                //取小的角度
                A=min(A,360-A);
                B=min(B,360-B);
                if(fabs(A-2*B)<=1e-10){
                    printf("%d %d %d\n",s,f,m);
                }
            }
        }
    }
    return 0;
}

试题C:卡片

解题思路:

二分枚举能够凑出的套牌数mid,通过check函数判断是否满足要求,如果满足要求,因为题目要求套牌数量最大化,故还得加大套牌数mid,继续判断是否满足条件,直到找不到比当前更大且满足条件的套牌数

check函数主要判断当前已有卡牌a[i]和当前可以手写的卡牌i的数量b[i]之和是否大于等于套牌数mid,如果小于,则一定不满足,否则统计当前总共需要的手写的卡牌数,最后判断总共手写的卡牌数是否小于等于题目中给的空白卡牌数,如果是则表示满足,否则表示不满足

代码实现:

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=2e5+5;
int a[N],b[N];
int n,m;
int check(int x){
    int temp=0;
    for(int i=0;i<n;i++){
    	//如果当前第i种卡牌已经满足条件,则第i种卡牌不需要消耗空白卡牌 
        if(x<=a[i])continue;
        //如果当前第i种卡牌就算用上所有能够手写第i种卡牌的空白卡牌仍然不满足条件,则直接返回false 
        if(x>a[i]+b[i])return 0;
        //否则统计当前用了多少张空白卡牌来手写第i种卡牌 
        temp+=x-a[i];
    }
    //如果使用的空白卡牌数超过了题目中提供的空白卡牌数m,则直接返回false 
    if(temp>m)return 0;
    //否则表示满足,返回true 
    else return 1;
}
signed main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    int l=0,r=2e5+5;
    while(l<r){
        int mid=l+r+1>>1;
        //如果当前套牌数满足条件,继续加大套牌数 
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}

试题D:最大数字

解题思路:

dfs暴力搜索即可,因为要求数字进行上述操作后的数值最大可知,优先从左往右进行操作一定是最右的操作顺序

对于每个数位,如果当前数位能够通过减法操作变成9,那么肯定将当前数位变为9

否则肯定不用减法操作,因为在不满足上述条件基础上使用减法操作一定会使得数值减小。如果当前加法操作能够使得当前数值x变成[x+1,9],则一定使用加法操作使其变成上述数值,但是不能超过上述数值,因为超过后会从0开始,数值就会减小

注意:

1)本题数值比较大,记得使用字符串存储和操作

2)每次递归记得恢复现场即可

代码实现:

#include<iostream>
#include<algorithm>
using namespace std;
string s,ans;
int a,b;
void dfs(int idx,int a,int b){
	//如果已经遍历完了整个数字的每一位,则更新最大值,并返回 
	if(idx>s.size()){
		ans=max(ans,s);
		return;
	}
	//当前数位通过减法操作变成9所需要的操作次数t 
	int t=s[idx]-'0'+1;
	//如果当前拥有的减法操作次数大于上述操作次数t,则将当前位变成9 
	if(b>=t){
		//保留现场 
		int temp=s[idx];
		//将当前位变成9
		s[idx]='9';
		//递归操作下一位,当前拥有的减法操作次数减少t次 
		dfs(idx+1,a,b-t);
		//恢复现场 
		s[idx]=temp;
	}
	//当前数位x通过加法操作变成[x+1,9]所需要的操作次数t1
	int t1=min(9-(s[idx]-'0'),a);
	////如果当前拥有的加法操作次数大于上述操作次数t1,则使用加法操作修改当前位 
	if(a>=t1){
		//保留现场 
		int temp=s[idx];
		//修改当前位 
		s[idx]=s[idx]+t1;
		//递归操作下一位,当前拥有的加法操作次数减少t1次 
		dfs(idx+1,a-t1,b);
		//恢复现场 
		s[idx]=temp;
	}
}
int main(){
	cin>>s>>a>>b;
	dfs(0,a,b);
	cout<<ans<<endl; 
	return 0;
}

试题E:最大数字

解题思路:

最短路模板题,送分题,个人评价,不喜勿喷,hh

注意点:

1)需要建立双向边

2)建立从u到v的双向边时:

  1.建立从u到v的单向边,将当前道路的开销设置为城市 到城市 v 的时间加上在城市v隔离观察花费的时间即可

  2.建立从v到u的单向边,将当前道路的开销设置为城市 到城市 v 的时间加上在城市u隔离观察花费的时间即可

3)最后结果需要减去在城市n隔离观察的时间,因为是求到达城市n那一刻的开销

代码实现:

由于是模板题,就不写什么注释了,不懂的可以去看看dijksta算法的实现,希望谅解

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define int long long
typedef pair<int,int>PII;
const int N=1e5+5,M=2*N;
int h[N],e[M],ne[M],w[M],a[N],dist[N],vis[N],idx;
void add(int x,int y,int z){
	e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
}
void dijkstra(){
	memset(dist,0x3f,sizeof dist);
	priority_queue<PII,vector<PII>,greater<PII> >q;
	q.push({0,1});
	dist[1]=0;
	while(q.size()){
		int dis=q.top().first;
		int s=q.top().second;
		q.pop();
		if(vis[s])continue;
		vis[s]=1;
		for(int i=h[s];~i;i=ne[i]){
			int j=e[i];
			if(dist[j]>dis+w[i]){
				dist[j]=dis+w[i];
				q.push({dist[j],j});
			}
		}
	}
}
signed main(){
	memset(h,-1,sizeof h);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z+a[y]);
		add(y,x,z+a[x]); 
	}
	dijkstra();
	cout<<dist[n]-a[n]<<endl;
	return 0;
}

试题F:费用报销

解题思路:

 dp[i]表示从第1天到第i天范围内的票据中选择的最大报销金额

从1枚举到一年的最大天数,每次考虑选择当前天的票据或者不选择当前天的票据

而选择当前天的票据的前提是上一次选择的票据一定在k天前且当前票据的报销金额加上k天前的最大报销金额不能超过m

则状态转移方程为:

dp[i]=max(dp[i]+dp[max(0,i-k)],dp[i-1])//如果第i天的票据能够满足条件,能选择
dp[i]=dp[i-1]//如果第i天的票据不满足条件,不能选择

代码实现:

#include<iostream>
#include<algorithm>
using namespace std;
const int N=5005;
//记录每月的天数 
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//dp[i]表示从第1天到第i天范围内的票据中选择的最大报销金额 
int dp[N];
int main(){
	int n,m,k;
	//前缀和求本年到当前月总共多少天 
	for(int i=1;i<=13;i++)month[i]+=month[i-1];
	cin>>n>>m>>k;
	while(n--){
		int x,y,z;
		cin>>x>>y>>z;
		//month[x-1]+y表示x月y号距离本年初共多少天 
		dp[month[x-1]+y]=max(dp[month[x-1]+y],z);
	}
	//从第一天枚举到本年最后一天 
	for(int i=1;i<=month[13];i++){
		//如果第i天的票据加上距离第i天前k天的票据的价值不超过m,则说明可以选择第i天的票据
		//取选择第i天的票据dp[i]+dp[max((int)0,i-k)]和不选择第i天的票据dp[i-1]的最大值 
		if(dp[i]+dp[max((int)0,i-k)]<=m)dp[i]=max(dp[i-1],dp[i]+dp[max((int)0,i-k)]);
		//如果第i天的票据不能选择,那么dp[i]直接就是dp[i-1]了 
		else dp[i]=dp[i-1];
	}
	cout<<dp[month[13]]<<endl; 
	return 0;
}

试题I:齿轮

解题思路:

这道题观察样例就可以知道,对于每个查询x,其实是问我们数组中是否两个数满足其倍数关系为x,所以我们只需要在数组输入的时候把每个数都标记一下,然后遍历一下整个数组,对于数组的每个数x,遍历一下它的倍数y,如果x*y被标记了,说明该数组能够找到两个数满足倍数为y的关系,那么就可以把y用另一个标记数组标记下来了,对于每个查询x,我们只需要看一下x是否被标记,只要被标记了,那么就输出YES,否则输出NO

注意:

1)当数组长度为1时,即最左边的齿轮就等同于最右边的齿轮,那么倍数1是满足条件的

2)当数组中存在相同的数字时,那么倍数1是满足条件的,否则倍数1肯定是不满足条件的

这道题我就不得不吐槽一下了,简直是极限卡常,用unordered_map直接卡掉40%的测试点,用数组才能过。所以写完这道题告诉我们不需要用unordered_map的时候最好还是不要用,否则会死得很难看,hh

代码实现:

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int mp[N],vis[N],a[N];
int main(){
    int n,m,flag=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
        //如果数组中遇到了相同的数,那么倍数1是满足条件的,标记一下 
        if(vis[a[i]])flag=1;
        //标记数组的每一个数,以便后续判断 
        vis[a[i]]=1;
    }
    //如果数组长度为1或者1被标记过了,则倍数1是满足条件的
    if(flag||n==1)mp[1]=1;
    //遍历数组的每个数a[i] 
    for(int i=0;i<n;i++){
    	//遍历数组每个数的倍数 
        for(int j=2;j*a[i]<=N;j++){
        	//如果a[i]*j被标记过, 那么倍数j是满足条件的,标记一下 
            if(vis[j*a[i]])mp[j]=1;
        }
    }
    while(m--){
        int x;
        cin>>x;
        //如果倍数x被标记过,直接输出YES 
        if(mp[x])cout<<"YES"<<endl;
        //否则输出NO 
        else cout<<"NO"<<endl;
    }
    return 0;
}

 

这篇关于第十三届蓝桥杯c++b组国赛题解(还在持续更新中...)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!