第8题代数运算——先别急着算先看题目给了什么试卷第 8 题是若 xy 7x-y 1则 x * y 的值为 。✅ D、12 这种题应该怎么做小朋友做代数题最容易犯的错误就是“看到字母就害怕”其实字母和数字没有本质区别。例如a 3 b 5那么a b就相当于3 5 8 表达式计算的诀窍减少变量的数量x y 7 x - y 1 等式左右分别相加依然为等式 x y (x - y) 7 1 x x 8 x 4我们已经得到 x 的值4计算 y 的值4 y 7 y 7 - 4 y 3计算 x * y 的值x * y 4 * 3 12我们遇到这种题可以养成一个习惯第一步把已知条件写出来a ? b ?第二步找到题目真正要求的东西例如要求ab a-b a×b a²b²第三步合并同类项减少项数不要被字母吓住。 第9题最小生成树——Kruskal 和 Prim 谁更适合第 9 题问的是关于最小生成树MST算法下列说法正确的是正确答案✅ A、题目给出的选项是A. Prim 算法适用于稠密图Kruskal 算法适用于稀疏图B. Prim 和 Kruskal 得到的最小生成树边集一定完全相同C. Kruskal 必须使用邻接矩阵D. Prim 只能处理有向图。 什么叫最小生成树想象有几个城市北京 —— 上海 | | 广州 —— 深圳城市之间修公路每条公路都有一个价格。我们的任务让所有城市连通同时修路总成本最低。这就是 最小生成树 MST Kruskal边的“选美大赛”Kruskal 的思路特别简单把所有边按照权值从小到大排序。例如边 价格 A-B 2 B-C 3 A-C 5 C-D 7然后2 → 3 → 5 → 7从小到大尝试。如果加进去不会形成环就选。 Prim从一个城市慢慢扩张Prim 的感觉不一样。比如从A出发。每次寻找连接“已经加入的城市”和“外面的城市”的最小边。所以它像一支探险队已经探索区域 ↓ 寻找最近的新城市 ↓ 加入 ↓ 继续扩大⭐ 为什么 A 正确通常来说稠密图边很多城市之间到处都有路Prim 往往比较适合。稀疏图边比较少只有少数道路Kruskal 往往很方便。所以考试中可以记Prim从点出发扩张。Kruskal把边排序后挑。❌ B 为什么错Prim 和 Kruskal 得到的最小生成树边集一定完全相同。不一定如果图存在多个权值相同的边A —— B \ / C可能有多棵同样重量的最小生成树。所以最小生成树可能不唯一。但是它们的总权值都是最小的。❌ C 为什么错Kruskal 并不要求邻接矩阵。它最喜欢的是边数组例如struct Edge { int u, v, w; };然后sort(edge, edge m, cmp);❌ D 为什么错Prim 是用来求无向连通图的最小生成树不是“只能处理有向图”。事实上最小生成树这个概念本身就是针对无向图的。 第10题Kruskal——第几条边能够上车第 10 题继续考 Kruskal某连通带权无向简单图使用 Kruskal 算法按照边权从小到大扫描第几条被选入最小生成树的边是什么这一题真正考⭐ “排序 判断成环” Kruskal 的固定套路假设边已经按照权值排序1 2 3 4 5 6我们从第一条开始看 ↓ 加进去会不会形成环 ↓ 不会 → 加 会 → 跳过 为什么会出现“跳过”例如A —— B \ / C假设A-B 1 B-C 2 A-C 3先选A-B再选B-C此时A —— B | C已经连通。再看A-C如果加进去A —— B \ | \ | C就形成环。所以❌ 不选 A-C。 考试秘诀看到“Kruskal 按边权从小到大扫描”脑袋里立刻出现排序 ↓ 最小边 ↓ 会不会成环 ↓ 不成环就选如果是代码题则会出现sort()加上并查集 第11题Dijkstra 的小根堆里放什么这道题非常经典。题目问在使用小根堆优先队列优化的 Dijkstra 算法中堆中每个元素通常存储什么答案✅ A也就是顶点编号 当前最短距离。️ 先理解 Dijkstra假设A ——2—— B ——3—— C \ | 5 1 \ | —— D我们从 A 出发。我们需要不断寻找目前离起点最近的那个点。 所以我们需要一个“排行榜”例如距离 城市 2 B 5 D ∞ C谁距离最小B先处理 B。这就是优先队列的作用。 为什么要存两个东西只存距离不行。因为你还得知道这个距离属于谁所以需要(距离顶点)例如(2, B) (5, D) C代码里经常写成priority_queue pairint, int, vectorpairint, int, greaterpairint, int q;里面放距离 顶点编号 记忆点把优先队列想成 “跑步排行榜”每个人都有姓名 成绩Dijkstra 中姓名 → 顶点 成绩 → 当前最短距离所以必须两个一起存。 第12题Floyd——k 到底是谁本题问在 Floyd 算法经典三重循环for (k) for (i) for (j)中最外层k表示什么答案✅ A即当前允许作为中间顶点的最大编号也就是只允许编号不超过 k 的顶点作为中间点。 这是 Floyd 最核心的思想Floyd 是解决任意两点之间最短路的经典算法。它的代码大家比较熟悉for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) d[i][j] min( d[i][j], d[i][k] d[k][j] ); k 在干什么假设k 1我们允许顶点 1 当中间人。然后k 2允许顶点 1、2 当中间人。然后k 3允许顶点 1、2、3 当中间人。所以k就像 “中间人开放权限”⭐ 为什么 k 必须放最外层因为 Floyd 的状态思想是d[i][j]表示在允许某些点作为中间点的情况下i 到 j 的最短距离。k一层一层扩大允许1 ↓ 允许1、2 ↓ 允许1、2、3 ↓ ……这正是动态规划的特点。 第13题复杂度——谁跑得慢谁跑得快本题考常见复杂度按照渐近增长速度从慢到快排列。答案是✅ C 复杂度速度排行榜我们可以把复杂度想象成赛车 最快O(1)无论数据多大基本不受影响。O(log n)非常快。典型二分查找 快速幂O(n)数据增加一倍工作量大约增加一倍。例如for (int i 1; i n; i)然后O(n log n)典型归并排序 快速排序平均情况再往后O(n²)典型for (...) for (...)更可怕O(n³)例如 Floyd。再往后O(2^n)通常非常恐怖。 一定记住这条“速度长龙”O(1) ↓ O(log n) ↓ O(n) ↓ O(n log n) ↓ O(n²) ↓ O(n³) ↓ O(2^n) ↓ O(n!)越往下面 数据一大越容易爆炸 第14题差分数组——区间加法的魔法对长度为n的数组使用差分数组支持m次区间加操作最后通过一次前缀和还原每个位置的最终值整个过程的渐进时间复杂度是多少答案✅ D题目本身明确描述了“差分数组 最后一次前缀和”。 普通方法为什么慢假设1 2 3 4 5 6 7 8现在要求[2, 7]全部加 10。普通方法2 加 3 加 4 加 5 加 6 加 7 加一次操作可能修改很多个数字。如果有m次操作就可能变得很慢。 差分数组来了差分数组d的思想不直接告诉每个人“你加10”而是只告诉“从这里开始 10从这里结束”。例如区间 [2,7] 10只需要d[2] 10; d[8] - 10;神奇 为什么因为最后做前缀和d[1] d[1]d[2] d[1]d[2]d[3] ...于是27之间都会自动得到10到了8又减回来。差分数组的核心思想我们不直接记录每个位置的具体值而是记录「相邻两个位置的差值」‌把原本需要遍历整个区间的修改变成只修改两个端点的标记最后通过一次前缀和还原出最终数组。1. 差分数组的定义对于原数组a长度为n我们以下标从1开始为例避免越界特判它的差分数组diff满足diff[1] a[1]第一个位置没有前驱差值就是它本身diff[i] a[i] - a[i-1]i≥2时存当前位置和前一个位置的差反过来‌原数组就是差分数组的前缀和‌a[i] diff[1] diff[2] ... diff[i]。举个最简单的例子原数组a [1, 3, 5, 6, 7]下标1~5对应的差分数组计算如下diff[1] 1diff[2] 3-1 2diff[3] 5-3 2diff[4] 6-5 1diff[5] 7-6 1即差分数组diff [1, 2, 2, 1, 1]对diff求前缀和就能还原回原数组。2. 区间加操作的原理为什么只需要改两个点如果我们要对原数组的区间[l, r]所有元素都加v差分数组只会发生两个变化在位置 la[l]比a[l-1]多了v所以diff[l] v——这个标记的含义是「从位置l开始后面所有元素都要加v」在位置r1a[r1]比a[r]少了v所以diff[r1] - v——这个标记的含义是「从位置r1开始后面所有元素都减回v抵消前面的加v效果」区间内部的元素因为同时加了v相邻差值完全不变所以不需要修改diff数组的其他位置。3. 前缀和还原最终数组所有操作完成后对diff数组从头开始求前缀和就能得到修改后的原数组⏱️ 复杂度怎么算每一次区间修改O(1)做m次O(m)最后一次前缀和O(n)所以总复杂度⭐ O(n m)这就是本题最重要的结论。 第15题C对象的构造与析构这题非常适合小学生理解因为它像机器人出生和离开房间。代码class A { public: A() { cout A; } ~A() { cout ~A; } };然后有一个class B : public A { public: B() { cout B; } ~B() { cout ~B; } };最后int main() { B b; return 0; }题目选项给出了A. BA~A~B B. BA~B~A C. AB~A~B D. AB~B~A正确答案✅ D 第一步B出生了我们写B b;表面上看创建 B。但是 B 是class B : public A也就是说B 是 A 的“孩子”。 C规定创建派生类对象时先构造父类再构造子类。所以A构造 ↓ B构造输出AB 那么销毁呢这时候顺序反过来先销毁子类再销毁父类。所以B析构 ↓ A析构输出~B~A 合起来创建AB销毁~B~A最终AB~B~A所以 答案 D 这个知识一定要记住我们可以想象出生爸爸先出生 ↓ 孩子再出生回家孩子先回家 ↓ 爸爸后回家所以⭐ 构造父 → 子⭐ 析构子 → 父 第815题知识地图题号考点一句话记忆8代数计算先看已知再代入计算合并同类项9MSTPrim扩点Kruskal挑边10Kruskal边权排序遇环跳过11Dijkstra 堆距离 顶点12Floydk是允许的中间点13时间复杂度从 O(1) 到 O(n!) 越来越慢14差分数组区间修改 O(1)最后前缀和15构造/析构父先子后析构反过来 “闯关地图”到这里选择题115题其实已经串成了一张知识地图C八级选择题 │ ┌───────────────┼───────────────┐ ↓ ↓ ↓ 数学 图论 C │ │ │ ┌────┼────┐ ┌───┼────┐ ┌──┼───┐ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 排列 杨辉 建模 MST Dijkstra Floyd 析构 复杂度 组合 三角 Kruskal 最短路 构造 差分其中最值得同学们反复掌握的8个“看到题目就要条件反射”的关键词是Kruskal → 排序 不成环Prim → 从一个点不断扩张Dijkstra → 小根堆里放距离 点Floyd → k是中间点差分 → 区间修改 O(1)前缀和 → 最后还原构造 → 父类先、子类后⚫析构 → 子类先、父类后