二分/双指针/单调栈队列专题

1.4924. 矩阵 - AcWing题库

一开始打表找规律以为是右上角向左下角递增,但当n很大的时候就不对了,因此我们得去观察

i * i + 100000 * (i - j) + j * j + i * j
这个式子,我们关心的是这个式子的单调性因此我们可以分别将i和j看作常数来对式子进行求导,可以得到

f'(i) = 2 * i + 100000 + j

f'(j) = 2 * j + i - 100000

2.4926. 中位数 - AcWing题库

注意,类似该题中的check函数原为每次二分查找,类似性质的情况下双指针复杂度更优

3.4932. DZY爱划分 - AcWing题库

将n拆分成k个不同的正整数,使得这k个数乘积最大,首先可以知道要想n个数相乘尽可能大那就使得,这n个数彼此之间的差尽可能的小,因此我们尝试构造一个公差为1的等差数列,但是有时候并不能正好凑出x,但缺少的值一定小于k(若大于等于k可以在这k个数身上每个加1),那么为了保证每个数之间差距尽可能小且不会出现重复我们从最大的数开始每个+1直到少的值加完

4.F-双生双宿之探_2025牛客寒假算法基础集训营1

一种做题技巧,像是上次一场div2的d题与中位数相关的题目都可以使用,那便是若一个数组中的数字只有两种性质,并且需要我们进行计数,那么不妨将两个种类的数字映射成1,-1,如此一来求出前缀和之后就可以快速知道一段区间中两种性质的数字的个数情况

5.4935. 范围发现 - AcWing题库

关键点在于对前缀和进行排序,如此一来此时的s[i] - s[j - 1]代表的是|a[j] + ....... + a[i]|

6.5086. 第一个 - AcWing题库

给定一个范围,求出一个数组中所有满足和在这个区间内的子数组,可以通过双指针来实现,实际上也可以理解成三指针,第一个指针是我们枚举的子数组的起点i,第二个指针l满足pre[l] - pre[i - 1] >= L,第三个指针r满足pre[r] - pre[i - 1] <= R,如此一来对于起点i而言所有位于[l , r]区间内的点都可以作为终点满足与i构成一个合法子数组