devbox
算法研究专家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

第十届蓝桥杯（省赛c++）_第十届蓝桥杯n组

作者：算法研究专家 | 2024-01-30 19:45:57

赞

踩

第十届蓝桥杯n组

真题训练

目录

1.（5分）

2.（5分） 

3.

4.（10分）

5.（15分）

6.（15分）

7.（15分）

8.（20分）

9.（25分）

1.（5分）

问题描述

　　小明对数位中含有 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到2019的平方和，存储这个平方和必须用long，不然int存储不了

  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. bool judge(int n){
  5. 	int t=n;
  6. 	while(t>0){
  7. 		int x=t%10;
  8. 		if(x==2||x==0||x==1||x==9)
  9. 			return true;
  10. 		t=t/10;
  11. 	}
  12. 	return false;
  13. }
  14.  
  15.  
  16. int main() {
  17. 	long long sum=0;
  18. 	for(int i=1;i<=2019;i++){
  19. 		if(judge(i)){
  20. 			sum+=i*i;
  21. 		}
  22. 	}
  23. 	std::cout<<sum;
  24. 	return 0;
  25. }

2.（5分） 

 

这道题我看网上很多题解都是跑不了的，利用斐波那契迭代版可以快速解出，O(1)空间，O(n)时间

  1. #include <stdio.h>
  2. int main(){
  3.   long int num1=1,num2=1,num3=1,num4=0;
  4.   long long i=3;
  5.   while(i<20190324){
  6. 	  num4=(num1+num2+num3)%10000;
  7. 	  num1=num2;
  8. 	  num2=num3;
  9. 	  num3=num4;
  10. 	  i++;
  11.   }
  12.    printf("%ld",num4);
  13.   return 0;
  14. }

3.

这题关键在于很多人做题会错误地用各种方法，或者是贪心的思想：（49+48+47+46+45+44+43），但是这种做法是错误的，因为求的是中位数，如果第二周的48是那一周的能量（中位数），那么就没有存在三张法术符大于48，所以

这道题不用编程就可以解决，

第一周：X X X 46 47 48 49（X代表只要比后四个数任意小就可以）

第二周：X X X 42 43 44 45

第三周：X X X 38 39 40 41

.....................

以此类推，很快就能得到（46+42+38+34+30+26+22）=238

4.（10分）

 直接暴力，但是可以回溯法（BFS）

下面的文章有完整解析

(2条消息) C++算法——BFS（图解）_隰有游龙的博客-CSDN博客_c++bfs

下面是大佬的代码

 (2条消息) 第十届蓝桥杯 ——迷宫_业余算法学徒的博客-CSDN博客

  1. #include <iostream>
  2. #include <cstring>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. typedef pair<int, int> PII;
  7.  
  8. char g[30][50];
  9. int dist[30][50];
  10.  
  11. char dir[] = {'D', 'L', 'R', 'U'};
  12. int dx[] = {1, 0, 0, -1}, dy[] = {0, -1, 1, 0};
  13.  
  14. void bfs()
  15. {
  16. 	memset(dist, -1, sizeof dist);
  17. 	queue<PII> q;
  18. 	q.push({29, 49});
  19. 	dist[29][49] = 0;
  20. 	
  21. 	while(q.size())
  22. 	{
  23. 		PII t = q.front();
  24. 		q.pop();
  25. 		
  26. 		for (int i = 0; i < 4; i ++)
  27. 		{
  28. 			int a = t.first + dx[i], b = t.second + dy[i];
  29. 			if(a < 0 || a >= 30 || b < 0 || b >= 50) continue;
  30. 			if(g[a][b] == '1' || dist[a][b] != -1) continue;
  31. 			q.push({a, b});
  32. 			dist[a][b] = dist[t.first][t.second] + 1;
  33. 		}
  34. 	}
  35. }
  36.  
  37. int main()
  38. {
  39. 	for (int i = 0; i < 30; i ++) cin >> g[i];
  40. 	
  41. 	bfs();
  42. 	
  43. 	string ans;
  44. 	int x = 0, y = 0;
  45. 	while(x != 29 || y != 49)
  46. 	{
  47. 		for (int i = 0; i < 4; i ++)
  48. 		{
  49. 			int a = x + dx[i], b = y + dy[i];
  50. 			if(a < 0 || a >= 30 || b < 0 || b >= 50) continue;
  51. 			if(g[a][b] == '1') continue;
  52. 			if(dist[x][y] == dist[a][b] + 1)
  53. 			{
  54. 				ans += dir[i];
  55. 				x = a, y = b;
  56. 				break;
  57. 			}
  58. 		}
  59. 	}
  60.  
  61. 	cout << ans << endl;
  62. 	return 0;
  63. }

5.（15分）

数学知识，做不出来。(2条消息) 蓝桥杯 RSA解密_林十六要努力的博客-CSDN博客_蓝桥杯rsa解密

6.（15分）

完全二叉树（注意是完全二叉树而不是满二叉树，我第一次做就入坑，）

没明白为什么只过一个点。。 

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int a[100002];
  5. int x1[10000]={0};
  6. int main(){
  7. 	int n;
  8. 	bool flag=0;
  9. 	cin>>n;
  10. 	int c=n/2;
  11. 	if(n<(pow(2,c)-1)){
  12. 		flag=1;
  13. 		c=c-1;
  14. 	}
  15. 	int x=0;
  16. 	int y;
  17. 	for(int i=0;i<n;i++){
  18. 		cin>>y;
  19. 		a[i]=y;
  20. 	}
  21. 	x1[0]=a[0];
  22. 	for(int i=0;i<c;i++){
  23. 		int t=i*2;
  24. 		for(int j=x+1;j<=x+t;j++){
  25. 			x1[i]+=a[j];
  26. 		}
  27. 		x+=t;
  28. 	}
  29. 	if(flag){
  30. 		for(int j=(pow(2,c)-1);j<n;j++)
  31. 		x1[c]+=a[j];
  32. 	}
  33. 	int max=-10000000;
  34. 	int maxindex=0;
  35.   	for(int i=0;i<c+1;i++){
  36. 	  	if(x1[i]>max){
  37. 		 	max=x1[i];
  38. 			maxindex=i+1; 	
  39. 	  	}  
  40. 	}
  41.   	cout<<maxindex;
  42.   	return 0;
  43. }

 标准代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. const int maxn=1e5+10;
  5. int a[maxn];
  6. long long  b[maxn];
  7. int main()
  8. {
  9.    int n,i,k,j,flag;
  10.    long long ans,x;
  11.    ans=0;
  12.    k=1;
  13.    j=1;
  14.    x= -100000000000;
  15.    flag=0;
  16.    cin>>n;
  17.    for(i=1;i<=n;i++)
  18.    {
  19.        cin>>a[i];
  20.        ans+=a[i];
  21.        if(i==(pow(2,k)-1))
  22.        {
  23.            if(ans>x)
  24.            {
  25.                x=ans;
  26.                j=k;
  27.            }
  28.            ans=0;
  29.            k++;
  30.            flag=1;
  31.        }
  32.        flag=0;
  33.    }
  34.    if(flag==0&&(ans>x))  //当不是完全平衡二叉树的时候
  35.    {
  36.        j=k;
  37.    }
  38.    cout<<j<<endl;
  39.    return 0;
  40. }

7.（15分）

 

就模拟

我用pair+sort()超时，留个心眼吧

总结pair数组用法

  1. typedef pair<int,int> P;
  2. pair<int,int> timex[1000001];
  3. bool cmp(P &s,P &b){
  4. 	return s.first<b.first;
  5. }
  6. for(int i=1;i<=1000000;i++){
  7. 		cin>>t>>x;
  8. 		timex[i]=make_pair(t,x);
  9. }
  10. sort(timex,timex+M,cmp);
  11. cout<<timex[i].first;
  12. cout<<timex[i].second;

 vector删除用法（找出vector小于3的删除）

  1. for(int i=0;i<v.size();i++){
  2.     if(level[v[i]]<3){
  3.         for(vector<int>::iterator a=v.begin();a!=v.end();a++)
  4.         {
  5.             if(*a==v[i]) 
  6.                 v.erase(a);
  7.         }
  8.     }
  9. }

上面废话一堆

答案如下

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. //顺带复习一下结构体的排序hhh
  6. int m,n,t;
  7. //store[id]第id号店上一次有的订单
  8. //flag[id]存储第id号店在不在优先缓存中
  9. //value[id]存储第id号店的得分
  10.  
  11. int store[100010],flag[100010],value[100010];
  12.  
  13. struct node{
  14.     int time,id;
  15. }a[100010];
  16.  
  17. bool cmp(node a , node b){
  18.     if(a.id==b.id)
  19.         return a.time<b.time;
  20.     return a.id<b.id;
  21. }
  22.  
  23. int main(){
  24.     cin>>n>>m>>t;
  25.     for(int i=0;i<m;i++){
  26.         cin>>a[i].time>>a[i].id;
  27.     }
  28.     sort(a,a+m,cmp);
  29.     for(int i=0;i<m;i++){
  30.         int tt=a[i].time,id=a[i].id;
  31.         //如果当前的订单不等于上一次的订单，则减去它们之间的间隔
  32.         //因为如果没有订单，则每个时刻减1
  33.         if(tt!=store[id])
  34.             value[id]-=tt-store[id]-1;
  35.         //value的值要大于等于0
  36.         value[id]=max(0,value[id]);
  37.         if(value[id]<=3)
  38.             flag[id]=0;
  39.         value[id]+=2;
  40.         if(value[id]>5)
  41.             flag[id]=1;
  42.         store[id]=tt;
  43.     }
  44.     for(int i=1;i<=n;i++){
  45.     //如果这个店的最后一个订单不是第 t 分钟的
  46.     //就减去最后一个订单的时间到 t 时间之间应该减去的
  47.         if(store[i]<t){
  48.             value[i]-=t-store[i];
  49.             if(value[i]<=3)
  50.                 flag[i]=0;
  51.         }
  52.     }
  53.     int ans=0;
  54.     for(int i=0;i<=n;i++)
  55.         if(flag[i])
  56.             ans++;
  57.     cout<<ans;
  58.     return 0;
  59. }

8.（20分）

我的代码TLE了，只能捞部分分

注意vector的find是基于algorithm头文件实现的，我这种实现肯定很慢，用dp应该会很快

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. vector<int> s;
  5. int main(){
  6. 	int N,t;
  7. 	cin>>N;
  8. 	cin>>t;
  9. 	s.push_back(t);
  10. 	for(int i=0;i<N-1;i++){
  11. 		cin>>t;
  12. 		while(1){
  13. 			vector<int>::iterator it=find(s.begin(),s.end(),t);
  14. 			if(it!=s.end()){
  15. 				t++;
  16. 			}	
  17. 			else{
  18. 				s.push_back(t);
  19. 				break;
  20. 			}
  21. 		}
  22. 	}
  23. 	for(int i=0;i<s.size();i++)
  24. 		cout<<s[i]<<" ";
  25.   	return 0;
  26. }

 

AC（是大佬的并查集）

(2条消息) 蓝桥杯 修改数组 【并查集】_可惜剑是断的的博客-CSDN博客_蓝桥杯修改数组

9.（25分）

状态压缩dp

(2条消息) 2019蓝桥杯C++A组——糖果_芷汀若静的博客-CSDN博客_蓝桥杯糖果

十进制转二进制

看不懂状态压缩可以看这个教程

(2条消息) DP-状态压缩DP（解释+典例）_豆苗子的博客-CSDN博客_状态压缩dp

10.（25分）

难，题目都看不懂，可以自行百度搜索 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/48794
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号