2024CSP考前整理

一、文件

1. 文件名不要打错
2. 保存关闭文件之后用命令行按规定指令编译
3. 检查输入输出文件
4. $\color{red}\star$ 测试大样例之前用规定指令编译
5. cerr 调试一定要删
6. 关闭所有窗口

二、题目

1. 必须计算空间复杂度
2. $\color{red}\star$ 注意溢出和越界
   -fsanitize=address,undefined
3. 注意时间常数，进行极限数据测试
4. 不确定的算法写完如果有时间要对拍
5. 大模数必须复制，注意是否素数
6. $\color{red}\star$ 必须用scanf&prinf输入输出
7. ceil()、floor()、pow()返回值是double的
8. unordered_map、unordered_map更快

三、算法

1. DP一定要计算空间
2. $\color{red}\star$ 线段树不要忘记pushup和pushdown
3. 考前看一下模板
4. $\color{red}\star$ 没思路依次想这些方法：DP、贪心、二分答案、数学、图论、猜结论、先写暴力再优化
5. 随机化可能有用
6. 多种贪心、错解取最优
7. $\color{red}\star$ STL

   name	func
   set	insert,find,erase,size,empty,clear
   map	[],auto x:a,count,erase
   stack	pop,push,front,empty
   queue	pop,push,front,empty
   deque	push_back,push_front,pop...,insert,erase,[]
   priority_queue	pop,push,top,empty

四、模板

1. GCD

   1 2 3

   int gcd(int x,int y) { return y?gcd(y,x%y):x; }

2. qpow（$n^k$）

   1 2 3 4 5 6 7

   long long ans=1; while(k){ if(k&1) ans=ans*n%p; n=n*n%p; k>>=1; }

3. inv（$\color{red}\star$ 质数）

   $\text{inv}(x)=x^{mod-2}\ \ \color{red}\text{(mod is a prime)}$

4. Dijkstra

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

   struct edge{ int v,w; }; struct node{ int x,d; friend bool operator < (node tmp_x,node tmp_y){ return tmp_x.d>tmp_y.d; } }; vector<edge>e[100001]; int dis[100001],vis[100001]; priority_queue<node>q; void dijkstra(int n,int s){ memset(dis,0x3f,sizeof(dis)); while(!q.empty())q.pop(); q.push({s,0}); dis[s]=0; while(!q.empty()){ int now=q.top().x; q.pop(); if(!vis[now]){ vis[now]=1; for(auto ed:e[now]){ int v=ed.v; int w=ed.w; if(dis[v]>dis[now]+w){ dis[v]=dis[now]+w; q.push({v,dis[v]}); } } } } }

5. SPFA

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

   struct edge{ int v,w; }; struct node{ int x,d; }; vector<edge>G[200005]; queue<int>q; int dis[200005]; int vis[200005]; int tot[200005]; bool spfa(){ memset(dis,0x3f,sizeof(dis)); memset(tot,0,sizeof(tot)); while(!q.empty())q.pop(); q.push(1); dis[1]=0; vis[1]=1; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(auto i:G[u]){ if(dis[i.v]>dis[u]+i.w){ dis[i.v]=dis[u]+i.w; tot[i.v]=tot[u]+1; if(tot[i.v]>=n){ return true; } q.push(i.v); vis[i.v]=1; } } } return false; }

6. Kruskal

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

   //不要忘记并查集初始化!!! #define int long long int n,m; struct edge{ int u,v,w; }G[1000001]; int fa[1000001]; int find(int x){ if(fa[x]!=x)fa[x]=find(fa[x]); return fa[x]; } bool cmp(edge _1,edge _2){ return _1.w<_2.w; } int Kruskal(){ int ans=0,tot=0; for(int i=1;i<=m;i++){ int fx=find(G[i].u); int fy=find(G[i].v); if(fx!=fy){ fa[fx]=fy; ans+=G[i].w; tot++; if(tot==n-1){ return ans; } } } return -1; } signed main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>G[i].u>>G[i].v>>G[i].w; } for(int i=1;i<=n;i++){ fa[i]=i; } sort(G+1,G+m+1,cmp); int tmp=Kruskal(); if(tmp==-1)cout<<"orz"<<endl; else cout<<tmp<<endl; return 0; }