2019蓝桥杯A组C++题目_2019蓝桥杯国赛 csdn a组

2019 蓝桥杯 A组题目解析

试题A：平方和

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

#include<iostream>
using namespace std;
int num[4] = {1,2,0,9}; 
int isIn(int value){
    //拆分后的个位数
	int sub;
    //拆分
	while (value){
		//得到当前整数 尾位数
		sub = value % 10;
		//切割这一整形
		value /= 10;
		//输出
//		cout << sub;
		for(int k = 0;k < 4;k++){
			if(sub == num[k]){
				return 1;
			}
		}
	}
	return 0;
}

int check(int value){
	while(value){
		if(value % 1 == 0 || value % 2 == 0 || value % 9 == 0 || value % 10 == 0){
			return true;
		}
	}
	return false;
}
int main(){
	//终于知道为什么要 long long
//	int result = 0;
	long long result = 0;
	for(int i = 1;i <= 2019;i++){
		if(check(i)){
			result += i*i;
		}
	}
	cout << result << endl;
}
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

试题B：数列求值

【问题描述】
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求
第 20190324 项的最后 4 位数字。

#include <iostream>
using namespace std;
//已知项数求前c项 
void fibo(int num){
	int a = 1,b = 1,c;
	cout << 1 << " " << 1 << " ";
	for(int i = 3;i <= num;i++){
		c = a + b;
		b = a;
		a = c;
		cout << c << " ";
	}
	cout << endl;
	// 打印出第10项 
	cout << c << endl;
}
void prefix_sum(long long int N){
	long long int a = 1,b = 1,c = 1;
    long long int d;
    cout << a << " " << b << " " << c << " ";
    for(int i=4;i <= N;i++)
    {
        d = (a+b+c) % 10000;
        a = b;
        b = c;
        c = d;
        cout << d << " ";
    }
    cout << endl;
    //打印出第10项 
    cout<< d <<endl;
}
void prefix_sum2(long long int target){
	long long int a = 1,b = 1,c = 1;
    long long int d;
    long long index;
    if (target == 1){
    	cout << 1;
	}
	index = 3;
    while(d <= target){
    	d = (a+b+c) % 10000;
        a = b;
        b = c;
        c = d;
        index ++;
        if(d == target){
        	break;
		}
	}
    cout << index << endl;
}
int main()
{
   
    fibo(10);
    prefix_sum(10);
    prefix_sum2(105);
    return 0;
}
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
59
60

顺便复习一下斐波那契数列

试题C：最大降雨量

#include<iostream>
#include<algorithm>
using namespace std;
//	建立7*7二维数组
//	从左到右严格递增
//	使每行中位数从上到下严格递增
//	得出该二维数组中位数右下角均为比它大的数
//	则中位数最大值为49-16+1
int main(){
	cout << 49 - 16 + 1 << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

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

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

【样例输出】
2

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
int N;
void print(vector<int>arr,int n){
	for(int i = 1;i < n;i++){
		cout << arr[i] << " ";
	}
	cout << endl;
}
int main(){
	cin >> N;
	int arr[N+1];
	for(int i = 1;i <= N;i++){
		cin >> arr[i]; 
	}
	int p = 1;
	vector<int>res(20);
	for(int i = 1;i <= N;i++){
		if(i >= pow(2,p)){
			p++;
		}
		res[p] += arr[i];
		
	}
	int max_v = res[1],Min=1;
	for(int i=1;i<=temp;i++){
		if(res[i]>max_v){
			Min=i;
			max_v=res[i];
		}
	}
	//打印中间res数组看下
	print(res,4);
	cout << Min << endl;
	return 0;
}
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

试题 G: 外卖店优先级

【问题描述】
“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有一个优先级，初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果优先级小于等于 3，则会被清除出优先缓存。
给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中。
【输入格式】
第一行包含 3 个整数 N、M 和 T 。
以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到一个订单。
【输出格式】
输出一个整数代表答案。
【样例输入】
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

【样例输出】
1

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
//构建订单结构体
struct order{
	int ts;
	int id;
	order(int t,int i){
		this->ts = t;
		this->id = i;
	}
	bool operator <(const order& rhs) const{
		return rhs.ts < ts;
	}
};
int N,M,T,ts,id;
int sum[maxn],book[maxn];
int main(){
	//优先队列，根据订单的时间出队
	priority_queue<order> q;
	cin >> N >> M >> T;
	while(M--){
		cin >> ts >> id;
		q.push(order(ts,id));
	}
	int ans = 0;
	while(!q.empty()){
		order temp = q.top();q.pop();
		id = temp.id;
		cout << temp.ts << " " << temp.id << endl;
		for(int i = 1;i <= N;i++){
			if (i == id) continue;
			// 对于每一个不是 id 的 店铺  sum[id] -= 1; 
			if (sum[i] > 0) sum[i]--;
			// 如果已经入优先缓存，并且优先级 <= 3 则 提出优先缓存
			if (sum[i] <= 3 && book[i]){
				book[i] = 0;
				ans--;
			}
		}
		sum[id] += 2;
		//如果没有进入优先缓存，并且优先级>5
		if(!book[id]&& sum[id] > 5){
			book[id] = 1;
			ans++;
		}
		
	}
	for(int j = 1;j <= 2;j++){
		cout << sum[j] << " ";
	}
	cout << endl;
	for(int j = 1;j <= 2;j++){
		cout << book[id] << " ";
	}
	cout << endl;
	cout << ans << endl;
	return 0;
}

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
59
60

试题 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。
第二行包含 N 个整数 A1, A2, · · · , AN 。
【输出格式】
输出 N 个整数，依次是最终的 A1, A2, · · · , AN。
【样例输入】
5
2 1 1 3 4
【样例输出】
2 1 3 4 5

int main(){
	int N;
	cin >> N;
	set<int> s;
	vector<int>arr;
	while(N--){
		cin >> x;
		while(s.count(x)) x++;
		s.insert(x);
		arr.push_back(x); 
	}
	for(int i = 0;i < arr.size();i++){
		cout << arr[i] << " ";
	}
	return 0;
	
}
int main(){
	unordered_map<int,int>map;
	vector<int>arr; 
	long long int N,x;
	cin >> N;
	while(N--){
		cin >> x;
		while(map[x]) x++;
		map[x]++;
		arr.push_back(x); 
	}
	
	for(int i = 0;i < arr.size();i++){
		cout << arr[i] << " ";
	}
	return 0;
}
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

第I题：糖果

【问题描述】
糖果店的老板一共有 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
思路：
显然的状压 $dp$ +滚动数组
$dp(i,j)dp(i,j)dp(i,j)$表示前$i$个数字组成j状态需要选择的最少糖果集数。
$dp(i,j|a[i])=min(dp(i-1,j|a[i]),j)+1))$

#include<bits/stdc++.h>
using namespace std;
const int maxn = (1<<20) +52;
const int inf = 1000;
int a[505], n, m, k, dp[2][maxn];

int min(int a, int b){
    return  a < b ? a:b;
}
int min(int a,int b,int c){
	return min(min(a,b),c);
}
void print(int N){
	for(int i = 0;i < 2;i++){
		for(int j = 0;j < N;j++){
			cout << dp[i][j] << " ";
		} 
		cout << endl << "*******************************" <<endl;
	
	}
} 
int main(){
    scanf("%d%d%d",&n,&m,&k);
    int e=1<<m;
    //输入
    for(int i=1;i<=n;i++){
        a[i]=0;
        for(int j=0;j<k;j++){
            int temp;
            scanf("%d",&temp);
            a[i]= a[i] | 1<<(temp-1);
            //当temp为 3时 即是 8所 以要先减一才对应得到 100
			//当temp为 4时 即是 16 所以要先减一才对应得到 1000
			// 100 | 1000 得到 1100 
        }
    }
    //初始化
    for(int i=0;i<maxn;i++){
        dp[0][i]=dp[1][i] = inf;
    }
    dp[0][0]=0;
    
    //递推dp
    bool pos=1;
    for(int i=1;i<=n;i++,pos=!pos){
        for(int j=0;j<e;j++){
            dp[pos][j]=dp[!pos][j];
        }
        for(int j=0;j<e;j++){
//        	cout << dp[!pos][j|a[i]] << " " << dp[!pos][j]+1 << endl;
//			还要和自己比较，是因为在迭代的过程中会覆盖调已经修改的值
//			j = 0, dp[pos][j|a[i]] = 1
//			j = 1, dp[pos][j|a[i]] = inf
//			因此会发生覆盖 
            dp[pos][j|a[i]]= min(dp[!pos][j|a[i]],dp[pos][j|a[i]],dp[!pos][j]+1);
//            cout << dp[pos][j|a[i]] << endl;
        }
        print(e);
    }
    //输出答案
    if(dp[!pos][e-1]==inf){
        printf("-1\n");
    }
    else  printf("%d\n",dp[!pos][e-1]);
    return 0;
}

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
59
60
61
62
63
64
65
66
67