第七届蓝桥杯B组试题解析_蓝桥杯煤球数目结果分析-程序员宅基地

技术标签: 算法  蓝桥刷题笔记  

第一题:煤球数目

有一堆煤球,堆成三角棱锥形。具体:
第一层放1个,
第二层3个(排列成三角形),
第三层6个(排列成三角形),
第四层10个(排列成三角形),

如果一共有100层,共有多少个煤球?

请填表示煤球总数目的数字。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。
————————————————

答案 :171700 。
思路 :相信大家都学过高数了 ,应该能够想象出三棱锥的形状 ,由题意我们可以知道第i层的三角形比i-1层的三角形多i个煤球 ,累加一下就好了 。

#include <stdio.h>
long long a[101],ans,temp=1;
int main()
{
    
	for(int i=1;i<=100;i++)
	{
    
		temp=i;
		a[i]=temp+a[i-1];
		ans+=a[i];
	}
	printf("%lld",ans);
	return 0;
}

第二题 :生日蜡烛

某君从某年开始每年都举办一次生日party,并且每次都要吹熄与年龄相同根数的蜡烛。

现在算起来,他一共吹熄了236根蜡烛。

请问,他从多少岁开始过生日party的?

请填写他开始过生日party的年龄数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

答案 :26 。

思路 :水题,哪怕某君是乌龟 ,此题暴力枚举也是很快的 。。。

#include <stdio.h>
int a[200];
int main()
{
    
	for(int i=1;i<=200;i++)
	{
    
		a[i]+=a[i-1]+i;
	}
	for(int i=1;i<=200;i++)  //从此时开始过生日
	{
    
		for(int j=i+1;j<=200;j++) //今年的年龄
		{
    
			if(a[j]-a[i-1]==236)
			{
    
				printf("%d\n",i);
			}
		}
	}
	return 0;
}

第三题:凑算式

在这里插入图片描述

(如果显示有问题,可以参见【图1.jpg】)

这个算式中AI代表19的数字,不同的字母代表不同的数字。

比如:
6+8/3+952/714 就是一种解法,
5+3/1+972/486 是另一种解法。

这个算式一共有多少种解法?

注意:你提交应该是个整数,不要填写任何多余的内容或说明性文字。

答案 :29 。

思路 :暴力就可以做出来 ,注意除法精度的问题 ,将除法换成加法。

#include <stdio.h>
int a[10],b[10],ans;
void dfs(int x)
{
    
	if(x==9)
	{
    
		int t1=a[2];
		int t2=a[6]*100+a[7]*10+a[8];
		int t3=a[3]*100+a[4]*10+a[5];
		if(a[0]*a[2]*t2+a[1]*t2+a[2]*t3==10*a[2]*t2)
		{
    
			ans++;
			return ;
		}
	}
	for(int i=1;i<=9;i++)
	{
    
		if(!b[i])
		{
    
			a[x]=i;
			b[i]=1;
			dfs(x+1);
			b[i]=0;
		}
	}
}
int main()
{
    
	dfs(0);
	printf("%d",ans);
	return 0;
}

第四题:快速排序

排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。

其思想是:先选一个“标尺”,
用它把整个队列过一遍筛子,
以保证:其左边的元素都不大于它,其右边的元素都不小于它。

这样,排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。

下面的代码是一种实现,请分析并填写划线部分缺少的代码。

#include <stdio.h>

void swap(int a[], int i, int j)
{
    
int t = a[i];
a[i] = a[j];
a[j] = t;
}

int partition(int a[], int p, int r)
{
    
int i = p;
int j = r + 1;
int x = a[p];
while(1){
    
while(i<r && a[++i]<x);
while(a[--j]>x);
if(i>=j) break;
swap(a,i,j);
}
______________________;
return j;
}

void quicksort(int a[], int p, int r)
{
    
if(p<r){
    
int q = partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}

int main()
{
    
int i;
int a[] = {
    5,13,6,24,2,8,19,27,6,12,1,17};
int N = 12;

quicksort(a, 0, N-1);

for(i=0; i<N; i++) printf("%d ", a[i]);
printf("\n");

return 0;
}

思路 :如果学习过快排,了解过快速排序的原理的应该是送分题目。在这里答案是swap(a,p,j).

第五题:抽签

X星球要派出一个5人组成的观察团前往W星。
其中:
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。

那么最终派往W星的观察团会有多少种国别的不同组合呢?

下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为:
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF

(以下省略,总共101行)

#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024

void f(int a[], int k, int m, char b[])
{
    
int i,j;

if(k== N){
     
b[M] = 0;
if(m==0) printf("%s\n",b);
return;
}
for(i=0; i<=a[k]; i++){
    
for(j=0; j<i; j++) b[M-m+j] = k+'A';
______________________; //填空位置
}
}
int main()
{
    
int a[N] = {
    4,2,2,1,1,3};
char b[BUF];
f(a,0,M,b);
return 0;
}

仔细阅读代码,填写划线部分缺少的内容。

注意:不要填写任何已有内容或说明性文字

答案:f(a,k+1,m-i,b) 。其中M-m+j中m代表剩余的人数。

第六题: 方格填数
如下的10个格子

(如果显示有问题,也可以参看【图1.jpg】)
在这里插入图片描述
填入0~9的数字。要求:连续的两个数字不能相邻。
(左右、上下、对角都算相邻)

一共有多少种可能的填数方案?

请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字

答案 : 1580

思路:我们可以先生成0~9的全排列 ,然后将生成的数填入表中 ,累加符合题意的情况有多少种即可 。

#include <stdio.h>
#include <math.h>
int a[10],b[10],c[5][5],book[4]={
    0,4,4,3},ans,next[8][2]={
    0,1,1,0,0,-1,-1,0,-1,-1,-1,1,1,1,1,-1};
int ok(int x,int y)  //相邻连续 返回0 
{
    
	int tx,ty;
	for(int i=0;i<8;i++)
	{
    
		tx=x+next[i][0];
		ty=y+next[i][1];
		if(tx==1&&ty>=2&&ty<=book[tx])
		{
    
			if(abs(c[tx][ty]-c[x][y])==1)
			{
    
				return 0;
			}
		}
		else if(tx>1&&tx<=3&&ty>=1&&ty<=book[tx]) 
		{
    
			if(abs(c[tx][ty]-c[x][y])==1)
			{
    
				return 0;
			}
		}
	}
	return 1;
}
void dfs(int x)
{
    
	if(x==10)
	{
    
		int p=0,f=0;
		for(int i=1;i<=3;i++)
		{
    
			if(i!=1)
			{
    
				for(int j=1;j<=book[i];j++)
				{
    
					c[i][j]=a[p++];
				}
			}
			else
			{
    
				for(int j=2;j<=book[i];j++)
				{
    
					c[i][j]=a[p++];
				}
			}
		}
		for(int i=1;i<=3;i++)
		{
    
			if(i!=1)
			{
    
				for(int j=1;j<=book[i];j++)
				{
    
					if(!ok(i,j))
					{
    
						f=1;
						book;
					}
				}
			}
			else
			{
    
				for(int j=2;j<=book[i];j++)
				{
    
					if(!ok(i,j))
					{
    
						f=1;
						book;
					}
				}
			}
			if(f)	book;
		}
		if(!f)
		{
    
			ans++;
			return ;
		}
	}
	for(int i=0;i<10;i++)
	{
    
		if(b[i]) continue ;
		a[x]=i;
		b[i]=1;
		dfs(x+1);
		b[i]=0;
	}
	
}
int main()
{
    
	dfs(0);
	printf("%d",ans);
	return 0;
}

第七题 :剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。
在这里插入图片描述
请你计算,一共有多少种不同的剪取方法。

请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

答案:116

思路:dfs ,本人水平有限 ,写的稍微有点麻烦,仅给大佬们提供个思路吧。
首先 ,要注意避免重复 ,我们可以和第六题一样 ,先选择5个数 ,这里我们用dfs ,对于1~12这些数 ,我们进行选择 ,12个数选择完并且恰好选择了5个数之后 ,我们再进行一次dfs ,判断这五个数在图中是否连通 ,如果是的话 ,则满足题意 。

#include <stdio.h>
#include <string.h>
int a[15],b[50],c[3][4]={
    1,2,3,4,5,6,7,8,9,10,11,12},d[3][4],next[4][2]={
    0,1,1,0,0,-1,-1,0},ans,flag,s;
void dfs1(int x,int y)
{
    
	int tx,ty;
	for(int i=0;i<4;i++)
	{
    
		tx=x+next[i][0];
		ty=y+next[i][1];
		if(tx>=0&&tx<3&&ty>=0&&ty<4&&a[c[tx][ty]]&&!d[tx][ty])
		{
    
			d[tx][ty]=1;
			s++;
			dfs1(tx,ty);
		}
	}
 } 
void dfs(int x,int p) //选了x个数 判断是否选择p 
{
    
	if(x==5&&p==13)  //如果选够了5个 并且判断了12个数 
	{
    
		s=1;
		int f=0;
		memset(d,0,sizeof(d));
		for(int i=0;i<5;i++) //b[i]所在的位置是否能连起来 
		{
    
			for(int k=0;k<3;k++)
			{
    
				for(int j=0;j<4;j++)
					{
    
						if(c[k][j]==b[i])
						{
    
							d[k][j]=1;
							dfs1(k,j);
							if(s==5)
							{
    
								f=1;
								break;
							}
						}
					}
				if(f)	break;
			}
			if(f)	break;
		}
		if(f)	
		{
    
			ans++;
		}
	}
	if(p==13)	return ;
	// 选择1~12中的5个数 
	dfs(x,p+1);    //不选 P  
	a[p]=1;       //标记 p 
	b[x]=p;      //选的第x+1个数是 p 
	dfs(x+1,p+1); //选 P 
	a[p]=0;    //回溯 
}
int main()
{
    
	dfs(0,1);
	printf("%d",ans);
	return 0;
}

第八题:四平方和

四平方和定理,又称为拉格朗日定理:
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去,就正好可以表示为4个数的平方和。

比如:
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
(^符号表示乘方的意思)

对于一个给定的正整数,可能存在多种平方和的表示法。
要求你对4个数排序:
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法

程序输入为一个正整数N (N<5000000)
要求输出4个非负整数,按从小到大排序,中间用空格分开

例如,输入:
5
则程序应该输出:
0 0 1 2
再例如,输入:
12
则程序应该输出:
0 2 2 2
再例如,输入:
773535
则程序应该输出:
1 1 267 838

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 3000ms

思路:暴力即可 ,四个数 ,我们用三层循环 ,减少耗时

#include <stdio.h>
#include <math.h>
int n;
int main()
{
    
    scanf("%d",&n);
    for(int i=0;i*i<=n;i++)
    {
    
        for(int j=i;j*j<=n;j++)
        {
    
            for(int k=j;k*k<=n;k++)
            {
    
                int z=sqrt(n-i*i-j*j-k*k);
                    if((i*i+j*j+k*k+z*z)==n&&z>k)
                    {
    
                        printf("%d %d %d %d",i,j,k,z);
                        return 0;
                    }
                
            }
        }
    }
    return 0;
}

第九题:交换瓶子

有N个瓶子,编号 1 ~ N,放在架子上。

比如有5个瓶子:
2 1 3 5 4

要求每次拿起2个瓶子,交换它们的位置。
经过若干次后,使得瓶子的序号为:
1 2 3 4 5

对于这么简单的情况,显然,至少需要交换2次就可以复位。

如果瓶子更多呢?你可以通过编程来解决。

输入格式为两行:
第一行: 一个正整数N(N<10000), 表示瓶子的数目
第二行:N个正整数,用空格分开,表示瓶子目前的排列情况。

输出数据为一行一个正整数,表示至少交换多少次,才能完成排序。

例如,输入:
5
3 1 2 5 4

程序应该输出:
3

再例如,输入:
5
5 4 3 2 1

程序应该输出:
2

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 1000ms

思路:这题比想象中要简单,输入n个数,并且记录n个数的位置 。然后从第一个位置开始判断 ,下标和当前值是否相等 ,不相等的话交换位置 。需要注意的是 ,交换位置后 ,每个数所处的位置发生了变化 ,更新一下储存位置的数组即可。

#include <stdio.h>
int n,a[10005],b[10005],ans;
void swap(int x,int y)
{
    
	int t;
	t=a[x];
	a[x]=a[y];
	a[y]=t;
}
int main()
{
    
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
    
		scanf("%d",&a[i]);
		b[a[i]]=i;  //记录 a[i]这个数的位置
	}
	for(int i=1;i<=n;i++)
	{
    
		if(a[i]!=i)
		{
    
		    int t=b[i];
		    int p=a[i];
			swap(i,b[i]);
			b[p]=t;
			ans++;
		}
	}
	printf("%d",ans);
	return 0;
}

第十题:最大比例

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且,相邻的两个级别间的比例是个固定值。
也就是说:所有级别的奖金数构成了一个等比数列。比如:
16,24,36,54
其等比值为:3/2

现在,我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。

输入格式:
第一行为数字N,表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000),用空格分开。每个整数表示调查到的某人的奖金数额

要求输出:
一个形如A/B的分数,要求A、B互质。表示可能的最大比例系数

测试数据保证了输入格式正确,并且最大比例是存在的。

例如,输入:
3
1250 200 32

程序应该输出:
25/4

再例如,输入:
4
3125 32 32 200

程序应该输出:
5/2

再例如,输入:
3
549755813888 524288 2

程序应该输出:
4/1

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 3000ms

思路:这题不做了 ,睡觉。。。。。。。。。。。。。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/guyjy/article/details/105421031

智能推荐

匈牙利算法:二分图最大匹配_二分图最大匹配om√n-程序员宅基地

文章浏览阅读65次。#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 510, M = 100010;int n1, n2, m;int h[N], e[M], ne[M], idx;int match[N];bool st[N];void add(int a, int b){ e[idx] = b, ne[idx] = h[_二分图最大匹配om√n

泛型_泛型 类-程序员宅基地

文章浏览阅读4.8k次。注解基础_泛型 类

二叉搜索树BST总结_bst 中序可以得到什么结果-程序员宅基地

文章浏览阅读254次。文章目录1. 概念2. 基本操作2.1 查找2.2 插入2.3 删除3. 性能分析1. 概念二叉搜索树又称二叉排序树,一颗BST应该满足以下特点:若它的左子树不为空,则左子树上所有节点的值都小于根节点的值;若它的右子树不为空,则右子树上所有节点的值都大于根节点的值;上图就是一颗二叉搜索树,对它进行中序遍历后得到的结果是[1,2,3,4,5,6,7,8,9],我们不难发现它是一个递增的序列,注意这是二叉搜索树的一个重要性质:BST中序遍历的结果呈增序排列。在很多涉及BST的问题中都要先考_bst 中序可以得到什么结果

Flutter 路由管理 Route、Navigator 使用示例_flutter modalroute.withname('/')-程序员宅基地

文章浏览阅读1.6k次。文章目录路由管理页面跳转示例页面不传参跳转页面传参跳转Navigator 的其他跳转方式无 context 页面跳转命名路由页面跳转传参页面返回传参命名路由封装404 页面处理返回按钮拦截路由管理在 Flutter 中,页面之间的跳转是通过 Route 和 Navigator 来管理。Router是页面的抽象,类似于Android中的Activity页面。该类定义了Navigator上的抽..._flutter modalroute.withname('/')

“元宇宙”火了,这玩意到底是啥?_单机元宇宙-程序员宅基地

文章浏览阅读282次。朋友,你听说过“元宇宙”吗?2021年,一个新奇的概念名词在网络上迅速蹿红,引发科技界和投资界的广泛关注。这个概念名词,就是“元宇宙”。今天这篇文章,就给大家介绍一下它。_单机元宇宙

爱尔兰B公式和爱尔兰C公式的计算_爱尔兰公式-程序员宅基地

文章浏览阅读1.3w次,点赞10次,收藏52次。1.话务量定义话务量指在一特定时间内呼叫次数与每次呼叫平均占用时间的乘积。话务量反映了电话负荷的大小,与呼叫强度和呼叫保持时间有关。呼叫强度是单位时间内发生的呼叫次数,呼叫保持时间也就是占用时间。话务量计算方法话务量公式为:A=C * t。 A是话务量,单位为erl(爱尔兰); C是呼叫次数,单位是次/小时; t是每次呼叫平均占用时长,单位是小时/次。..._爱尔兰公式

随便推点

ffmpeg源码简析(七)解码-avformat_open_input,avformat_find_stream_info()_avformat_open_input avformat_find_stream_info-程序员宅基地

文章浏览阅读2.5k次,点赞2次,收藏4次。1.avformat_open_input打开媒体的的过程开始于avformat_open_input,因此该函数的重要性不可忽视。在该函数中,FFMPEG完成了:输入输出结构体AVIOContext的初始化;输入数据的协议(例如RTMP,或者file)的识别(通过一套评分机制):1判断文件名的后缀 2读取文件头的数据进行比对;使用获得最高分的文件协议对应的URLProtocol,通过函数指针的方式_avformat_open_input avformat_find_stream_info

python批量读取图片gps位置_基于Python就可获取照片的GPS位置信息?是的你没听错...-程序员宅基地

文章浏览阅读341次。这篇文章主要介绍了基于Python获取照片的GPS位置信息,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下。这篇文章主要介绍了基于Python获取照片的GPS位置信息,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下。说明:一般手机拍照时默认会打开地理位置开关经过压缩后,通常会将GPS信息压缩掉EXI..._python 批量 jpg gps

webpack中将打包后的文件复制到指定路径_copyplugin-程序员宅基地

文章浏览阅读4.5k次。项目中有一部分使用了另一项目的打包文件,.每次打包后都需要手动复制此文件到现有项目中,讨厌得很,故查阅后const path = require("path");const CopyPlugin = require('copy-webpack-plugin');const entryArr = []module.exports = {mode: "developmen..._copyplugin

10种软件滤波算法及其代码实现(C语言)-程序员宅基地

文章浏览阅读1w次,点赞23次,收藏210次。文章目录前言一、滤波方式介绍二、10种经典的软件滤波方法1. 限幅滤波法2. 中位值滤波法3. 算术平均滤波法4. 递推平均滤波法5. 中位值平均滤波法6. 限幅平均滤波法7. 一阶滞后滤波法8. 加权递推平均滤波法9. 消抖滤波法10. 限幅消抖滤波法参考前言本文介绍了10种常用的软件滤波方法,包含具体的滤波实现过程及优缺点,并附上了相应的代码示例(C语言)。所述滤波方法各有优劣,需根据实际应用需求进行选择。注:本文假定从8位AD中读取数据(若采用更高位的AD可定义数据类型为int);子程序为g_软件滤波

Java以form表单形式提交(文件流和json数据)_java 后端 提交form表单集合-程序员宅基地

文章浏览阅读2.8k次。目录HttpClientFormImpl层HttpClientFormimport com.alibaba.fastjson.JSONObject;import org.apache.http.Consts;import org.apache.http.HttpEntity;import org.apache.http.HttpStatus;import org.apache.http.client.ClientProtocolException;import org.apache.http._java 后端 提交form表单集合

今日头条、抖音推荐算法原理全文详解!-程序员宅基地

文章浏览阅读977次,点赞2次,收藏6次。本次分享将主要介绍今日头条推荐系统概览以及内容分析、用户标签、评估分析,内容安全等原理。一、系统概览推荐系统,如果用形式化的方式去描述实际上是拟合一个用户对内容满意度的函..._头条抖音根据哪些方面做大数据推送

推荐文章

热门文章

相关标签