一口气开了好多坑啊（
由于 whk 原因做题时间较少，故大概是周更 or 月更。
积土成山，风雨兴焉；积水成渊，蛟龙生焉。
二分专题
P1182
答案在数列最大值和数列所有数的和之间，所以二分答案，check 用前缀和优化一下。
CF1625A
将所有数都转换成二进制，对于 $x_i$，如果 $1$ 多，则 $y$ 该位取 $1$，反之取 $0$。
ABC217D
开个 set 存每个区间的左端点，修改直接插入，询问用 lower_bound 找，$r$ 就是 $x$ 所在区间右端点 $+1$，$x$ 所在区间的左端点就是 set 中 $r$ 的上一个数，长度就是 $r - l$。
P2920
二分答案，check 就是将初始时间定为休息时间，每次加上所需时间，如果超时就不合法。
ABC279D
P1638
对于一个合法区间，$r$ 增大时 $l$ 一定不会减小，然后就是双指针板子了。
ABC388E
二分答案，贪心一下显然是 $a_i$ 放在 $a_{n - ans + i}$ 上最优，所以 check 直接判断就行
POJ3685
题意
有一个 $n \times n$ 的方阵 $a$，$a_{i, j} = i ^ 2 + 100000 \times i + j ^ 2 - 100000 \times j + i \times j$，求该方阵的第 $k$ 小值。
Solution
二分套二分板子。
每一行每一列元素变化都是单调的，所以我们用第一重二分用于搜索每行第 $k$ 小的元素的值，对于每一个找到的值，再用一次二分用于检验该值是否是第 $k$ 小的元素。
第一重 check 显然是比该元素小的值是否小于k个。
第二重二分 check：对于每一列分别进行判断，在每一列中分别找到比当前元素的小的元素的个数并累加。总和即是第一重二分需要判断的比该元素小的元素的个数。
ABC374E
二分 $w$，check 按照贪心考虑，先买性价比高的机器，再用性价比低的机器逐个替换掉性价比高的机器，随便选个大数枚举性价比低的机器使用多少台，选小的作为答案。
POJ2976 / P10505
ABC373E
票数如果多于正确票数则一定有解，少于则一定无解，故二分正确票数。
先对每个人的当前票数从大到小排序，对于第 $i$ 个人，二分其需要增加的票数为 $k$，二分当前值在原序列中的位置，即找到一个合适的 $l$ 使 $A_l\le A_i+k$，$A_{l-1}>A_i+k$。
考虑如果想让第 $i$ 个人不上当选，则至少要让除第 $i$ 个人以外的前 $M$ 个人当选，可以使用前缀和计算。
需特判 $M=N$ ，全部输出 $0$ 即可。
POJ3579
题意
给出 $n$ 个数，要求将这 $n$ 个数两两相减，输出这些数排序后的中位数。
Solution
POJ3484 / SP4204
题意
给出一系列等差数列，给出第一项和最后一项和公差，这些等差数列中每个数出现的次数只有一个是奇数，找出这个数，并求出其出现的次数。
Solution
人类智慧。
枚举一个数的时候，求出小于等于这个数字的数有多少个：
如果是奇数个，说明该数 $\geq$ 解
如果是偶数，该数 $<$ 解
CF2009G1
POJ3662 / P1948
CF2026D
POJ3525 / UVA1396
POJ2018 / P10450
我们需要一个尽可能大的平均数，我们将这个平均数视为“基准”，或 $0$。然后我们将数列中的所有数减去“基准”，判断是否存在一个子段和非负且长度不小于 $L$ 的子段即可。
于是选择二分基准，check 函数中求前缀和，判断是否有一个长度为 $L$ 的区间满足要求即可。
最优化专题
P5062
优先吃最美味的食物，答案就是 $\max_{i = 1}^{n}{\frac{a_i^2}{i}}$
POJ1328 / UVA1193
首先将问题转化为区间选点：给出 $n$ 个区间，在 $x$ 轴上放置最少的点，使得每个区间至少含有一个点。
然后就把区间按左端点升序排序，能放则放，优先放右端点最小的。
P1007
两个人相遇转身分别转身，其实就等效于两个人穿过对方继续走，然后直接算就行。
CF1687A
$k \leq n$ 直接前缀和。
$k > n$ 贪心，前 $k - n + 1$ 分钟在一号点，剩下时间遍历一遍，正确性显然，求区间价值就是等差数列求和。
$$ \sum_{i = 1}^{n}{(k - i)} = \frac{(k - 1 + k - n)\times n}{2} $$
P1106
找到高峰就删。
正确性证明待补。
CF1646B
数组降序，大的给红色，小的给蓝色，让红比蓝少一个，讨论一下 $n$ 奇偶就做完了。
P4053
类似反悔贪心，优先修 ddl 靠前的，如果无法修理好，则取消修理时间最长的建筑，用优先队列实现。
POJ2586 / UVA10576
题意
已知一个公司的 $12$ 个月的账目，每个月有两种状态盈利 $s$ 或损失 $d$。现在只知道每连续五个月的收支状态都是相同的亏损（ $1−5 ， 2−6 ，\cdots ， 8−12$ 的收支总和相同），问公司最多可能有多大盈利。
Solution
由于每连续五个月的收支状态都是相同的亏损，设 1−5 月的收支分别为 $a,b,c,d,e$ ，那么 6−12 一定为 $a,b,c,d,e,a,b$ 。
枚举 $a$ 到 $e$ 为盈利还是亏损，找到符合条件的最大值即可。
CF2057B
统计有多少种不同的数，只要次数还没用完把这种数变成数量最多的那种数即可。
CF1772C
构造间隔为 $1, 2, 3, \cdots$ 的排列，超过 $n$ 了的话就将后面的间隔全部修改为 $1$ 即可。
CF1627B
枚举每个位置，求出离四个角落的距离，从小到大输出。
ABC281D
$f_{i, j, k}$ 表示前 $i$ 个数选了 $j$ 个，当前数的和对 $d$ 取模的值为 $k$ 的最大和。
转移方程如下
不选第 $i + 1$ 个数：
$$ f_{i + 1, j, k} = \max\{f_{i, j, k}\} $$
选第 $i + 1$ 个数：
$$ f_{i + 1, j + 1, (k + a_{i + 1})\bmod d} = \max\{f_{i, j, k} + a_{i + 1}\} $$
CF1675E
从前往后依次降成 $\texttt{a}$ 。
POJ3040 / P2376
尽量先用面值大的。
对于 $V_i < C$ 的部分，如果凑不够，就用第一个大于等于需要的面值的硬币凑。
CF1753A1
让相邻的两项两两配对。
$n$ 为奇数时显然无解。
$n$ 为偶数时，若相邻两项相同，可以直接将他们并入一个块中。若相邻两项不同，将他们分别并入两个不同的块中即可。在一个块中会这两项直接抵消，在不同块中也能恰好抵消。
POJ3190 / P2859
区间覆盖问题，按区间左端点排序，找右端点最靠左的，能加入当前调控系统就加，否则就新开一个。
实现用优先队列即可。