第1题gcd万能吗1、故事数学骑士拿出一个函数 不管 a b 还是 a b都能算最大公约数2、判断步骤① 核心代码while (b) { int temp b; b a % b; a temp; }② 如果 a b 会怎样 第一轮就会自动交换3、✅结论✔️ 正确4、小口诀 辗转相除法自带交换功能 第2题最小公倍数公式1、故事数学精灵说 lcm(a, b) a × b ÷ gcd(a, b)2、判断步骤① gcd 是最大公约数② 公式是标准数学结论3、⚠️注意 只要 gcd 正确这个公式就成立4、✅结论✔️ 正确5、小口诀 最小公倍数 乘积 ÷ 最大公约数 第3题质因数分解代码1、故事程序员想输出 6 → [2, 3] 8 → [2, 2, 2]2、检查代码关键错误prime_factor[i] prime_factor[i] j;❌ vector 不能这样加3、正确写法应该是prime_factor[i].push_back(j);4、❌结论❌ 错误5、小口诀 vector 加元素要用 push_back 第4题归并排序只执行一次1、故事程序里打印 HERE有人说 只会打印一次2、分析归并排序 会不断拆分 合并每一次合并都会调用 merge3、❌结论❌ 错误 会打印很多次4、小口诀 分治算法 → 会多次合并 第5题归并排序复杂度1、故事归并排序被称为“稳定的排序大师”2、分析 不管情况如何最好O(n log n)最坏O(n log n)平均O(n log n)3、✅结论✔️ 正确4、小口诀 归并排序稳如泰山O(n log n) 第6题查字典 二分查找1、故事查字典 一次翻一半2、分析① 看中间② 判断往前还是往后③ 继续缩小范围 完全就是二分查找3、✅结论✔️ 正确4、小口诀 每次砍一半 二分查找 第7题Dijkstra是贪心1、故事最短路径大师 每次选“当前最近的点”2、分析 每一步都选最优最近 典型贪心思想3、✅结论✔️ 正确4、小口诀 每次选最近 贪心 第8题分治一定更慢1、故事有人说 分治要拆开再合并所以更慢2、分析❌ 不一定 很多算法更快比如快速排序归并排序3、❌结论❌ 错误4、小口诀 分治不仅不慢还很聪明 第9题递归会无限循环1、故事函数if (n 1) return 1; if (n % 2 0) return puzzle(n / 2); return puzzle(3 * n 1);2、分析这是“3n1问题”猜想 有些数会变来变去但题目问一定无限递归吗3、❌结论❌ 错误 不一定无限当3n1 2 ^ n, 数会回到14、小口诀 看起来危险但不一定死循环 第10题线性筛复杂度1、故事筛法高手登场 每个合数只被筛一次2、分析 时间复杂度O(n)3、✅结论✔️ 正确4、小口诀 每个数只筛一次 线性 知识点总结1️⃣ gcd 自带交换2️⃣ lcm ab / gcd3️⃣ vector 用 push_back4️⃣ merge 会执行多次5️⃣ 归并排序永远 n log n6️⃣ 查字典就是二分7️⃣ Dijkstra 是贪心8️⃣ 分治不一定慢9️⃣ 递归不一定死循环 线性筛是 O(n)