信奥赛C++常用的算法总结（信息学奥赛c语言和c++有什么区别）

1、桶排序

核心：

①创建盛下所有数的数组

②将每个数作为编号放入桶里

优点：稳定、简单、容易考

缺点：空间复杂度较大，时间复杂度较大。

#include<bits/stdc++.h>
using namespace std;
int main(){
	//将 50 40 30 30 10 排序成10 20 30 40 50
	int arr[101]={};
	for(int i=1;i<=5;i++){
		int a;
		cin>>a; 
		//重点在这里 桶思想。 
		arr[a]++;
	} 
	for(int i=1;i<=101;i++){
		for(int j=1;j<=arr[i];j++){
			cout<<i<<" ";
		}
	}
	return 0;
}

2、冒泡排序

核心：邻居好说话 邻居交换

重点：swap(a,b);

#include<bits/stdc++.h>
using namespace std;
int main(){
	//将 50 40 30 30 10 排序成10 20 30 40 50
	int arr[5] = {5,4,3,2,1};
	//次数 
	for(int i=0;i<4;i++){ 
		//交换的位置  i:0 
		for(int j=0;j<4-i;j++){
			if(arr[j]>arr[j+1]){
				swap(arr[j],arr[j+1]);
			}
		}
	}
	for(int i=0;i<5;i++){
		cout<<arr[i]<<" ";
	}            
	return 0;
}

3、快速排序

核心：找基准值 比较 小的放到基准值前 大的放到基准值后

重点：递归 用递归方法进行排列

#include <bits/stdc++.h>
using namespace std;
int a[1000000],n;
void quick_sort(int left,int right){
	if(left >= right) return;
	int i = left;
	int j = right;
	int x = a[left];
	while(i < j){
		while(i < j && x <= a[j]) j--;
		a[i] = a[j];
		while(i < j && x >= a[i]) i++;
		a[j] = a[i];
	}
	a[i] = x;
	quick_sort(left,i-1);
	quick_sort(i+1,right); 
}
int main(){
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >>  a[i];
	}
	quick_sort(0,n-1);
	for(int i = n-1;i >=0;i--){
		cout << a[i] << " ";
	}
	return 0;
}

4、队列

核心：队列用数组去模拟 有两个变量 头和尾

重点：head++出队 tail++ 入队

经典例题：2019年CSP-J第二轮第2题交通换乘

#include<iostream>
using namespace std;
struct toy{
	int price,time;
}yhp[10000001];
int main(){
	int che,qian,ke,n,sum=0,head=0,tail=0;
	cin>>n;  //6
	for(int i=1;i<=n;i++){
		cin>>che>>qian>>ke; 
		if(che==0){ //地铁 
			yhp[tail].price=qian;
			yhp[tail].time=ke+45;
			tail++;
			sum+=qian;
		}else{
			bool key=1;  //假设公交车花钱 
			for(int i=head;i<tail;i++){
				if(yhp[i].time<ke){ //过期 
					head++;
				}else if(yhp[i].price>=qian){
					key=0;
					yhp[i].price=0;
					break;
				}
			}
			if(key){
				sum+=qian;
			}
		}
	}
	cout<<sum;
	return 0;
}

5、栈

核心：栈用数组去模拟 有一个 栈顶

重点：top++ 入栈 top -- 出栈

经典例题：

#include <iostream>
using namespace std;
const int N = 1010;
int stack[N],a[N];
int top,n;
int main() {
	for (int i = 1; i <= 5; ++ i) {
		cin >> a[i];
	}
	top = 0;
	for (int i = 1,cur = 1; i <= 5; i++) {
		while (cur <= a[i]) {
			stack[++top] = cur;
			cur = cur+2; 
		}
		if (stack[top] == a[i]) {
			--top;
		} else {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}

6、字符串处理

7、桶思想

核心：用桶存数据

重点：根据条件遍历桶。

经典例题：CSP-J2020 直播获奖

经典例题：CSP-J2020 优秀的拆分

8、模拟算法之数学思想（近两年经常考的）

核心：脑子快

重点：灵感。

经典例题：CSP-J2023 小苹果

经典例题：CSP-J2023 公路

9、贪心算法

核心：排序

重点：只能拿到局部最优解 只能拿到小部分分（大概率是0分） 但是一定要会！

经典例题：

经典例题：（贪心做法70分）

P2096 最佳旅游线路（测试样例不对不代表没有分，思路要对）

经典例题：（）

P5019 [NOIP2018 提高组] 铺设道路

经典例题：

P1094 [NOIP2007 普及组] 纪念品分组

10、深搜算法

核心：递归

重点：可以拿到最终的结果 但是大概率拿不到满分，会超时（大概率是40-50分） 一定要会！

经典例题：P1036 [NOIP2002 普及组] 选数

#include <bits/stdc++.h>
using namespace std;
bool isprime(int a){
    if(a == 1) return false;
    for(int i = 2;i < a; i++)
        if(a % i == 0)
            return false;
    return true;
}
int n,k;
int a[25];
long long ans;
void dfs(int m, int sum, int startx){  //0 0 0
	//m代表现在选择了多少个数  sum表示当前的和  startx表示升序排列，以免算重
    if(m == k){// 剪枝（） 
        if(isprime(sum))//如果和是素数
            ans++;
        return ;
    }
    for(int i = startx; i < n; i++)
        dfs(m + 1, sum + a[i], i + 1);//递归
        //步数要加一，和也要加  升序起始值要变成i+1,以免算重
    return ;//这一个步骤下，所有的都枚举完了
}
int main(){
    scanf("%d%d",&n,&k);//输入  4  3
    for(int i = 0; i < n; i++)
        scanf("%d",&a[i]);//循环读入   3 7 12 19
    dfs(0,0,0);//调用函数
    
    printf("%d\n",ans);//输出答案
    return 0;//结束程序
}

11、动态规划

核心：

①当前状态是怎么来的 加上某个值构成当前状态 不加某个值当前状态就是前一个状态 用这两个状态比较 谁好就用谁。

②将值 放到数组里 加或者不加

优点：时间复杂度低 空间复杂度低

缺点：难 （DP方程不好找。）

③DP是一定有一个存储状态的数组， 状态是由条件准备的。

12、骗分（当做不出难题的时候可以进行使用）

核心：

①DP用贪心or深搜进行小范围判断，拿到部分分

②直接输出答案 没有分数。

优点：可以拿到小部分分数。

经典例题：P8816 [CSP-J 2022] 上升点列

第一种解法：该解法是深搜骗25分。

第二种解法：深搜中+记忆化搜索 40分。

第三种解法：深搜中+记忆化搜索 100分。

第四种解法：动态规划的代码如下