当前位置：首页>前端>正文

蓝桥杯（CC++）知识点------杂

前端2024-04-27 20:38:40

蓝桥杯知识点（杂）

一、二分查找

1、普通的二分查找

使用二分查找的前提就是必须是有序的数组

关于二分查找，首先需要注意的是，所给的区间，一般情况下有两种，第一种就是两头都是闭区间，第二种就是左闭右开的区间

第一种

/*
[1,mid],[mid+1,size]
*/


int BinarySelect(int* arr, int n, int target) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] > target) {
            right = mid - 1;
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            return mid;
        }
    }

    return -1;
}


int main() {

    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    
    int n = sizeof(arr) / sizeof(int);
    //所找的元素，则我们返回的就是他的下标
    int target = 8;

    int index = BinarySelect(arr, n, target);
    
    printf("index = %d\n", index);

    return 0;
}

第二种

/*
[1,mid-1],[mid,size]

*/

int BinarySelect(int* arr, int n, int target) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        int mid = (left + right) >> 1;
        if (arr[mid] > target) {
            right = mid;
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            return mid;
        }
    }

    return -1;
}


int main() {

    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    
    int n = sizeof(arr) / sizeof(int);
    //所找的元素，则我们返回的就是他的下标
    int target = 10;

    int index = BinarySelect(arr, n, target);
    
    printf("index = %d\n", index);

    return 0;
}

2、二分查找的列题

蓝桥杯（CC++）知识点------杂,在这里插入图片描述,第1张

Demo：

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

//数组中的数为num,要查找的数是x
bool isBlue1(int num, int x) {
	if (num < x) {
		return true;
	}
	else {
		return false;
	}
}

//数组中的数为num,要查找的数是x
bool isBlue2(int num, int x) {
	if (num <= x) {
		return true;
	}
	else {
		return false;
	}
}

int binary_select1(int* arr,int n,int x) {
	int left = -1, right = n;
	while (left + 1 != right) {
		int mid = (left + right) >> 1;
		if (isBlue1(arr[mid], x)) {
			left = mid;
		}
		else {
			right = mid;
		}
	}
	if (arr[right] == x) {
		return right;
	}
	else {
		return -1;//找不到返回-1
	}
}

int binary_select2(int* arr,int n,int x) {
	int left = -1;
	int right = n;

	while (left + 1 != right) {
		int mid = (left + right) >> 1;
		if (isBlue2(arr[mid],x)) {
			left = mid;
		}
		else {
			right = mid;
		}
	}

	if (arr[left] == x) {
		return left;
	}
	else {
		return -1;//找不到返回-1
	}
}

int main() {

	int arr[] = { 0 };
	//n为数组中的元素的个数，q为要查询元素的个数
	int  n, q;
	scanf("%d %d", &n, &q);

	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	//x表示就是要查询的数
	int x;

	while (q--) {
		scanf("%d", &x);

		//index1就是要查询的数第一次出现的位置（下标）
		int index1 = binary_select1(arr, n, x);
		//index2就是要查询的数最后一次出现的位置（下标）
		int index2 = binary_select2(arr, n, x);

		printf("index1 = %d , index2 = %d\n", index1, index2);
	}
	return 0;
}

3、浮点数的二分查找

/*
求出一个数开三次方
思想：就是在一个区间中使用二分法，去找出那个数的三次方等于我们输入的那个数
*/
#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

int n = 0;

bool check(double mid) {
	if (mid * mid * mid <= n) {
		return true;
	}
	else {
		return false;
	}
}


int main() {
	
	scanf("%d", &n);

	double left = -100, right = 100;
	while (right - left > 1e-8) {
		double mid = 1.0*(left + right) / 2;

		if (check(mid)) {
			left = mid;
		}
		else {
			right = mid;
		}
	}

	printf("%lf\n", left);
	printf("%lf\n", right);

	return 0;
}

二、二进制

在给定的二进制数中，找到其中1的个数

int main() {

        int BinaryNum = 0;
        scanf("%d", &BinaryNum);

        int count = 0;

        while (BinaryNum) {
            //在底层是用的补码进行&运算，&：表示两个1才为1，其他就是0
            if (BinaryNum & 1 == 1) {
                count++;
            }
            BinaryNum = BinaryNum >> 1;

        }
    
        printf("count = %d\n", count);
        return 0;
}

求二进制数中的第k位的数值是什么

int main() {

        int BinaryNum = 0;
        scanf("%d", &BinaryNum);

        //你想知道第几位的值
        int k = 3;

        printf("%d\n", BinaryNum>>(3-1)&1);
        return 0;
}

三、前缀和

关于前缀和就是在一个数组中，前n个数的和，但是在这里我们介绍一个题目，使用前缀和的思想，可以快速求解，并且不会超时

1、快速求出两个区间的数的总和

关于这里，很多同学可能都是想到的是暴力，虽然可以通过，但是如果我们输入的数很多的话就可能会超时，达不到提交的要求

先使用暴力写一遍

Demo：

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(){
	int num = 0;
	int seekNum = 0;
	int arr[] = { 0 };
	int sum = 0;
	scanf("%d%d", &num, &seekNum);

	for (int i = 0; i < num; i++) {
		scanf("%d", &arr[i]);
	}

	while (seekNum--) {
		int left = 0;
		int right = 0;
		scanf("%d%d", &left, &right);
		sum = 0;
		for (int i = left; i <= right; i++) {
			sum += arr[i];
		}
		printf("sum = %d\n", sum);
	}
	return 0;
}

再使用前缀和的思想

关于使用前缀和的思想，这里采用的下标是从1开始的，比如输入的数组为：4 2 1 3 5，right=1,left=5,则sum = 15，就是输入right和left就是下标

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(){
	int num = 0;
	int seekNum = 0;
	int arr[] = { 0 };
	int sum[] = {0};
	scanf("%d%d", &num, &seekNum);

	for (int i = 1; i <= num; i++) {
		scanf("%d", &arr[i]);
        //使用sum数组将每一个数的前缀和保存起来
		sum[i] = sum[i - 1] + arr[i];
	}

	while (seekNum--) {
		int left = 0;
		int right = 0;
		scanf("%d%d", &left, &right);
		//这里看不懂的，可以画一个数组，再根据代码细看
		printf("sum = %d\n", sum[right]-sum[left-1]);
	}
	return 0;
}

2、再二维数组中使用前缀和求出两个坐标点之间的元素的总和

蓝桥杯（CC++）知识点------杂,在这里插入图片描述,第2张

这个公式是由画图直接得出来的

注意：公式的有一个位置是写错了的，最后的s[x1-1] [y2-1]应该改成s[x1-1] [y1-1]

Demo：

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h> 
#include <stdbool.h>

int main(){
	int row = 0;
	int col = 0;
	int seekNum = 0;
	int arr[][10000] = { 0 };
	int sum[][10000] = { 0 };

	scanf("%d%d%d", &row, &col, &seekNum);

	for (int i = 1; i <= row; i++) {
		for (int j = 1; j <= col; j++) {
			scanf("%d", &arr[i][j]);
			sum[i][j] = arr[i][j] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];	
		}
	}

	while (seekNum--) {
		int x1, x2, y1, y2;
		scanf("%d%d%d%d", &x1, &x2, &y1, &y2);

		printf("sum = %d\n", sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);
	}

	return 0;
}

3、给定一个目标值，在两个数组中分别使用一个元素，让这两个数的和等于这个目标值

这里就要使用到，双指针的技巧了。首先在使用之前，我们要使用的是一个在头一个在尾的双指针，这样就是一个单调的（控制变量）

Demo：（不知道为什么我的会超出数组范围）

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h> 
#include <stdbool.h>

int main(){
	int arr1[] = { 0 };
	int arr2[] = { 0 };
	int num1 = 0;
	int target = 0;
	int num2 = 0;
	
	scanf("%d%d%d", &num1, &num2, &target);

	for (int i = 0; i < num1; i++) {
		scanf("%d", &arr1[i]);
	}

	for (int j = 0; j < num2; j++) {
		scanf("%d", &arr2[j]);
	}
	
	for (int i = 0, j = num2 - 1; i < num1; i++) {
		while (j >= 0 && arr1[i] + arr2[j] > target) {
			j--;
		}

		if (arr1[i] + arr2[j] == target) {
			printf("index1 = %d,index2 = %d\n", i, j);
			return 0;
		}

	}
	return 0;
}

四、双指针

关于双指针的问题，在上面的问题中已经提到了，我们在这里就简单提一下，双指针的问题，可以分为两个指针在同一的起点，也可以分为一前一后，也就是对撞指针

1、递增三元组

题目描述：

给定三个整数数组

A=[A1,A2,…AN]
,
B=[B1,B2,…BN]
,
C=[C1,C2,…CN]
,

请你统计有多少个三元组 (i,j,k)
 满足：

1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N
。

第二行包含 N
 个整数 A1,A2,…AN
。

第三行包含 N
 个整数 B1,B2,…BN
。

第四行包含 N
 个整数 C1,C2,…CN
。

输出格式
一个整数表示答案。

数据范围
1≤N≤105
,
0≤Ai,Bi,Ci≤105
输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27

==思路分析1：==在这道题中可以使用我们之前提到的二分查找法，就是将去遍历中间的那个数，使中间的这个数满足题目的要求

但是在使用二分查找法的时候，必须将数组进行排序，二分查找法只针对有序数组

五、关于DFS（深度优先算法）

一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

1、全排列问题

题目描述
按照字典序输出自然数 
1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式
一个整数 
n。

输出格式
由 1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 
5
5 个场宽。

输入输出样例
输入 
3
输出 
    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

做这道题的话就是可以使用画图的方式，先将大概的思路写清楚，再结合代码

蓝桥杯（CC++）知识点------杂,在这里插入图片描述,第3张

Demo：

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


const int N = 10;
bool st[N];//true表示选过这个数，false表示没有选过这个数

int arr[N];//存的是答案，即{1,2,3}
int n = 0;

void dfs(int x) {//x是当前枚举到了数组的哪个位置
		if (x > n) {
			for (int i = 1; i <= n; i++) {
				printf("%5d", arr[i]);
			}
			printf("\n");
			return;
		}		
		for (int i = 1; i <= n; i++) {
			if (!st[i]) {
				st[i] = true;//就是选了这个数
				arr[x] = i;//让数组记录下这个数
				dfs(x + 1);//再进行选择下一个数
				st[i] = false;//再把状态置空，即当回溯时，会回到上一个状态
				arr[x] = 0;
			}
		}
}


int main() {
	scanf("%d", &n);
	dfs(1);
	return 0;
}

2、组合的输出

题目描述
排列与组合是常用的数学方法，其中组合就是从 n 个元素中抽出 r 个元素（不分顺序且 r≤n），我们可以简单地将 n 个元素理解为自然数1,2，···n，从中取出r个数 
现要求你输出所有组合。

例如 n=5,r=3，所有组合为：

123
,
124
,
125
,
134
,
135
,
145
,
234
,
235
,
245
,
345
123,124,125,134,135,145,234,235,245,345。

输入格式
一行两个自然数 n,r(1<n<21,0≤r≤n)。

输出格式
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

注意哦！输出时，每个数字需要 
3
3 个场宽。以 C++ 为例，你可以使用下列代码：

cout << setw(3) << x;
输出占 3 个场宽的数,注意你需要头文件 iomanip。

输入输出样例
输入 
5 3 
输出 
  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5

这道题跟上面的那道题差不多，都是选数，但是就是说这道题是组合，而上面那道题就是排列，排列要考虑顺序，组合就不需要考虑顺序，还是可以先画出深度搜索图，

蓝桥杯（CC++）知识点------杂,在这里插入图片描述,第4张

Demo：

 #define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, r;
const int N = 21;
int arr[N];

/*
int x;//记录枚举到了哪个位置
int arr[];//用来记录存了哪些数据
int start;//用来记录当前位置从几开始枚举·
*/


void dfs(int x, int start) {
	//退出搜索
	if (x > r) {
		for (int i = 1; i <= r; i++) {
			printf("%3d", arr[i]);
		}
		printf("\n");
		return;
	}

	for (int i = start; i <= n; i++) {
		arr[x] = i;
		dfs(x + 1, i + 1);
		arr[x] = 0;
	}
}

int main() {
	scanf("%d%d", &n, &r);

	dfs(1,1);

	return 0;
}

3、跳台阶

一个楼梯共有 n 级台阶，每次可以走一级或者两级，问从第 00 级台阶走到第 n 级台阶一共有多少种方案。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

1≤n≤15

输入样例：

输出样例：

Demo：

#include <stdio.h> 

int dfs(int n){ 
	if(n==1){
		return 1;
	}else if(n==2){
		return 2;
	}else{
		return dfs(n-1)+dfs(n-2);
	}
	
}

int main(){
	
	int n = 0;
	int ret = 0;
	scanf("%d",&n); 
	ret = dfs(n);
	printf("%d",ret);
	return 0;
}

4、递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

输入样例：

输出样例：

Demo：

#include<iostream>
using namespace std;


const int N = 21; 
int st[N];//记录状态 ，1表示选，2表示不选，0表示还在考虑  
int n;

void dfs(int x){
	
	if(x>n){
		int i = 0;
		for(int i=1;i<=n;i++){
			if(st[i]==1){
				printf("%d ",i);
			}
			
		}
		printf("\n");
		return;
	} 
	
	
		//不选
		st[x] = 2;
		dfs(x+1);
		st[x] = 0;//恢复现场
		
		//选 
		st[x] = 1;
		dfs(x+1);
		st[x] = 0;//恢复现场  
	
}


int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}

5、递归实现排列型枚举

题目描述

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n。

输出格式

由1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5 个场宽。

输入输出样例

**输入 **

**输出 **

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

说明/提示

1≤n≤9。

Demo：

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


const int N = 10;
bool st[N];//true表示选过这个数，false表示没有选过这个数

int arr[N];//存的是答案，即{1,2,3}
int n = 0;

void dfs(int x) {//x是当前枚举到了数组的哪个位置
		if (x > n) {
			for (int i = 1; i <= n; i++) {
				printf("%5d", arr[i]);
			}
			printf("\n");
			return;
		}		
		for (int i = 1; i <= n; i++) {
			if (!st[i]) {//表示如果这个数没有被选过就选择它
				st[i] = true;
				arr[x] = i;
				dfs(x + 1);
				st[i] = false;
				arr[x] = 0;
			}
		}
}


int main() {
	scanf("%d", &n);
	dfs(1);
	return 0;
}

6、递归实现组合型枚举

题目描述

排列与组合是常用的数学方法，其中组合就是从 n 个元素中抽出 r 个元素（不分顺序且r≤n），我们可以简单地将 n 个元素理解为自然数 1,2,…,n，从中任取 r 个数。

现要求你输出所有组合。

例如 n=5,r=3，所有组合为：

123,124,125,134,135,145,234,235,245,345123,124,125,134,135,145,234,235,245,345。

输入格式

一行两个自然数 n*,r(1<n<21,0≤r≤n)。

输出格式

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

注意哦！输出时，每个数字需要 33 个场宽。以 C++ 为例，你可以使用下列代码：

cout << setw(3) << x;

输出占 33 个场宽的数 x。注意你需要头文件 iomanip。

输入输出样例

**输入 **

5 3

**输出 **

Demo：



#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, r;
const int N = 21;
int arr[N];

/*
int x;//记录枚举到了哪个位置
int arr[];//用来记录存了哪些数据
int start;//用来记录当前位置从几开始枚举·
*/


void dfs(int x, int start) {
	//退出搜索
	if (x > r) {
		for (int i = 1; i <= r; i++) {
			printf("%3d", arr[i]);
		}
		printf("\n");
		return;
	}

	for (int i = start; i <= n; i++) {
		arr[x] = i;
		dfs(x + 1, i + 1);
		arr[x] = 0;
	}
}

int main() {
	scanf("%d%d", &n, &r);

	dfs(1,1);

	return 0;
}

六、关于蓝桥杯中常用的STL

①vector容器

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>  
#include <string>  
#include <vector>
using namespace std;

int main() {
    //创建一个int类型的vector数组，记得要包含头文件
    vector<int> arr;

    

    /*
    还有其他的定义方法：
    vector<int> a(3);//定义一个长度为3的vector  未初始化 输出》0 0 0

    vector<int> a(10, 3); //定义一个长度为10，且每个数赋值为3
    
    //将向量b中从下标0 1 2（共三个）的元素赋值给a，a的类型为int型
	//它的初始化不和数组一样 
	vector<int>a(b.begin(),b.begin+3);

    int b[7] = { 1,2,3,4,5,6,7 };
    vector<int> a(b, b + 7);//给a赋值1-7的数值
    */


    //尾插进去数据
    arr.push_back(1);
    arr.push_back(2);
    arr.push_back(3);
    arr.push_back(4);
    arr.push_back(5);

    //遍历数组中的元素，使用迭代器
    vector<int>::iterator it;
    for (it = arr.begin(); it != arr.end(); it++)
        printf("%d ", *it);

    //在任意的位置插入元素,在第i+1个元素前面插入数据10，即在第二个元素前面插入数据10
    arr.insert(arr.begin() + 1, 10);//1 10 2 3 4 5
  
    //删除元素：    
    arr.erase(arr.begin() + 2); //删除第i+1个元素,即删除第三个元素

    arr.erase(arr.begin() + 0, arr.end() + 4); //删除区间[i, j - 1]; 区间从0开始
   
    //删除尾部元素
    arr.pop_back();

    //求数组大小:
    arr.size();

    //清空
    arr.clear();

    return 0;
}

关于vector中最核心的也就是排序和逆序

（1）排序

//关于在vector中使用排序的方法，也是有直接封装好了的方法，直接可以调用
//注意使用<algorithm>头文件

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = { 10,4,1,0,3,7,8 };
    sort(arr.begin(),arr.end());

    vector<int>::iterator it;
    for (it = arr.begin(); it != arr.end(); it++) {
        printf("%d ", *it);
    }

    return 0;
}

（2）逆序

//
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = { 1,2,3,4,5 };
    
    reverse(arr.begin(), arr.end()); //将元素翻转，即逆序排列！

    vector<int>::iterator it;
    for (it = arr.begin(); it != arr.end(); it++) {
        printf("%d ", *it);
    }


    return 0;
}

②map容器（有序的但是可以重复）

关于map容器和vector不一样，它通过键值对的形式存储数据的，一个key对应一个value，而且在存储的时候，不能存在相同的key，还有注意就是在使用map容器的时候要包含头文件

③set容器（有序但是不重复）

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <set>
#include <algorithm>

using namespace std;

int main() {
    //创建一个set数组
    set<int> s;
    //插入数据，并且自动根据数据的大小进行排序
    s.insert(10);
    s.insert(40);
    s.insert(20);
    s.insert(40);
    s.insert(90);
    s.insert(60);
    //遍历set
    set<int>::iterator it;
    for (it = s.begin(); it != s.end(); it++) {
        printf("%d ", *it);
    }
    printf("\n");
    //删除起始位置的元素
    s.erase(s.begin());
    
    //根据元素删除
    s.erase(40);

    //查找元素是否存在，存在就返回它的迭代器，不存在就返回set.end();
    set<int>::iterator ret = s.find(90);
    printf("%d", *ret);

    //查找元素的个数
    int count = s.count(60);

    //清空
    s.clear();
    return 0;
}

④队列

queue<Type, Container> (<数据类型，容器类型>）
初始化时必须要有数据类型，容器可省略，省略时则默认为deque 类型

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <queue>
#include <list>
#include <algorithm>

using namespace std;

int main() {

    /*默认为用deque容器实现的queue
    queue<int> q1;
    queue<double> q2;
    queue<char> q3;
    */


    //用list容器实现的queue 
    queue<char, list<char>> q1;
        
    //注意：不能使用vector去初始化队列
        
    //push() 在队尾插入一个元素
    q1.push(10);
    q1.push(20);
    q1.push(30);
    q1.push(40);
    q1.push(50);

    //pop() 删除队列第一个元素
    q1.pop();

    //size() 返回队列中元素个数
    int size = q1.size();

    //empty() 如果队列空则返回true
    bool flag = q1.empty();

    //front() 返回队列中的第一个元素
    int first = q1.front();

    //back() 返回队列中最后一个元素
    int tail = q1.back();

    //遍历队列
    for (int i = 0; i < size; i++) {   //myqueue_size 必须是固定值
        printf("%d ", q1.front());
        /*q1.push(q1.front());*/
        q1.pop();
    }


    return 0;
}

七、c++中常用的数学函数

	//求常数e的x次方。#define e 2.71828182845904523536
    exp(x);  
    //求x的y次方
    pow(x, y);  
    //开平方
    sqrt(x);
    
    //求e为底的对数 ln
    log(x);    
    //求10为底的对数 lg
    log10(x);    
    //求x为底的y的对数
    log(y) / log(x);  
    
    //整数型的绝对值
    int abs(x);   
    //浮点型的绝对值 
    double fabs(double x);
    
    //向上取整 返回的是大于或等于x的最小整数
    ceil(x);   

    //向下取整 返回的是小于或等于x的最大整数
    floor(x);    

    //朝零方向取整
    fix(x);    

    //四舍五入到最近的整数
    round(x);    

    //使用round保留2位小数
    double num = 3.1415926;
    double roundedNum = round(num * 100) / 100;
    cout << roundedNum << endl;     //输出 3.14  
    
    //产生一个在[0,50)区间内的随机数
	r = rand() % 50;    
	//产生[a,b]区间的随机数
	r = a + rand() % (b-a+1);   
	
	//三角函数
	sin(x);    //正弦
	cos(x);    //余弦。cos(π)=-1,故 π = acos(-1)
	tan(x);    //正切
 
	//反三角函数
	asin(x);    //反正弦 [−π/2, π/2]
	acos(x);    //反余弦 [0, π]
	atan(x);    //反正切（主值）   [−π/2, π/2]
	atan2(x);    //反正切（整圆值） [−π, π]
	
	
	//两个数比较
	min(a, b, comp);    //取最小值，comp为指定的比较规则，可缺省
	max(a, b, comp);
 
	//多个数比较，需加 { } 
	min({a,b,c,d}, comp);


	辗转相除法求最大公约数：

	int gcd(int a,int b){

         int temp;

         while(a%b!=0){

                  temp=a;

                  a=b;

                  b=temp%b;

         }

         return b;

	}

	辗转相除法最小公倍数：

	int lcm(int a,int b){

         int a1=a,b1=b,temp;

         while(a%b!=0){

                  temp=a;

                  a=b;

                  b=temp%b;
         }
         return a1/b*b1;
	  }

	杨辉三角：
	任意一行的所有元素

	C[0]=1;

	For(int i=1;i<=n;i++)         
        C[i]=C[i-1]*(n-i+1)/

八、常考知识点

1、优先队列

关于在c++中的优先队列就是可以拿出优先级最高的元素

Demo：这里默认使用的是大顶堆

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <queue>
#include <list>
#include <algorithm>

using namespace std;

int main() {
    //定义一个存储int型的优先队列
    priority_queue<int> queue;//大顶堆

    //向队列中插入元素
    queue.push(1);
    queue.push(-3);
    queue.push(0);
    queue.push(5);
    queue.push(8);
    queue.push(10);

    //获取元素的数量
    int size = queue.size();

    //删除优先级最高的元素
    queue.pop();

    //访问优先级最高的元素
    queue.top();

    //0判断优先队列是否为空
    bool flag = queue.empty();


    while (!queue.empty()) {
        printf("%d ", queue.top());
        queue.pop();
    }
    return 0;
}

Demo：小顶堆

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <queue>
#include <list>
#include <algorithm>

using namespace std;


int main() {
    //定义一个存储int型的优先队列
    priority_queue<int,vector<int>,greater<int>> queue;//就改成了小顶堆，大顶堆是less<int>

    //向队列中插入元素
    queue.push(1);
    queue.push(-3);
    queue.push(0);
    queue.push(5);
    queue.push(8);
    queue.push(10);

    //获取元素的数量
    int size = queue.size();

    //删除优先级最高的元素
    queue.pop();

    //访问优先级最高的元素
    queue.top();

    //0判断优先队列是否为空
    bool flag = queue.empty();


    while (!queue.empty()) {
        printf("%d ", queue.top());
        queue.pop();
    }
    return 0;
}

查看全文

https://www.xamrdz.com/web/2hp1936580.html

蓝桥杯知识点（杂）

一、二分查找

1、普通的二分查找

2、二分查找的列题

3、浮点数的二分查找

二、二进制

三、前缀和

1、快速求出两个区间的数的总和

2、再二维数组中使用前缀和求出两个坐标点之间的元素的总和

3、给定一个目标值，在两个数组中分别使用一个元素，让这两个数的和等于这个目标值

四、双指针

1、递增三元组

五、关于DFS（深度优先算法）

1、全排列问题

2、组合的输出

3、跳台阶

输入格式

输出格式

数据范围

输入样例：

输出样例：

4、递归实现指数型枚举

输入格式

输出格式

数据范围

输入样例：

输出样例：

5、递归实现排列型枚举

题目描述

输入格式

输出格式

输入输出样例

说明/提示

6、递归实现组合型枚举

题目描述

输入格式

输出格式

输入输出样例

六、关于蓝桥杯中常用的STL

①vector容器

（1）排序

（2）逆序

②map容器（有序的但是可以重复）

③set容器（有序但是不重复）

④队列

七、c++中常用的数学函数

八、常考知识点

1、优先队列

相关文章：