CSP-J复赛准备 模板题

文章目录

CSP-J复赛准备 模板题最小生成树单源最短路径链式前向星堆优化 并查集树状数组-点修改树状数组-区间修改线性筛简单DP01背包完全背包高精度加高精度减二叉建树求二叉树先序

整理了一些有点难度的常用板子，希望 RP++

最小生成树

#include<bits/stdc++.h> using namespace std; const int MAX_M = 200010; const int MAX_NODE = 5010; struct s{ int a; int b; int z; } con[MAX_M]; int father[MAX_NODE]; bool vis[MAX_NODE]; bool cmp(s a, s b){ return a.z<b.z; } int find_root(int x) { if(father[x]!=-1) { return father[x] = find_root(father[x]); } return x; } /* * 1: success * 0: fail */ int union_(int x, int y) { int x_root = find_root(x); int y_root = find_root(y); if(x_root!=y_root) { father[y_root] = x_root; return 1; } return 0; } int main() { memset(father, -1, sizeof(father)); int m, n, x, y, z, ans = 0; cin>>n>>m; for(int i=0; i<m; i++) { cin>>x>>y>>z; con[i].a = x; con[i].b = y; con[i].z = z; } sort(con, con+m, cmp); for(int i=0; i<m; i++) { if(union_(con[i].a, con[i].b)) { vis[con[i].a] = true; vis[con[i].b] = true; ans += con[i].z; } } for(int i=1; i<=n; i++) { if(!vis[i]) { cout<<"orz"<<endl; return 0; } } cout<<ans<<endl; return 0; }

单源最短路径

链式前向星

#include<bits/stdc++.h> using namespace std; const int MAXN = 10001; const int MAXM = 500001; const int INF = 2147483647; struct edge{ int from; int to; int w; int next; }; edge e[MAXM]; struct node{ int w; int id; friend bool operator <(const node& a, const node& b) { return a.w>b.w; } }; int cnt = 0; int head[MAXN], vis[MAXN], m, n, s; long long dis[MAXN]; void add(int from, int to, int w) { e[++cnt].from = from; e[cnt].to = to; e[cnt].w = w; e[cnt].next = head[from]; head[from] = cnt;//head指from点的所有边 } priority_queue<node> q; void dijkstra(int s) { for(int i=1;i<=n;i++) { dis[i]=INF; } dis[s]=0;//赋初值 q.push((node){0,s}); while(!q.empty()) { node x=q.top(); q.pop(); int u=x.id; if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(dis[v]>dis[u]+e[i].w) { dis[v]=dis[u]+e[i].w; q.push((node){dis[v],v}); } } } } void printAns() { for(int i=1; i<=n; i++) {//从1开始 cout<<dis[i]<<" "; } cout<<endl; } int main() { cin>>n>>m>>s; int x, y, z; for(int i=0; i<m; i++) { cin>>x>>y>>z; add(x, y, z); } dijkstra(s); printAns(); return 0; }

堆优化

#include<bits/stdc++.h> using namespace std; /*我也不知道为什么用英文注释*/ const int maxn = 100010;//arr size too small will cause RE(seg fault) typedef unsigned long long ull; struct Edge{ int from; int to; ull w; }; struct Node{ int n; ull w; friend bool operator < (const Node& a, const Node& b) { return a.w>b.w; } }; int n, m, s = 1; ull dis[maxn+1]; vector<Edge> edges; vector<int > head[maxn]; void addEdge(int from, int to, ull w) { edges.push_back((Edge){from, to, w}); head[from].push_back(edges.size()-1); } priority_queue<Node> pq; void dijsktra(int start) { for(int i=1; i<=n; i++) { dis[i] = 1e10; } dis[start] = 0; pq.push((Node){start, 0}); while(!pq.empty()) { Node temp = pq.top();pq.pop(); int n = temp.n; ull w = temp.w; if(w!=dis[n]) { continue; } for(int i=0; i<head[n].size(); i++) { Edge& now = edges[head[n][i]]; if(dis[now.to]>dis[now.from]+now.w) { dis[now.to] = dis[now.from] + now.w; pq.push((Node){now.to, dis[now.to]});//it should update only at the time it needed } } } } void print_ans() { for(int i=1; i<=n; i++) { cout<<dis[i]<<" "; } cout<<endl; } int main() { cin>>n>>m>>s; int from_, to_; ull w; for(int i=0; i<m; i++) { cin>>from_>>to_>>w; addEdge(from_, to_, w); //addEdge(to_, from_, w); } dijsktra(s); print_ans(); return 0; }

并查集

#include<iostream> #include<cstring> using namespace std; const int maxn = 10010; int father[maxn] ; void init() { memset(father, -1, sizeof(father)); } int find_father(int x) { if(father[x]==-1) { return x; } return father[x] = find_father(father[x]); } void union_(int x, int y) { int x_root = find_father(x); int y_root = find_father(y); if(x_root!=y_root) father[x_root] = y_root; } int main() { init(); int m, n, x, y, z; int x_r=0, y_r=0; cin>>n>>m; for(int i=0; i<m; i++) { cin>>z>>x>>y; if(z==1) union_(x, y); else { x_r = find_father(x); y_r = find_father(y); if(x_r==y_r) cout<<"Y"<<endl; else cout<<"N"<<endl; } } return 0; }

树状数组-点修改

#include<iostream> using namespace std; const int maxn = 5000000; int d[maxn] , n; int lowbit(int x) { return x&(-x); } int query(int x) {/*Query from a[x] + ... + a[y]*/ register int sum = 0; while(x) { sum += d[x]; x -= lowbit(x); } return sum; } void modify(int x, int v) {/*Add v y a[x]*/ while(x<=n) { d[x] += v; x += lowbit(x); } } int main(int argc, char const *argv[]) { #ifdef ONLINE_JUDGE //freopen("test.in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); //debug stuff int m, temp; cin>>n>>m; for(int i=1; i<=n; i++) { cin>>temp; modify(i, temp);//cout<<temp<<endl; } int option, x, y; for(int i=0; i<m; i++) { cin>>option>>x>>y; if(option==1) modify(x, y); else if(option==2) cout<<query(y) - query(x-1)<<endl; } return 0; }

树状数组-区间修改

#include<iostream> using namespace std; /*这是模板， 于ubuntu bash生成*/ const int maxn = 500000 + 10000; int d[maxn], n, m; int lowbit(int x) { return x&(-x); } int query(int x) {/*Query from a[x] + ... + a[y]*/ register int sum = 0; while(x) { sum += d[x]; x -= lowbit(x); } return sum; } void modify(int x, int v) {/*Add v y a[x]*/ while(x<=n) { d[x] += v; x += lowbit(x); } } int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE //freopen("test.in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>n>>m; int temp, temp2 = 0, option, l, r, x; for(int i=1; i<=n; i++) cin>>temp, modify(i, temp - temp2), temp2 = temp; for(int i=1; i<=m; i++) { cin>>option; if(option==1) { cin>>l>>r>>x; modify(l, x); modify(r+1, -x); } else { cin>>x; cout<<query(x)<<endl; } } return 0; }

线性筛

#include<iostream> //const int maxn = 100000005;//垃圾数组，耗我青春 using namespace std; int n, m; int prime[1000000];//这里不用开大 bool noprime[100000005];//省空间 int main() { cin>>n>>m; //cout<<m; noprime[0] = noprime[1] = true; for(int i=2; i<=n; i++) { if(!noprime[i]) { prime[++prime[0]] = i; } for(int j=1; j<=prime[0] && prime[j]*i<=n; j++) {//prime[j]*i防越界 noprime[i*prime[j]] = true; if(i%prime[j]==0) break; } } int temp; for(int i=0; i<m; i++) { cin>>temp; if(noprime[temp] ) cout<<"No"<<endl; else cout<<"Yes"<<endl; } return 0; }

简单DP

#include<iostream> using namespace std; const int maxm = 210; const int maxn = 210; int m, n, f[maxm][maxn]; int max3(int a, int b, int c) { return max(max(a, b), c); } int main() { cin>>m>>n; int tmp; for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { cin>>tmp; f[i][j] = max3(f[i-1][j-1], f[i-1][j], f[i-1][j+1]) + tmp; /*他吃东西有一个习惯——只吃自己前方或左前方或右前方的盘中的食物*/ } } cout<<max3(f[m][n/2], f[m][n/2+1], f[m][n/2+2])<<endl;/*瞎*/ return 0; }

01背包

#include<iostream> using namespace std; const int MAXM = 105; const int MAXT = 1005; int v[MAXM], w[MAXM], f[MAXM][MAXT]; int main(){ int t, m; /*Input*/ cin>>t>>m; for(int i=1; i<=m; i++) { cin>>w[i]>>v[i]; } /*Find Answer*/ for(int i=1; i<=m; i++) {/*第i种草药*/ for(int j=t; j>0; j--) {/*背包容量j*/ if(w[i]<=j) {/*能装下*/ f[i][j] = max(f[i-1][j], f[i-1][j-w[i]]+v[i]); } else {/*装不下*/ f[i][j] = f[i-1][j]; } } } cout<<f[m][t]<<endl; return 0; }

完全背包

#include<iostream> using namespace std; /*完全背包*/ const int maxm = 233333;//数组开小了怎么行 int t, m, f[maxm]; int main() { cin>>t>>m; int w, v; for(int i=1; i<=m; i++){ cin>>w>>v; for(int j=w; j<=t; j++){ f[j] = max(f[j], f[j-w]+v); } } cout<<f[t]<<endl; return 0; }

高精度加

#include<iostream> #include<cstring> using namespace std; const int maxn = 510; char a[maxn], b[maxn]; int a2[maxn], b2[maxn], c2[maxn]; int main() { cin>>a; cin>>b; int strlena = strlen(a); int strlenb = strlen(b); int i; for(i=0; i<strlena; i++) { a2[i] = a[strlena - i - 1]-'0'; } for(i=0; i<strlenb; i++) { b2[i] = b[strlenb - i - 1]-'0'; } //for(i=0; i<strlena; i++) /* for(i=0; i<strlena; i++) { cout<<a2[i]; }cout<<endl; for(i=0; i<strlenb; i++) { cout<<b2[i]; }cout<<endl;*/ int tot = max(strlena, strlenb); int y = 0; for(i=0; i<tot; i++) { c2[i] = a2[i] + b2[i] + y; y = c2[i] / 10; c2[i] %= 10; } if(y!=0) cout<<y; for(i=tot-1; i>=0; i--) { cout<<c2[i]; }cout<<endl; return 0; }

高精度减

#include<iostream> #include<cstring> using namespace std; const int maxn = 10100; char a[maxn], b[maxn]; int a2[maxn], b2[maxn], c2[maxn]; int cmp() { int i; if(strlen(a)>strlen(b)) { return 2; } else if(strlen(b)>strlen(a)) { return 1; } else { for(i=0; i<strlen(a); i++) { if(a[i]-'0'<b[i]-'0') { return 1; } if(a[i]-'0'>b[i]-'0') { return 2; } } return 0; } return 0; } void swapab() { int i; for(i=0; i<strlen(a); i++) { c2[i] = a2[i]; } memset(a2, 0, sizeof a2); for(i=0; i<strlen(b); i++) { a2[i] = b2[i]; } memset(b2, 0, sizeof b2); for(i=0; i<strlen(a); i++) { b2[i] = c2[i]; } memset(c2, 0, sizeof c2); } int main() { cin>>a; cin>>b; int strlena = strlen(a); int strlenb = strlen(b); int i; for(i=0; i<strlena; i++) { a2[i] = a[strlena - i - 1] - '0'; } for(i=0; i<strlenb; i++) { b2[i] = b[strlenb - i - 1] - '0'; } bool isFushu = false; switch(cmp()) { case 1: isFushu = true; swapab(); swap(strlena, strlenb); break; case 0: cout<<0<<endl; return 0; case 2: isFushu = false; break; } if(isFushu) cout<<'-'; /* for(i=0; i<strlena; i++) { cout<<a2[i]; }cout<<endl; for(i=0; i<strlenb; i++) { cout<<b2[i]; }cout<<endl; */ int tot = max(strlena, strlenb); int jiewei = 0; for(i=0; i<tot; i++) { c2[i] = a2[i] - b2[i] - jiewei; //cout<<"c2["<<i<<"] is "<<c2[i]<<endl; if(c2[i]<0) { jiewei = 1; c2[i] = 10 + c2[i]; // cout<<"And now it's "<<c2[i]<<endl; } else { jiewei = 0; } } bool notOK = true; for(i=tot-1; i>=0; i--) { if(notOK) { if(c2[i]!=0) { notOK = false; } else continue; } cout<<c2[i]; } cout<<endl; return 0; }

二叉建树

#include<iostream> #include<cmath> #include<cstdio> using namespace std; const char NULL_SUB = '*'; const int maxn = 2049;//数组开大 char tree[maxn]; int string_[maxn], n; void build_tree(int root, int from, int to) { //cout<<"building "<<root<<" from "<<from<<" to "<<to<<endl; int left_subtree = 2 * root; int right_subtree = 2 * root + 1; int mid = (from + to) / 2; if(from==to) { switch(string_[from]) { case 0: tree[root] = 'B'; break; case 1: tree[root] = 'I'; break; } tree[left_subtree] = NULL_SUB; tree[right_subtree] = NULL_SUB; return; } else{ build_tree(left_subtree, from, mid); build_tree(right_subtree, mid + 1, to); if(tree[left_subtree]==tree[right_subtree]) { if(tree[left_subtree]=='B') { tree[root] = 'B'; } else if(tree[left_subtree]=='I'){ tree[root] = 'I'; } else { tree[root] = 'F'; } } else { tree[root] = 'F'; } } } void print_ans(int root) { if(tree[root]!=NULL_SUB) { //cout<<"printing "<<root<<endl; int left_subtree = root * 2; int right_subtree = root * 2 + 1; print_ans(left_subtree); print_ans(right_subtree); putchar(tree[root]); } } int main() { cin>>n; n = pow(2, n); char temp; for(int i=0; i<n; i++) { //cin>>string_[i]; cin>>temp; string_[i] = temp - '0'; } build_tree(1, 0, n-1); print_ans(1); putchar('\n'); return 0; }

求二叉树先序

#include<iostream> #include<cstring> using namespace std; string zx, hx;//中序便利，后序便利 int tree[1000]; void build(int root, int rootnum, int from, int to);//建树 中序便利（from， to）， 根为 rootnum 存储在root int findRoot(int l, int r);//在 后序便利 中 寻找 中序便利 (l, r)子树中的根 void xxbl(int root);//输出先序便利 int main() { memset(tree, -1, sizeof(tree)); cin>>zx>>hx; build(1, findRoot(0, zx.length()-1), 0, zx.length()-1); //for(int i=0; i<100; i++) { // cout<<tree[i]<<" "; //} xxbl(1); cout<<endl; return 0; } /** * 函数 */ void build(int root, int rootnum, int from, int to) { //cout<<"build "<<from<<to<<endl; //cout<<"root"<<rootnum<<endl; tree[root] = rootnum; int lchild = root * 2; int rchild = root * 2 + 1; //if(rootnum == from + 1 || rootnum == to -1){ if(rootnum == from+1) { tree[lchild] = from; } else { int nextrootnum = findRoot(from, rootnum-1); if(nextrootnum!=-1) build(lchild, nextrootnum, from, rootnum-1); } if(rootnum == to-1) { tree[rchild] = to; } else { int nextrootnum = findRoot(rootnum+1, to); if(nextrootnum!=-1) build(rchild, nextrootnum, rootnum+1, to); } // } } int findRoot(int l, int r) { int root = -1; int maxa = -10; for(int i=l; i<=r; i++) { if((int)hx.find(zx[i])>maxa) { maxa = (int)hx.find(zx[i]); root = i; } } return root; } void xxbl(int root) { int lchild = root * 2; int rchild = root * 2 + 1; if(tree[root]!=-1) { cout<<zx[tree[root]]; }else { return; } xxbl(lchild); xxbl(rchild); }