第1题 组合计数答案B455题目从7 本不同算法书和5 本不同数学书中选4 本要求两类书都至少选1 本。问一共有多少种选法第一步为什么不能直接计算1、有的同学第一反应一共有7512 本书选四本但是这样错了因为这里把下面两种情况也算进去了2、全部都是算法书算法 算法 算法 算法全部都是数学书数学 数学 数学 数学题目要求两类书都至少一本。所以必须去掉这些情况。方法可以使用分类讨论法和补集法。第二步分类讨论1、因为一共选4本。算法书至少一本。数学书至少一本。那么算法书可能选1 本 2 本 3 本不能0本也不能4本。所以只有三种情况。2、第一种1算法1本数学3本2算法方案数数学方案数方案数小计第二种1算法2本数学2本2算法方案数数学方案数方案数小计第三种1算法3本数学1本2算法方案数数学方案数方案数小计第三步全部相加1计算70210280 2801754552所以答案方法二补集法竞赛常用1、先不考虑限制。12本里面选四本2、去掉两种非法情况。1全部都是算法书7本里面选四本2全部都是数学书5本里面选四本3因此495-35-5得到455两种方法比较方法思路推荐程度分类讨论按算法书选1、2、3本分类⭐⭐⭐⭐⭐容易理解补集法总方案减去非法方案⭐⭐⭐⭐计算更快 一句话总结遇到题目中出现两类都至少选一个一般有两种经典做法方法一——分类讨论第一类选1个 第一类选2个 第一类选3个 ……把所有合法情况分别计算后相加。方法二——补集法总方案 − 第一类一个都没选 − 第二类一个都没选第2题 排列计数答案B4801、题意若干个人排成一排。其中甲乙不能相邻。问共有多少种。2、思路这是经典题。采用总方案 − 相邻方案3、分步计算第一步所有排列假设共有6个人那么6!720第二步1甲乙绑在一起把甲乙看成一个整体。又由于甲乙内部还能交换ABBA所以要乘2。2于是整体数量变成5个人排列即3最后720-240480所以答案B4、记忆口诀以后遇到两人不能相邻若干元素不能相邻第一反应就是总数−相邻数第3题 二项式展开答案C151、这是经典二项式定理2、展开(ab)^n第k项3、怎样找常数项1秘诀指数全部加起来等于0。令x指数0即可求出k。2找到对应组合数即可。计算后得到组合数所以答案15第4题 杨辉三角答案A1、看代码for (int i 0; i n; i) { c[i][0] c[i][i] 1; for (int j 1; j i; j) c[i][j] ________; }2、杨辉三角公式组合数满足C(i,j)C(i−1,j−1)C(i−1,j)因此c[i][j] c[i-1][j-1] c[i-1][j];答案A3、为什么1因为当前位置就是左上正上2例如1 1 1 1 2 1 1 3 3 13数字3就是124、这是组合数学最重要公式之一。以后DP组合数Lucas都会反复使用。第5题 快速幂答案C131、看程序qpow(3,20,17)2、不需要真的算3²⁰因为要求的是3、根据费马小定理17是质数1所以2因此3变成4而 135所以答案134、快速幂不会直接计算巨大数字。而是不断平方取模时间复杂度第6题 归并排序答案DO(nlogn)1、归并排序每次长度 n ↓ 分成 n/2 ↓ n/4 ↓ ……2、高度就是3、每层合并需要4、例如8个数 第一层 8 第二层 44 第三层 2222 第四层 1……1每层工作量都是8共有log₂83层。2于是8×3一般就是这是归并排序最经典结论。第7题 三角形面积答案A1、这是平面几何经典公式。三个点面积公式考试时直接代入坐标即可。2、另一种理解实际上它来源于叉积Cross Product即很多几何题都会利用叉积来判断三点是否共线面积左转右转凸包因此这道题是在考察解析几何与向量叉积的基础应用。1~7题知识点题号考点核心方法1组合计数分类讨论、组合数2排列组合总数相邻数3二项式展开找常数项、组合数4杨辉三角组合数递推公式5快速幂模运算、费马小定理6归并排序分治时间复杂度 O(nlogn)7三角形面积叉积求面积这7道选择题几乎覆盖了八级前半部分最重要的基础知识排列组合、二项式定理、组合数递推、快速幂、分治排序、解析几何。