机试代码模板

进制转换

#include <iostream>
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>using namespace std;
string a="0123456789ABCDEF";
void d_to(int x,int m){if (x==0)return;d_to(x/m,m);cout<<a[x%m];}int main() {int x,m;cin>>x>>m;d_to(x,m);return 0;}

高精度加/乘法

#include <bits/stdc++.h>using namespace std;
int a[80], g[80], c[80];string add(string x, string y) {string temp;for (int i = 0; i < x.size(); ++i) {a[x.size() - i - 1] = x[i] - '0';}for (int i = 0; i < y.size(); ++i) {g[y.size() - i - 1] = y[i] - '0';}int ans = max(x.size(), y.size());for (int i = 0; i < ans; ++i) {c[i] += a[i] + g[i];c[i + 1] = c[i] / 10;c[i] %= 10;}ans++;if (c[ans - 1] == 0 && ans > 1)ans--;for (int i = 0; i < ans; ++i) {temp += to_string(c[ans - i - 1]);}memset(a, 0, sizeof(a));memset(g, 0, sizeof(g));memset(c, 0, sizeof(c));return temp;
}string mul(string x, string y) {string temp;for (int i = 0; i < x.size(); ++i) {a[x.size() - i - 1] = x[i] - '0';}for (int i = 0; i < y.size(); ++i) {g[y.size() - i - 1] = y[i] - '0';}int ans = max(x.size(), y.size());for (int i = 0; i < ans; ++i) {for (int j = 0; j < ans; ++j) {c[i + j] += a[i] * g[j];c[i + j + 1] += c[i + j] / 10;c[i + j] %= 10;}}int as = x.size() + y.size();while (c[as - 1] == 0 && as > 1)as--;for (int i = 0; i < as; ++i) {temp += to_string(c[as - i - 1]);}memset(a, 0, sizeof(a));memset(g, 0, sizeof(g));memset(c, 0, sizeof(c));return temp;
}int main() {int n;string s = "0";cin >> n;for (int i = 1; i <= n; ++i) {string jc = "1";for (int j = 1; j <= i; ++j) {string k = to_string(j);jc = mul(jc, k);}s = add(s, jc);}cout << s;
}

搜索

BFS

#include <iostream>
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <queue>using namespace std;
int a[100][100], v[100][100];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
struct point {int x;int y;int step;
};
queue<point> r;int main() {int n, m, startx, starty, p, q;cin >> n >> m;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> a[i][j];}}cin >> startx >> starty >> p >> q;// BFSpoint start;start.x = startx;start.y = starty;start.step = 0;r.push(start);v[startx][starty] = 1;int flag = 0;while (!r.empty()) {int x = r.front().x;int y = r.front().y;if (x == p && y == q) {flag = 1;cout << r.front().step;break;}for (int i = 0; i < 4; ++i) {int tx, ty;tx = x + dx[i];ty = y + dy[i];if (a[tx][ty] == 1 && v[tx][ty] == 0) {point temp;temp.x = tx;temp.y = ty;temp.step = r.front().step + 1;r.push(temp);v[tx][ty] = 1;}}r.pop();}if (flag==0){cout<<"No Answer";}return 0;}

DFS

#include <iostream>using namespace std;
int p, q;
int miN = 99999999;
int a[100][100];// 1是空地，2是障碍物
int v[100][100];//0表示未访问，1表示访问
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};void dfs(int x, int y, int step) {if (x == p && y == q) {if (step < miN)miN = step;return;}// 顺时针试探for (int i = 0; i < 4; ++i) {int tx, ty;tx = x + dx[i];ty = y + dy[i];if (a[tx][ty] == 1 && v[tx][ty] == 0) {v[tx][ty] = 1;dfs(tx, ty, step + 1);v[tx][ty] = 0;}}return;
}int main() {int m, n;int startx, starty;cin >> m >> n;for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {cin >> a[i][j];}}cin >> startx >> starty >> p >> q;v[startx][starty] = 1;dfs(startx, starty, 0);cout << miN;return 0;}

树

二叉树遍历

#include <iostream>
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>using namespace std;
typedef struct node {char data;struct node *lchild, *rchild;
} *BitTree;void CreateBitTree(BitTree &T) {char c;cin >> c;if (c == '0')T = NULL;else {T = new node;T->data = c;CreateBitTree(T->lchild);CreateBitTree(T->rchild);}
}void PreOrder(BitTree T) {if (T != NULL) {cout << T->data << ' ';PreOrder(T->lchild);PreOrder(T->rchild);}
}void InOrder(BitTree T) {if (T != NULL) {InOrder(T->lchild);cout << T->data << ' ';InOrder(T->rchild);}
}void PostOrder(BitTree T) {if (T != NULL) {PostOrder(T->lchild);PostOrder(T->rchild);cout << T->data << ' ';}
}int main() {BitTree T;CreateBitTree(T);cout << "前序遍历：";PreOrder(T);cout << endl;cout << "中序遍历：";InOrder(T);cout << endl;cout << "后序遍历：";PostOrder(T);
}

图

Dijkstra算法

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>#define inf 0x3f3f3f3f
using namespace std;
const int M = 1e4 + 10;
const int N = 1000 + 10;
int n, m, s;
int mp[N][N];
int dis[N], vis[N];
int pre[N];void init() {memset(mp, inf, sizeof(mp));
}void dijkstra(int s) {memset(dis, 0x3f, sizeof(dis));memset(vis, 0, sizeof(vis));dis[s] = 0;while (1) {int mini = 0, miN = inf;for (int i = 1; i <= n; ++i) {if (vis[i] == 0 && miN > dis[i]) {mini = i;miN = dis[i];}}if (mini == 0)break;vis[mini] = 1;for (int i = 1; i <= n; ++i) {if (vis[i] == 0 && dis[i] > dis[mini] + mp[mini][i]) {dis[i] = dis[mini] + mp[mini][i];pre[i]=mini;}}}
}void output(int z){if (z==0)return;output(pre[z]);cout<<z<<"->";
}int main() {init();cin >> n >> m >> s;for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;if (w < mp[u][v]) {mp[u][v] = mp[v][u] = w;}}dijkstra(s);cout<<dis[n]<<endl;for (int i = 1; i <= n; ++i) {output(i);cout<<endl;}
}

Kruskal算法

#include <iostream>using namespace std;const int maxn = 5005;struct node {int u, v, w;
} edge[200001];int cmp(node x, node y) {return x.w < y.w;
}int fa[maxn];int find(int x) {if (x == fa[x])return x;fa[x] = find(fa[x]);return fa[x];
}int main() {int N, M;cin >> N >> M; // N是结点，M是边for (int i = 0; i < M; ++i) {cin >> edge[i].u >> edge[i].v >> edge[i].w;}for (int i = 1; i <= N; ++i) {fa[i] = i;}int sum = 0;int total = 0;sort(edge, edge + M, cmp);for (int i = 0; i < M; ++i) {int fx = find(edge[i].u);int fy = find(edge[i].v);if (fx != fy) {fa[fx] = fy;sum += edge[i].w;total++;}}if (total < N - 1)cout << "orz";elsecout << sum;return 0;
}

动态规划

最长公共子序列(LCS)

#include <iostream>
#include <string>using namespace std;
const int MAX = 1000 + 10;
string s1, s2;
int f[MAX][MAX] = {0};
string ans;void LCS(int i, int j) {if (i == 0 || j == 0)return;if (s1[i - 1] == s2[j - 1]) {LCS(i - 1, j - 1);cout << s1[i - 1];} else if (f[i - 1][j] > f[i][j - 1]) {LCS(i - 1, j);} else {LCS(i, j - 1);}}int main() {cin >> s1 >> s2;int n = s1.size();int m = s2.size();for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (s1[i - 1] == s2[j - 1]) {f[i][j] = 1 + f[i - 1][j - 1];} else {f[i][j] = max(f[i - 1][j], f[i][j - 1]);}}}cout << f[n][m] << endl;LCS(n, m);return 0;
}

最长上升子序列(LIS)

#include <iostream>using namespace std;
const int MAX = 1000 + 10;
int a[MAX];
int dp[MAX];
int n;int LIS() {int ans = 0;for (int i = 1; i <= n; ++i) {dp[i] = 1;for (int j = 1; j < i; ++j) {if (a[j] < a[i]) {dp[i] = max(dp[i], dp[j] + 1);}}ans = max(ans, dp[i]);}return ans;
}int main() {cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}int res = LIS();cout << res;return 0;
}

KMP算法

#include <iostream>
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>using namespace std;
int Next[1000005];void getNext(char s[], int len) {int j = -1;Next[0] = -1;for (int i = 1; i < len; ++i) {while (j != -1 && s[i] != s[j + 1]) {j = Next[j];}if (s[i] == s[j + 1]) {j++;}Next[i] = j;}
}int KMP(char text[], char patten[]) {int n = strlen(text), m = strlen(patten);getNext(patten, m);int j = -1, ans = 0;for (int i = 0; i < n; ++i) {while (j != -1 && text[i] != patten[j + 1]) {j = Next[j];}if (text[i] == patten[j + 1]) {j++;}if (j == m - 1) {ans++;j = Next[j];}}return ans;
}int main() {char s1[1000005], s2[1000005];cin >> s1 >> s2;int a=KMP(s1, s2);cout<<a;
}