企业官网建设流程全解析

1. 2020华东师大机试概况与备考定位

1.1 这套题到底是什么水平

把“华东师范大学2020机试题解”这几个字甩到搜索引擎里，能翻出来的完整版本其实不多。我当年备考时为了找齐回忆版题目，论坛、群聊、各种网盘翻了个遍，最后发现一个规律：华师计算机相关专业的复试机试，难度一直控制得很稳定——四道题左右，三个小时，C/C++答题，前两题属于“认真学过就能写”的基础题，第三题开始上强度，最后一题需要一点算法思维和临场应变。整体氛围就是：不劝退，但也绝不让裸考的人轻松过关。

这篇博客我按回忆版整理出四道具有代表性的题目，完整给出思路、代码和易错点。不管你是第一年考还是二战，只要能把这几类题吃透，机试这一关基本就有底了。适合的人群很明确：正在准备华师计算机、软件工程等方向考研复试的同学，以及想了解高校机试出题风格、想找典型题练手的同学。

1.2 机试环境与提交前必须知道的事

华师机试一般使用在线评测系统，也就是传统的OJ页面，写代码、提交、看反馈，和平时刷题网站没本质区别。但有几个细节值得提前适应。

第一，编译器版本通常不会太新。C++11的特性不一定全支持，更别说C++17了。所以我写代码默认用最传统的C++98风格，数组放在全局区，头文件用<cstdio>、<cstring>、<algorithm>，这类老牌头文件最保险。auto、unordered_map这类东西能不用就不用，不是不能写，而是没必要在考场上赌环境。

第二，输入输出全部走标准输入输出，不搞文件读写。个别同学在本地IDE里习惯用文件重定向调试，提交前一定记得删掉freopen，不然OJ上直接判错。

第三，数据范围要养成“先看题再动手”的习惯。有的题n只有100，有的题n直接给到100000，这决定了你是用O(n^2)还是必须优化到O(nlogn)。我看到不少同学拿到题就闷头写，写完才发现超时，白费大量时间。

第四，多测样例一定要自己构造。OJ上给的样例通常很友好，但它只是帮你验证基本思路，不是保证AC的凭证。边界数据、最大数据、极端输入这些都得自己在脑子里过一遍。

2. 题目A：上台阶方案数——递推与递归的选择

2.1 题目描述与样例分析

这道题是典型的“递推入门题”，和华师历年机试第一题的风格非常吻合。

题目大意：一个楼梯共有n级台阶，每次可以跨1级或者2级，问从地面走到楼顶一共有多少种不同的走法。输入一个正整数n，输出方案数。n的范围大概是1到70。

举个例子，n=3时，一共有三种走法：1+1+1、1+2、2+1。这道题本质上是斐波那契数列的变形：走到第n级台阶的最后一步，要么是从第n-1级跨1级上来的，要么是从第n-2级跨2级上来的，所以走到第n级的方案数等于走到第n-1级的方案数加上走到第n-2级的方案数。

2.2 为什么推荐递推而不是递归

很多同学第一反应是写一个递归函数：f(n) = f(n-1) + f(n-2)。这个思路本身没错，但如果n给到70，直接递归会陷入指数级的重复计算，本地跑都要卡半天，更别说OJ限时了。换句话说，递归写法在n比较小的时候很优雅，在大数据下就是灾难。

正确做法是自底向上的递推，用一个数组从第1项开始一路算到第n项，时间复杂度是O(n)，任何数据量都轻松扛住。这也是机试里一个非常重要的思维转变：能递推就不要递归，能迭代就不要深搜，除非递归深度确实可控。

这里还要提一个n=70的隐藏考点：结果会非常大，早就超过int范围了。就算70级台阶，方案数大约是190392490709135，这是一个15位数，必须用long long类型存。用int的人会直接溢出变成负数，样例过了但提交就是WA。

2.3 参考代码

#include <cstdio> long long dp[75]; int main() { int n; scanf("%d", &n); dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } printf("%lld\n", dp[n]); return 0; }

这段代码只有几个关键点：dp[1]表示1级台阶有1种走法，dp[2]表示2级台阶有2种走法，从第3项开始循环往上推。n最小是1，所以数组从1开始用，不要浪费dp[0]的位置。

2.4 这道题最容易踩的坑

第一个坑是初始化。有人会把dp[0]设成1，然后从dp[2] = dp[1] + dp[0]开始推，逻辑上也能解释通，但更容易绕晕。不如直接给dp[1]和dp[2]赋初值，简单直观。

第二个坑是%lld。老OJ上输出long long用的是%lld，有些人写成%d，结果小数据碰巧能过，n一超过int范围就出错。

第三个坑是n=1这种边界情况。如果输入1，循环根本不会执行，直接输出dp[1]也就是1，这个没问题。但如果你只初始化了dp[2]和dp[3]，n=1时输出一个未初始化的垃圾值，那就翻车了。边界永远要单独验证。

第四个坑是我自己踩过的：用递归加记忆化也能过，代码写起来甚至更短，但OJ的栈空间如果比较小，深层次递归有可能直接爆栈。机试现场出这种问题非常麻烦，所以求稳就用递推。

3. 题目B：根据前序和中序序列输出后序序列

3.1 题目描述与输入输出形式

二叉树遍历是机试里的常青树，几乎每所学校的机试题库里都会出现。2020年这道题的要求是：输入一个整数n，表示二叉树节点个数；接下来一行给出前序遍历序列，再一行给出中序遍历序列；要求输出这棵二叉树的后序遍历序列。

测试样例通常长这样：

7 A B D E C F G D B E A F C G

对应输出应该是：

D E B F G C A

这道题考的是递归分治的思想，一旦想通，代码量其实很小。核心依据是：前序遍历的第一个节点一定是整棵树的根节点，然后拿着这个根节点到中序序列里去找位置，它左边是所有左子树节点，右边是所有右子树节点。对左子树和右子树分别重复这个过程，最后输出根节点，得到的就是后序遍历。

3.2 递归分治的核心思路

我第一次做这类题的时候，总觉得需要真的“建一棵树”出来，指针左连右连，写得很复杂。后来发现完全没必要。所谓的建树，其实只是一个递归的过程：给出一段前序区间和一段中序区间，找到根节点，递归处理左右两部分，递归返回前输出根节点。

一个关键变量是“中序序列中根节点的位置”。前序序列的第一个元素是根，但在中序里它可能在中间某个位置。假设它在inOrder数组里的下标是pos，那么：

• 左子树的节点数量是pos - inLeft，也就是中序区间中根左边的元素个数。
• 右子树节点数量是原来的区间长度减去左子树数量再减一。

递归时，前序区间需要根据左子树的节点数量来划分：左子树在前序里紧跟根节点，长度为左子树节点数；右子树再往后。只要这几个参数对得上，递归就能正确完成。

3.3 参考代码

#include <cstdio> int n; char preOrder[100], inOrder[100]; void postOrder(int preL, int preR, int inL, int inR) { if (preL > preR) { return; } char root = preOrder[preL]; int pos = -1; for (int i = inL; i <= inR; i++) { if (inOrder[i] == root) { pos = i; break; } } int leftSize = pos - inL; // 递归处理左子树 postOrder(preL + 1, preL + leftSize, inL, pos - 1); // 递归处理右子树 postOrder(preL + leftSize + 1, preR, pos + 1, inR); // 后序：最后输出根节点 printf("%c ", root); } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf(" %c", &preOrder[i]); } for (int i = 0; i < n; i++) { scanf(" %c", &inOrder[i]); } postOrder(0, n - 1, 0, n - 1); printf("\n"); return 0; }

3.4 边界与常见错误

这个代码的难点全在参数计算上。preL + 1到preL + leftSize这个区间，长度就是leftSize；preL + leftSize + 1到preR是右子树区间。如果leftSize算错，递归会直接越界或者访问到错误节点。

我遇到过的经典错误是：把中序区间参数传错，导致每层递归找到的pos不在当前区间里，最终死循环或者输出乱序。解决方案也很简单，在进入递归前加一个判断：如果区间内找不到根节点，说明参数有问题，立刻检查边界。

还有一个容易被忽略的点：读字符时，用scanf(" %c", &preOrder[i])，前面那个空格负责吃掉上一行的换行符。如果直接写scanf("%c", &preOrder[i])，第一次读到的很可能就是一个换行符，整个序列全部错位。

我在复盘时还认真想过一个问题：这道题能不能用哈希表优化查找根节点的位置。可以，但没必要。n一般不超过几十或者一百，每层线性扫描的复杂度完全能接受。考试时优先保证思路清晰，不要过早优化。

4. 题目C：单源最短路问题

4.1 题目描述与数据范围

第三题开始上难度了。题目大意：某城市有n个路口，编号从1到n，m条道路把路口连接起来，每条道路有一个长度。要求从路口1出发，到达路口n的最短距离是多少。如果无法到达，输出-1。

这类题在机试中出现频率极高，属于“图论模板题”。难点不在于算法本身，而在于你能不能快速写出正确无误的模板，并处理重边、不连通等情况。

数据范围我印象中n在1000以内，m可以到几千或者上万。这个规模下，朴素Dijkstra算法的时间复杂度是O(n^2)，能稳稳通过。如果你的n到了100000，那才需要考虑堆优化版本的Dijkstra。

4.2 算法选择：Dijkstra还是Floyd

有人拿到题会想：n才1000，直接用Floyd不是更简单？三层for循环，代码不到十行，但问题是Floyd的复杂度是O(n^3)，n=1000时就是10亿次操作，在OJ的时限下几乎不可能通过。Floyd适合n在200以内的稠密图，用来做多源最短路，这道题是单源，用不到。

Dijkstra算法的核心思想是贪心：每次从未确定最短路的节点中选一个距离起点最近的节点，用这个节点去松弛它能到达的邻居节点。重复这个过程直到所有节点都被处理完。

代码实现有两种常见方式：邻接矩阵和邻接表。n=1000时邻接矩阵没问题，但如果有重边就要小心：输入时加一条判断，保留长度最短的那条边即可。

4.3 参考代码

#include <cstdio> #include <cstring> #include <algorithm> const int INF = 0x3f3f3f3f; const int MAXN = 1005; int graph[MAXN][MAXN]; int dis[MAXN]; bool vis[MAXN]; void dijkstra(int n) { memset(dis, INF, sizeof(dis)); memset(vis, false, sizeof(vis)); dis[1] = 0; for (int i = 1; i <= n; i++) { int u = -1; int minDis = INF; for (int j = 1; j <= n; j++) { if (!vis[j] && dis[j] < minDis) { u = j; minDis = dis[j]; } } if (u == -1) { break; } vis[u] = true; for (int v = 1; v <= n; v++) { if (!vis[v] && graph[u][v] < INF) { dis[v] = std::min(dis[v], dis[u] + graph[u][v]); } } } } int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { memset(graph, INF, sizeof(graph)); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); if (w < graph[u][v]) { graph[u][v] = w; graph[v][u] = w; } } dijkstra(n); int ans = dis[n]; if (ans >= INF) { printf("-1\n"); } else { printf("%d\n", ans); } } return 0; }

4.4 粗心导致的低级错误

我第一次写这道题的时候，直接在main函数里完成了所有逻辑，没拆成函数。结果样例过了，提交WA，查了半天才发现是graph数组初始化的位置不对——我只在声明时初始化了一次，但OJ是多组数据输入，第二组数据来了之后，上一组遗留的边还在数组里，导致结果完全错乱。后来我把初始化放进while循环，问题立刻解决。

INF的取值也有讲究。用0x3f3f3f3f而不是0x7fffffff，是因为两个INF相加不会溢出int，而且这个数足够大，能表示“不可达”。如果你用0x7fffffff，在松弛操作里做加法可能直接溢出成负数，然后出现“负的路径长度”，这种bug非常隐蔽。

另外一个我提醒自己很多次的点是：图如果是无向图，建边时必须同时设置graph[u][v]和graph[v][u]。漏掉一条就相当于道路变成单行道了。

5. 题目D：最长上升子序列（LIS）

5.1 题目描述与基本思路

最后一道题一般是压轴题，2020年考的是最长上升子序列。题目给一个长度为n的整数序列，要求找出其中严格递增的最长子序列的长度。所谓子序列，不要求连续，只要在原序列中保持相对顺序就行。

比如序列3 1 4 1 5 9 2 6，最长上升子序列是1 4 5 9或者1 2 6，长度都是4。

这个问题是经典动态规划题。定义dp[i]表示以第i个元素结尾的最长上升子序列长度，那么dp[i]至少是1，因为单个数字本身也构成一个长度为1的上升子序列。对于每个j小于i，只要a[j] < a[i]，就可以考虑把a[i]接到以a[j]结尾的子序列后面，更新dp[i] = max(dp[i], dp[j] + 1)。

5.2 两种解法的取舍

如果n给到5000甚至10000，O(n^2)的写法是能过的。但有的题目会把n拉到100000，这时候必须用O(nlogn)的贪心加二分做法。

O(nlogn)的思路很巧妙：维护一个数组d，d[i]表示长度为i的上升子序列中，末尾数字的最小值。遍历原序列时，对每个a[i]，在d中找到第一个大于等于它的位置，把这个位置的值更新为a[i]。如果整个d都小于a[i]，就把a[i]追加到末尾。

这个做法为什么正确？原因在于：同样长度的上升子序列，末尾数字越小，后面接数字的潜力越大。所以d是一个单调递增的数组，可以用二分查找快速定位更新位置。

机试时如果时间紧张，先把O(n^2)的DP写出来拿基础分，如果n确实很大，再改成O(nlogn)版本。两种写法我都放在这里，考试时按需选用。

5.3 参考代码

O(n^2)写法：

#include <cstdio> #include <algorithm> const int MAXN = 10005; int a[MAXN]; int dp[MAXN]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } 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] = std::max(dp[i], dp[j] + 1); } } ans = std::max(ans, dp[i]); } printf("%d\n", ans); return 0; }

O(nlogn)写法：

#include <cstdio> #include <algorithm> const int MAXN = 100005; int a[MAXN]; int d[MAXN]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } int len = 0; d[0] = -1000000000; for (int i = 1; i <= n; i++) { if (a[i] > d[len]) { d[++len] = a[i]; } else { int pos = std::lower_bound(d + 1, d + len + 1, a[i]) - d; d[pos] = a[i]; } } printf("%d\n", len); return 0; }

5.4 DP初始化与严格递增的陷阱

这道题的一个常见误区是忘记dp[i]初始化为1。如果不初始化，dp[0]是0，dp[i]默认是0，整个更新过程就会出错，最终答案可能是0而不是正确答案。

另一个陷阱是“严格递增”和“非严格递增”的区别。题目只要说是上升，通常意味着a[j] < a[i]；如果题目说“不下降子序列”，那条件就要改成a[j] <= a[i]。这个差异直接影响判断条件，一字之差代码就不对。

还有一点容易忽略：O(nlogn)版本里，lower_bound找到的是第一个不小于目标值的位置，因此保证数组d的严格单调性。但如果题目要求非严格上升，这里就要改用upper_bound，因为等于目标值的时候应该更新而不是跳过。我在刷题时经常被这两种情况绕晕，后来总结出一个口诀：严格上升用lower_bound，非严格上升用upper_bound。

6. 考场实战经验与刷题建议

6.1 拿到题先做什么

走进机试考场，第一件事不是急着敲代码，而是把所有题目都读一遍，用五分钟做一个全局判断：哪些是送分题，哪些是中等题，哪些可能做不出来。华师这套题通常难度递增，所以我会从第一题开始往后做，但遇到卡壳超过二十分钟的题，果断跳过，先保证能拿的分全部拿到。

做题过程中，每道题都先在草稿纸上写清大致的边界条件和数据范围。比如第一题n=70要用long long，第三题n=1000要不要考虑重边，第四题n是5000还是50000。这些信息比代码本身的逻辑更值钱，想清楚再动手，能省出大量调试时间。

6.2 调试技巧与心态调整

机试最难受的不是不会写，而是样例过了却AC不了。遇到这种情况，我会先检查三件事：数组是否开小了，初始化是否清干净了，变量类型是否够用。这三类问题占了WA原因的一大半。

调试时不要慌着打印一堆中间变量。先自己构造几个边界数据，比如n=1、n最大值、全是相同数字的序列、图不连通的情况。把这些数据跑一遍，很多问题立刻暴露出来。

心态上要接受一个事实：不可能每道题都做出来。我的策略是给自己定一个底线分，比如至少AC两道题，第三题部分AC，第四题暴力拿一小部分分数。有了这个目标，做起来心理压力会小很多。

6.3 从刷题到机试模拟的备考路线

如果离考试还有一段时间，我建议按这个顺序准备：先刷完这类模板题——递推、栈和队列、二叉树遍历、排序、二分查找、并查集、最短路径、最小生成树、简单DP。每写一道题，不要只满足于提交通过，试着改一改条件再做一遍，比如把“前序+中序”改成“后序+中序”，把“最长上升子序列”改成“最长不下降子序列”。

考前两周，找一个OJ平台练习三到四场完整的模拟赛，严格按照三小时、四道题的时间限制来。模拟赛的意义不只是练代码，更是练分配时间的节奏感、练调试时的冷静程度、练看到没见过的题时的心理承受能力。

我个人还有一个习惯：把每类题的模板压缩成一页A4纸，考前一天只看这页纸，不刷任何新题。比如Dijkstra的邻接矩阵写法、二叉树的递归分治写法、LIS的lower_bound写法，这些核心代码必须做到闭着眼睛都能默写。但模板只是起点，真正拉开差距的还是你能不能根据题目要求灵活变形，这一点只能靠多练多总结，没有捷径。