算法竞赛经典代码集锦

1、排列论文#includebits/stdc.h using namespace std; const int N105; vectorintg[N]; int a[N]; int n,m; int flag; int topSort(){ queueintq; for(int i1;in;i){ if(a[i]0){ q.push(i); } } int cnt0; flag1; while(!q.empty()){ int tq.front(); q.pop(); cnt; if(!q.empty())flag2; for(int i0;ig[t].size();i){ int xg[t][i]; a[x]--; if(a[x]0)q.push(x); } } if(cntn)flag0; return flag; } int main(){ while(cinnm){ for(int i1;in;i){ g[i].clear(); a[i]0; } for(int i1;im;i){ int u,v; cinuv; a[v]; g[u].push_back(v); } int resulttopSort(); if(result0)cout0\n; else if(result1)cout1\n; else if(result2)cout2\n; } return 0; }2、十进制到二进制的转换#includebits/stdc.h using namespace std; int main(){ int n; cinn; if(n0){ cout0endl; return 0; } int a[45]; int idx0; while(n0){ a[idx]n%2; nn/2; idx; } for(int iidx-1;i0;i--){ couta[i]; } coutendl; return 0; }3、周末舞会#includebits/stdc.h using namespace std; int main(){ int boy,girl,k; cinboygirlk; queueintb_q,g_q; for(int i1;iboy;i){ b_q.push(i); } for(int i1;igirl;i){ g_q.push(i); } while(k--){ int x,y; xb_q.front(); b_q.pop(); yg_q.front(); g_q.pop(); coutx yendl; b_q.push(x),g_q.push(y); } return 0; }4、哥德巴赫猜想#includebits/stdc.h using namespace std; bool ss(int x){ if(x2)return false; for(int i2;i*ix;i){ if(x%i0){ return false; } } return true; } int main(){ int n,ans; while(cinn){ ans0; if(n0)break; for(int i2;in/2;i){ if(ss(i)ss(n-i)){ ans; } } coutansendl; } return 0; }5、查找二叉树#includebits/stdc.h using namespace std; const int N105; struct node{ int value; int left; int right; }a[N]; int n; int target; int cnt0; int result-1; void zhongxu(int idx){ if(idx0)return; zhongxu(a[idx].left); cnt; if(a[idx].valuetarget){ resultcnt; } zhongxu(a[idx].right); } int main(){ cinn; cintarget; for(int i1;in;i){ cina[i].valuea[i].lefta[i].right; } zhongxu(1); coutresultendl; return 0; }6、图的遍历------广度优先搜索#include bits/stdc.h using namespace std; const int MAXN 55; int vis[MAXN]; int a[MAXN][MAXN]; queueint q; // 广度优先搜索函数 void bfs(int n) { q.push(0); vis[0] 1; cout 0 ; while (!q.empty()) { int x q.front(); q.pop(); for (int i 0; i n; i) { if (a[x][i] 1 vis[i] 0) { vis[i] 1; q.push(i); cout i ; } } } } int main() { int n; cin n; for (int i 0; i n; i) { for (int j 0; j n; j) { cin a[i][j]; } } bfs(n); return 0; }7、图的遍历------深度优先搜索#includebits/stdc.h using namespace std; int vis[55]; int a[55][55]; int n; void dfs(int k){ vis[k]1; coutk ; for(int i0;in;i){ if(vis[i]0a[k][i]1)dfs(i); } } int main(){ cinn; for(int i0;in;i){ for(int j0;jn;j){ cina[i][j]; } } dfs(0); return 0; }8、FBI树二叉树#include bits/stdc.h using namespace std; int a[204810]; int len; // 构建FBI树 void buildTree(int root) { if(rootlen)return; buildTree(2*root); buildTree(2*root1); if(a[2*root]1a[2*root1]1)a[root] 1; else if(a[2*root]0a[2*root1]0)a[root]0; else a[root]2; } // 后序遍历FBI树 void dfsTree(int root) { if(root2*len)return; dfsTree(2*root); dfsTree(2*root1); if (a[root]1)coutI; else if(a[root]0)coutB; else coutF; } int main() { int n; string str; cinn; cinstr; len1n; // 将输入的字符串存储到数组中 for(int ilen;i2*len-1;i){ a[i]str[i-len]-0; } buildTree(1); dfsTree(1); return 0; }9、图着色问题#includebits/stdc.h using namespace std; const int N510,MN*N; int color[N]; vectorint g[M]; int v,m,k,n; void add(int a,int b){ g[a].push_back(b); g[b].push_back(a); } int judge(int cnt){ if(cnt!k)return 0; for(int i1;iv;i){ for(int j0;jg[i].size();j){ int tg[i][j]; if(color[i]color[t])return 0; } } return 1; } int main(){ cinvmk; while(m--){ int a,b; cinab; add(a,b),add(b,a); } cinn; for(int i0;in;i){ setint se;//set具有去重功能 for(int j1;jv;j){ cincolor[j]; se.insert(color[j]); } if(judge(se.size()))coutYesendl; else coutNoendl; } return 0; }10、地下迷宫探索#include bits/stdc.h using namespace std; const int N 1005; int vis[N]; int g[N][N]; stackint stk; int n, m, src; // 深度优先搜索函数 void dfs(int k) { vis[k] 1; if (vis[src]) cout k; else cout k; stk.push(k); for (int i 1; i n; i) { if (!vis[i] g[k][i] 1) { cout ; dfs(i); } } stk.pop(); if(!stk.empty()){ cout stk.top(); } } int main() { memset(vis, 0, sizeof(vis)); cin n m src; // n代表节点数m代表边数src代表初末位置 int s, d; for (int i 1; i m; i) { cin s d; g[s][d] g[d][s] 1; } dfs(src); bool connected true; for (int i 1; i n; i) { if (!vis[i]) { connected false; break; } } if (!connected) cout 0; return 0; }11、寻宝图#includebits/stdc.h using namespace std; const int N1e51; int n,m,flag0; string map_m[N]; int cnt0,cns0;//cnt代表岛屿的数量cns代表宝藏的数量 int dx[4]{1,0,-1,0},dy[4]{0,1,0,-1}; void dfs(int x,int y){ if(x0||xn||y0||ym||map_m[x][y]0)return; if(map_m[x][y]1){ flag1; } map_m[x][y]0; for(int i0;i4;i){ dfs(xdx[i],ydy[i]); } } int main(){ cinnm; for(int i0;in;i)cinmap_m[i]; for(int i0;in;i){ for(int j0;jm;j){ if(map_m[i][j]0){ cnt; flag0; dfs(i,j);//查看是否有宝藏 if(flag)cns; } } } coutcnt cns; return 0; }12、信使#includebits/stdc.h using namespace std; const int N105; int n,m; int g[N][N]; int dist[N]; bool st[N]; const int INF0x3f3f3f3f; int dij(){ memset(dist,0x3f,sizeof dist); dist[1]0; for(int i1;in;i){ int t0; for(int j1;jn;j){ if(!st[j]dist[j]dist[t]){ tj; } } st[t]true; for(int k1;kn;k){ dist[k]min(dist[k],dist[t]g[t][k]); } } int res0; for(int i1;in;i){ if(dist[i]INF) return -1; resmax(res,dist[i]); } return res; } int main(){ cinnm; memset(g,0x3f,sizeof g); for(int i1;in;i){ g[i][i]0; } for(int i0;im;i){ int u,v,w; cinuvw; g[u][v]min(g[u][v],w); g[v][u]min(g[v][u],w); } coutdij()endl; return 0; }13、求先序排列后中求先#includebits/stdc.h using namespace std; struct node{ char value; node* left; node* right; node(char x):value(x),left(NULL),right(NULL){} }; //post表示后序idx表示中序 node* buildtree(string post, string idx){ if(post.empty() || idx.empty()) return NULL; // 后序遍历的最后一个字符是根节点 char rootv post.back(); node* root new node(rootv); // 在中序遍历中找到根节点的位置 int rootidx idx.find(rootv); // 分割中序遍历为左子树和右子树 string leftidx idx.substr(0, rootidx); string rightidx idx.substr(rootidx 1); // 分割后序遍历为左子树和右子树 string leftpost post.substr(0, leftidx.length()); string rightpost post.substr(leftidx.length(), rightidx.length()); // 修正递归调用的参数顺序(后序, 中序) root-left buildtree(leftpost, leftidx); root-right buildtree(rightpost, rightidx); return root; } void xianxu(node* root){ if(root NULL) return; //直接返回不返回值 cout root-value; xianxu(root-left); xianxu(root-right); } int main(){ string post, idx; // 修正变量名以反映实际用途 cin idx post; //先输入中序再输入后序 node* root buildtree(post, idx); xianxu(root); cout endl; return 0; }14、还原二叉树#includebits/stdc.h using namespace std; struct node{ char value; node* left; node* right; // 添加构造函数 node(char val) : value(val), left(NULL), right(NULL) {} }; int n; node* buildtree(string pre, string idx){ if(pre.empty() || idx.empty()){ return NULL; } char vroot pre[0]; node* root new node(vroot); int idxroot idx.find(vroot); string leftidx idx.substr(0, idxroot); string rightidx idx.substr(idxroot1); string leftpre pre.substr(1, leftidx.length()); string rightpre pre.substr(1 leftidx.length()); root-left buildtree(leftpre, leftidx); root-right buildtree(rightpre, rightidx); return root; } // 修正函数名和返回值类型 int treeHeight(node* root){ if(root NULL) return 0; int leftheight treeHeight(root-left); int rightheight treeHeight(root-right); return max(leftheight, rightheight) 1; } int main(){ cin n; string pre, idx; cin pre idx; node* root buildtree(pre, idx); // 构建二叉树 int h treeHeight(root); // 调用修正后的函数名 cout h endl; return 0; }15、求二叉树的叶子结点#includebits/stdc.h using namespace std; const int N1e35; char a[N]; int cnt0; string str; void dfs(int r){ if(a[2*r]!-1)dfs(2*r); couta[r]; if(a[2*r]-1a[2*r1]-1){ cnt; } if(a[2*r1]!-1){ dfs(2*r1); } } int main(){ cinstr; stackintst; st.push(1); for(int i0;istr.size();i){ int pst.top(); st.pop(); if(str[i]!#){ a[p]str[i]; st.push(2*p1); st.push(2*p); } else{ a[p]-1; } } dfs(1); cout\ncnt; return 0; }16、二叉树非叶子#includebits/stdc.h using namespace std; const int N105; struct node{ int value; int left; int right; }a[N]; int n; void xianxu(int idx){ if(idx0)return; couta[idx-1].value ; xianxu(a[idx-1].left); xianxu(a[idx-1].right); } int main(){ cinn; for(int i0;in;i){ cina[i].valuea[i].lefta[i].right; } for(int i0;in;i){ if(a[i].left!0a[i].right!0){ a[i].value1; } } xianxu(1); coutendl; return 0; }17.约瑟夫问题#includeiostream #includequeue using namespace std; int n,m; int main(){ cinnm; queueintq; for(int i1;in;i){ q.push(i); } int i1; while(!q.empty()){ if(im){ coutq.front() ; q.pop(); i1; } else{ q.push(q.front()); q.pop(); ii1; } } return 0; }18、二叉树求高度#includebits/stdc.h using namespace std; const int N105; struct node{ int data; int left; int right; }a[N]; int n; int dfs(int root){ if(root0)return 0; int h1dfs(a[root].left); int h2dfs(a[root].right); return max(h1,h2)1; } int main(){ cinn; for(int i1;in;i){ cina[i].dataa[i].lefta[i].right; } coutdfs(1); return 0; }19、完全二叉树的权值#includebits/stdc.h using namespace std; const int N1e55; int a[N]; int n,x; int main(){ int h0,nn0; cinn; for(int i1;in;i){ if(inn){ nnpow(2,h); h; } cinx; a[h]x; } int max_a0,maxh0; for(int i1;ih;i){ if(a[i]max_a){ max_aa[i]; maxhi; } } coutmaxhendl; return 0; }20、围圈报数#includebits/stdc.h using namespace std; int main(){ queueintcl; int n,m; cinnm; for(int i1;in;i){ cl.push(i); } while(!cl.empty()){ int x; for(int i1;im-1;i){ xcl.front(); cl.pop(); cl.push(x); } xcl.front(); cl.pop(); coutx ; } return 0; }21、走出迷宫#include iostream #include queue using namespace std; char a[105][105]; int b[105][105]; int n, m; struct Node { int r, c; int step; }; int dir[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 检查坐标是否在网格内 bool isValid(int r, int c) { return r 1 r n c 1 c m; } void bfs(int sr, int sc, int er, int ec) { queueNode dl; Node q, next; q.r sr; q.c sc; q.step 0; dl.push(q); b[q.r][q.c] 1; while (!dl.empty()) { q dl.front(); dl.pop(); if (q.r er q.c ec) { cout q.step endl; // 如果当前点是终点 return; } for (int i 0; i 4; i) { next.r q.r dir[i][0]; next.c q.c dir[i][1]; // 1可走 2未走过 3不出边界 if (a[next.r][next.c] . b[next.r][next.c] 0 isValid(next.r, next.c)) { next.step q.step 1; b[next.r][next.c] 1; dl.push(next); } } } cout No path found! endl; // 未找到路径 } int main() { int sr, sc, er, ec; cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; if (a[i][j] S) { sr i; sc j; } if (a[i][j] T) { er i; ec j; a[i][j] .; // 将终点状态记为可走 } } } bfs(sr, sc, er, ec); return 0; }