第十三届蓝桥杯c++b组国赛题解（还在持续更新中...）
阿里云国际版折扣https://www.yundadi.com |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
试题A2022
解题思路
有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是否相等判断是否满足条件
注意
1double相减存在误差最好不要直接判断相等
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的单向边将当前道路的开销设置为城市 u 到城市 v 的时间加上在城市v隔离观察花费的时间即可
2.建立从v到u的单向边将当前道路的开销设置为城市 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;
}试题H机房
解题思路
lca板子题
首先要搞清楚题意题意表达的意思就是对于一个点它发送消息的延迟是与出度有关也就是说某个点的出度是多少那么消息经过它时就会延迟多久。
我们这里可以把1号点当做树根root然后使用dist[x]表示x点发送消息到root所需要的时间。 很显然x发送出去的时候经过自身的延迟后到达另外一个点另外一个点在经过延迟到达下一个点以此类推
那么任意两个点之间的距离一般就是使用dist[x] + dist[y] - 2 * dist[lca(a, b)] 但是对于本题而言当减去两倍的最近公共祖先anc到root的距离时就会把自身的一个延迟多减了一次所以还需要加上anc的出度。 所以本题正确计算距离的公式应该为 d = (dist[x] + dist[y] - 2 * dist[anc] + d[anc]) 其中anc表示x和y的最近公共祖先d[anc]表示点anc的出度
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
const int N=1e5+5,M=2*N;
int h[N],e[M],ne[M],idx;
//fa[i][j]表示结点i向上跳2^j步所到达的结点
//depth[i]表示结点i的深度
//dist[i]表示结点i到根节点的数据传输时间
//d[i]表示和结点i相连的边数
int fa[N][20],depth[N],dist[N],d[N];
void add(int x,int y){
e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void bfs(){
queue<int>q;
q.push(1);
memset(depth,0x3f,sizeof depth);
//结点0的深度为0结点1的深度为1
depth[0]=0,depth[1]=1;
//结点1根结点的传输时间为自己的延迟时间
dist[1]=d[1];
while(q.size()){
int t=q.front();
q.pop();
//遍历所有子节点
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
//这句话其实表示子节点还未被访问过因为访问过后,depth[j]一定小于depth[t]+1
//如果未被访问过则更新depth和dist数组
if(depth[j]>depth[t]+1){
depth[j]=depth[t]+1;
dist[j]=d[j]+dist[t];
q.push(j);
//利用倍增法依次更新往上跳的父节点
fa[j][0]=t;
for(int k=1;k<=16;k++){
//j向上跳2^k步等同于j先向上跳到2^(k-1)的位置然后再往上跳2^(k-1)步
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
}
int lca(int a,int b){
// 为方便处理,当a在b上面时,把a和b互换
if(depth[a]<depth[b])swap(a,b);
//把深度更深的a往上跳到b
for(int i=16;i>=0;i--){
//当a跳完2^i依然在b下面,我们就一直跳
if(depth[fa[a][i]]>=depth[b])a=fa[a][i];
}
//如果跳到了b
if(a==b)return a;
//a,b同层但是不同结点
for(int i=16;i>=0;i--){
//假如a,b都跳出根节点,fa[a][i]==fa[b][i]==0 不符合更新条件
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
//循环结束 到达lca下一层
//lca(a,b) = 再往上跳1步即可
return fa[a][0];
}
signed main(){
int n,m;
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
//统计结点x和结点y的边因为时间取决于每个结点的边数
d[x]++,d[y]++;
//建立双向边
add(x,y);
add(y,x);
}
//初始化lca和dist数组
bfs();
while(m--){
int x,y;
cin>>x>>y;
//求最近公共祖先
int anc=lca(x,y);
//直接套公式求解传输时间
cout<<dist[x]+dist[y]-2*dist[anc]+d[anc]<<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;
}