蓝桥杯算法练习(用筛选法求N内的素数,蛇形矩阵,分糖果,错误票据
1.用筛法求之N内的素数(简单题)
题目描述
用筛法求之N内的素数。
输入
0~N的素数
样例输入复制
100
样例输出复制
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
**解题思路 **
2.蛇形矩阵(简单题)
题目描述
蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。
输入
本题有多组数据,每组数据由一个正整数N组成。(N不大于100)
输出
对于每一组数据,输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。
样例输入复制
5
样例输出复制
1 3 6 10 15
2 5 9 14
4 8 13
7 12
11
解题思路
#include
#include using namespace std;int main()
{int n;cin >> n;//创建动态二维数组int** a = new int* [n];for (int i = 0; i < n; i++)a[i] = new int[n];//初始化第一个为0a[0][0] = 1;//利用规律初始化第一列for (int i = 1; i < n; i++){a[i][0]=a[i - 1][0] + i;}//利用行的规律把每行初始化int tem = 2;//第一行第一个数是从2开始加for (int i = 0; i <n-1; i++){int tem2 = tem;for (int j = 1; j < n; j++){a[i][j] = a[i][j - 1] + tem2;tem2++;//下一个数要加1}tem++;//下一行第一个数是比上一行多加1}//输出for (int i = 0; i < n; i++){for (int j = 0; j < n - i; j++){cout << a[i][j] << " ";}cout << endl;}for (int i = 0; i < n; i++)delete[]a[i];delete[]a;}
3.分糖果(简单题)
题目描述
有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果,然后进行下面的游戏:
每个小朋友都把自己的糖果分一半给左手边的孩子。
一轮分糖后,拥有奇数颗糖的孩子由老师补给1个糖果,从而变成偶数。
反复进行这个游戏,直到所有小朋友的糖果数都相同为止。
你的任务是预测在已知的初始糖果情形下,老师一共需要补发多少个糖果。
输入
程序首先读入一个整数N(2< N< 100),表示小朋友的人数。
接着是一行用空格分开的N个偶数(每个偶数不大于1000,不小于2)
输出
要求程序输出一个整数,表示老师需要补发的糖果数。
样例输入复制
3
2 2 4
样例输出复制
4
解题思路
#include
#include using namespace std;int main()
{int n;cin >> n;int* a = new int[n];//输入n个整数for (int i = 0; i < n; i++)cin >> a[i];int flag = 1;//判断数组所有元素是否相等用int count = 0;//记录增加的数目while (flag){flag = 0;//假设相等//每个数减半for (int i = 0; i < n; i++){a[i] = a[i] / 2;}//把自己减掉的一半给下一个int tem = a[n-1];for (int i = n-1; i >0; i--){a[i] = a[i] + a[i - 1];}a[0] = tem + a[0];//把不死偶数的变成偶数for (int i = 0; i < n; i++){if ((a[i] % 2) != 0){a[i] = a[i] + 1;count++;}}//判断是否相等for (int i = 1; i < n; i++){if (a[i] != a[0]){flag = 1;break;}}} cout << count;delete[]a;}
4.错误票据(简单题)
题目描述
某涉密单位下发了某种票据,并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的,但ID的开始数码是随机选定的。
因为工作人员疏忽,在录入ID号的时候发生了一处错误,造成了某个ID断号,另外一个ID重号。
你的任务是通过编程,找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
输入
要求程序首先输入一个整数N(N< 100)表示后面数据行数。
接着读入N行数据。
每行数据长度不等,是用空格分开的若干个(不大于100个)正整数(不大于),请注意行内和行末可能有多余的空格,你的程序需要能处理这些空格。
每个整数代表一个ID号。
输出
要求程序输出1行,含两个整数m n,用空格分隔。
其中,m表示断号ID,n表示重号ID
样例输入复制
2
5 6 8 11 9
10 12 9
样例输出复制
7 9
解题思路
#include
#include
#include
using namespace std;
int main()
{int n;cin >> n;//使用静态的数组储存空间int tem[100000];//输入数据int pos = 0;while (n--){while (cin >> tem[pos]){pos++;if (cin.get() == '\n')break;//输入的是换行符就跳出内循环}}//sort函数进行排序sort(tem, tem + pos);//判断缺失与重复int m = 0;int s=0;for (int i = 0; i < pos-1; i++){if (tem[i] + 1 != tem[i + 1] && tem[i] != tem[i + 1])m = tem[i] + 1;if (tem[i] == tem[i + 1])s = tem[i];}cout << m << " " << s;return 0;}
5.kAc给糖果你吃(贪心)
问题描述
kAc有n堆糖果,每堆有A[i]个。
kAc说你只能拿m次糖果,聪明的你当然想要拿最多的糖果来吃啦啦啦~
//第二天,kAc问你还想吃糖果么?(嘿嘿嘿)说着眼角路出奇怪的微笑…
输入格式
第一行两个数字n和m,第二行有n个数字A[i]。
输出格式
输出一行表示最多能拿几个糖果。
样例输入
2 2
1 2
样例输出
**解题思路:贪心算法,所做的是当前最优的解法,到最后达成最优的结果 **
每次都选取当前最多的糖果,达到最后最多的糖果
suot函数先排序,使用()进行升序排序,
#include
#include
#include using namespace std;int main()
{int n, m;cin >> n >> m;if (m > n)m = n;int* a = new int[n];for (int i = 0; i < n; i++){cin >> a[i];}sort(a, a + n,greater<int>());//降序排序long long int sum = 0;//必须是long long int数据,不然数据存不进去for (int i = 0; i < m; i++){sum = sum + a[i];}cout << sum;delete[]a;return 0;
}
6最大获利(数组)
问题描述
是一位年轻有为的企业家,最近他在进军餐饮行业。他在各地开拓市场,共买下了N个饭店。在初期的市场调研中,他将一天划分为M个时间段,并且知道第i个饭店在第j个时间段内,会有Aij位服务员当值和Bij位客户光临。他还分析了不同饭店不同时间段客户的需求,得到第i个饭店在第j个时间段内,平均每位客户消费Cij元。为了创设品牌形象,决定每个饭店每天只选择一个时间段营业,每个服务员至多接待一位顾客(若顾客数多于服务员数,超过部分的顾客当天就无法在该店消费了)。
企业家的目的终究还是获利。请你安排营业时间,并告诉每天消费总额最多为多少。
输入格式
第一行两个整数,N、M。
第二行开始依次给出三个矩阵A(NM)、B(NM)、C(N*M)。
输出格式
一行一个整数,最大消费总额。
样例输入
2 3
1 2 3
3 2 1
3 2 1
1 2 3
4 5 2
3 1 6
样例输出
16
解题思路:[参考]((26条消息) 蓝桥杯 ALGO-226 最大获利_张(⊙﹏⊙)的博客-CSDN博客)
注意审题明确数据的取值范围,不能一股脑的就定为int型
#include
#include
#include using namespace std;int main()
{int n, m;//n家商店m个时间段cin >> n >> m;//动态二维数组int** a = new int*[n];for (int i = 0; i < n; i++)a[i] = new int[m];//先储存服务员的在没个商店每个时间段服务员的数量for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> a[i][j];}}//储存顾客数int c;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> c;//如果顾客数比服务员数少,则为数组就改为顾客数,if (a[i][j] > c)a[i][j] = c;}}long long int nmax = 0;//记录每个商店的最大消费long long int result = 0;//把每个商店的最大消费加到一起long long int price;//输入当前的平均消费价格for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){//计算第一个商店的最大消费数cin >> price;if (price * a[i][j] > nmax)nmax = price * a[i][j];}result += nmax;nmax = 0;}cout << result;//销毁二维数组for (int i = 0; i < n; i++){delete[] a[i];}delete[] a;return 0;
}
7.数的潜能()
问题描述
将一个数N分为多个正整数之和,即N=a1+a2+a3+…+ak,定义M=*…*ak为N的潜能。
给定N,求它的潜能M。
由于M可能过大,只需求M对5218取模的余数。
输入格式
输入共一行,为一个正整数N。
输出格式
输出共一行,为N的潜能M对5218取模的余数。
样例输入
10
样例输出
36
数据规模和约定