蓝桥杯算法练习（用筛选法求N内的素数，蛇形矩阵，分糖果，错误票据，kAc分糖果给你吃，最大获利，翻硬币）

2023-11-26 18:50
文章标签 算法 筛选 最大 错误 练习 蓝桥 矩阵 素数 糖果 法求 蛇形 获利 硬币 票据 kac

本文主要是介绍蓝桥杯算法练习（用筛选法求N内的素数，蛇形矩阵，分糖果，错误票据，kAc分糖果给你吃，最大获利，翻硬币），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.用筛法求之N内的素数(简单题)

题目描述

用筛法求之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

**解题思路 **

  • 申请一个动态数组，从1-N初始化

  • 从第二个数开始，（2是素数），并且用循环把该数的倍数的数置为1

  • 然后访问下一个不是1的数（一定为素数），重复上面一个步骤

  • 最后用循环把不是一的数输出

    #include<iostream>
#include<vector>using namespace std;int main()
{int n;cin >> n;//动态申请并初始化int* a = new int[n];for (int i = 0; i < n; i++){a[i] = i + 1;}//把素数的置为1for (int i = 0; i < n; i++){if (a[i] != 1){for (int j = i + 1; j < n; j++)if (a[j] % a[i] == 0)a[j] = 1;}}//输出for (int i = 0; i < n; i++){if (a[i] != 1)cout << a[i] << endl;}delete[]a;
}

2.蛇形矩阵（简单题）

题目描述

蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。

输入

本题有多组数据，每组数据由一个正整数N组成。（N不大于100）

输出

对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。

样例输入复制

5

样例输出复制

1 3 6 10 15
2 5 9 14
4 8 13
7 12
11

解题思路

  • 利用二维数组进行求解
  • 利用规律初始化并输出
#include<iostream>
#include<vector>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<iostream>
#include<vector>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个）正整数（不大于100000），请注意行内和行末可能有多余的空格，你的程序需要能处理这些空格。
每个整数代表一个ID号。

输出

要求程序输出1行，含两个整数m n，用空格分隔。
其中，m表示断号ID，n表示重号ID

样例输入复制

2
5 6 8 11 9
10 12 9

样例输出复制

7 9

解题思路

  • 一维数组做数据储存，根据题目，申请固定储存空间。（用vector的时候，会导致内存过大，也不知道是什么原因）
  • 用sort函数对数组进行排序，[关于sort（）的使用]((26条消息) C++ sort()排序详解_ACfun-CSDN博客_c++sort排序)
#include<iostream>
#include<vector>
#include<algorithm>
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

样例输出

3

**解题思路：贪心算法，所做的是当前最优的解法，到最后达成最优的结果 **

​ 每次都选取当前最多的糖果，达到最后最多的糖果

suot函数先排序，使用greater()进行升序排序，

#include<iostream>
#include<vector>
#include<algorithm>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最大获利（数组）

问题描述

Chakra是一位年轻有为的企业家，最近他在进军餐饮行业。他在各地开拓市场，共买下了N个饭店。在初期的市场调研中，他将一天划分为M个时间段，并且知道第i个饭店在第j个时间段内，会有Aij位服务员当值和Bij位客户光临。他还分析了不同饭店不同时间段客户的需求，得到第i个饭店在第j个时间段内，平均每位客户消费Cij元。为了创设品牌形象，Chakra决定每个饭店每天只选择一个时间段营业，每个服务员至多接待一位顾客（若顾客数多于服务员数，超过部分的顾客当天就无法在该店消费了）。
　　企业家的目的终究还是获利。请你安排营业时间，并告诉Chakra每天消费总额最多为多少。

输入格式

第一行两个整数，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<iostream>
#include<vector>
#include<algorithm>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=a1a2a3*…*ak为N的潜能。
　　给定N，求它的潜能M。
　　由于M可能过大，只需求M对5218取模的余数。

输入格式

输入共一行，为一个正整数N。

输出格式

输出共一行，为N的潜能M对5218取模的余数。

样例输入

10

样例输出

36

数据规模和约定

1<=N<10^18

解题思路

  • 关键点1：通过题目给出的结果，是求一个数分解成多个数后，多个数的乘积最大

  • 关键点2：要使乘积达到最大，就要分解成3，2或者4的组合

  • 关键点3：在求乘积的时候用的快速幂算法，同时边乘边模的思想

    [关于快速幂的理解]((26条消息) 递归实现快速幂_haoran的博客-CSDN博客)

    [关于本题的解题参考](试题 算法训练 数的潜能 正整数分解使得乘积最大问题 (nicethemes.cn))

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;int p = 5218;
int fastPow(long long int a, long long int k)//递归实现快速幂
{//递归出口if (k == 0)return 1;//if (k % 2 == 1){return a * fastPow(a, k - 1)%p;}else{long long int tem = fastPow(a, k / 2);return (tem * tem)%p;}
}int main()
{long long int n;cin >> n;if (n < 3){cout << n;return 0;}long long int tem;if (n % 3 == 0){tem = n / 3;cout << fastPow(3, tem) % p;}else if (n % 3 == 1){tem = n / 3;cout << fastPow(3, tem-1)*4 % p;}else if(n%3==2){tem = n / 3;cout << fastPow(3, tem)*2 % p;}return 0;
}

8.翻硬币（中等题）

题目描述

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：oo*oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入

两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度< 1000

输出

一个整数，表示最小操作步数。

样例输入复制

*o**o***o*** 
*o***o**o***

样例输出复制

1

解题思路

  • 通过画图来找思路，[参考链接](蓝桥杯历届试题-翻硬币 （C/C++代码）规律题-Dotcpp编程社区)
  • [在这里插入图片描述
#include<iostream>
#include<string>using namespace std;int main()
{string s1, s2;cin >> s1 >> s2;int start = 0, count = 0;//start为发生不同的开始的位置for (int i = 0; i < s1.size(); i++){if (s1[i] != s2[i])//发生了不同{if (start){//两个发生不同count += (i - start);start = 0;//完成了一对的计算}else{start = i;//每一对发生不同的开始}}}cout << count;return 0;
}

9数组的交，并，差集

资源限制

时间限制：1.0s 内存限制：256.0MB

输入两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。交集、并集和余集的计算都要求写成一个单独的函数。
　　输入第一行为一个整数n，表示集合A中的元素个数。
　　第二行有n个按从小到大的顺序输入且互不相同的整数，表示集合A中的元素
　　第三行为一个整数m，表示集合B中的元素个数。
　　第四行有m个按从小到大的顺序输入且互不相同的整数，表示集合B中的元素
　　集合中的所有元素均为int范围内的整数，n、m<=1000。
　　输出第一行按从小到大的顺序输出A、B交集中的所有元素。
　　第二行按从小到大的顺序输出A、B并集中的所有元素。
　　第三行按从小到大的顺序输出B在A中的余集中的所有元素。
输入：
　　5
　　1 2 3 4 5
　　5
　　2 4 6 8 10
　　输出:
　　2 4
　　1 2 3 4 5 6 8 10
　　1 3 5

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>using namespace std;void Jiaoji(int n,int m,int a1[],int a2[])
{vector<int>tem;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (a1[i] == a2[j])//遍历集合B中的每个数，看看与A中的该元素是否相同{tem.push_back(a1[i]);//放到向量里面}}}sort(tem.begin(), tem.end());//对向量进行排序for (int i = 0; i < tem.size(); i++)//输出cout << tem[i] << " ";cout << endl;
}
void Bingji(int n, int m, int a1[], int a2[])
{vector<int>tem;for (int i = 0; i < n; i++)//先把A集合放入向量中{tem.push_back(a1[i]);}int flag = 1;//标记B中某个元素不相同for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (a2[i] == a1[j]){flag = 0;//出现相同的元素}}if (flag)//同相同则把B中的该元素加入到向量里面tem.push_back(a2[i]);flag = 1;}sort(tem.begin(), tem.end());//排序for (int i = 0; i < tem.size(); i++)//输出cout << tem[i] << " ";cout << endl;
}
void Chaji(int n, int m, int a1[], int a2[])
{vector<int>tem;int flag = 1;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (a1[i] == a2[j]){flag = 0;}}if (flag)tem.push_back(a1[i]);flag = 1;}sort(tem.begin(), tem.end());for (int i = 0; i < tem.size(); i++)cout << tem[i] << " ";cout << endl;
}
int main()
{int n, m;cin >> n;//动态生成A集合，并输入A集合int* a1 = new int[n];for (int i = 0; i < n; i++){cin >> a1[i];}//动态生成B集合，并输入B集合cin >> m;int* a2 = new int[m];for (int i = 0; i < m; i++){cin >> a2[i];}//函数调用Jiaoji(n, m, a1, a2);Bingji(n, m, a1, a2);Chaji(n, m, a1, a2);delete[]a2;delete[]a1;return 0;
}

这篇关于蓝桥杯算法练习（用筛选法求N内的素数，蛇形矩阵，分糖果，错误票据，kAc分糖果给你吃，最大获利，翻硬币）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/426164。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
XTU 1233 n个硬币连续m个正面个数（dp）

XTU 1233 n个硬币连续m个正面个数（dp）

题面： Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o
阅读更多...
poj 3723 kruscal，反边取最大生成树。

poj 3723 kruscal，反边取最大生成树。

题意： 需要征募女兵N人，男兵M人。 每征募一个人需要花费10000美元，但是如果已经招募的人中有一些关系亲密的人，那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度，征募某个人的费用是10000 - （已经征募的人中和自己的亲密度的最大值）。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析： 先设想无向图，在征募某个人a时，如果使用了a和b之间的关系
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2