枚举#

时间复杂度 $O(n^2)$

枚举 $(i,j)$ 二元组，满足条件便累加

代码如下

暂无

二分#

时间复杂度 $O(logm)$

假设我们知道小明拥有的苹果数，想要尽可能小明拥有的苹果数多，那么其他的的苹果数就尽可能少，同时需要满足相邻编号的人苹果数最多相差 $1$。

根据贪心性质，小明最多，编号左右两边按 1 递减，就好像一个单峰（山峰）一样。比如，小明 k = 3, n = 4, （1 2 3 2 1）的数据呈现是一个单峰

另外要注意，如果递减的过程中发现会 $\le 0$，此时需要分配苹果数为 $1$ （满足最少分配一个苹果的条件）

同时，也可以发现一个性质，如果小明分配的苹果越多，通过这种方式分配，可能苹果数不够，而小明分配的苹果越少，那么最后需要的苹果数可能是小于等于总苹果数的，如果是小于，我们把剩余的苹果从端点慢慢开始分配即可。比如：（1 2 3 2 1）剩余 4 -> (2, 2, 3, 2, 1) 剩余 3 -> …… -> (2, 3, 3, 3, 2) 剩余 0

综上，得到一个结果，可以通过二分小明的苹果数量，范围为 $[1,m]$，然后计算一下通过贪心方式分配需要多少苹果，如果需要的苹果小于等于苹果总数，则舍弃左半区间，否则舍弃右半区间

代码如下

暂无

尺取#

时间复杂度 $O(n)$

从前往后扫描，设 $p$ 记录第 $0$ 个位置（下标从 $1$ 开始），或者当前遍历的位置，左边第一个 $d$ 的下标。设 $r,e$ 分别记录从 $p + 1$ 开始 $r,e$ 字符分别出现的最后位置。

如果当前 $r,e$ 字符全部遍历到了，并且没有遍历到 $d$，那么以当前下标为最后一个字符串的所有满足题意的连续字串数量为 $min(r,e) - p$

如果当前遍历到了 $d$，那么更新一下 $p, r, e$ 的值，因为后面的满足题意的字符一定不会包含当前字符。

代码如下

暂无

TIP

注意开 long

写在最后，题目不难，但是第二题第三题注意开 long