第十届蓝桥杯大赛C++A组

试题B,D,F均为B组原题

试题A:平方和

题目描述

小明对数位中含有2、0、1、9 的数字很感兴趣,在1 到40 中这样的数包
括1、2、9、10 至32、39 和40,共28 个,他们的和是574,平方和是14362。
注意,平方和是指将每个数分别平方后求和。
请问,在1 到2019 中,所有这样的数的平方和是多少?

  • 暴力判断
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll ans;
bool judge(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() {
	for(int i=1;i<=2019;i++){
		if(judge(i)){
			ans+=i*i;
		}
	}
	cout<<ans;
    return 0;
}

试题C:最大降雨量

题目描述

​ 由于沙之国长年干旱,法师小明准备施展自己的一个神秘法术来求雨。
​ 这个法术需要用到他手中的49 张法术符,上面分别写着1 至49 这49 个数字。
法术一共持续7 周,每天小明都要使用一张法术符,法术符不能重复使用。
​ 每周,小明施展法术产生的能量为这周7 张法术符上数字的中位数。
法术施展完7 周后,求雨将获得成功,降雨量为7 周能量的中位数。
​ 由于干旱太久,小明希望这次求雨的降雨量尽可能大,请大最大值是多少?

  • 贪心:保证第四周第四天的降雨量最大
34

试题E:RSA解密

img

试题G:外卖店优先级

题目描述

​ “饱了么”外卖系统中维护着N 家外卖店,编号1~N。
每家外卖店都有一个优先级,初始时(0 时刻) 优先级都为0。
​ 每经过1 个时间单位,如果外卖店没有订单,则优先级会减少1,最低减到0;
而如果外卖店有订单,则优先级不减反加,每有一单优先级加2。
​ 如果某家外卖店某时刻优先级大于5,则会被系统加入优先缓存中;
如果优先级小于等于3,则会被清除出优先缓存。
​ 给定T 时刻以内的M 条订单信息,请你计算T 时刻时有多少外卖店在优先缓存中。

输入

第一行包含3 个整数N、M 和T。
以下M 行每行包含两个整数ts 和id,表示ts 时刻编号id 的外卖店收到一个订单
1<=N, M, T<=100000,1<=ts<=T,1<=id<=N。

输出

输出一个整数代表答案。

样例输入

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

样例输出

1
#include<bits/stdc++.h>

using namespace std;

int m,n,t;
//store[id]第id号店上一次有的订单
//flag[id]存储第id号店在不在优先缓存中
//value[id]存储第id号店的得分

int store[100010],flag[100010],value[100010];

struct node{
    int time,id;
}a[100010];

bool cmp(node a , node b){
    if(a.id==b.id)
        return a.time<b.time;
    return a.id<b.id;
}

int main(){
    cin>>n>>m>>t;
    for(int i=0;i<m;i++){
        cin>>a[i].time>>a[i].id;
    }
    sort(a,a+m,cmp);
    for(int i=0;i<m;i++){
        int tt=a[i].time,id=a[i].id;
        //如果当前的订单不等于上一次的订单,则减去它们之间的间隔
        //因为如果没有订单,则每个时刻减1
        if(tt!=store[id])
            value[id]-=tt-store[id]-1;
        //value的值要大于等于0
        value[id]=max(0,value[id]);
        if(value[id]<=3)
            flag[id]=0;
        value[id]+=2;
        if(value[id]>5)
            flag[id]=1;
        store[id]=tt;
    }
    for(int i=1;i<=n;i++){
    //如果这个店的最后一个订单不是第 t 分钟的
    //就减去最后一个订单的时间到 t 时间之间应该减去的
        if(store[i]<t){
            value[i]-=t-store[i];
            if(value[i]<=3)
                flag[i]=0;
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++)
        if(flag[i])
            ans++;
    cout<<ans;
    return 0;
}

试题H:修改数组

题目描述

​ 给定一个长度为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(1<=N<=100000)
第二行包含N个整数A1,A2,...,AN(1<=Ai<=1000000)

输出

输出N个整数,依次是最终的A1,A2,...,AN

样例输入

5
2 1 1 3 4

样例输出

2 1 3 4 5
  • 并查集
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=1000005;

int n,ns[N],p[N];

int find(int x){
	if(x!=p[x]){
		p[x]=find(p[x]);
	}
	return p[x];
}

int main(){
 	cin>>n;
 	for(int i=0;i<n;i++){
 		cin>>ns[i];
	}
	for(int i=0;i<=N;i++)
		p[i]=i;
	
	for(int i=0;i<n;i++){
		int x =find(ns[i]);
		cout<<x<<" ";
		p[x]=x+1;
	}
	
    return 0;
}

试题I:糖果

题目描述

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

输入

第一行包含三个整数N、M 和K。
接下来N 行每行K 这整数T1,T2,...,TK,代表一包糖果的口味。
1<=N<=100,1<=M<=20,1<=K<=20,1<=Ti<=M。

输出

一个整数表示答案。如果小明无法品尝所有口味,输出-1。

样例输入

6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

样例输出

2
  • 状压DP(不会

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×