第8题 统计因子2出现多少次

答案：C（3）

1、代码：

int n = 40; int cnt = 0; while(n % 2 == 0) { cnt++; n /= 2; }

2、故事理解

（1）想象数字40是一块巧克力。

不断问：

还能不能平均掰成两半？

如果能，就继续掰。

（2）第一次：

40 ÷2 =20

cnt=1

（3）第二次：

20÷2=10

cnt=2

（3）第三次：

10÷2=5

cnt=3

（4）第四次：

5不能再除2

结束。

（5）输出：

3

所以答案就是C。

3、分解质因子

40 = 2³ ×5

2一共出现3次。

4、这段代码统计的是：

质因数2的个数。

这是分解质因数的基础之一。

第9题 lower_bound模板

答案：C

1、题目：

在一个有序数组中查找第一个大于或等于x的元素位置，横线处应填写（ ）。

int lowerBound(vector<int>& 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

应该返回：

索引为3

（2）现在：

mid=4

发现：

6 <= 6

（3）说明：

右侧全部没用。

同时答案可能就是索引4。

（4）但是：

左边可能还有满足条件的。

所以应该：

r=mid;

包含mid,继续往左找。

3、为什么不是

r=mid-1;

有的同学最容易错这里。

如果mid

正好就是答案。

r=mid-1

答案自己被删掉了。

所以就错了。

4、记忆口诀

要看mid自己是否满足条件：

满足条件 ↓ 保留mid

因此：

r=mid

第10题 二分答案

答案：B

1、故事

（1）有很多木头。

希望：

所有木头最长不要超过x。

（2）老师问：

x=10

可以吗？

如果：

可以。

那么：

9 8 7

也许还能行。

所以：

答案一定在左边。

（3）于是：

r=mid;

继续缩小。

（4）如果：

mid

不行。

说明：

太小了。

只能：

l=mid+1;

（5）因此：

if(check(...)) r=mid; else l=mid+1;

答案选B。

2、二分答案口诀

求：

最小可行值

一定：

check成功 ↓ 向左找 ↓ r=mid

这是五级出现频率比较高的模板。

第11题 快速排序partition

答案：B

1、代码：

pivot=arr[low];

最后：

i==j

说明：

已经找到基准应该放的位置。

2、于是：

应该交换：

pivot ↓ 当前位置

即：

swap(arr[low],arr[i]);

答案B。

3、故事

（1）老师指定一个队长：

pivot

大家左右分别站队。

（2）最后：

左边 < pivot 右边 > pivot

（3）队长要走到中间。

所以：

交换：

队长 ↓ 最终位置

第12题 归并排序思想

答案：B

1、归并排序简单一句话：

先分，再合。

（1）例如：

8 4 7 3

（2）先分：

8 4 7 3

（3）再分：

8 4 7 3

（4）开始合：

4 8 3 7

（5）再合：

3 4 7 8

（6）所以：

答案：

分成两半 ↓ 分别排序 ↓ 再合并

就是B。

2、其它选项：

（1）选项 A

选择排序。

（2）选项 C

冒泡排序。

（3）选项 D

插入排序。

第13题 merge调用次数

答案：A

1、其实规律非常简单。

（1）假设：

1个数

不用合并。

0次

（2）2个数

1次

（3）4个数

2次 + 1次

3 次

（4）8个数

4 + 2 + 1

=

7

（5）有没有发现？

1→0 2→1 4→3 8→7

规律：

merge次数 = n-1

（6）因此：

长度为

8

调用：

7次

所以答案A。

2、为什么？

归并排序其实就是：

一棵二叉树。

8 ↓ 4 4 ↓ 2 2 2 2 ↓ 1 1 1 1 1 1 1 1

每合并一次。

树上减少一个结点。

最终：

剩一个。

所以：

n-1

第14题 双指针贪心

答案：C

1、故事：

最轻：

l

最重：

r

（1）如果：

两个可以一起坐船

两个人都已经安排。

（2）于是：

l++ r--

所以：

应该：

l++; r--;

（3）否则：

r--;

2、答案是C。

为什么？

（1）例如：

1 2 5

limit

6

（2）第一轮：

1+5=6

成功。

于是：

1 5

都没了。

（3）下一轮：

只剩

2

因此：

两个指针一起移动。

第15题 高精度减法

答案：A

1、代码：

if(a[i]<b[i]) { a[i+1]--; ________; }

2、故事

（1）例如：

1000 - 1

（2）个位：

0-1

不够。

怎么办？

（3）向十位借：

10

（4）于是个位加10：

+10

再减。

（5）代码就是：

a[i]+=10;

答案A。

3、记忆口诀

高精度减法：

不够减 ↓ 向高位借1 ↓ 当前位+10

即：

a[i+1]--; a[i]+=10;

8～15题知识总结

题目中用到的 8 个模板

建议把下面这 8 个模板背熟，它们几乎每年都会以不同形式出现：

① 欧几里得算法 gcd(a,b)=gcd(b,a%b); ② 欧拉筛 if(i%prime==0) break; ③ lower_bound if(a[mid]>=x) r=mid; else l=mid+1; ④ 二分答案（最小值） if(check(mid)) r=mid; else l=mid+1; ⑤ 快速幂 power(x,n)=power(x,n/2); ⑥ 快速排序 swap(arr[low],arr[i]); ⑦ 高精度减法 a[i+1]--; a[i]+=10; ⑧ 双指针 满足条件：l++，r--;