第8题 统计因子2出现多少次答案C31、代码int n 40; int cnt 0; while(n % 2 0) { cnt; n / 2; }2、故事理解1想象数字40是一块巧克力。不断问还能不能平均掰成两半如果能就继续掰。2第一次40 ÷2 20cnt13第二次20÷210cnt23第三次10÷25cnt34第四次5不能再除2结束。5输出3所以答案就是C。3、分解质因子40 2³ ×52一共出现3次。4、这段代码统计的是质因数2的个数。这是分解质因数的基础之一。第9题 lower_bound模板答案C1、题目在一个有序数组中查找第一个大于或等于x的元素位置横线处应填写 。int lowerBound(vectorint a, int x) { int l 0, r a.size(); while (l r) { int mid l (r - l) / 2; if (a[mid] x) ________________; // 在此处填入代码 else l mid 1; } return l; }2、模拟操作1假设数字1 3 5 6 6 7 7 7 9 索引0 1 2 3 4 5 6 7 8找第一6应该返回索引为32现在mid4发现6 63说明右侧全部没用。同时答案可能就是索引4。4但是左边可能还有满足条件的。所以应该rmid;包含mid,继续往左找。3、为什么不是rmid-1;有的同学最容易错这里。如果mid正好就是答案。rmid-1答案自己被删掉了。所以就错了。4、记忆口诀要看mid自己是否满足条件满足条件 ↓ 保留mid因此rmid第10题 二分答案答案B1、故事1有很多木头。希望所有木头最长不要超过x。2老师问x10可以吗如果可以。那么9 8 7也许还能行。所以答案一定在左边。3于是rmid;继续缩小。4如果mid不行。说明太小了。只能lmid1;5因此if(check(...)) rmid; else lmid1;答案选B。2、二分答案口诀求最小可行值一定check成功 ↓ 向左找 ↓ rmid这是五级出现频率比较高的模板。第11题 快速排序partition答案B1、代码pivotarr[low];最后ij说明已经找到基准应该放的位置。2、于是应该交换pivot ↓ 当前位置即swap(arr[low],arr[i]);答案B。3、故事1老师指定一个队长pivot大家左右分别站队。2最后左边 pivot 右边 pivot3队长要走到中间。所以交换队长 ↓ 最终位置第12题 归并排序思想答案B1、归并排序简单一句话先分再合。1例如8 4 7 32先分8 4 7 33再分8 4 7 34开始合4 8 3 75再合3 4 7 86所以答案分成两半 ↓ 分别排序 ↓ 再合并就是B。2、其它选项1选项 A选择排序。2选项 C冒泡排序。3选项 D插入排序。第13题 merge调用次数答案A1、其实规律非常简单。1假设1个数不用合并。0次22个数1次34个数2次 1次3 次48个数4 2 175有没有发现1→0 2→1 4→3 8→7规律merge次数 n-16因此长度为8调用7次所以答案A。2、为什么归并排序其实就是一棵二叉树。8 ↓ 4 4 ↓ 2 2 2 2 ↓ 1 1 1 1 1 1 1 1每合并一次。树上减少一个结点。最终剩一个。所以n-1第14题 双指针贪心答案C1、故事最轻l最重r1如果两个可以一起坐船两个人都已经安排。2于是l r--所以应该l; r--;3否则r--;2、答案是C。为什么1例如1 2 5limit62第一轮156成功。于是1 5都没了。3下一轮只剩2因此两个指针一起移动。第15题 高精度减法答案A1、代码if(a[i]b[i]) { a[i1]--; ________; }2、故事1例如1000 - 12个位0-1不够。怎么办3向十位借104于是个位加1010再减。5代码就是a[i]10;答案A。3、记忆口诀高精度减法不够减 ↓ 向高位借1 ↓ 当前位10即a[i1]--; a[i]10;815题知识总结题号考点一句话口诀8分解质因数不断除2统计次数9lower_bound找第一个≥满足条件保留midrmid10二分答案最小可行值check成功→rmid11快速排序最后交换pivot和i位置12归并排序先分治再合并13归并次数merge调用次数 n−114双指针贪心能配对→l、r--15高精度减法借位高位-1当前位10题目中用到的 8 个模板建议把下面这 8 个模板背熟它们几乎每年都会以不同形式出现① 欧几里得算法 gcd(a,b)gcd(b,a%b); ② 欧拉筛 if(i%prime0) break; ③ lower_bound if(a[mid]x) rmid; else lmid1; ④ 二分答案最小值 if(check(mid)) rmid; else lmid1; ⑤ 快速幂 power(x,n)power(x,n/2); ⑥ 快速排序 swap(arr[low],arr[i]); ⑦ 高精度减法 a[i1]--; a[i]10; ⑧ 双指针 满足条件lr--;