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

[TOC]

拿到试题解压一看，就这？啪的一下A题直接提交1，传统功夫A题点到为止。这题不用优化，那题直接暴力求解，半个小时不到就到了J题，很快啊。回头一检查，这题写错了、这题看错题意，全部丢分了，我大意了啊，他说他是简单题，他可不是简单题，排列组合、质因数分解、prim、优先队列、回溯，看来是有备而来！我劝年轻人好自为之，好好反思，以后不要再犯这样的聪明，贪图一时快…武林要以和为贵，要细心读题，仔细码题，谢谢朋友们！

考前：第一场这么难..

拿到试题：重铸省一荣光，我辈义不容辞

看了大佬题解：拿到省三就算成功

结果填空题

填空题答案一览

题目 答案 分值
A: 求余 $1$ $5$
B: 双阶乘 $59375$ $5$
C: 格点 $15698$ $10$
D: 整数分解 $691677274345$ $10$
E: 城邦 $4046$ $15$

A: 求余

代码：

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>
using namespace std;

int main(){
    cout<< 2021%20 <<endl;
    return 0;
}
//1

B: 双阶乘

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

代码:

1
2
3
4
5
6
7
8
9
10
#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: 格点

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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: 整数分解

解法一-四重循环暴力求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main(){ 
    long long res = 0;
    int n =2021;
    for(int a = 1;a<=500;a++){
        int an = n-a;
        for(int b = a;b<=1000;b++){
            int bn = an -b;
            for(int c = b;c<=1500;c++){
                int cn = bn -c ;
                for(int d = c;d<=cn;d++){
                    int e = cn - d;
                    int t = 0;
                    if(e >= d){
                        //五个相等
                        if(a == e) t =1;
                        //四个相等
                        else if((a==d) || (b==e)) t =5;
                        //三个相等                        
                        else if((a==c) || (b==d) || (c==e)) t= 20;
                        //两对相等
                        else if((a==b && c==d) || (a==b && d==e) || (b==c && d ==e)) t= 30;
                        //一对相等
                        else if(a==b || b==c || c==d || d==e) t = 60;
                        //全不相等
                        else t = 120;
                    }

                    res += t;
                }
            }
        }
    }
    cout<< res <<endl;
    return 0;
}
//691677277715

解法二-转换思路的三重循环：

分析：三重循环枚举三个数，差是m，和为m的两个正整数可能是m-1种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main()
{
	ll res = 0;
	int n = 2021;
    for(int a = 1;a<=n;a++)
        for(int b = 1;b<=n;b++)
            for(int c = 1;c<=n;c++)
            {
                int d = n -a -b -c;
                if(d <= 1) break;
                res += d-1;
            }
	cout<< res <<endl;
	return 0;
}
//691677274345

解法三-动态规划：

1-2021，取五个数的和是2021的可能数

$dp[i][j]$表示$i$个数和为$j$的可能数

$k$表示$dp[i-1][j-k]$加上一个数$k$，就是$dp[i][j]$的所有可能

$$
dp[i][j] = \begin{cases} dp[i][j] +dp[i-1]j-k\0 \end{cases}
$$
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main(){
    ll dp[6][2022];
    memset(dp, 0, sizeof dp);
    for(int i = 1;i<2022;i++) dp[1][i] = 1; //边界处理
    for(int i =2;i<=5;i++)
        for(int j =1; j<2022;j++)
            for(int k = 1;k<2022;k++){
                if(j-k > 0) dp[i][j] += dp[i-1][j-k];
            }
    cout<< dp[5][2021];
    return 0;
}
//691677274345

隔板法

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>
using namespace std;

int main() {
	cout<< 1ll*2020*2019*2018*2017/4/3/2<<endl;
	return 0;
}

E: 城邦

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

这题比赛的时候理解错权重了，给的数据

2021 和 922加起来是 (2 + 0 + 1) + (0 + 9 + 2) = 14

以为权重等于不同数字的和！！！15分凉凉

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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(){
    memset(cost , INF , sizeof cost);
    memset(used , false, sizeof used);  
    cost[1] = 0;
    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;
    while(a || b){
        if(a%10 != b%10) res+=a%10 + b%10;
        a/=10, 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);
        }
    }
    cout<< prim() <<endl;
}
int main(){
    solve();
    return 0;
}
//4046

程序设计题

F: 特殊年份

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#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: 完全平方数

分析：对n进行质因数分解，将奇数个的所有质因数的乘积就是答案。

$ \sqrt{p} = \sqrt{p_1^{a1} \cdot P_2^{a2} \cdot P_3^{a3}} = \sqrt{p_1^{a1}} \cdot\sqrt{ P_2^{a2}} \cdot \sqrt{P_3^{a3}}，当a1是偶数时，\sqrt{p_1^{a1}} = \sqrt{p_1^{a1/2}} \cdot \sqrt{p_1^{a1/2}}, a2 、a3 同理$

举例子：对某个数$a$质因数分解的结果是：$a = 2 ^3 \cdot 3^3$，那么$res = a \cdot 2 \cdot 3$，$res$就是完全平方数，答案是$6$;

举例子：某个数的质因数分解的结果是：$a = 2 ^2 \cdot 3^3 \cdot 5^3$， 那么$res = a \cdot 3 \cdot 5$，$res$就是完全平方数，答案是$15$；

举例子：某个数的质因数分解的结果是：$a = 2 ^2 \cdot 3^2 \cdot 5^2$， 那么$res = a$，$res$就是完全平方数，答案是$1$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main(){
    ll n;
    cin>>n;
    ll res =1;
    for(int i =2;i<=10000010;++i){
        if(n<2) break;
        ll t = 0;
        while(n%i==0){
            ++t;
            n/=i;
        }
        if(t%2==1) res *= i;
    }
    cout << res;
    return 0;
}

I: 负载均衡

分析：

代码要实现的功能总结：枚举所有任务，对于当前每个任务，消耗算力并将该算力倒计时，直到任务结束返回算力（当前任务消耗d算力c秒）。

由于时间的数据范围10^9，枚举所有的时间会超时。怎么进行算力倒计时决定了这道题的时间复杂度

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

时间复杂度$O(m\cdot\log m)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

#define maxn 200010
int n, m;
int arr[maxn];
int a, b, c, d;
struct Node
{
    int endTime, id , val;
    bool operator< (const Node &node)const {
        return endTime > node.endTime;
    }
};

priority_queue<Node> q;
//释放算力
void getd(){
    while(!q.empty()){
        Node t= q.top();
        if(t.endTime > a) break;
        q.pop();
        int i =t.id, v = t.val;
        arr[i] += v;
    }
}
//消耗算力
void task(){
    getd();
    if(arr[b] >= d){
        q.push({a+c, b ,d});//算力排队
        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: 国际象棋(状态压缩DP)

当前行的摆放位置，受到前两行的约数，重复子问题，可以用dp。由于n很小，所以可以用状态压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = 1<<6,K = 21, MOD = 1e9+7;
int n, m ,k;
int dp[N][M][M][K];
#define ll  long long

int getCnt(int num){
    int res = 0;
    while (num)
    {
        res ++;
        num &= (num-1);
    }
    return res;
}
int main(){
    cin >> n >> m >> k;
    dp[0][0][0][0] = 1;
    for(int i =1;i<=m;i++){
        for(int a = 0;a< 1<<n;a++){
            for(int b = 0; b< 1<<n;b++){
                if(a & (b << 2) || b & (a << 2)) continue;
                for(int c = 0;c < 1<<n; c++){
                    if(b & (c << 2) || c & (b << 2)) continue;
                    if(a & (c << 1) || c & (a << 1)) continue;
                    int t = getCnt(a);
                    for(int j = t;j<=k;j++){
                        dp[i][a][b][j] += dp[i-1][b][c][j-t] % MOD;
                    }
                }
            }
        }
    }
    ll res = 0;
    for(int i =0;i<1<<n;i++)
        for(int j =0;j< 1<<n;j++)
            res += dp[m][i][j][k]%MOD;

    cout<< res %MOD <<endl;
    return 0;
}

蓝桥杯

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！