题目pdf下载：十三届蓝桥杯c++b组2022国赛题目pdf下载
G题没有写，J题是暴力的，其他好像都写出来，但是估计还是有错的。
目录
正文：
试题 A: 2022
试题 B: 钟表
试题 C: 卡牌
试题 D: 最大数字
试题 E: 出差
试题 F: 费用报销
试题 G: 故障
试题 H: 机房
试题 I: 齿轮
试题 J: 搬砖
结尾：
正文：
试题 A: 2022
题意： 2022分为不同十个不同的正整数的情况数。
思路：动态规划,我的答案是：379187662194355221。
以为挺简单的，但是dfs写完连100都跑不出来，这题难度不简单，估计卡了不少人时间
后面暴力出了答案，从55开始有答案（因为最小的十个不同的正整数是：1,2,3,4…10，和是55），根据前10个数很像哈代-拉马努金拆分数列，然后求出来和后面的不一样，而且会炸long long，所以这个数列应该是错的。
动态规划做法：
暂无，明天更
暴力代码：
#include#include#include#includeusing 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<动态规划代码：
#include#includelong long i,j,k,dp[50000][20];int main(){for(i=1;i=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+m*60)/(60*12);，如果有res分钟，那么a=s/12+res/12，因为就算分钟决定的是1/12的区域。
注意优弧劣弧的概念，小数的角度是<=0.5的。
代码：
#includeusing 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;m0.5" />试题 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]b[i]) return 0;//如果需要的比限制多返回NOsum+=mid-a[i];if(sum>m) return 0;//如果使用空白牌多与m，返回NO}}return 1;}代码：
#includeusing 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]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);}}}代码：
#includeusing namespace std;#define fo(a,b) for(int i=a;i9-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);}}代码：
#includeusing 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>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];}代码：
#includeusing 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]);elsedp[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]);}}}代码：
#includeusing 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];vectorv[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]=0;i--){if(h[a]-(1<=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=2e5if(vis[i]==i){//vis[i]表示i在该数组中for(int j=i*2;j<=MAX;j+=i){ans[j/i]=vis[j];//ans是结果数组}}}代码：
#includeusing 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>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>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
这些
....
然后计算判断更新最后答案
代码：
#includeusing 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 operatortemp.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;for(int i=1;i>x[i].a>>x[i].b;sort(x+1,x+n+1);dfs(0,0);cout<<maxx<<endl;return 0;}结尾：
看了下演草纸，才用了1页多，一般比赛要好几页的。不少题是算法及相关的题，总体acm选手估计是叫好，但是对其他选手不清楚了，这题个人觉得难度适中，因为往年很多题不能暴力，而且到现在，那些题也没有题解（csdn上）。今年只有一题没看，一个暴力，难度肯定是降了不少的。