第1题 组合计数1、题目某班有8名男生、6名女生。选3人组成学习小组。要求至少1名男生至少1名女生共有多少种方案A.112B.168C.224D.288答案D方法一分类讨论推荐满足条件只有两种情况第一种2男1女男生C(8,2)28女生C(6,1)6所以28×6168第二种1男2女男生C(8,1)8女生C(6,2)15所以8×15120总方案168120288所以答案D方法二总数减去非法1、总方案从14人选3人C(14,3)3642、非法情况全部男生C(8,3)56全部女生C(6,3)203、因此364−56−20288也是正确答案。八级考点这是经典组合计数。以后经常遇到至少一个至多一个恰好一个很多题都可以采用分类讨论或者总数-非法第2题 杨辉三角答案B1、题目第10行所有数字之和是多少2、有的同学会一个一个去写出来。其实不用。记住公式杨辉三角第n行所有数字之和 2 ^ n这里n10所以2 ^ 10 10243、答案B、1024八级考点需要牢记二项式定理杨辉三角组合数三者互相关联。第3题 快速幂复杂度答案B1、题目是快速幂代码。核心代码while(e0) { if(e1) ... bb*b; e1; }2、为什么快普通算法乘e次复杂度O(e)例如2¹⁰⁰⁰要乘1000次。3、快速幂每次e/2例如1000↓500↓250↓125↓62↓31↓15↓7↓3↓1↓0大约进行了log₂1000≈10次。4、所以复杂度O(log n)答案B。八级考点以后遇见快速幂二分倍增LCA很多都是O(log n)第4题 组合计数答案C1、题目5本数学书4本物理书选3本至少一本数学书2、建议总数-非法1全部方案9本选3本C(9,3)842非法全部物理C(4,3)43所以84−4 80答案C3、为什么不用分类当然可以3数2数1物1数2物但是更慢。4、所以看到至少首先想到总数−非法第5题 BST答案B1、首先判断根中序1 2 3 4 5先序第一个3说明3一定是根。2、判断左、右子树于是左子树1 2右子树4 53、逐项判断A错误不一定是完全二叉树。B正确4与5中只能一个是3的孩子所以不可能是兄弟。C错误左边只有两个节点。1深度不会超过3。D错误2未必是1父亲。例如3 / 1 \ 2BST合法。八级考点BST一定要熟悉中序一定有序。这是最重要性质。第6题 Dijkstra复杂度答案C1、普通Dijkstra找最小点每次扫描全部复杂度O(n²)2、如果使用优先队列堆优化每次取最小变成log最终复杂度O((nm)log n)3、因此答案C。八级考点算法复杂度普通DijkstraO(n²)堆优化DijkstraO(nm) log n)FloydO(n³)Bellman-FordO(nm)SPFA平均快最坏O(nm)这是最常用的一张表。第7题 最短路径最多多少条边答案B1、题目没有负环。问任意最短路径最多多少条边2、本题关键最短路径一定是简单路径即不会重复经过同一个点。否则重复绕圈没有意义。3、假设共有n个点。最多能经过n个点边数就是n−14、因此答案B、n−1 条边。第一部分1~7题知识点这7道题几乎覆盖了八级算法竞赛中的基础理论建议同学们牢记下面这些结论题号知识点必须掌握1组合计数分类讨论、总数减非法2杨辉三角第 n 行数字和 (2^n)3快速幂时间复杂度 O(log n)4组合数至少/至多问题优先考虑补集法5BST中序遍历一定有序6Dijkstra堆优化复杂度 O(mnlog n)7最短路简单路径最多经过 n−1 条边
