devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【2023蓝桥杯】2019年第十届C/C++A组真题（解析笔记）_蓝桥杯答案2023 c

作者：IT小白 | 2024-03-24 14:17:31

赞

踩

蓝桥杯答案2023 c

目录

【平方和】

【数列求值】

【最大降雨量】

【迷宫】 

【RSA解密】

【完全二叉树的权值】

【外卖店优先级】

【修改数组】

【糖果】

【组合数问题】 

 【平方和】

long long；

填空题可以尝试小的数字，判断程序是否正确！

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;  //long long  
  4. long long ans=0;
  5. //只要含有0，1，2，9都算 
  6. int check(int x){
  7. 	while(x){
  8. 		int t=x%10; //求余数
  9. 		if(t==0||t==1||t==2||t==9)  
  10. 			return 1;
  11. 		x/=10; //求整 
  12. 	} 
  13. 	return 0; 
  14. }
  15.  
  16. int main(){
  17. 	for(int i=1;i<=2019;i++){
  18. 		if(check(i))  ans+=i*i;
  19. 	} 
  20. 	cout<<ans<<endl;
  21. 	return 0;
  22. }

【数列求值】

蓝桥杯第 8-10 届真题解析 - 《数列求值》名师讲解     

同余理论！

可以用Excel确保编程正确！

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     int t1=1, t2=1, t3=1, t4 ;
  6. 	for(int i=4;i<=20190324;i++){
  7. 		t4=(t1+t2+t3)%10000;
  8. 		t1=t2; t2=t3; t3=t4;	
  9. 	} 
  10. 	cout<<t4<<endl;
  11. 	return 0;
  12. }

 【最大降雨量】

 思维能力，无需编程！绝！推理题

【迷宫】 

  1. #include<bits/stdc++.h>
  2. #include<queue> 
  3. #include<string>
  4. using namespace std;
  5. //4行6列 
  6. #define ROWS 4
  7. #define COLS 6
  8. //二维数组 
  9. string maze[ROWS+2]={
  10. 	"010000",
  11. 	"000100",
  12. 	"001001",
  13. 	"110000"
  14. }; 
  15.  
  16. //4个方向 
  17. int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}}; //D L R U
  18. char dirs[5]="DLRU";
  19.  
  20. //定义结构体，结点到达的每一个位置 
  21. struct node{
  22. 	int x,y;    //X行y列 
  23. 	char pos;	//从上一个结点（父节点）到达当前结点所走的方向 DLRU 
  24. };
  25.  
  26. //代表每一个位置有没有走过 
  27. int visited[ROWS+2][COLS+2]; //稍微大一些，不能扣 ，0表示未访问过 
  28. //队列 node数据 
  29. queue<node> Q;
  30. //每个位置[x][y]的父结点（上一个结点）father[x][y] 
  31. node father[ROWS+2][COLS+2];
  32. //是否出边界
  33. int in(int tx, int ty){
  34. 	return (tx>=0&&tx<ROWS&&ty>=0&&ty<COLS);
  35. } 
  36. //伸缩函数
  37. void dfs(int x, int y){
  38. 	if(x==0&&y==0)
  39. 		return; //找到入口就不再递归下去
  40. 	else{
  41. 		dfs(father[x][y].x,father[x][y].y);
  42. 		cout<<father[x][y].pos; //因为是在回退时输出“路径”（上的字符） ，所以应该在这里输出 
  43. 	} 
  44. } 
  45. int main(){
  46. 	node start, now, next; //定义结点，起始结点，当前结点，下一个结点 
  47. 	int i, tx, ty; //走到（x,y） 的下一个坐标 (tx,ty)
  48. 	start.x =0; start.y=0;//构造起始结点 
  49. 	Q.push(start); 
  50. 	visited[0][0]=1; //进行入队列 
  51. 	while(!Q.empty()){
  52. 		now=Q.front(); //取出当前结点 
  53. 		Q.pop(); 
  54. 		if(now.x==ROWS-1&&now.y==COLS-1) break;
  55. 		for(i=0; i<4;i++){ //检查4个方向 
  56. 			tx=now.x+dir[i][0];
  57. 			ty=now.y+dir[i][1];
  58. 			if(in(tx,ty)&&maze[tx][ty]=='0'&&visited[tx][ty]==0){
  59. 				visited[tx][ty]=1;
  60. 				father[tx][ty].x=now.x;
  61. 				father[tx][ty].y=now.y;
  62. 				father[tx][ty].pos=dirs[i];
  63. 				next.x=tx;
  64. 				next.y=ty;
  65. 				Q.push(next); //入队列 
  66. 			}
  67. 		}
  68. 	}
  69. 	dfs(ROWS-1,COLS-1); 
  70. 	return 0;
  71. }

【RSA解密】

 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. //扩展欧几里得求逆元（a和b互质） 
  5. ll ext_gcd(ll a, ll b, ll& x, ll&y){
  6. 	int t, ret;
  7. 	if(!b){ //b==0
  8. 		x=1, y=0;
  9. 		return a;
  10. 	} 
  11. 	ret=ext_gcd(b, a%b, x, y);
  12. 	t=x, x=y, y=t-a/b*y;  //x是a对模b的逆元，y是b对模a的逆元 
  13. 	return ret;
  14. }
  15.  
  16. //求（x*y）%p （快速乘，防止爆long long） 
  17. inline ll mul(ll x, ll y, ll p){
  18. 	ll z=(long double)x /p*y;
  19. 	ll res=(unsigned long long)x*y-(unsigned long long)z*p;
  20. 	return (res+p)%p;
  21. } 
  22.  
  23. //fpm 快速幂 求X=C^e mod n 并返回X 
  24. ll fpm(ll C, ll e, ll n){
  25. 	C%=n;
  26. 	ll ans=1;
  27. 	for(; e; e>>=1, C=mul(C,C,n)) //e>>=1:e 右移一位并赋值给e，即 e/=2 
  28. 		if(e&1)	(ans=mul(ans, C,n))%=n; //& 按位与？ 
  29. 	return ans;
  30. } 
  31.  
  32. //C=20190324, e=823816093931522017, n=1001733993063167141
  33. ll power(ll C, ll e, ll n){	//求X=C^e mod n 并返回X 
  34. 	ll i, ans=1;
  35. 	for(i=1; i<=e; i++)
  36. 		ans=(ans*C)%n;
  37. 	return ans;
  38. }
  39. int main() {
  40. 	ll n=1001733993063167141, d=212353, p, q;
  41. 	//暴力枚举求p，q 
  42. 	for(ll i=3; i*i<n; i+=2){
  43. 		if(n%i==0){ //n%i==0 首个满足if条件的i一定为素数 
  44. 			p=i; q=n/i; break;
  45. 		}
  46. 	}
  47. //	cout<<"p="<<p<<endl; 
  48. //	cout<<"q="<<q<<endl; 
  49. 	p=891234941;
  50. 	q=1123984201;
  51. 	
  52. 	ll e, m=(p-1)*(q-1), x, y;
  53. 	ext_gcd(d, m, x, y); 	//x是d对模m的逆元，y是m对模d的逆元 
  54. 	e=(x%m+m)%m;			//防止x<0或x>m作的修正 
  55. //	cout<<"e="<<e<<endl; 	//e=823816093931522017 意味着 
  56. 	
  57. 	ll C=20190324; 
  58. 	//cout<<power(C,e,n) <<endl; 	//求X=C^e mod n并输出X（估计至少要运行100年） 
  59. 	cout<<fpm(C,e,n)<<endl;			//求X=C^e mod n并输出X (快速幂算法)
  60. 	return 0; 	
  61. }

【完全二叉树的权值】

比赛时，多拟几组数据，确保编程正确！

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. int main() {
  6. 	ll maxsum = -755360000011, sum; //最大和，每层整数和
  7. 	int N, num, cnt=0;
  8. 	int flag =0; //flag为 1表示已经读入了所有的整数
  9. 	int layer,maxlayer=1;
  10. 	int i;
  11. 	cin>>N;
  12. 	//读入每一层的结点，根结点为第一层 
  13. 	for(layer=1; ;layer++){
  14. 		sum=0;
  15. 		//读入每层layer的所有结点，2^(layer-1) 
  16. 		for(i=0;i<(1<<(layer-1));i++ ) //1按位左移计算,二进制左移 
  17. 		{
  18. 			cin>>num;
  19. 			sum+=num;
  20. 			//已读入的整数个数已经到达了N个 
  21. 			if(++cnt>=N){
  22. 				flag = 1; break;
  23. 			}
  24. 		 } 
  25. 		 //一层 
  26. 		 if(sum>maxsum){
  27. 		 	maxsum=sum;
  28. 		 	maxlayer=layer;
  29. 		 } 
  30. 		 if(flag) break; 
  31. 	} 
  32. 	cout<<maxlayer<<endl;
  33. 	return 0;
  34. }

【外卖店优先级】

 

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> PII;
  4. const int MAXN=100010;
  5. const int MAXM=100010;
  6.  
  7. int N,M,T;
  8. int priority[MAXN];//priority记录外卖店优先级(初值为0)
  9. int last[MAXN];//Last记录外卖店上一个订单的时刻(初值为0)
  10. bool st[MAXN];//外卖店是否在优先缓存中的标志
  11. PII order[MAXM];//每个订单的时刻(ts)及外卖店(id)
  12.  
  13.  
  14. int  main()
  15. {
  16. 	int i,j;
  17. 	scanf("%d%d%d", &N, &M, &T);
  18. 	for(i=0; i<M; i++)
  19. 		scanf("%d%d", &order[i].first, &order[i].second);
  20. 		sort(order,order + M);//按照订单时间先后排序,时间相同再按外卖店序号从小到大排序
  21. 		for(i = 0; i<M;){//只考虑有订单的时刻(即M条订单)
  22. 			j = i;
  23. 			while(j< M && order[j]==order[i]) j++;//同一时间同一店铺有多条订单
  24. 			
  25. 			int t = order[i].first,id = order[i].second, cnt = j-i;//订单数
  26. 			i=j;
  27. 			priority[id] -= t-last[id] - 1;//先减去没有订单的优先级
  28. 			if(priority[id]<0) priority[id] =0;//优先级最低为0
  29. 			if(priority[id]<=3) st[id] = false;//出缓存
  30. 			priority[id] += cnt*2;//加上cnt个订单带来的优先级
  31. 			if(priority[id] >5) st[id] = true;//进缓存
  32. 			last[id] = t;//维护last
  33. 		}
  34. 		for(i = 1; i <= N; i++){//最后T时刻更新所有店铺优先级
  35. 			if(last[i]<T){
  36. 				priority[i]-=T-last[i];
  37. 				if(priority[i]<=3) st[i]=false;
  38. 			}
  39. 		}
  40. 		int ans = 0;//最终答案:在优先缓存中的外卖店数量
  41. 		for(i = 1; i <=N; i++ ) ans+= st[i];
  42. 		printf("%d\n",ans);
  43. 		return 0;
  44.  
  45. }

【修改数组】

 

 

 80%

  1. #include<bits/stdc++.h>
  2. #include<time.h> 
  3. using namespace std;
  4. #define MAXN 100005
  5. #define MAXA 100005
  6. int A[MAXN];
  7. int bused[MAXA];//1~100000o是否已经出现过的标志
  8. int main( )
  9. { 
  10. 	//freopen("d2.in","r", stdin);
  11. 	// freopen("d2.out","w", stdout);
  12. 	time_t time, start, end;//程序运行总时间、程序运行开始时刻、结束时刻
  13. 	start = clock( );//取得系统当前时刻
  14. 	int i,j,N;
  15. 	scanf( "%d",&N);
  16. 	for(i = 1; i<=N; i++)
  17. 		scanf( "%d",&A[i]);
  18. 	bused[A[1]]= 1;
  19. 	for(i=2; i<=N; i++){//调整A[i]:检查A[1]~A[i-1]
  20. 		if( !bused[A[i]]){ //A[i]没有出现过,直接在bused数组里将A[i]所处位置标志置1
  21. 		bused[A[i]] = 1; continue;
  22. 		}
  23. 		do{//A[i]已经出现过,则A[i]增加1,再判断A[i]you| 
  24. 			A[i]++;
  25. 		}while(bused[A[i]]);
  26. 		bused[A[i]]= 1;
  27. 	} 
  28. 	for(i = 1; i <N; i++)
  29. 		printf("%d ",A[i]);
  30. 	printf("%d\n",A[N]);
  31. 	end = clock( );//取得系统当前时刻
  32. 	time = end - start;
  33. 	// printf("%d\n", time );
  34. 	return 0;
  35. }

100% 并长集 -高手入

 【糖果】

【组合数问题】 

【指路】蓝桥杯第 8-10 届真题解析 - 《组合数问题》名师讲解 - 蓝桥云课 (lanqiao.cn)

 

 

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

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

  

闽ICP备14008679号