题目pdf下载:十三届蓝桥杯c++b组2022国赛题目pdf下载
G题没有写,J题是暴力的,其他好像都写出来,但是估计还是有错的。
目录
正文:
试题 A: 2022
题意: 2022分为不同十个不同的正整数的情况数。
思路:动态规划,我的答案是:379187662194355221。
以为挺简单的,但是dfs写完连100都跑不出来,这题难度不简单,估计卡了不少人时间
后面暴力出了答案,从55开始有答案(因为最小的十个不同的正整数是:1,2,3,4...10,和是55),根据前10个数很像哈代-拉马努金拆分数列,然后求出来和后面的不一样,而且会炸long long,所以这个数列应该是错的。
动态规划思路:
以后有空更
暴力代码:
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int a=55;int ans=0;void dfs(int d,int sum,int pre){ //d是选的数量,sum是选的和,pre是上次选的点 if(d==10){ if(sum==a) ans++; return; } for(int i=pre+1;i<=a;i++){ if(i+sum<=a){ dfs(d+1,sum+i,i); } }}int main(){ dfs(0,0,0); cout<<ans<<endl; return 0;}
动态规划代码:
#include<stdio.h>#include<string.h>long long i,j,k,dp[50000][20];int main(){ for(i=1;i<=2022;i++) { for(j=2022;j>=1;j--) { for(k=1;k<=9;k++) { dp[j+i][k+1]=dp[j+i][k+1]+dp[j][k]; } } dp[i][1]++; }// for(i=1;i<=100;i++)// printf("%lld\n",dp[i][10]); printf("%lld\n",dp[2022][10]); return 0;}
试题 B: 钟表
题意:一个钟表的时针、分针的角度差==分针、秒针的角度差,求此时的时分秒。
思路:暴力,我的答案是:4 48 0
三个for起手不难,主要就是计算三个针的角度,
秒的角度就是:m/60
分的角度就是:f/60+(m/60)/60,因为秒贡献的度数最多是1/60,贡献了m/60(1/60)
时的角度就是:s/12+(f+m60)/(6012);,因为分钟贡献的度数最多是1/12,如果有res分钟,那么a=s/12+res/12
注意优弧劣弧的概念,小数的角度是<=0.5的。
代码:
#include<bits/stdc++.h>using namespace std;#define dou double#define EXP 1e-6#define M 100010int main(){ for(dou s=0;s<=6;s++) for(dou f=0;f<60;f++) for(dou m=0;m<60;m++){ dou a=s/12+(f+m*60)/(60*12); //时针在表上角度 dou b=f/60+m/(60*60); //分针在表上角度 dou c=m/60; //秒针在表上角度 dou x=fabs(a-b)>0.5?1-fabs(a-b):fabs(a-b); //x是时针和分针夹角 dou y=fabs(b-c)>0.5?1-fabs(b-c):fabs(b-c); //x是分针和秒针夹角 if(fabs(x-2*y)<EXP){ //如果A==2*B cout<<s<<" "<<f<<" "<<m<<endl; } } return 0;}
试题 C: 卡牌
题意:a[i]数组是已有的 i 类手牌的数量,每个类(1-n类)的出1张可以组成一套,还有m张空白的,可以随便写成任意i类。b数组是该类最多被空白牌写成几张,求组成的最多套牌。
思路:二分
容易知道是把空白牌用到少的类上,这题思路就是直接二分答案了
check函数:
int check(int mid){ //看看mid套行不行 LL sum=0; for(int i=1;i<=n;i++){ if(a[i]<mid){ //i类原来数量就超过mid张就不用考虑了 if(mid-a[i]>b[i]) return 0; //如果需要的比限制多返回NO sum+=mid-a[i]; if(sum>m) return 0; //如果使用空白牌多与m,返回NO } } return 1;}
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define M 1000005LL n,m;LL a[M],b[M];int check(int mid){ LL sum=0; for(int i=1;i<=n;i++){ if(a[i]<mid){ if(mid-a[i]>b[i]) return 0; sum+=mid-a[i]; if(sum>m) return 0; } } return 1;}int main(){ scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) scanf("%lld",&b[i]); LL l=0,r=n*n,ans=0; while(l<=r){ LL mid=(l+r)/2; if(check(mid)){ l=mid+1; ans=mid; }else{ r=mid-1; } } printf("%lld\n",ans); return 0;}
试题 D: 最大数字
题意:给一个小于1e18的数字,不超过a次可以给一位+1,9再+就变成0,
不超过b次可以给一位-1,0再-变成9。
思路:思维+暴力深搜(dfs)
使用肯定是从前面开始的,因为是不超过多少次使用,前面就是能省则省,但是但凡有用,必须使用,暴力出答案即可。
dfs代码:
void dfs(LL a,LL ans,LL b,LL c){ //a表示当前的N,ans是10的某次方,表示数量级,b和c是剩余数量 if(ans==0){ maxx=max(maxx,a); //更新答案 return; } int d=a/ans%10; if(b>9-d){ //能变成9就变9, int r=b-(9-d); dfs(a+(9-d)*ans,ans/10,r,c); }else{ //不能变成9就全用 dfs(a+b*ans,ans/10,0,c); } if(c!=0){ if(c>=d+1){ //能变成9就用,不能变就省着 int r=c-(d+1); dfs(a-d*ans+9*ans,ans/10,b,r); } }}
代码:
#include<bits/stdc++.h>using namespace std;#define fo(a,b) for(int i=a;i<=b;i++)#define inf 0x3f3f3f3f#define LL long long#define M 100010LL a,b,c;LL maxx=0;void dfs(LL a,LL ans,LL b,LL c){ if(ans==0){ maxx=max(maxx,a); return; } int d=a/ans%10; if(b>9-d){ int r=b-(9-d); dfs(a+(9-d)*ans,ans/10,r,c); }else{ dfs(a+b*ans,ans/10,0,c); } if(c!=0){ if(c>=d+1){ int r=c-(d+1); dfs(a-d*ans+9*ans,ans/10,b,r); } }}int main(){ cin>>a>>b>>c; LL tmp=a; LL ans=1; while(a){ a/=10; ans*=10; } dfs(tmp,ans/10,b,c); cout<<maxx<<endl; return 0;}
试题 E: 出差
题意:n个点,m条边构成一个有边权的无向图,然后每个顶点都有自己的停留时间,即到达该点要停的时间,都是正数,求1到n点的最短时间
思路:最短路的贝尔曼-福特算法(Bellman-Ford)
这题就是最短路模板题,只是加上了顶点要停留,感觉迪杰斯特拉算法(Dijkstra)应该也行,但觉得贝尔曼-福特算法(Bellman-Ford)应该更合适。
只是在使用边的时候,将边权+终点停留时间,终点为n时不加
更新代码:
for(int k=1;k<=n;k++){ //n次更新 for(int i=1;i<=m;i++){ int res1=0,res2=0; if(b[i]!=n) res1=x[b[i]]; //终点不为n,边权+停留时间 if(a[i]!=n) res2=x[a[i]]; dist[b[i]]=min(dist[b[i]],dist[a[i]]+c[i]+res1); dist[a[i]]=min(dist[a[i]],dist[b[i]]+c[i]+res2); } }
代码:
#include<bits/stdc++.h>using namespace std;#define fo(a,b) for(int i=a;i<=b;i++)#define inf 0x3f3f3f3f#define LL long long#define M 100005int n,m;int x[M];int dist[M],a[M],b[M],c[M];int main(){ scanf("%d%d",&n,&m); memset(dist,inf,sizeof(dist)); dist[1]=0; for(int i=1;i<=n;i++) cin>>x[i]; for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for(int k=1;k<=n;k++){ for(int i=1;i<=m;i++){ int res1=0,res2=0; if(b[i]!=n) res1=x[b[i]]; if(a[i]!=n) res2=x[a[i]]; dist[b[i]]=min(dist[b[i]],dist[a[i]]+c[i]+res1); dist[a[i]]=min(dist[a[i]],dist[b[i]]+c[i]+res2); } } cout<<dist[n]<<endl; return 0;}
试题 F: 费用报销
题意:给同一年的一些天,这些天都一个或多个的钱,选一些天使金额最多且不超多m,其中所有相邻的天数相差不超过k(>=k)
思路:动态规划
比较简单得到动态规划,首先将天转变为一维数组,dp[i]表示该天最大的金额。
那么dp[i]=max(dp[i-1],dp[i-k]+a[i]) //对应的就是不选和选
核心代码:
for(int i=1;i<=500;i++){ //一年365天,dp超过365就行 if(dp[i]+dp[i-k]<=m) dp[i]=max(dp[i]+dp[i-k],dp[i-1]); else //如果选了会超过m,就不选了 dp[i]=dp[i-1]; }
代码:
#include<bits/stdc++.h>using namespace std;#define fo(a,b) for(int i=a;i<=b;i++)#define inf 0x3f3f3f3f#define LL long long#define M 100005int n,m,k;int x,y,z;int mp[105][105],dp[10005];int r[]={0,31,28,31,30,31,30,31,31,30,31,30,31};int main(){ int sum=0; for(int i=1;i<=12;i++){ for(int j=1;j<=r[i];j++){ sum++; mp[i][j]=sum; //映射天数 } } scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++){ scanf("%d%d%d",&x,&y,&z); dp[mp[x][y]]=max(dp[mp[x][y]],z); } for(int i=1;i<=500;i++){ if(dp[i]+dp[i-k]<=m) dp[i]=max(dp[i]+dp[i-k],dp[i-1]); else dp[i]=dp[i-1]; } cout<<dp[500]<<endl; return 0;}
试题 G: 故障
题意:不知
思路:不知,题有点多,做不过来
代码:未有
试题 H: 机房
题意:给一颗无边权的树,查询m次两点路劲之间,所有点的直接连接点的数量和。
思路:LCA+树形DP
还是比较好想的,dfs处理出给个点的直接连接点的数量,再dfs,求出每个点到顶点的直接连接点的数量的前缀和,用dp[i]表示。
d表示两点x和y的LCA(共公祖先),pre[d]表示d的父点,结果就是dp[x]+dp[y]-dp[d]-dp[pre[d]],其中
核心代码:
void dfs(int d,int pre,int sum){ for(int i=1;i<n+5;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i); //LCA倍增 fa[d][0]=pre; //LCA倍增 h[d]=h[pre]+1; //LCA倍增 p[d]=pre; //父点 for(int i=1;i<=lg[h[d]]+1;i++) //LCA倍增 fa[d][i]=fa[fa[d][i-1]][i-1]; int l=v[d].size(); //l也是当前结点直接连接其他结点数量 dp[d]=l+sum; //sum是之前父链的和 fo(0,l-1){ int now=v[d][i]; if(pre!=now){ dfs(now,d,dp[d]); } }}
代码:
#include<bits/stdc++.h>using namespace std;#define fo(a,b) for(int i=a;i<=b;i++)#define inf 0x3f3f3f3f#define LL long long#define M 200005int n,m,x,y;int dp[M],p[M];vector<int>v[M];int h[M],lg[M],fa[M][35];void dfs(int d,int pre,int sum){ for(int i=1;i<n+5;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i); //LCA倍增 fa[d][0]=pre; //LCA倍增 h[d]=h[pre]+1; //LCA倍增 p[d]=pre; //父点 for(int i=1;i<=lg[h[d]]+1;i++) //LCA倍增 fa[d][i]=fa[fa[d][i-1]][i-1]; int l=v[d].size(); //l也是当前结点直接连接其他结点数量 dp[d]=l+sum; //sum是之前父链的和 fo(0,l-1){ int now=v[d][i]; if(pre!=now){ dfs(now,d,dp[d]); } }}int LCA(int a,int b){ if(h[a]<h[b]) swap(a,b); for(int i=lg[h[a]]+1;i>=0;i--){ if(h[a]-(1<<i)>=h[b]) a=fa[a][i]; } if(a==b) return a; for(int i=lg[h[a]]+1;i>=0;i--) if(fa[a][i]!=fa[b][i]){ a=fa[a][i]; b=fa[b][i]; } return fa[a][0];}int main(){ cin>>n>>m; fo(1,n-1){ cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } dfs(1,0,0); while(m--){ int x,y; cin>>x>>y; int d=LCA(x,y); cout<<dp[x]+dp[y]-dp[d]-dp[p[d]]<<endl; } return 0;}
试题 I: 齿轮
题意:给一个数组为齿轮大小,问能不能换顺序后,尾转的速度是首转的速度的qi倍,询问Q次。
思路:不难发现这个中间的没有用,就是首的半径=尾的半径*qi就可。而且这种排序是随便的,只需要找这个数组中没有两个数相除==qi即可。
那么需处理出这个数组所有的可有倍数即可。具体看代码更容易理解,这个时间复杂度是n*logn的,对1e6也应该能用,注意倍数1的判断
预处理代码:
for(int i=1;i<=MAX;i++){ //MAX=2e5 if(vis[i]==1){ //vis[i]表示i在该数组中 for(int j=i*2;j<=MAX;j+=i){ if(vis[j]==1) ans[j/i]=1; //ans是结果数组 } } }
代码:
#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define LL long long#define M 1000005int MAX=400005;int n,m,flag=0;int a[M];int vis[M],ans[M];int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; if(vis[a[i]]==1) flag=1; //单独判断ans[1] vis[a[i]]=1; //表明数组有这个数 } if(flag) ans[1]=1; for(int i=1;i<=MAX;i++){ if(vis[i]==1){ for(int j=i*2;j<=MAX;j+=i){ if(vis[j]==1) ans[j/i]=1; } } } int x; while(m--){ cin>>x; if(ans[x]) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0;}
试题 J: 搬砖
题意:选取若干个从上到下放,重量不能小于上面的和,求总价值最大
思路:可能是动态规划,写差不多觉得和题意有点出入,就直接dfs暴力了
暴力挺简单的,先结构体排序,重量小的一定先选在上面,不然直接压垮了。然后同重量的价值大的一定先选。
dfs出所有的1-n排序,也就是:
1 2 3 4 5
1 2 3 4
3 4 5
2 4 5
这些
....
然后计算判断更新最后答案
代码:
#include<bits/stdc++.h>using namespace std;#define fo(a,b) for(int i=a;i<=b;i++)#define inf 0x3f3f3f3f#define LL long long#define M 200005int n,maxx=0;struct Node{ int a,b; bool operator<(const Node temp)const{ if(a==temp.a) return b>temp.b; return a<temp.a; }}x[M];//此代码是暴力代码,只能过30%int q[M],v=0;void dfs(int d,int pre){ if(d==n){ //判断q数组中的顺序是否合法 int sum=0,ans=0; for(int i=1;i<=v;i++){ if(x[q[i]].a<sum) break; sum+=x[q[i]].a; ans+=x[q[i]].b; if(i==v) maxx=max(maxx,ans); } return; } for(int i=pre+1;i<=n;i++){ q[++v]=i; dfs(d+1,i); v--; } if(v!=0) dfs(d+1,pre);}int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>x[i].a>>x[i].b; sort(x+1,x+n+1); dfs(0,0); cout<<maxx<<endl; return 0;}
结尾:
看了下演草纸,才用了1页多,一般比赛要好几页的。不少题是算法及相关的题,总体acm选手估计是叫好,但是对其他选手不清楚了,这题个人觉得难度适中,因为往年很多题不能暴力,而且到现在,那些题也没有题解(csdn上)。今年只有一题没看,一个暴力,难度肯定是降了不少的。