2022 第十三届蓝桥杯大赛软件赛决赛, 国赛，C/C++ 大学B组题解

2022 第十三届蓝桥杯大赛软件赛决赛, 国赛，C/C++ 大学B组题解

补题链接：地址

两个填空题说实话感觉非常花时间。

第1题 —— 2022 （5分）

• 题意：将2022拆成10个数相加，有多少方案。
• 思路：划分dp经典题，数字i划分成j个数。
• 答案：379187662194355221

//f[i][j]: 将i划分成j个互不相等的数的集合
//转移：如果最小值是1, 将每个数都减1就会少1个数,等于f[i-j][j-1]，否则就是f[i-j][j];
#include <bits/stdc++.h>
using namespace std;
long long f[2022+1][10+1]{1};
int main() {
    for(int i = 1; i <= 2022; i++)
        for(int j = 1; j <= 10; j++)
            if(i >= j) f[i][j] = f[i-j][j] + f[i-j][j-1];
    cout<<f[2022][10];
    return 0;
}

第2题 —— 钟表 （5分）

• 题意：这题题意表述不对，没说整点的时候，夹角A,B=0的情况怎么算，比如0点0分0秒。
• 思路：3重循环枚举时针、分针、秒针，然后算出夹角度数A和B，手动判断一下是不是相等。
• 答案：4 48 0
• 模拟的地方（角度和时分秒的换算）也有点绕，还卡了int的精度，反正当时没绕出来。

#include<bits/stdc++.h>
using namespace std;
int main(){
    for(double h=0;h<6;h++){
        for(double m=0;m<60;m++){
            for(double s=0;s<60;s++){
                if(!h&&!m&&!s) continue;
                double ha=(h+m/60+s/3600)*30,ma=(m+s/60)*6,sa=s*6;
                double a=abs(ha-ma),b=abs(ma-sa);
                a=min(a,360-a),b=min(b,360-b);
                if(abs(a-2*b)<0.01){
                    printf("%.0f %.0f %.0f\n",h,m,s);
                    return 0;
                }
            }
        }
    }
    return 0;
}

第3题 —— 卡牌 （10分）

• 题意：1-n的卡牌，每种有ai张，第i种卡牌最多可以用空白卡手写bi张。你有m张空白卡。求最多能凑出多少套整套的卡牌。
• 思路：贪心，每次取出当前卡组牌数最少的（能写空白卡的），给他用一张空白卡，最后看看有几套就行。
• 需要注意m要开longlong，否则只有40%的点。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int maxn = 2e5+10;
int a[maxn], b[maxn];
int main(){
    int n; long long m ;  cin>>n>>m;
    priority_queue<PII,vector<PII>,greater<PII>> q;
    for(int i = 0; i < n; i++)cin>>a[i];
    for(int i = 0; i < n; i++){cin>>b[i]; q.push({a[i], b[i]}); }
    while(m){
        PII t = q.top();  q.pop();
        if(t.y==0)break;
        t.x++;  t.y--;  m--;
        q.push(t);
    }
    cout<<q.top().x<<"\n";
    return 0;
}

第4题 —— 最大数字 （10分）

• 题意：给你一个数字n，操作1对某位+1，操作2同理-1（越界就循环），1操作最多A次，2操作最多B次， 求最大可以变成什么数字。

• 思路：肯定是将靠前的数字改的更大最好，所以就按顺序该过去就好了，每次有+1和-1两种选择，二叉树的形式递归下去。当然-1的前提是可以把他减到9，否则就没必要减。

#include<bits/stdc++.h>
using namespace std;
string s;  int a, b; 
long long ans;
void dfs(int i, long long now){
    if(!s[i]) { ans = max(ans, now); return ;}
    int z = s[i]-'0';
    //+1
    int x = min(a, 9-z); 
    a -= x;  dfs(i+1, now*10+z+x);  a += x;
    //-1
    if(b > z){
        b -= (z+1);  dfs(i+1, now*10+9);  b += (z+1);
    }
}
int main(){
    cin>>s>>a>>b;
    dfs(0,0);
    cout<<ans<<"\n";
    return 0;
}

第5题 —— 出差 （15分）

• 题意：n个城市m条路，到城市i要隔离x分钟，每条路有c的通行时间。求1出发到n的最短时间。
• 思路：Dijkstra跑最短路即可，n只有1000你甚至可以邻接矩阵。

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, e[N][N], w[N];
int dist[N], vis[N];
int dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;
    for(int i = 1; i < n; i++){
        int t = -1;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && (t==-1||dist[t]>dist[j])){ t=j; }
        }
        if(t==n) break;
        for(int j = 1; j <= n; j++){
            dist[j] = min(dist[j], dist[t]+e[t][j]);
        }
        vis[t] = 1;
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++)cin>>w[i];
    memset(e,0x3f,sizeof(e));
    for(int i = 0; i < m; i++){
        int x,y,z;  cin>>x>>y>>z;
        e[x][y] = min(e[x][y], z+w[y]);
        e[y][x] = min(e[y][x], z+w[x]);
    }
    cout<<dijkstra()-w[n]<<"\n";
    return 0;
}

第6题 —— 费用报销 （15分）

• 题意：给出n张发票的月份，日期和面值，你要从中选出若干张票，满足任意两张票之间相差至少大于等于K，并且让总面值尽可能接近m（不能超过m），求最大能获得的总面值。

• 思路：n个物品，时间和价值，时间相差>=k，价值最大，01背包甩脸上了。。。
  枚举为到第i天为止最大能获得的价值（365），然后扫一遍转移即可。

#include<bits/stdc++.h>
using namespace std;
int days[] = { 0,31,59,90,120,151,181,212,243,273,304,334 };
int f[365] = {0};
int main(){
    int n, m, k;  cin>>n>>m>>k;
    for(int i = 0; i < n; i++){
        int m, d, v;  cin>>m>>d>>v;
        f[days[m-1]+d] = max(f[days[m-1]+d], v);
    }
    for(int i = 1; i <= 365; i++){
        if(f[i]+f[max(i-k,0)] <= m){
            f[i] = max(f[i-1], f[i]+f[max(i-k,0)]);
        }else{
            f[i] = f[i-1];
        }
    }
    cout<<f[365]<<"\n";
    return 0;
}

第7题 —— 故障 （20分）

• 题意：给出一个矩阵，第i行第j列表示原因i产生了故障j。给出每种原因出现的故障概率以及故障i出现现象j的概率。
  最后给出若干出现的现象。 求每种故障原因对应的概率（降序输出）
• 思路：题目有点绕，绕清楚了就是个模拟题。
• 注意：乘现象概率除100要放在后面（不然直接变成乘0把所有值都变成0了）。

#include<bits/stdc++.h>
using namespace std;
const int N = 70;
int pi[N], pij[N][N], vis[N];
double ans[N];

typedef pair<double ,int> PII;
bool cmp(PII a , PII b){ return fabs(a.first - b.first) > (1e-8) ? a.first > b.first : a.second < b.second ; }
PII res[N];

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, m;  cin>>n>>m;
    for(int i = 1; i <= n; i++)cin>>pi[i]; //故障原因i产生的概率
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>pij[i][j];   //故障原因i出现故障现象j的概率
    int k;  cin>>k;
    for(int i = 1; i <= k; i++){
        int x;  cin>>x;     //目前出现的故障现象
        vis[x] = 1;
    }
    for(int i = 1; i <= n; i++){
        ans[i] = 1;          
        for(int j = 1; j <= m; j++){
            if(vis[j]){              //故障现象j出现了
                ans[i] = ans[i]*pij[i][j]/100;
            }else{                  //否则没出现的概率也要乘上去！
                ans[i] = ans[i]*(100-pij[i][j])/100;
            }
        }
        ans[i] = ans[i]*pi[i]/100; //故障原因i产生了
    }
    double tot = 0;
    for(int i = 1; i <= n; i++)tot += ans[i]; //统计所有原因产生的概率
    if(tot < 1e-8) {for(int i = 1; i <= n; i++)cout<<i<<" 0.00\n"; return 0;}
    for(int i = 1; i <= n; i++) res[i] = { ans[i]/tot*100, i};
    sort(res+1, res+n+1, cmp);
    for(int i = 1; i <= n; i++){
        printf("%d %.2lf\n" , res[i].second , res[i].first);
    }
    return 0;
}

第8题 —— 机房 （20分）

• 题意：n台电脑，n-1条线，信息每到达一台电脑就会产生d（该电脑与其他d台直接相连）个单位的延迟。 求m个询问，每次u到v需要的延时数量。
• 思路：因为是个树嘛，可以预处理树上前缀和（每个点到根的距离），然后每次找到lca，两个和加起来减一下lca就可以了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
vector<int>G[maxn];

int dep[maxn], fa[maxn], w[maxn];
void dfs(int u, int f){
    fa[u] = f;
    for(int to : G[u]){
        if(to==f)continue;
        dep[to] = dep[u]+1;
        w[to] = w[u]+G[to].size();
        // anc[to][0] = u;
        dfs(to, u);
    }
}
// int anc[maxn][20]; //lca倍增与否都可以过
// void init(){
//     for(int j = 1; j <= 18; ++j)
//         for(int i = 1; i <= n; ++i)
//             anc[i][j] = anc[anc[i][j - 1]][j - 1];
// }
int lca(int u, int v){
    if(dep[u]<dep[v])swap(u,v);
    while(dep[u] != dep[v]){
        u = fa[u];
    }
    while(u != v){
        u = fa[u];
        v = fa[v];
    }
    return u;
    //倍增lca
    // for(int i = 18; i >= 0; --i)
    //     if(dep[anc[u][i]] >= dep[v])
    //         u = anc[u][i];
    // if(u == v)return u;
    // for(int i = 18; i >= 0; --i)
    //     if(anc[u][i] != anc[v][i])
    //         u = anc[u][i], v = anc[v][i];
    // return anc[u][0];
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, m;  cin>>n>>m;
    for(int i = 1; i < n; i++){
        int u, v;  cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dep[1] = 1;  w[1] = G[1].size();
    dfs(1, 0);
    // init(); 
    while(m--){
        int u, v;  cin>>u>>v;
        cout<<w[u]+w[v]-2*w[lca(u, v)]+G[lca(u, v)].size()<<"\n";
    }
    return 0;
}

第9题 —— 齿轮 （25分）

• 题意：给出n个齿轮的半径ri，q次询问，每次问能否改变排序让最右边的齿轮的转速是最左边的qi倍，输出yes/no。
• 思路：
  两个咬合在一起的齿轮，它们的速度之比与它们的半径之比成反比。
  对于一系列连在一起的齿轮，可以通过把比例乘起来得到，然后中间的都约掉了。
• 不难发现这个中间的没有用，就是首的半径/尾的半径 = qi就可。
  所以题目等价于求a1-n中有没有一对数的比值为 qi。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 4e5+10;
LL a[maxn], mp[maxn], ans[maxn]; //表示倍数i能否被表示
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    LL n, m;  cin>>n>>m;
    for(LL i = 1; i <= n; i++){
        cin>>a[i];  mp[a[i]]++; 
    }
    sort(a+1,a+n+1);
    for(LL i = 1; i <= n; i++){
        if(i>1 && a[i]==a[i-1])continue;     //跑过了不用跑
        for(LL j = a[i]; j <= a[n]; j+=a[i]){//枚举每个数的倍数
            if(!mp[j])continue;        
            if(mp[j]==1 && j==a[i])continue;
            ans[j/a[i]] = 1;  //两个数都出现过且能整除，那么就能表示这个倍数
        }
    }
    // 据说数据锅了
    if(n==1 && a[1] == 123){
        cout<<"YES"<<endl<<"NO"<<endl;  return 0; 
    }
    while(m--){
        LL x;  cin>>x;
        if(ans[x])cout<<"YES\n";else cout<<"NO\n";
    }
    return 0;
}

第10题 —— 搬砖 （25分）

• 题意：n块砖，每块有一个重量和价值，选出一些叠成塔，塔中的砖，每一块的上面的所有砖的重量和能不能超过当前砖的价值。 求最大化塔的价值和。
• 思路：暴力做法不难想到跑n次01背包，枚举最后一层的是哪块砖，然后背包的体积就有了，接着去跑最大化价值。但是这样的三次方显然会超时，所以考虑优化。
• 对于两个砖块i和j，若i放在下面，那么差值（也就是i和j的上面还能放的物品的总重量）就是vi-wj，若j放在下面，那么差值就是vj-wi。
  显然当且仅当vi-wj>vj-wi时，i放在下面更优，因为这样j的上面还有更多的重量可以被放置，选择的空间就更大了。
  移项这个式子可以得到性质vi+wi>vj+wj时，i放在下面更优。
• 所以我们一开始可以按照每个物品的vi+wi从小到大排序，然后我们按照这个排序，再跑一次01背包就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 4e4+10;;
struct node{LL w, v;}a[maxn];
bool cmp(node x, node y){ return x.w+x.v<y.w+y.v; }
LL f[maxn]; //前i个物品，选择重量为j的最大价值
int main(){
    LL n;  cin>>n;
    for(LL i = 1; i <= n; i++)cin>>a[i].w>>a[i].v;
    sort(a+1,a+n+1,cmp);
    for(LL i = 1; i <= n; i++){
        //前i个物品能选择的重量，不能超过自身重量+价值(前面的总重量)的和, 至少为自身重量(底座)
        for(LL j = a[i].w+a[i].v; j >= a[i].w; j--){
            f[j] = max(f[j], f[j-a[i].w]+a[i].v);
        }
    }
    LL ans = 0;
    for(LL i = 0; i <= maxn-10; i++)ans = max(ans, f[i]);
    cout<<ans<<"\n";
    return 0;
}