乐鑫科技提前批算法岗笔试
昨晚的题,两道编程第一道是求冰雹猜想收敛次数最大的数,一直以为有规律可找,后来发现其实收敛的很快,暴力求解就完事了。
第二道咋一看以为二叉树,后来发现就是一棵树,本质是求树上两个节点间的距离,所以bfs即可,求亲密距离时边权为1,求辈分距离时边权是父到子为1,子到父为-1。
第二题的AC代码:
#include <iostream> #include <cstdio> #include <vector> #include <queue> using namespace std; struct Node { int v, w; Node(int vv, int ww): v(vv), w(ww){} }; int main() { int n, p1, p2; cin >> n >> p1 >> p2; vector<vector<Node>> graph(n); int u, v; for (int i = 1; i < n; i++){ cin >> u >> v; graph[u].push_back(Node(v, 1)); graph[v].push_back(Node(u, -1)); } int qm = 0, bf = 0; queue<Node> que; que.push(Node(p1, 0)); vector<int> vis(n+1, 0); while (!que.empty()){ Node now = que.front(); que.pop(); if (now.v == p2){ qm = now.w; break; } if (vis[now.v]) continue; vis[now.v] = 1; for (int i = 0; i < graph[now.v].size(); i++) if (!vis[graph[now.v][i].v]) que.push(Node(graph[now.v][i].v, now.w+1)); } while (!que.empty()) que.pop(); vis.assign(n+1, 0); que.push(Node(p1, 0)); while (!que.empty()){ Node now = que.front(); que.pop(); if (now.v == p2){ bf = now.w; break; } if (vis[now.v]) continue; vis[now.v] = 1; for (int i = 0; i < graph[now.v].size(); i++) if (!vis[graph[now.v][i].v]) que.push(Node(graph[now.v][i].v, now.w+graph[now.v][i].w)); } cout << qm << " " << bf << endl; return 0; } /* 15 7 2 0 1 0 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 */