CSP-S学习笔记
2025-07-30 20:34:55
发布于：江苏
21阅读
0回复
0点赞
DAY 1：
-
时间复杂度：衡量算法效率的 运行规模：10^8次方
2n^2+3n+1 -> n^2
2n^2+3n+m -> n^2+m
2.求某一个值的时候：二分
使用二分之前一定要检查这个范围是否有序
在a数组的索引1到索引n之间查找第一个大于等于x的指的位置
***这个函数的返回值是地址
lower_bound(a+1 ，a+1+n , x) - a;
upper_bound(a+1 ，a+1+n , x) - a;
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[10] = {0};
for(int i=0;i<10;i++)
{
a[i] = i;
}
cout<<lower_bound(a,a+10 , 4) - a<<endl; // 4
cout<<upper_bound(a,a+10 , 4) - a<<endl; // 5
}
3.图的存储：邻接矩阵(节点比较少，边比较多) 邻接表（节点比较多，边比较少的）
4.深搜和广搜: 图的算法 组合 路径查找
DAY2：
图的遍历：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int mp[1005][1005];
int vis[1005];
void DFS(int x)
{
for(int i=1;i<=n;i++)
{
if( mp[x][i] == 1 && vis[i]==0 && i != x )
{
cout<<i<<" ";
vis[i] = 1;
DFS(i);
}
}
}
int main(){
cin>>n>>m;
//图的存储
while(m--)
{
int a , b;
cin>>a>>b;
mp[a][b] = 1;
}
cout<<"1 ";
//图的遍历
// DFS的遍历
DFS(1);
}
最短路算法：
#include<bits/stdc++.h>
using namespace std;
int n,m,s,u,v,w;
int mp[1005][1005]; //图的存放
int dis[1005] , vis[1005]; // dis：起点到i点的最短距离 vis：标记是否已经确定
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
mp[u][v] = w;
}
// 初始化数组 dis为超大常数
for(int i=0;i<=n;i++) dis[i]= 1e9;
// 把起点位置的值改为 0
dis[s] = 0;
//开始查找
for(int i=1;i<=n;i++)
{
int idx = 0;
for(int j=1;j<=n;j++)
{
//在未确定的节点当中找到最小的点
if(dis[j] <= dis[idx] && vis[j]==0 )
{
idx = j;
}
}
vis[idx] = 1; //标记这个点为已经确定点
//更新从idx到其他未确定点的最短距离
for(int j=1;j<=n;j++)
{
if(mp[idx][j])
{
//看看是不是更短 松弛
if( dis[j] > dis[idx] + mp[idx][j] ) dis[j] = dis[idx] + mp[idx][j];
}
}
}
for(int i=1;i<=n;i++) cout<< dis[i]<<" ";
}
DAY3：
树的存储：
1.顺序存储
#include<bits/stdc++.h>
using namespace std;
int main(){
//1.顺序存储,存的是数据，父子关系通过下标 , 容易浪费空间
// i的左右孩子节点： 2i 2i+1 i的父亲节点 ： i/2
char tree[10];
for(int i=1;i<=8;i++)
{
cin>>tree[i];
}
}
2.链式存储
#include<bits/stdc++.h>
using namespace std;
struct tree{
char data; // 数据
//关系： father lchild rchild
tree *lchild , *rchild , *father;
};
int main(){
//链式存储
vector<int> a[100];
a[1].push(2);
a[1].push(-1);
a[1].push(-1);
a[1].push('A');
int alchild = a[1][0];
}
3.堆排序：
#include <iostream>
using namespace std;
void swap(int arr[], int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void adjustHeap(int arr[], int i, int length) {
int temp = arr[i];
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;
}
void heapSort(int arr[], int length) {
for (int i = length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, length);
}
for (int j = length - 1; j > 0; j--) {
swap(arr, 0, j);
adjustHeap(arr, 0, j);
}
}
int main() {
int arr[9] = {9, 8, 7, 6, 10, 4, 3, 2, 1};
heapSort(arr, 9);
for (int i = 0; i < 9; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
DAY 4：
拓扑排序：排列的不是大小而是顺序
#include<bits/stdc++.h>
using namespace std;
/*
拓扑排序: 必须先先修课程再完成选修课程 先修第一段路再修第二段路
通常情况下是用来对有向无环图当中的节点进行线性排序
Kahn算法(入度法)：
1.计算每一个节点的入度
2.把入度为零的所有节点全部入队(第一个节点去排序就有可能出现多个入度为零的节点)
3.把队首元素取出来(输出/加入拓扑排序), 遍历这个节点所有的邻居(从队首元素可以到达的所有节点),
把这些邻居节点的入度 -1,如果有谁的入度变成了 0 , 那么我就入队
4.检查你的拓扑排序和原来的节点数是否相同，不同就意味着存在环
优先队列： priority_queue<int> q;
*/
int n,m,ind[50];
vector<int> a[50] , s;
priority_queue<int , vector<int> ,greater<int> > q;
int main(){
cin>>n>>m;
// 1.存储并记录每个节点的入度
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
ind[v]++; //记录节点的入度数
}
//2.把入度为零的所有节点全部入队
for(int i=1;i<=n;i++)
{
if(ind[i]==0) q.push(i);
}
//3.把队首元素取出来,遍历这个节点所有的邻居
while( !q.empty())
{
int now = q.top();
q.pop();
s.push_back(now);
// a[now]里面存放在所有从now出发可以到达的节点
for(int i=0;i<a[now].size();i++)
{
//遍历出他的每一个下一个节点
int next = a[now][i];
ind[next]--;
if( ind[next]==0 ) q.push(next); // 判断去掉一个入度之后是否为 0
}
}
for(int i=0;i<n;i++) cout<<s[i]<<" ";
}
这里空空如也
有帮助，赞一个