• 第十三届蓝桥杯c++b组2022年国赛决赛题解

    题目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，所以这个数列应该是错的。

    动态规划思路：

           解释在下面动态规划代码的注释，大致就是dp[2022][10]=dp[1][9]+dp[2][9]+dp[3][9]....+dp[2021][9]的动态规划，用倒叙去实现每个整数只用一次（类似01背包）。

    暴力代码：

    1. #include<cstdio>
    2. #include<cstring>
    3. #include<iostream>
    4. #include<algorithm>
    5. using namespace std;
    6. int a=55;
    7. int ans=0;
    8. void dfs(int d,int sum,int pre){        //d是选的数量，sum是选的和，pre是上次选的点
    9.     if(d==10){
    10.         if(sum==a)
    11.         ans++;
    12.         return;
    13.     }
    14.     for(int i=pre+1;i<=a;i++){
    15.         if(i+sum<=a){
    16.             dfs(d+1,sum+i,i);
    17.         }
    18.     }
    19. }
    20. int main()
    21. {
    22.     dfs(0,0,0);
    23.     cout<<ans<<endl;
    24.     return 0;
    25. }

    动态规划代码：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. long long i,j,k,dp[50000][20];
    4. //dp[i][j]表示选j个数总和为i的方案数
    5. int main()
    6. {
    7.     for(i=2022;i>=1;i--)
    8.     {
    9.         //这里i的顺序不影响结果
    10.         for(j=2022;j>=1;j--)
    11.         {
    12.             //为了dp不相互影响这里从大到小dp
    13.             //如果从小到大的话需要再开数组存结果
    14.             for(k=1;k<=9;k++)
    15.             {
    16.                 dp[j+i][k+1]+=dp[j][k];
    17.                 //对于k个数总和为j的方案dp[j][j];
    18.                 //可以选i使得k+1个数总和为j+i
    19.             }
    20.         }
    21.         dp[i][1]=1;//表示选1个数总和为i的方法加1
    22.     }
    23.     for(i=1;i<=100;i++)
    24.     {
    25.         cout<<i<<" "<<dp[i][10]<<endl;
    26.     }
    27.     cout<<dp[2022][10]<<endl;
    28.     return 0;
    29. }

    试题 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);，因为分钟贡献的度数最多是1/12，如果有res分钟，那么a=s/12+res/12

    注意优弧劣弧的概念，小数的角度是<=0.5的。

    代码：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define dou double
    4. #define EXP 1e-6
    5. #define M 100010
    6. int main()
    7. {
    8.     for(dou s=0;s<=6;s++)
    9.         for(dou f=0;f<60;f++)
    10.             for(dou m=0;m<60;m++){
    11.                 dou a=s/12+(f+m*60)/(60*12);    //时针在表上角度
    12.                 dou b=f/60+m/(60*60);       //分针在表上角度
    13.                 dou c=m/60;             //秒针在表上角度
    14.                 dou x=fabs(a-b)>0.5?1-fabs(a-b):fabs(a-b);      //x是时针和分针夹角
    15.                 dou y=fabs(b-c)>0.5?1-fabs(b-c):fabs(b-c);      //x是分针和秒针夹角
    16.                 if(fabs(x-2*y)<EXP){                //如果A==2*B
    17.                     cout<<s<<" "<<f<<" "<<m<<endl;
    18.                 }
    19.             }
    20.     return 0;
    21. }

    试题 C: 卡牌

     

     题意：a[i]数组是已有的 i 类手牌的数量，每个类（1-n类）的出1张可以组成一套，还有m张空白的，可以随便写成任意i类。b数组是该类最多被空白牌写成几张，求组成的最多套牌。

    修改：这题比赛的时候被改成a,b<n*2了，不是原来的n*n了

    思路：二分

            容易知道是把空白牌用到少的类上，这题思路就是直接二分答案了

    如果当前类牌不够mid张，当然是将空白的编变成该类牌，一是看是否超过了b数组的限制，二是看是否超过了最大空白牌数量。

    直到最后也是没有被返回NO，那么返回YES

    check函数：

    1. int check(int mid){        //看看mid套行不行
    2.     LL sum=0;
    3.     for(int i=1;i<=n;i++){
    4.         if(a[i]<mid){        //i类原来数量就超过mid张就不用考虑了
    5.             if(mid-a[i]>b[i]) return 0;        //如果需要的比限制多返回NO
    6.             sum+=mid-a[i];
    7.             if(sum>m) return 0;        //如果使用空白牌多与m，返回NO
    8.         }
    9.     }
    10.     return 1;
    11. }

    代码：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define LL long long
    4. #define M 1000005
    5. LL n,m;
    6. LL a[M],b[M];
    7. int check(int mid){
    8.     LL sum=0;
    9.     for(int i=1;i<=n;i++){
    10.         if(a[i]<mid){
    11.             if(mid-a[i]>b[i]) return 0;
    12.             sum+=mid-a[i];
    13.             if(sum>m) return 0;
    14.         }
    15.     }
    16.     return 1;
    17. }
    18. int main()
    19. {
    20.     scanf("%lld%lld",&n,&m);
    21.     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    22.     for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    23.     LL l=0,r=n*2,ans=0;
    24.     while(l<=r){
    25.         LL mid=(l+r)/2;
    26.         if(check(mid)){
    27.             l=mid+1;
    28.             ans=mid;
    29.         }else{
    30.             r=mid-1;
    31.         }
    32.     }
    33.     printf("%lld\n",ans);
    34.     return 0;
    35. }

    试题 D: 最大数字

     题意：给一个小于1e18的数字，不超过a次可以给一位+1，9再+就变成0，

    不超过b次可以给一位-1，0再-变成9。

     思路：思维+暴力深搜（dfs）

            使用肯定是从前面开始的，因为是不超过多少次使用，前面就是能省则省，但是但凡有用，必须使用，暴力出答案即可。

    对于每种情况只能是暴力的搜答案，时间复杂度最坏应该是2^18了差不多。

    然后一直纠结用字符串还是整数来表示，整数肯定更方便计算和简洁，字符串便于修改，后面用数量级还是实现了整数的修改。

    dfs代码：

    1. void dfs(LL a,LL ans,LL b,LL c){    //a表示当前的N，ans是10的某次方,表示数量级,b和c是剩余数量
    2.     if(ans==0){
    3.         maxx=max(maxx,a);        //更新答案
    4.         return;
    5.     }
    6.     int d=a/ans%10;
    7.     if(b>9-d){                        //能变成9就变9,
    8.         int r=b-(9-d);
    9.         dfs(a+(9-d)*ans,ans/10,r,c);
    10.     }else{                        //不能变成9就全用
    11.         dfs(a+b*ans,ans/10,0,c);
    12.     }
    13.     if(c!=0){
    14.         if(c>=d+1){                //能变成9就用，不能变就省着
    15.             int r=c-(d+1);
    16.             dfs(a-d*ans+9*ans,ans/10,b,r);
    17.         }
    18.     }
    19. }

    代码：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define fo(a,b) for(int i=a;i<=b;i++)
    4. #define inf 0x3f3f3f3f
    5. #define LL long long
    6. #define M 100010
    7. LL a,b,c;
    8. LL maxx=0;
    9. void dfs(LL a,LL ans,LL b,LL c){
    10.     if(ans==0){
    11.         maxx=max(maxx,a);
    12.         return;
    13.     }
    14.     int d=a/ans%10;
    15.     if(b>9-d){
    16.         int r=b-(9-d);
    17.         dfs(a+(9-d)*ans,ans/10,r,c);
    18.     }else{
    19.         dfs(a+b*ans,ans/10,0,c);
    20.     }
    21.     if(c!=0){
    22.         if(c>=d+1){
    23.             int r=c-(d+1);
    24.             dfs(a-d*ans+9*ans,ans/10,b,r);
    25.         }
    26.     }
    27. }
    28. int main()
    29. {
    30.     cin>>a>>b>>c;
    31.     LL tmp=a;
    32.     LL ans=1;
    33.     while(a){
    34.         a/=10;
    35.         ans*=10;
    36.     }
    37.     dfs(tmp,ans/10,b,c);
    38.     cout<<maxx<<endl;
    39. 	return 0;
    40. }

    试题 E: 出差

     题意：n个点，m条边构成一个有边权的无向图，然后每个顶点都有自己的停留时间，即到达该点要停的时间，都是正数，求1到n点的最短时间

    思路：最短路的贝尔曼-福特算法(Bellman-Ford)

            这题就是最短路模板题，只是加上了顶点要停留，感觉迪杰斯特拉算法（Dijkstra）应该也行，但觉得贝尔曼-福特算法(Bellman-Ford)应该更合适。

    只是在使用边的时候，将边权+终点停留时间，终点为n时不加

    更新代码：

    1.  for(int k=1;k<=n;k++){        //n次更新
    2.         for(int i=1;i<=m;i++){
    3.             int res1=0,res2=0;
    4.             if(b[i]!=n) res1=x[b[i]];        //终点不为n，边权+停留时间
    5.             if(a[i]!=n) res2=x[a[i]];
    6.             dist[b[i]]=min(dist[b[i]],dist[a[i]]+c[i]+res1);
    7.             dist[a[i]]=min(dist[a[i]],dist[b[i]]+c[i]+res2);
    8.         }
    9.     }

    代码：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define fo(a,b) for(int i=a;i<=b;i++)
    4. #define inf 0x3f3f3f3f
    5. #define LL long long
    6. #define M 100005
    7. int n,m;
    8. int x[M];
    9. int dist[M],a[M],b[M],c[M];
    10. int main(){
    11.     scanf("%d%d",&n,&m);
    12.     memset(dist,inf,sizeof(dist));
    13.     dist[1]=0;
    14.     for(int i=1;i<=n;i++) cin>>x[i];
    15.     for(int i=1;i<=m;i++)
    16.         scanf("%d%d%d",&a[i],&b[i],&c[i]);
    17.     for(int k=1;k<=n;k++){
    18.         for(int i=1;i<=m;i++){
    19.             int res1=0,res2=0;
    20.             if(b[i]!=n) res1=x[b[i]];
    21.             if(a[i]!=n) res2=x[a[i]];
    22.             dist[b[i]]=min(dist[b[i]],dist[a[i]]+c[i]+res1);
    23.             dist[a[i]]=min(dist[a[i]],dist[b[i]]+c[i]+res2);
    24.         }
    25.     }
    26.     cout<<dist[n]<<endl;
    27.     return 0;
    28. }

    试题 F: 费用报销

     

     题意：给同一年的一些天，这些天都一个或多个的钱，选一些天使金额最多且不超多m，其中所有相邻的天数相差不超过k（>=k）

    思路：动态规划

            比较简单得到动态规划，首先将天转变为一维数组，dp[i]表示该天最大的金额。

    那么dp[i]=max(dp[i-1],dp[i-k]+a[i])                //对应的就是不选和选

    核心代码：

    1.  
    2.     for(int i=1;i<=500;i++){            //一年365天，dp超过365就行
    3.         if(dp[i]+dp[max(0,i-k)]<=m)
    4.             dp[i]=max(dp[i]+dp[max(0,i-k)],dp[i-1]);
    5.         else        //如果选了会超过m，就不选了
    6.             dp[i]=dp[i-1];
    7.     }

    代码：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define fo(a,b) for(int i=a;i<=b;i++)
    4. #define inf 0x3f3f3f3f
    5. #define LL long long
    6. #define M 100005
    7. int n,m,k;
    8. int x,y,z;
    9. int mp[105][105],dp[10005];
    10. int r[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    11. int main(){
    12.     int sum=0;
    13.     for(int i=1;i<=12;i++){
    14.         for(int j=1;j<=r[i];j++){
    15.             sum++;
    16.             mp[i][j]=sum;        //映射天数
    17.         }
    18.     }
    19.     scanf("%d%d%d",&n,&m,&k);
    20.     for(int i=1;i<=n;i++){
    21.         scanf("%d%d%d",&x,&y,&z);
    22.         dp[mp[x][y]]=max(dp[mp[x][y]],z);        //k最小为1，当天的就选个最大的就行
    23.     }
    24.     for(int i=1;i<=500;i++){
    25.         if(dp[i]+dp[max(0,i-k)]<=m)
    26.             dp[i]=max(dp[i]+dp[max(0,i-k)],dp[i-1]);
    27.         else
    28.             dp[i]=dp[i-1];
    29.     }
    30.     cout<<dp[500]<<endl;
    31.     return 0;
    32. }
    33. #include<bits/stdc++.h>
    34. using namespace std;
    35. #define fo(a,b) for(int i=a;i<=b;i++)
    36. #define inf 0x3f3f3f3f
    37. #define LL long long
    38. #define M 100005
    39. int n,m,k;
    40. int x,y,z;
    41. int mp[105][105],dp[10005];
    42. int r[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    43. int main(){
    44.     int sum=0;
    45.     for(int i=1;i<=12;i++){
    46.         for(int j=1;j<=r[i];j++){
    47.             sum++;
    48.             mp[i][j]=sum;        //映射天数
    49.         }
    50.     }
    51.     scanf("%d%d%d",&n,&m,&k);
    52.     for(int i=1;i<=n;i++){
    53.         scanf("%d%d%d",&x,&y,&z);
    54.         dp[mp[x][y]]=max(dp[mp[x][y]],z);        //k最小为1，当天的就选个最大的就行
    55.     }
    56.     for(int i=1;i<=500;i++){
    57.         if(dp[i]+dp[max(0,i-k)]<=m)
    58.             dp[i]=max(dp[i]+dp[max(0,i-k)],dp[i-1]);
    59.         else
    60.             dp[i]=dp[i-1];
    61.     }
    62.     cout<<dp[500]<<endl;
    63.     return 0;
    64. }

    试题 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]]。

    核心代码：

    1. void dfs(int d,int pre,int sum)
    2. {
    3.     for(int i=1;i<n+5;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);           //LCA倍增
    4.     fa[d][0]=pre;                   //LCA倍增
    5.     h[d]=h[pre]+1;                  //LCA倍增
    6.     p[d]=pre;                  //父点
    7.     for(int i=1;i<=lg[h[d]]+1;i++)                  //LCA倍增
    8.         fa[d][i]=fa[fa[d][i-1]][i-1];
    9.     int l=v[d].size();                    //l也是当前结点直接连接其他结点数量
    10.     dp[d]=l+sum;                          //sum是之前父链的和
    11.     fo(0,l-1){
    12.         int now=v[d][i];
    13.         if(pre!=now){
    14.             dfs(now,d,dp[d]);
    15.         }
    16.     }
    17. }

    代码：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define fo(a,b) for(int i=a;i<=b;i++)
    4. #define inf 0x3f3f3f3f
    5. #define LL long long
    6. #define M 200005
    7. int n,m,x,y;
    8. int dp[M],p[M];
    9. vector<int>v[M];
    10. int h[M],lg[M],fa[M][35];
    11. void dfs(int d,int pre,int sum)
    12. {
    13.     for(int i=1;i<n+5;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);           //LCA倍增
    14.     fa[d][0]=pre;                   //LCA倍增
    15.     h[d]=h[pre]+1;                  //LCA倍增
    16.     p[d]=pre;                  //父点
    17.     for(int i=1;i<=lg[h[d]]+1;i++)                  //LCA倍增
    18.         fa[d][i]=fa[fa[d][i-1]][i-1];
    19.     int l=v[d].size();                    //l也是当前结点直接连接其他结点数量
    20.     dp[d]=l+sum;                          //sum是之前父链的和
    21.     fo(0,l-1){
    22.         int now=v[d][i];
    23.         if(pre!=now){
    24.             dfs(now,d,dp[d]);
    25.         }
    26.     }
    27. }
    28. int LCA(int a,int b)
    29. {
    30.     if(h[a]<h[b]) swap(a,b);
    31.     for(int i=lg[h[a]]+1;i>=0;i--){
    32.         if(h[a]-(1<<i)>=h[b])
    33.             a=fa[a][i];
    34.     }
    35.     if(a==b) return a;
    36.     for(int i=lg[h[a]]+1;i>=0;i--)
    37.         if(fa[a][i]!=fa[b][i]){
    38.             a=fa[a][i];
    39.             b=fa[b][i];
    40.         }
    41.     return fa[a][0];
    42. }
    43. int main(){
    44.     cin>>n>>m;
    45.     fo(1,n-1){
    46.         cin>>x>>y;
    47.         v[x].push_back(y);
    48.         v[y].push_back(x);
    49.     }
    50.     dfs(1,0,0);
    51.     while(m--){
    52.         int x,y;
    53.         cin>>x>>y;
    54.         int d=LCA(x,y);
    55.         cout<<dp[x]+dp[y]-dp[d]-dp[p[d]]<<endl;
    56.     }
    57.     return 0;
    58. }

    试题 I: 齿轮

     题意：给一个数组为齿轮大小，问能不能换顺序后，尾转的速度是首转的速度的qi倍，询问Q次。

    思路：不难发现这个中间的没有用，就是首的半径=尾的半径*qi就可。而且这种排序是随便的，只需要找这个数组中有没有两个数相除==qi即可。

    那么需处理出这个数组所有的可有倍数即可。具体看代码更容易理解，这个时间复杂度是n*logn的，对1e6也应该能用，注意倍数1的判断

    预处理代码：

    1. for(int i=1;i<=MAX;i++){            //MAX=2e5
    2.         if(vis[i]==1){                //vis[i]表示i在该数组中
    3.             for(int j=i*2;j<=MAX;j+=i){
    4.                 if(vis[j]==1) ans[j/i]=1;        //ans是结果数组
    5.             }    
    6.         }
    7.     }

    代码：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define inf 0x3f3f3f3f
    4. #define LL long long
    5. #define M 1000005
    6. int MAX=400005;
    7. int n,m,flag=0;
    8. int a[M];
    9. int vis[M],ans[M];
    10. int main(){
    11.     cin>>n>>m;
    12.     for(int i=1;i<=n;i++){
    13.         cin>>a[i];
    14.         if(vis[a[i]]==1) flag=1;        //单独判断ans[1]
    15.         vis[a[i]]=1;            //表明数组有这个数
    16.     }
    17.     if(flag) ans[1]=1;
    18.     for(int i=1;i<=MAX;i++){
    19.         if(vis[i]==1){
    20.             for(int j=i*2;j<=MAX;j+=i){
    21.                 if(vis[j]==1) ans[j/i]=1;
    22.             }
    23.         }
    24.     }
    25.     int x;
    26.     while(m--){
    27.         cin>>x;
    28.         if(ans[x]) cout<<"YES"<<endl;
    29.         else cout<<"NO"<<endl;
    30.     }
    31.     return 0;
    32. }

    试题 J: 搬砖

     题意：选取若干个从上到下放，重量不能小于上面的和，求总价值最大

    思路：可能是动态规划，写差不多觉得和题意有点出入，就直接dfs暴力了

    暴力挺简单的，先结构体排序，重量小的一定先选在上面，不然直接压垮了。然后同重量的价值大的一定先选。

    dfs出所有的1-n排序，也就是：

    1 2 3 4 5

    1 2 3 4

    3 4 5

    2 4 5

    这些

    ....

    然后计算判断更新最后答案

    代码：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define fo(a,b) for(int i=a;i<=b;i++)
    4. #define inf 0x3f3f3f3f
    5. #define LL long long
    6. #define M 200005
    7. int n,maxx=0;
    8. struct Node
    9. {
    10.     int a,b;
    11.     bool operator<(const Node temp)const{
    12.         if(a==temp.a) return b>temp.b;
    13.         return a<temp.a;
    14.     }
    15. }x[M];
    16.  
    17. //此代码是暴力代码，只能过30%
    18.  
    19. int q[M],v=0;
    20. void dfs(int d,int pre){
    21.     if(d==n){                //判断q数组中的顺序是否合法
    22.         int sum=0,ans=0;
    23.         for(int i=1;i<=v;i++){
    24.             if(x[q[i]].a<sum) break;
    25.             sum+=x[q[i]].a;
    26.             ans+=x[q[i]].b;
    27.             if(i==v) maxx=max(maxx,ans);
    28.         }
    29.         return;
    30.     }
    31.     for(int i=pre+1;i<=n;i++){
    32.         q[++v]=i;
    33.         dfs(d+1,i);
    34.         v--;
    35.     }
    36.     if(v!=0) dfs(d+1,pre);
    37. }
    38. int main(){
    39.     cin>>n;
    40.     for(int i=1;i<=n;i++)
    41.         cin>>x[i].a>>x[i].b;
    42.     sort(x+1,x+n+1);
    43.     dfs(0,0);
    44.     cout<<maxx<<endl;
    45.     return 0;
    46. }

    结尾：

            看了下演草纸，才用了1页多，一般比赛要好几页的。不少题是算法及相关的题，总体acm选手估计是叫好，但是对其他选手不清楚了，这题个人觉得难度适中，因为往年很多题不能暴力，而且到现在，那些题也没有题解（csdn上）。今年只有一题没看，一个暴力，难度肯定是降了不少的。

  • 相关阅读:
    【python百炼成魔】python之元组详解
    二、图像处理
    吉时利2600A系列/2611A数字源表
    Ubuntu—在线安装convert_geotiff
    2022年台湾省矢量数据（点线面）及数字高程数据下载
    安全评估报告怎么写 安全风险评估报告流程 安全评估报告认定
    网络安全系列-三十八: 网络分析的瑞士军刀 CyberChef
    漫谈：C语言 C++ 所有编程语言 =和==的麻烦
    探秘小米增程汽车与仿生机器人的未来：AI大模型的潜在影响及苹果iPhone15Pro发热问题解决之道
    shell脚本入门到实战（二）--shell输入和格式化输出
  • 原文地址：https://blog.csdn.net/m0_58177653/article/details/125345906