轻保研推出了VIP全流程辅导班，专注为大三的同学走好“保研最后一步”，同时为大一大二的同学提供了先人一步的机会，关注轻保研，回复【VIP圆梦班】了解VIP圆梦班的详细概况～
欢迎来到【研路导航】 栏目！在这里，我们汇集了各种实用的保研干货，包括面试技巧、时间规划、备考方法等。这里不仅有详细的策略分享，还有经验丰富的专家和学长学姐们为你解读和分析每个关键步骤。无论你是刚刚起步还是即将面临保研挑战， '研路导航' 将成为你的贴心顾问和可靠指南，助你在保研之路上游刃有余。
轻保研
研路导航
保研机试技巧
写在前面
今天我们来解析一下 2018 年北航的复试上机试题。希望能帮助大家更好地理解和应对类似的题目。
01
二维空间线段连通问题
01
题目
在二维空间中给定一定数量的线段，线段的右端点的横坐标必然比左端点的横坐标大。输入 n（n < 10000），表示一共有 n 条线段。之后输入 n 行，每一行依次输入左端点的横、纵坐标，右端点的横、纵坐标；一些线段可以连在一起，规定连接的规则只能是一条线段的左端点和另一条线段的右端点相连。要求输出连在一起的大线段最多有多少条线段，以及最大线段起点（左端点）的横、纵坐标。输入的数据规模不会超过 int 型变量范围。
02
代码及解析
这道题可以使用贪心算法解决。关键在于按起点（左端点）的横坐标排序，然后递归枚举每条线段来判断能连接的线段数。
Step 1: 定义数据结构和变量
#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constint maxn = 10010; // 定义最大线段数量int cnt[maxn], temp = 0; // cnt数组用于存储每个线段的连通数量，temp用于临时存储连通数量int n, s, t; // n为线段数量，s和t为暂存变量structline {int sx, sy, tx, ty; // 定义线段的起点和终点坐标}l[maxn];
在这部分代码中，我们定义了一些全局变量和一个 line 结构体来存储每个线段的信息。cnt 数组用于存储每个线段的连通数量。
Step 2: 检查线段是否连通
voidcheck(int i, int now){for(int j = now + 1; j < n; j++) {if(l[j].sx == l[now].tx && l[j].sy == l[now].ty) { // 若此时重合temp++;check(i, j);temp--;} elseif(l[j].sx > l[now].tx) { // 因已按横坐标排序，此句用于加速判断，可以不写return;}}if(temp > cnt[i]) {cnt[i] = temp;}return;}
这个 check 函数用于检查从当前线段 now 开始的最大连通线段数量。通过递归检查每一个可能的连接线段。
Step 3: 比较函数用于排序
boolcmp(line a, line b){return a.sx < b.sx; // 按起点横坐标从小到大排序}
cmp 函数用于对线段数组进行排序，以便按起点的横坐标从小到大进行处理。
Step 4: 主函数
intmain(){scanf("%d", &n);for(int i = 0; i < n; i++) {scanf("%d%d%d%d", &l[i].sx, &l[i].sy, &l[i].tx, &l[i].ty);}sort(l, l + n, cmp); // 对所有线段按起点横坐标从小到大排序memset(cnt, 0, sizeof(cnt));for(int i = 0; i < n; i++) {check(i, i);}int MAX = -1, num;for(int i = 0; i < n; i++) {if(cnt[i] > MAX) {MAX = cnt[i];num = i;}}printf("%d %d %d\n", MAX + 1, l[num].sx, l[num].sy);return0;}
主函数中，首先读取输入的线段信息，然后进行排序。接着调用 check 函数对每个线段进行检查，最后找到最大连通线段数量并输出结果。
03
测试用例
输入：
11223
输出：
112输入：
41223233434412356
输出：
31202
三叉树最稳定节点问题
01
题目
燕子会将巢穴建立在最稳定的地方，对于三叉树而言，一个结点的子分支越多越稳定。输入 n（n < 10000），之后输入 n 行，每一行输入 4 个数字，分别为根节点，和其左孩子、中孩子、右孩子（确保每个根已经在之前出现过）的节点编号。求前序遍历（根，左，中，右）中子分支最多而且深度最深（高度最低）的节点编号，以及第几次遍历到该节点。若有多个满足题目要求的结点，取最先遍历到的结点。若输入的孩子节点编号为-1，则代表不存在此孩子分支。输入的数据规模不会超过 int 型变量范围。
02
代码解析
这道题主要是考察三叉树的建树和前序遍历。我们可以通过 map 来记录每个节点的指针，并在遍历过程中记录最大子分支数和最大深度。
Step 1: 定义数据结构和变量
#include<cstdio>#include<map>usingnamespacestd;constint maxn = 10010;int n, num, time, numtime, dmax = -1, cntmax = -1;structnode {int data, depth;node *lchild, *mchild, *rchild;};map<int, node*> m;
这部分代码中，我们定义了必要的全局变量和一个 node 结构体来表示三叉树的节点。使用 map 来建立节点编号与节点指针的映射关系。
Step 2: 创建新节点
node* newnode(int x){if(x == -1) {returnNULL;}node* root = new node;root->data = x;root->lchild = NULL;root->mchild = NULL;root->rchild = NULL;return root;}
newnode 函数用于创建新节点。如果输入值为 -1，则返回空指针。
Step 3: 前序遍历函数
voidpreOrder(node* root, int d){if(root == NULL) {return;}root->depth = d;time++;int cnt = 0;if(root->lchild != NULL) cnt++;if(root->mchild != NULL) cnt++;if(root->rchild != NULL) cnt++;if(cnt >= cntmax && d > dmax) {dmax = d;cntmax = cnt;num = root->data;numtime = time;}preOrder(root->lchild, d + 1);preOrder(root->mchild, d + 1);preOrder(root->rchild, d + 1);}
preOrder 函数进行前序遍历，同时记录满足条件的节点信息，包括子分支数量和遍历次数。
Step 4: 主函数
intmain(){scanf("%d", &n);int n1, n2, n3, n4;node* root;for(int i = 0; i < n; i++) {scanf("%d %d %d %d", &n1, &n2, &n3, &n4);if(i == 0) {root = newnode(n1);m[n1] = root;}node* rtemp = m[n1];rtemp->lchild = newnode(n2);rtemp->mchild = newnode(n3);rtemp->rchild = newnode(n4);m[n2] = rtemp->lchild;m[n3] = rtemp->mchild;m[n4] = rtemp->rchild;}preOrder(root, 1);printf("%d %d\n", num, numtime);return0;}
在主函数中，我们根据输入数据构建三叉树，并调用 preOrder 函数进行前序遍历。最终输出满足条件的节点编号及其第一次被遍历到的次数。
03
测试用例
输入：
2202-17764-1
输出：
73输入：
4109-17965-17-131111-114-1
输出：
9204
机试技巧分享
1、提前练习：熟悉常见的数据结构和算法，如数组、链表、栈、队列、树、图、排序和搜索算法等。通过刷题网站（如LeetCode、牛客网）进行系统练习。
2、时间管理：在考场上，合理分配时间非常重要。遇到难题时，不要纠结太久，尽快进入下一题，确保尽可能多地完成题目。
3、代码风格：保持代码简洁，变量命名清晰，注释适当，方便自己检查和调试。
4、调试技巧：养成良好的调试习惯，利用打印输出或调试器找出问题所在，特别是处理边界情况时要小心。
5、复查代码：写完代码后，务必进行复查，检查是否有漏掉的情况，特别是边界条件的处理是否完备。
写在最后
机试题目往往需要我们在短时间内完成高效的代码编写和优化。通过掌握和练习经典算法，我们可以在保研机试中占据优势。在此过程中，注重代码的规范性和细节处理，才能确保在关键时刻发挥出最佳水平。希望今天的分享对大家有所帮助，祝大家在保研路上顺利！
以上就是保研机试的技巧分享，想要获取更多保研干货，可以看看我们新推出的《轻保研·一步到位资料包》！
7 大核心资料包，全方位助力保研成功！
全面覆盖：
1、保研理念指南：从基础到高阶，全面解析保研流程和时间节点。
2、一站式备考宝典：专业课复习资料、常见面试题库，备考无忧。
3、英语口语大师手册：口语技巧、实战策略与题库示例，轻松应对英语面试。
4、前辈经验秘籍：100+位学长学姐的亲身经验和成功心得，一手掌握。
5、保研面试共题攻略：院校专业问题详解，实战计划与答题技巧，面试无惧。
6、文书模板框架：个人陈述、简历和文书模板，完美呈现自我。
7、机试知识模板：ACM模板、机械技巧和算法经典，让你脱颖而出。
突破备考难关，拿下保研offer！
在公众号后台回复【一步到位资料包】或者扫码上方二维码领取《轻保研·一步到位资料包》，一研为定！