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

liuian 2025-07-07 20:10 51 浏览

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深搜进行小范围判断，拿到部分分

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

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