第十二届蓝桥杯省赛第二场C++大学C组题解

文章目录

• 结果填空题
• • 填空题答案一览
  • A: 求余
  • B: 双阶乘
  • C: 格点
  • D: 整数分解（不会)
  • E: 城邦
• 程序设计题
• • F: 特殊年份
  • G: 小平方
  • H: 完全平方数（暴力做法）
  • I: 负载均衡
  • J: 国际象棋(不会)

结果填空题

填空题答案一览

A: 求余

分析：

B: 双阶乘

分析：高位上的数字对结果没有影响，取余截掉

代码:

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

int main(){
    int num = 1;
    for(int i =2021;i>0;i-=2) num = (num * i) %1000000;
    cout<< num % 100000 <<endl;
    return 0;
}
//59375

C: 格点

分析: 根据题意，枚举所有可能符合的坐标，进行判断

代码：

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

int main(){
    int res = 0;
    for(int i =1;i<=2030;i++){
        for(int j =1;j<=2030;j++){
                if(i * j <=2021) res++;
        }
    }
    cout<< res <<endl;
    return 0;
}
//15698

D: 整数分解（不会)

E: 城邦

分析：构建邻接矩阵，最小生成树套模板（prim）

代码：

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

#define maxn 2030
#define INF 0x3f3f3f3f
int e[maxn][maxn];
int cost[maxn];
bool used[maxn];
int V = 2021;

//prim
int prim(){
    for(int i =1;i<=2021;i++){
        cost[i] = INF;
        used[i] = false;
    }
    cost[1] = 0;
    // used[1] = 1;

    int res = 0;
    while (1)
    {
        int v = -1;
        for(int u = 1;u<=V;u++){
            if(!used[u] && (v==-1 || cost[u] < cost[v])) v = u;
        }
        if(v == -1) break;
        used[v] = 1;
        res += cost[v];
        for(int u = 1;u<=V;u++){
            cost[u] = min(cost[u], e[v][u]);
        }
    }
    return res;
}
//获取权重
int get(int a, int b){
    int res = 0,cnt[10];;
    memset(cnt, 0, sizeof cnt);
    while(a){
        int t = a%10;
        if(!cnt[t]) res += t;
        cnt[t]++;
        a/=10;
    }
    memset(cnt, 0, sizeof cnt);
    while(b){
        int t = b%10;
        if(!cnt[t]) res += t;
        cnt[t]++;
        b/=10;
    }
    return res;
}
void solve(){
   //邻接矩阵
    memset(e, 0, sizeof e);
    for(int i =1;i<=2021;i++)
    {
        for(int j =1;j<=2021;j++)
        {
            if(i == j) continue;
            e[i][j] = e[j][i] = get(i , j);
        }
    }
    prim();
    cout<< prim() <<endl;
}
int main(){
    solve();
    return 0;
}
//27278

程序设计题

F: 特殊年份

分析：根据题意，求各位的数字，进行判断

代码：

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

#define maxn 10

int a[maxn];
int main(){

    for(int i =0;i<5;i++) cin>>a[i];

    int res = 0;
    for(int i=0;i<5;i++){
        int q = a[i] /1000;
        int b = a[i] %1000 / 100;
        int s = a[i] %100 / 10;
        int g = a[i] %10;
        if(q == s && g == b +1) {
            res ++;
        }
    }
    cout<< res;
    return 0;
}

G: 小平方

分析：暴力枚举，数据规模小（1 ≤ n ≤ 10000）

代码：

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

int main(){
    int n;
    cin >> n;
    int res = 0;
    for(int i =1;i<n;i++){
        if( (i*i%n) < (n /2.0)) res++;
    }
    cout<< res;
    return 0;
}

H: 完全平方数（暴力做法）

分析：暴力骗分

代码：

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

#define ll long long
int main(){
    int n;
    cin>>n;
    ll i = 1;
    for(;i<=n;i++){
        ll num = i *n;
        ll sqr = (int)sqrt(num);
        if(sqr*sqr == num ) break;
    }
    cout<< i;
    return 0;
}

I: 负载均衡

分析：优先队列维护任务占用的算力，算力释放的时间 =（ai+di)。每次分配任务前，先释放算力，如果足够分配当前任务，将该任务消耗的算力压入优先队列。

时间复杂度O(m*log(m))，应该能过全部数据吧。

代码：

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

#define maxn 200010
#define PIII pair<int,pair<int,int>>
int n, m;
int arr[maxn];
int a, b, c, d;
priority_queue<PIII,vector<PIII>, greater<PIII> > q;
//释放算力
void getd(){
    while(!q.empty()){
        PIII  node= q.top();
        if(node.first > a) break;
        q.pop();
        int i = node.second.first, v = node.second.second;
        arr[i] += v;
    }
}
//算力排队
void pd(){
    q.push(make_pair(a+c, make_pair(b, d)));
}
//消耗算力
void task(){
    getd();
    if(arr[b] >= d){
        pd();
        arr[b] -= d;
        cout<< arr[b];
    }else{
        cout<<"-1";
    }
}
int main(){
    cin>>n>>m;
    memset(arr, 0 , sizeof arr);
    for(int i =1;i<=n;i++) cin>>arr[i];
    while(m--){
        cin>> a>> b >>c>>d;
        task();
        if(m>0) cout<<endl;
    }
    return 0;
}

J: 国际象棋(不会)

有错的地方请指正