2019第十届蓝桥杯c++A组省赛试题及个人解法_蓝桥杯第十届c++真题a组

第十届蓝桥杯2019年C/C++ 大学A组省赛试题

2019年蓝桥杯第十届软件类省赛#

C/C++ 大 学 A 组#

试题 A: 平方和#（暴力）

本题总分：5 分

【问题描述】
小明对数位中含有 2、0、1、9 的数字很感兴趣，在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574，平方和是 14362。注意，平方和是指将每个数分别平方后求和。
请问，在 1 到 2019 中，所有这样的数的平方和是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
提示：如果你编写程序计算，发现结果是负的，请仔细检查自己的程序， 不要怀疑考场的编程软件。

2658417853 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool ok(int x)
{
    while(x)
    {
        if(x%10==2||x%10==0||x%10==1||x%10==9)return true;
        x/=10;
    }
    return false;
}
int main()
{
    ll ans=0;
    for(int i=1;i<=2019;i++)if(ok(i))ans+=i*i;
    cout<<ans<<endl;
}

试题 B: 数列求值#（暴力）

本题总分：5 分

【问题描述】
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求
第 20190324 项的最后 4 位数字。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个 4 位整数（提示：答案的千位不为 0），在提交答案时只填写这个整数，填写多余的内容将无法得分。

4659

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll f1,f2,f3;
    ll tmp;
    f1=f2=f3=1;
    for(int i=4;i<=20190324;i++)
    {
        tmp=((f1+f2)%10000+f3)%10000;
        f1=f2;
        f2=f3;
        f3=tmp;
    }
    cout<<tmp<<endl;
}

 

试题 C: 最大降雨量#(构造）

本题总分：10 分

【问题描述】
由于沙之国长年干旱，法师小明准备施展自己的一个神秘法术来求雨。
这个法术需要用到他手中的 49 张法术符，上面分别写着 1 至 49 这 49 个
数字。法术一共持续 7 周，每天小明都要使用一张法术符，法术符不能重复使用。
每周，小明施展法术产生的能量为这周 7 张法术符上数字的中位数。法术
施展完 7 周后，求雨将获得成功，降雨量为 7 周能量的中位数。
由于干旱太久，小明希望这次求雨的降雨量尽可能大，请大最大值是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

34

证明：无法找到比34更优的方案了。如下图，假设每周选的数已经排好序

第一周: x  x  x  x  x  x  x  ( x1,x2,x3,x4,x5,x6 满足 x1<x2<x3<x4<x5<x6）
第二周: x  x  x  x  x  x  x
第三周: x  x  x  x  x  x  x
第四周: x  x  x  x  x  x  x
第五周: x  x  x  x  x  x  x
第六周: x  x  x  x  x  x  x
第七周: x  x  x  x  x  x  x 

则标记红色的是每周的中位数：

第一周: x  x  x  x  x  x  x  
第二周: x  x  x  x  x  x  x
第三周: x  x  x  x  x  x  x
第四周: x  x  x  x  x  x  x
第五周: x  x  x  x  x  x  x
第六周: x  x  x  x  x  x  x
第七周: x  x  x  x  x  x  x 

此时不看第几周,每一行里：红色的x右边的x必然比x大。

假设上面的七行按行按照x由小到大重新排序后得到

x  x  x  x1  x  x  x  
x  x  x  x2  x  x  x
x  x  x  x3  x  x  x
x  x  x  x4  x  x  x
x  x  x  x5  x  x  x
x  x  x  x6  x  x  x
x  x  x  x7  x  x  x 

则x1<x2<x3<x4<x5<x6<x7  题目要求的中位数的中位数就是x4了

问题是x4最大能取到多少呢？注意到上图中x4右下角(如下图）的元素都应比x4大。。(共15个)

因此答案为49-15=34

x  x  x  x    x  x  x  
x  x  x  x    x  x  x
x  x  x  x    x  x  x
x  x  x  x4  x  x  x
x  x  x  x    x  x  x
x  x  x  x    x  x  x
x  x  x  x    x  x  x 

 

试题 D: 迷宫#（BFS)

本题总分：10 分

试题没有。思路就是bfs。注意字典序最小的答案可通过设置D,L,R,U的优先级别来获得。

 

 

试题 E: RSA 解密#（数论）

试题没有。由于模数n太大,要用到快速幂和快速加才不会爆long long.

分解n以后还要会求欧拉函数才能做出此题。

 

试题 F: 完全二叉树的权值（二叉树简单性质）

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

【问题描述】
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · AN 。
【输出格式】
输出一个整数代表答案。
【样例输入】
7
1 6 5 4 3 2 1

【样例输出】
2

【评测用例规模与约定】
对于所有评测用例，1 ≤ N ≤ 100000，−100000 ≤ Ai ≤ 100000。

Mycode:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100005];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int level=1;//层数
    ll MAX=a[1];
    ll ans=1;//第一层
    int num=1;//该层的节点数
    int pos=2;//下一层开头指针位置
    for(;;)
    {
        level++;
        num*=2;
        ll sum=0;
        for(int j=pos;j<=min(pos+num-1,n);j++)sum+=a[j];
        if(sum>MAX)
        {
            ans=level;
            MAX=sum;
        }
        pos=pos+num;
        if(pos>n)break;
    }
    printf("%lld\n",ans);
    return 0;
}

 

 

试题 G: 外卖店优先级#

这题赛后想想当时做的很差。。

 

 

试题 H: 修改数组#（树状数组+二分）

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

【问题描述】
给定一个长度为 N 的数组 A = [A1, A2, · · · AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改
A2, A3, · · · , AN。
当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则小明会给 Ai 加上 1 ；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直到 Ai 没有在 A1 ∼ Ai−1 中出现过。
当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。现在给定初始的 A 数组，请你计算出最终的 A 数组。
【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · , AN 。
【输出格式】
输出 N 个整数，依次是最终的 A1, A2, · · · , AN。
【样例输入】
5
2 1 1 3 4

【样例输出】
2 1 3 4 5

【评测用例规模与约定】
对于 80% 的评测用例，1 ≤ N ≤ 10000。
对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。

Mycode：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int bit[2000050];
int  n=1000001;
int sum(int i)
{
    int s=0;
    while(i>0)
    {
        s+=bit[i];
        i-=i&-i;
    }
    return s;
}
void add(int i,int x)
{
    while(i<=n)
    {
        bit[i]+=x;
        i+=i&-i;
    }
}
bool ok(int k,int pre)
{
    int l=k-pre+1;
    int cnt=sum(k)-sum(pre-1);
    return cnt<l;
}
bool vis[1000005];
int ans[100005];
int N;
int a[100005];
int main()
{
    scanf("%d",&N);
    for(int i=0;i<N;i++)scanf("%d",&a[i]);
    for(int i=0;i<N;i++)
    {
        if(!vis[a[i]])
        {
            ans[i]=a[i];
            vis[a[i]]=1;
            add(a[i],1);
        }
        else {
            int l=a[i];int r=1000002;
            int mid;
            while(r-l>1)
            {
                mid=(l+r)/2;
                if(ok(mid,a[i]))r=mid;
                else l=mid;
            }
            ans[i]=r;
            vis[r]=1;
            add(r,1);
        }
    }
    for(int i=0;i<N;i++)printf("%d%c",ans[i],i==N-1?'\n':' ');
    return 0;
}
 
 
 
 
 
 

 

 

试题 I: 糖果#（状压dp）（感觉更可能是最小费用流？）

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

【问题描述】
糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种口味编号 1 ∼ M。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而 是 K 颗一包整包出售。
幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。
给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

【输入格式】
第一行包含三个整数 N、M 和 K。
接下来 N 行每行 K 这整数 T1, T2, · · · , TK，代表一包糖果的口味。
【输出格式】
一个整数表示答案。如果小明无法品尝所有口味，输出 −1。
【样例输入】
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

【样例输出】
2

【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ N ≤ 20 。
对于所有评测样例，1 ≤ N ≤ 100，1 ≤ M ≤ 20，1 ≤ K ≤ 20，1 ≤ Ti ≤ M。

Mycode:

#include<bits/stdc++.h>
using namespace std;
int dp[1000005];
int n,m,k;
int s[105];//代表第i包糖果
int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++)
    {
        int ss=0;
        int t;
        for(int j=0;j<k;j++)
        {
            scanf("%d",&t);
            ss|=(1<<(t-1));
        }
        s[i]=ss;
        dp[ss]=1;
    }
 
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<(1<<m);j++)
        {
            if(dp[j]==-1)continue;
            if(dp[j|s[i]]==-1)dp[j|s[i]]=dp[j]+dp[s[i]];
            else dp[j|s[i]]=min(dp[j|s[i]],dp[j]+dp[s[i]]);
        }
    }
    printf("%d\n",dp[(1<<m)-1]);
    return 0;
}

 

 

试题 J: 组合数问题#

这题赛场上不会做只会用暴力骗一些分。就先不写了。

 

总结：蓝桥杯这种没有即时判题返回结果的方式真的很让人抓狂，很容易失误，所以必须小心再小心。哎，说到底自己还是太菜了。