第十届蓝桥杯省赛CB组

第十届蓝桥杯大赛软件类省赛 C/C++ 大学 B 组

[TOC]

填空题

填空题答案一览

题目 答案 分数
试题 A: 组队 5
试题 B: 年号字串 BYQ 5
试题 C: 数列求值 4659 10
试题 D: 数的分解 43316 10
试题 E: 迷宫 15

试题 A: 组队

略

试题 B: 年号:字串

答案：

解析：

进制转换

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a [100];
    int n = 2019,len = 0;
    while(n>0){
        a[len++] = --n % 26;
        n = n/26;
    }
    for(int i = len-1;i>=0;i--) printf("%c", a[i]+'A');
    cout<< endl;
    return 0;
}

试题 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 n = 20190324;
    int a, b ,c;
    a = b = c =1;
    for(int i =4;i<=n;i++){
        int tmp = a + b + c;
        a = b,b = c, c = tmp%100000;
    }
    cout<< c%10000 <<endl;
    return 0;
}

试题 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
#include <bits/stdc++.h>
using namespace std;

bool get(int a, int b, int c){
    while(a || b || c){
        if(a%10==4 || a%10==2) return 0;
        if(b%10==4 || b%10==2) return 0;
        if(c%10==4 || c%10==2) return 0;
        a/=10, b/=10, c/=10;
    }
    return 1;
}
int main(){
    int n = 2019;
    int ans = n;
    for(int i =0;i<n;i++){
        for(int j =i;j+i<n;j++){
            int k = n - j - i;
            if( k >= j && get(i,j,k)) ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}

试题 E: 迷宫

答案：

解析：

代码：

程序设计大题

试题 F: 特别数的和

题目：

试题 F: 特别数的和

时间限制: 1.0s 内存限制: 256.0MB 本题总分：15 分

【问题描述】

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到

40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

【输入格式】

输入一行包含两个整数 n。

【输出格式】

输出一行，包含一个整数，表示满足条件的数的和。

【样例输入】

40

【样例输出】

574

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n ≤ 10。

对于 50% 的评测用例，1 ≤ n ≤ 100。

对于 80% 的评测用例，1 ≤ n ≤ 1000。

对于所有评测用例，1 ≤ n ≤ 10000。

解析：

枚举1~n的所有数，判断是含有2、0、1、9其中的数字，就加入到答案

代码：

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

bool get(int x){
    while(x){
        int t = x%10;
        if(t == 1 || t == 2 || t ==0 || t == 9) return 1;
        x /=10;
    }
    return 0;
}
int main(){
    int n, ans = 0;;
    cin>>n;
    for(int i = 1;i<=n;i++){
        if(get(i)) ans += i;
    }
    cout<< ans <<endl;
    return 0;
}

试题 G: 完全二叉树的权值

题目：

试题 G: 完全二叉树的权值

时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分

【问题描述】

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从

上到下、从左到右的顺序依次是 A1, A2, · · · A**N，如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点

权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

【输入格式】

第一行包含一个整数 N。

第二行包含 N 个整数 A1,

A2, · · · A**N 。

【输出格式】

输出一个整数代表答案。

【样例输入】

7

1 6 5 4 3 2 1

【样例输出】

2

【评测用例规模与约定】

对于所有评测用例，1 ≤ N ≤ 100000，−100000 ≤ A**i ≤ 100000。

解析：

完全二叉树数组的层次遍历，注意int数值会越界

代码：

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 maxn 100005
int n, a[maxn];
int main(){
    cin>> n;
    for(int i =0;i<n;i++) cin>>a[i];
    long maxv = LONG_MIN;int maxf = 0;
    int i = 0, f = 0;
    while(i < n){
        long sum = 0;
        for(;i<(1<<f);i++) sum+=a[i];
        if(sum > maxv){
            maxv = sum, maxf = f;
        }
        ++f;
    }
    cout<< maxf <<endl;
    return 0;
}

试题 H: 等差数列

题目：

试题 H: 等差数列

时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分

【问题描述】

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

【输入格式】

输入的第一行包含一个整数 N。

第二行包含 N 个整数 A1, A2, · · · , A**N。(注意 A1 ∼ A**N 并不一定是按等差数列中的顺序给出)

【输出格式】

输出一个整数表示答案。

【样例输入】

5

2 6 4 10 20

【样例输出】

10

【样例说明】

包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、18、20。

【评测用例规模与约定】

对于所有评测用例，2 ≤ N ≤ 100000，0 ≤ A**i ≤ 109。

解析：

求排序后的数列的所有相邻差值的最小公倍数，再计算相邻之间是否要补多少数。

求得补的数+n就是答案

代码：

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;

#define maxn 100005
int n, a[maxn];

int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int main(){
    cin >> n;
    int minv = INT_MAX;
    for(int i =0;i<n;i++) cin >> a[i];
    sort(a, a + n);
    int x = a[1] - a[0];
    for(int i =1;i<n-1;i++) x = gcd(a[i+1] -a[i], x);
    int res = 0;
    for(int i =0;i<n-1;i++) res += ((a[i+1]-a[i])/x-1);
    cout << res + n<<endl;
    return 0;
}

试题 I: 后缀表达式

解析：

排序，小的减，大的加

代码：

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 maxn 200005
#define ll long long
int N, M, a[maxn];
int main(){
    cin >> N >> M;
    int n = N+M+1;
    for(int i = 0;i<n;i++) cin>> a[i];
    sort(a, a+n);
    ll res = 0;
    int i = 0;
    while(M--) res -= a[i++];
    while(i<n) res += a[i++];
    cout<< res <<endl;
    return 0;
}