第十届蓝桥杯B组CC++省赛编程题题目及答案解析

目录

试题F：特别数的和

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

试题H：等差数列 

         试题I：后缀表达式

试题J：灵能传输

---

---

试题F：特别数的和

【试题解析】

枚举1-n，取出中满足题意的数累加即可。

#include 

using namespace std;

const int N = 10010;

int main()
{
    int n;
    cin >> n;
    int res = 0;
    for(int i = 1; i <= n; i ++) //枚举1-n的所有数
    {
        int x = i;
        while(x)
        {
            int t = x % 10; //每次取出末位的数
            if(t == 0 || t == 1 || t == 2 || t == 9) 
            {
                res += i;
                break;
            }
            x /= 10; //将末位的数移去
        }
    }
    cout << res;
    return 0;
}

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

【试题解析】

找规律＋双指针，双指针i, j依次枚举每层深度的起点和终点，依次记录每层的权值，输出最大权值对应的层数即可。

​
#include 
#include 
#include 

using namespace std;

const int N = 100010;

typedef long long LL;

int q[N];
int n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        scanf("%d", &q[i]);
        
    LL maxv = INT_MIN, res = 0;
    int depth = 1;
    for(int i = 1; i <= n; i *= 2) //枚举每一层的起点
    {
        LL s = 0;
        for(int j = i; j <= i * 2 - 1 && j <= n; j ++) //对于每一层的起点i,分析可知终点为i * 2 - 1
        {
            s += q[j];   
        }
        if(s > maxv)
        {
            maxv = s, res = depth; //记录最大值及对应的层数
        }
        depth ++;
    }
    cout << res;
    return 0;
}

​

试题H：等差数列 

【题目解析】 

两种做法：1.暴力枚举每一个公差d，找到满足题意的最大公差， 根据 (a[n - 1] - a[0]) / d，

a[n - 1]和a[0]已定，取d最大，即可保证项数最小。

                  2.枚举任意两个数的差，为kd（k为整数)，求出所有kd的最大公约数，即为最大公差。

两种方法在蓝桥杯官网都能AC，但理论上来说第一种暴力的方法时间复杂度为O（）会存在被卡数据的情况。

//暴力做法
#include 
#include 

using namespace std;

const int N = 100010;

int a[N];

int n;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    
    sort(a, a + n);
    
    int d = a[1] - a[0];
    
    if(a[n - 1] == a[0])    cout << n; //特判公差为0的情况，此时项数最少即为n
    for(int j = d; j >= 1; j --)
    {
        bool falg = true;
        for(int i = 1; i < n; i ++)
        {
            if((a[i] - a[i - 1]) % j)
            {
                falg = false;
                break;
            }
        }
        if(falg == true)
        {
            cout << (a[n - 1] - a[0]) / j + 1;
            break;
        }
    }
    return 0;
}

//求kd最大公约数的方法
#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int gcd(int a, int b)
{
    return b? gcd(b, a % b) : a;
}

int a[N];

int n;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    sort(a, a + n);
    int d = a[1] - a[0];
    if(d == 0)
        cout << n;
    else
    {
        for(int i = 1; i < n; i ++)
        {
            d = gcd(d, a[i] - a[0]);
        }
        cout << (a[n - 1] - a[0]) / d + 1;
    }
    return 0;
}

 

试题I：后缀表达式

【试题解析】

贪心，摘自AcWing 1247. 后缀表达式+思维图解 - AcWing 的图解，分析可知当M > 0时，我们总可以将M个‘ - ’号化为一个，此时我们只需减去A中的最小值，再加上A中最大值，剩余的数如果大于0我们就加上，小于0就减去。

（代码很简单，难在理解如何将M个' - '化为一个' - '）

#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

int n, m, k;

const int N = 2e5 + 10;

int a[N];

int main()
{
    cin >> n >> m;
    k = n + m + 1;
    for(int i = 0; i < k; i ++) scanf("%d", &a[i]);
    
    sort(a, a + k);
    LL res = 0;
    
    if(!m)
        for(int i = 0; i < k; i ++ )    res += a[i];
    else
    {
        res = res + a[k - 1] - a[0];
        for(int i = 1; i < k - 1; i ++)
            res += abs(a[i]); //加上大于0的数和减去小于0的数都可以记为加上该数的绝对值
    }
    cout << res;
    return 0;
}

试题J：灵能传输

【试题解析】

又是一道贪心题，这题没写，转发AcWing 1248. 灵能传输--详细说一些细节 - AcWing大佬的题解

#include "bits/stdc++.h"

using namespace std;

typedef long long LL;

const int N = 3e5 + 10;

int t, n;
LL s[N], a[N]; // s为前缀和数组 a为存放前缀和顺序的数组
bool st[N];

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        memset(st, 0, sizeof st);
        for (int i = 1; i <= n; i++)
            cin >> s[i], s[i] += s[i - 1];
        LL s0 = s[0], sn = s[n];
        if (s0 > sn)
            swap(s0, sn);
        sort(s, s + n + 1);
        // 寻找排完序后s0和sn的位置
        // 如果s0和sn相同的话则前面的为s0 后面的为sn
        for (int i = 0; i <= n; i++)
            if (s[i] == s0)
            {
                s0 = i;
                break;
            }
        for (int i = n; i >= 0; i--)
            if (s[i] == sn)
            {
                sn = i;
                break;
            }
        int l = 0, r = n;
        for (int i = s0; i >= 0; i -= 2)
        {
            a[l++] = s[i];
            st[i] = 1;
        }
        for (int i = sn; i <= n; i += 2)
        {
            a[r--] = s[i];
            st[i] = 1;
        }
        for (int i = 0; i <= n; i++)
            if (!st[i])
                a[l++] = s[i];
        LL res = 0;
        for (int i = 1; i <= n; i++)
            res = max(res, abs(a[i] - a[i - 1]));
        cout << res << endl;
    }
    return 0;
}