第十届蓝桥杯软件赛省赛C++ A组

第十届蓝桥杯软件赛省赛C++ A组题解。

填空题

1. 平方和

模拟，判断并求平方和，2658417853。

2. 数列求值

以62000为循环，20190324 % 62000 = 40324，输出 v[40324] = 4659。

3. 最大降雨量

（无代码，数学解）贪心，最大数至少少于3个数，即46，第二大数至少少于 3 + 1 + 3 个数，即42
以此类推，第四大数（即最后的中位数）为 34。

4. 迷宫

找步数最小中字典序最小的解。按 DLRU顺序 bfs 即可。DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

5. RSA解密

程序题

6. 完全二叉树的权值

模拟，计算每一层的权值和，进行比较。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int dep[10000];
int log_2[100005];

signed main()
{

    for(int i = 2; i < 100005; i++){
        log_2[i] = log_2[i >> 1] + 1;
    }

    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        dep[log_2[i] + 1] += x;
    }

    int res = 0;
    int maxx = 1e-11;
    for(int i = 1; i <= log_2[n] + 1; i++){
        if(dep[i] > maxx){
            maxx = dep[i];
            res = i;
        }
    }
    cout << res;
    return 0;
}

7. 外卖店优先级

模拟，将订单信息按店铺分类，按时间排序，将每一家店铺单独处理。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, t; cin >> n >> m >> t;
    map<int, priority_queue<int>>v;
    for(int i = 1; i <= m; i++){
        int ts, id; cin >> ts >> id;
        v[id].emplace(ts);
    }

    int res = 0;
    for(auto &sto : v){
        vector<int> days(t + 1);
        while(!sto.second.empty()){
            days[sto.second.top()]++;
            sto.second.pop();
        }
        int pri = 0, ok = 0;
        for(int i = 1; i <= t; i++){
            if(!days[i] && pri) pri--;
            else{
                pri += days[i] * 2;
            }

            if(pri > 5) ok = 1;
            else if(pri <= 3) ok = 0;
        }
        res += ok;
    }
    cout << res;
    return 0;
}

8. 修改数组

并查集，对于每一个元素，修改后的值为其所在并查集中的最大值（祖先），修改后将该并查集与其后继的并查集合并。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int p[N];

int find(int x) {
    return p[x] = (p[x] == x) ? x : p[x] = find(p[x]);
}

int main()
{
    for(int i = 1; i < N; i++){
        p[i] = i;
    }

    int n; cin >> n;
    while(n--){
        int a; cin >> a;
        int fa = find(a);
        cout << fa << ' ';
        p[fa] = find(fa + 1);
    }

    return 0;
}

9. 糖果

状压dp，用 dp[u] 表示状态 u 需要的最小糖果数。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 21, M = 1 << N;
int dp[M], vis[M];

signed main()
{
    int n, m, k; cin >> n >> m >> k;
    
    vis[0] = 1;
    for(int i = 1; i <= n; i++){
        int x = 0;
        for(int j = 1; j <= k; j++){
            int t; cin >> t;
            x |= 1 << (t - 1);
        }
        for(int j = 0; j < 1 << m; j++){
            if(vis[j]){
                int u = j | x;
                if(vis[u]){
                    dp[u] = min(dp[u], dp[j] + 1);
                }
                else{
                    vis[u] = 1, dp[u] = dp[j] + 1;
                }
            }   
        }
    }

    if(dp[(1 << m) - 1]) cout << dp[(1 << m) - 1] << '\n';
    else cout << -1;

    return 0;
}

小花生