Creator's World

8.23

CF814C An impassioned circulation of affection

双指针。

我们先直接做个前缀和，然后对于每个询问，我们直接双指针。

CF1545B AquaMoon and Chess

组合计数。

我们发现两个 $1$ 是可以自由移动的，那么我们把自由移动的设为 $a$，$0$ 的个数为 $b$，答案为 $C_{a+b}^a$。

CF1547F Array Stabilization (GCD version)

线段树、二分。

容易发现做 $i$ 次，就是求 $i+1$ 个数的 $\gcd$，那么求区间 $\gcd$ 的话可以用线段树或 st 表，这里我们还要断环成链。同时我们要求最小次数，那么我们可以用二分。

CF1366D Two Divisors

其实开始想到了要求两个互质的质因数，不过似乎要用最小的质因数不断除掉原数。

CF1557D Ezzat and Grid

dp、set。

求最小删除个数，那么就是求最多留下的个数。设 $f_i$ 表示前 $i$ 行最多留下的个数，那么若 $i$ 和 $j$ 有相同的列都是 $1$，那么 $f_{i}=\max(f_i,f_j+1)$。直接转移的话要 $O(n^2)$，显然不能过。我们可以用 set 来优化。

CF1276B Two Fairs

$(a,b)$ 会把原图分成 $a$ 左边的点、$a$ 和 $b$ 中间的点、$b$ 右边的点，那么我们选 $u$ 就是选 $a$ 左边的点，选 $v$ 就是选 $b$ 右边的点，那么我们从 $a$ 开始 dfs 直到 $b$ 就结束，那么这时候标记的就是 $a$ 左边和中间的，同理我们从 $b$ 开始 dfs。那么根据乘法原理那么左边的乘以右边的即可。

8.22

CF1379C Choosing flowers

CF1370D Odd-Even Subsequence

二分。

看到这么一个式子一下子不知道怎么做，那么就仔细分析式子的本质。他要求奇数下标和偶数下标的最大值的最小值，因此我们只要最小化其中一个值就行了，那么直接分奇偶二分就行了。

CF1548B Integers Have Friends

二分、st 表、gcd。

转化题意：求 $a$ 所有子串中满足 $a_l\equiv a_{l+1}\equiv a_{l+2}\equiv \cdots \equiv a_{r} \bmod m$ 的最长长度。我们发现余数和模数我们都不知道，因此我们要去掉一个未知数，考虑做 $a$ 的差分数组，然后接下来就是找最长区间 $[l,r]$ 满足对于区间中的 $b_{i}$ 都满足 $m|b_i$。然后满足条件的区间是有单调性的，因此可以二分。而求区间 $gcd$ 我们可以用 $st$ 表来做。

8.20

CF643E Bear and Destroying Subtrees

期望、dp。

考虑dp，我们设 $f_{u,i}$ 表示以 $u$ 为根的子树期望最深深度小于等于 $i$ 的概率，考虑从 $u$ 的儿子 $v$ 转移，$u$ 到 $v$ 这条边有 $\frac{1}{2}$ 的概率断，有 $\frac{1}{2}$ 不断，断的话只对于 $v$ 这个儿子，最长链一定小于等于 $i$，否则的话就是 $f_{v,i-1}$，因此 $f_{u,i}=\prod_{v\in u's \ son} f_{v,i-1}+1$。然后发现 $f_{u,i}$ 只与 $f_{}$

CF1385E Directing Edges

拓扑排序。

题目要求最后是个有向无环图，那么应该要迅速想到拓扑排序。无解的情况就是原图就存在环的情况，这个可以在跑拓扑的过程中判断，然后在拓扑时给每个点打上拓扑序，那么有向无环图中的特点就是有向边的起点拓扑序比终点小，根据这个改变无向边。

CF1380D Berserk And Fireball

贪心。

首先显然有贪心的想法：选性价比最高的方法。那么先在 $a$ 中找出所有 $b$，然后直接枚举，每两个 $b$ 之间就是我们要消去的，设之间块的长度为 $len$，当 $len<k$ 的话一定不能用火球术，但也有可能无解：就是维护要删掉的数的最大值 $maxn$，当 $maxn>\max(a_i,a_last)$ 的话就不能用狂暴消完。当 $len>k$ 的话就比较性价比，直接做就行了。

8.19

CF1399E1 Weights Division (easy version)

贪心、堆、树、dfs。

首先我们分析一下根到所有叶子节点的距离和有什么构成，单独考虑每条边的贡献：等于其权值 $\times$ 其出现次数，这个可以通过 dfs 来处理，同时为了方便，我们可以将边转化为点（这种技巧之前也见过了）。接下来考虑怎么求最小操作数，显然有贪心策略：我们开个优先队列，每次操作会减少的权值是 $(val_i-val_2/2)\times num_i$ (这里把边转化到点上)，那我们每次都选减少的权值最大的来减少。

P5527 [Ynoi2012] NOIP2016 人生巅峰

二进制枚举、树状数组、倍增。

先简化题目：根据鸽巢原理，当区间子集个数大于最大贡献的时候一定有解，可以推出区间最长为 $13$。然后修改操作可以用倍增来做，区间修改可以用树状数组差分来做，最后我们直接枚举 $2^{r-l+1}$ 个集合，若有重复的就有解，不用担心重复，因为重复的话把重复部分剪掉就好了，算值的话用 lowbit。

AT4926 [AGC033C] Removing Coins

博弈论、树的直径。

在模拟赛中做到的，当时没有时间做，想了链的部分分其实就离正解很近了，只能说一定要安排好时间，题目一定要敢想，把能做的一定要做出来。首先链的情况，选择中间点会减少 $2$ 个点，选择端点会减少 $1$ 个点，那么就是经典的 sg 函数，直接递推转移即可。然后在树上的情况，发现最后留下来的就是最长的那条链，也就是树的直径，因此我们直接考虑直径就行了，直接判断直径长度即可。

8.18

$[P6116 [JOI 2019 Final]たのしいたのしいたのしい家庭菜園](https://www.luogu.com.cn/problem/P6116)$

dp。

看题目所求和数据范围都很像 dp。而像这种类型的题目我们之前做过，就是确定一个目标状态，然后给初始状态编号，然后求逆序对。我们设 $f_{i,j,k,0/1/2}$ 表示前面已经放了 $i$ 个 'R'，$j$ 个 'G'，$k$ 个 'Y'，当前这位放 'R'、'G'、'Y' 的最小操作数。那么我们先预处理出每个颜色在原状态中的位置，然后转移即可。

8.17

CF1555E Boring Segments

双指针、线段树。

题目要求线段的最大值和最小值的差最小，那么这东西想想似乎是有单调性的，那么尝试用双指针来做。那么怎么去考虑线段是否覆盖整个数轴呢？我们可以用线段树来维护区间加、区间取 $\min$，那样当 $[1,m]$ 的最小覆盖线段数为 $0$ 的话就是还没完全覆盖。

8.16

P2714 四元组统计

容斥。

求 $gcd=1$ 比较难，因此我们考虑容斥，求那些 $gcd\ne 1$ 的。我们 $gcd\ne 1$ 的话就是有共同的因数，我们直接从小到大枚举因数，然后组合计数算出贡献，同时要注意，算了一个因数后，他还要减掉它的倍数产生的贡献，避免重复计算。

P2163 [SHOI2007]园丁的烦恼

二维数点、树状数组。

$n,m\leq 5\times 10^5$，显然不能直接用二维前缀和来做，考虑别的方法。既然二维前缀和不行，那我们能不能通过一些方法将其变成一维前缀和。既然这么想了，我们怎么才能去掉一维的影响，其实很简单，我们先把所有树的坐标和询问的坐标都按 $x$ 轴从小到大排序后，那么我们就不用考虑 $x$ 的影响。为什么呢？因为从小到大排序后，后面的点的横坐标一定大于前面的点的，那么只需要计算有多少点的纵坐标也比这个点小就行了。而这样的操作我们可以用树状数组来做。

8.15

CF1428F Fruit Sequences

我们考虑每一位左端点对答案产生的贡献：若第 $i$ 是 $0$ 位的话那么不会产生贡献；若第 $i$ 位是 $1$ 的话，设从第 $i$ 位到该连通块末尾长度为 $len$，那么考虑对那些右端点会产生影响，显然是那些长度小于 $len$ 的贡献会加 $1$，因此直接从后往前模拟就行了。

CF1552D Array Differentiation

dfs、图论。

我们发现可以把题意简化为：可以将 $a$ 中的一些元素取反后使得能在 $a$ 中选出一个子集满足子集和为 $0$，直接 dfs 即可。

因为我们只考虑 $a_1\sim a_{n-1}$ 的话非常简单，只要让 $b_{i+1}=b_i+a_i$ 即可。那么若有一段 $\sum_{i=l}^r a_i=a_n$ 的话，那么 $b_r-b_{l-1}=a_n$，也就是 $b_{l-1}-b_r=-a_n$，其实就是求一个边权和为 $0$ 的环。

AT4826 [ABC160F] Distributing Integers

树上拓扑、换根 dp。

因为一个点能填的前提是这个点的所有父亲节点都填过了，那么显然是一个拓扑排序的 dfs 序。关于树上拓扑方案计数，有公式 $\frac{n!}{\prod size_u}$，那么只要求 $\prod size_u$ 即可，那么这就是一个经典的换根 dp，设 $f_i$ 表示 $i$ 为根时 $\prod size_u$ 的值。那么先令 $f_1$ 为所有 $size$ 的乘积，然后根据 $f_{u}=f_{fa} \times \frac{n-siz_u}{siz_u}$。

CF1552C Maximize the Intersections

贪心。

我们考虑怎么连弦使得它们的交点最多，显然每个点 $i$ 连上 $i + n$ 后交点是最多的，为什么呢？因为交换两条弦后发现交点数只会更少。那么把还没连的点按顺序编号，再像上面那样连边就行了。然后再依次判断是否相交就行了。

AT5312 [ABC156E] Roaming

组合计数。

我们发现动来动去的非常麻烦，因为一个人走后可能有人走来代替他。我们从别的角度来考虑，发现最后一定只有 $i$ 个房间有人，那么一定移动了 $n-i$ 次，那么若 $n-i\leq m$ 那它会对答案产生贡献。那么有 $n$ 个人要分给 $i$ 个房间，那么可以用隔板法得到贡献为 $C_{n-1,i-1}$。那么 $ans=\sum_{i=1}^n C_{n,i}\times C_{n-1,i-1}$。

CF1557B Moamen and k-subarrays

离散化。

我们发现我们只关心它们的相对大小关系，并不在意其具体大小，因此我们把原序列进行离散化，然后我们发现连续的我们就把它们分在同一个数组中。

CF1557C Moamen and XOR

位运算、计数。

首先明确位运算的性质。与：这一位为 $1$ 仅当所有数这一位都是 $1$，否则为 $0$。异或：这一位为 $1$ 仅当有计数个数这一位为 $1$，否则为 $0$。

$k$ 其实就是最终有 $k$ 位。设 $n$ 个数与起来的答案为 $sum_1$，异或起来的答案为 $sum_2$，要求 $sum_1\geq sum_2$，那我们开始分类讨论：

1. 若 $sum_1=sum_2$。

   那么 $sum_1$ 和 $sum_2$ 的每一位都相同，考虑第 $i$ 位为 $0$，仅当 $n$ 个数中至少有一个这一位为 $0$，且 $1$ 的个数为偶数，那么贡献就是 $C_{n}^i(0\leq i< n,i \mod 2 = 0)$；若第 $i$ 位为 $1$，仅当所有数这一位都是 $1$，且 $n$ 为奇数，对答案贡献为 $1$。

2. 若 $sum_1 > sum_2$。

   这意味着有一位 $i$ 满足前 $i-1$ 位 $sum_1$ 和 $sum_2$ 都相同，$sum_1$ 第 $i$ 位为 $1$，$sum_2$ 这一位为 $0$，后面就随便了。这种情况只有在 $n$ 为偶数才有可能。然后乘法原理计算贡献即可。

7.22

CF437B The Child and Set

贪心、位运算。

首先知道任何一个数都是可以表示为若干个二次幂的和的形式。然后我们可以贪心的考虑，从 $limit\sim 1$，若当前数的 lowbit 小于等于当前的 sum，那么直接选它，sum 减去这个 lowbit。最后若有剩余的话则无解。为什么呢？因此 lowbit 是有重复的，因此对于一个高位的我们一定要取它，否则的话要用两个比它低一位的才能造成同样效果。

7.21

CF1223D Sequence Sorting

dp。

如果实在想不出来什么东西的话，考虑 dp 也是可行的。

设 $f_{i,0/1/2}$ 表示前 $i-1$ 小的数都排好了，第 $i$ 小的数不动/向前/向后的最小操作数。

接下来分析转移：

$f_{i,0}$：第 $i$ 小的数不动的话，若 $i-1$ 和它有交叉，那么 $i-1$ 一定要向前移，否则的话 $i-1$ 不动/向前都行，因此

$f_{i,0}=f_{i-1,1}(\text{i和i-1相交})$

$f_{i,0}=\min(f_{i-1,0},f_{i-1,1})(\text{i和i-1不相交})$

$f_{i,1}$：第 $i$ 个向前，那么 $i-1$ 一定也要向前，因此

$f_{i,1}=f_{i-1,1}+1$

$f_{i,2}$：第 $i$ 个向后，那么 $i-1$ 随便怎样都行，因此

$f_{i,2}=\min(f_{i-1,0},f_{i-1,1},f_{i-1,2})+1$

7.20

CF1280B Beingawesomeism

题目要求把所有字符变为 A，那么显然只与 A 有关与 P 无关，那么接下来思考 A 在什么位置使得答案是多少。我们分类讨论：

• 答案为 $0$

  所有字符都是 A。

• 答案为 $1$

  有一条边全部都是 A，只要刷一下就行了。

• 答案为 $2$

  边角有一个 A，移动一下变成有一条边全是 A。

• 答案为 $3$

  边上有 A，移动到边角变成上一个情况。

• 答案为 $4$

  有一个 A，移动到边上变成上面的情况。

7.19

CF358D Dima and Hares

dp。

本题的 dp 思路非常有趣，一开始看下去发现取当前的物品会影响到后面的决策，因此不太好转移。

CF543A Writing Code

dp、背包。

设 $f_{i,j}$ 表示前 $i$ 行代码出现 $j$ 个 bug 的方案数，然后依次枚举行数、程序员、bug 数跑完全背包就行了。写完后一测，怎么错了？读题，“两个方案不同当且仅当某个程序员编写的行数不同”，因此我们不能把行数放在一开始枚举，这样的话会造成同一个程序员写同样代码，仅因为位置不同而被重复计算，把行数放在最里面枚举就行了。

7.18

CF917A The Monster

我们可以直接枚举左右端点，并通过左右括号以及问号的个数来判断该区间是否满足条件。设左括号有 $l$ 个，右括号有 $r$ 个，问号有 $q$ 个，显然若 $l+q<r$ 该区间不行，同理 $r+q<l$ 也不行。

CF914C Travelling Salesman and Special Numbers

dp。

7.17

CF1065F Up and Down the Tree

树形 dp。

我们发现跳到叶子后能不能回来会影响答案，因此我们设 $f_{i,0/1}$ 表示从 $i$ 往下走最后回到/不回到 $i$ 的最大价值。考虑转移，从 $u$ 往下走到 $v$，若 $v$ 能到 $u$ 及以上的话 $f_{u,0}+=f_{v,0}$。考虑 $f_{u,1}$ 怎么转移，显然 $f_{u,1}$ 可以直接加上 $f_{u,0}$，再考虑从 $u$ 的子树中转移，若 $v$ 能到 $u$ 及以上，那么 $v$ 剩下的价值为 $f_{v,1}-f_{v,0}$；否则的话，$f_{u,1}$ 加上 $f_{v,1}$。

CF1083A The Fair Nut and the Best Path

树形 dp。

我们设 $f_{i,0/1}$ 表示 $i$ 节点作为路径中间点和两个端点的最大收益值，因为每个点只能经过一次，因此作为中间点的 $f_{i,0}$ 从子树中的最大值和次大值转移而来，作为端点的 $f_{i,1}$ 从子树中的最大值转移而来。因为中途不能有负数，因此 $maxn1$ 和 $maxn2$ 初始值都设为 $0$ 即可。

CF933A A Twisty Movement

dp。

因为题目中只有 $1$ 和 $2$ 两个数，那么我们发现答案一定是形如 $[1,1,1,\cdots],[2,2,2,\cdots],[1,1,1,\cdots],[2,2,2,\cdots]$ 然后翻转第二段和第三段构成答案。因此我们设 $f_{i}$ 表示当前到第 $i$ 段的最长长度，那么有以下转移

$f_1=f_1+1 \ (s_i=1)$

$f_2=\max(f_1,f_2+1 \ (s_i=2))$

$f_3=\max(f_2,f_3+1 \ (s_i=1))$

$f_4=\max(f_3,f_4+1 \ (s_i=2))$

7.16

CF958C3 Encryption (hard)

dp。

一开始想到个很显然的 dp：设 $f_{i,j}$ 表示前 $i$ 个数分成 $j$ 组的最小价值，那么转移的话我们枚举上一组的结束点 $k$，则方程为

$f_{i,j} = \min(f_{i,j}, f_{k,j-1}+(sum_{i}-sum_{k})\bmod p)$

时间复杂度为 $O(n^2k)$，然后考虑优化。

我们发现对于 $f_{i,j}$ 是要用 $f_{k,j-1}$ 中最小的那个来更新，因此我们直接在枚举 $i$ 的时候我们维护最小值 $minn$ 和下标 $id$，直接更新就行了，时间复杂度为 $O(nk)$。

7.15

CF1096D Easy Problem

dp。

很显然的 dp，设 $f_{i,j}$ 表示让前 $i$ 个字符不出现 "hard" 的前 $j$ 个字符的最小代价，那么答案就是 $f_{n,4}$。转移的话，对于所有 $j$，都有 $f_{i,j}=f_{i-1,j}$。然后因为不出现前 $j$ 个字符只要让前 $j$ 个字符中没有其中一个就行了，因此根据当前 $s_i$ 等于什么来转移。

7.14

CF1290B Irreducible Anagrams

思维、性质。

当 $l=r$ 时一定是 "Yes"。

当 $s_l\ne s_r$ 时一定是 "Yes"。因为设 $s_l=x$，$s_r=y$，我们把所有的 $y$ 放到最前面，所有的 $x$ 放到最后面，一定满足条件。

当 $l\sim r$ 之间有三种及以上个不同字符时一定是 "Yes"。因为 保证有 $s_l=s_r=x$，又有两种字符 $y,z$，那把所有的 $y$ 放最前面，所有的 $z$ 放最后面一定满足条件。

7.13

CF1286B Numbers on Tree

构造、树形结构。

考虑无解的情况，发现若对于一个节点 $i$ 来说，若它的 $size_i>c_i$ 的话一定没有解。否则的话构造一个没有重复权值的要比有重复权值的要更容易合法，因此我们构造一个权值是排列的方案。然后就 dfs 遍历树上的每一个节点，对于 $a_i$，它满足比 $a_i$ 小的还没出现的数等于 $c_i$，因为出现过的都在它上面，没出现的都在下面，可以满足条件。

CF1283D Christmas Trees

一开始想法是用个优先队列存每个点的位置和离最近圣诞树的距离，结果发现里最近圣诞树的距离要用类似最短的方法用个 $dis$ 数组来维护，那这样也不用优先队列，因为队列本身满足单调性，用普通的就好了。

7.12

CF1534F1 Falling Sand (Easy Version)

tarjan。

很容易就发现这似乎是道图论题，将每块沙和它掉落时会影响的沙都连条边，然后发现可能有环，就跑 tarjan 缩点后统计入度为 $0$ 的点的个数就行了。不过连边的过程有点麻烦，它上面的、下面的、左边的、右边的都需要考虑，细心连就好了。

7.7

CF1536C Diluc and Kaeya

我们发现若 $s=s_1+s_2$，我们可以得出下面的推论：

$n_{s_1}(D):n_{s}(K)=n_{s_1}(D):n_{s_2}(K)$

因此我们用 map 维护 $n(D)/n(K)$ 的比值出现个数即可。

CF1538F Interesting Function

有个很显然的想法，我们从低位到高位一次计算贡献即可，统计进位。

CF1299B Aerodynamic

计算几何。

我们会发现题目就是让我们判断给出图形是不是偶数边的中心对称图形。如何判断中心对称图形呢？每一个点和它对应点的中点都相同，每个点和它对应点相差 $n/2$ 个点。

CF1296E2 String Coloring (hard version)

dp。

像这种交换邻项元素的我们肯定会想到逆序对，我们发现每一对逆序对它们的颜色一定不同。我们可以把这个转化为另一个模型：将原序列分成多个最长下降子序列，求最小分成几个。直接 dp 即可。

7.6

[CF1304D Shortest and Longest LIS](https://www.luogu.com.cn/problem/CF1304D

构造。

首先考虑最短的 LIS：连续的 '<' 是 LIS 的下限，我们为了让 LIS 最小，尽量让大的在前面；再考虑最长的 LIS，我们发现 '>' 会减少 LIS，我们为了让 LIS 最大，尽量让小的在前面。

CF1316C Primitive Primes

它这个卷积我就看不懂了……不过似乎就是找到一个与它互质的数，加上一个和它不互质的数一定与它互质。

P4138 [JOISC2014] 挂饰

背包。

我们会发现有些我们是一定要拿的，有些是是一定不拿的，剩下就只有有挂钩但权值为负的、没挂勾但权值为正的，我们背包选到特定挂钩的最大权值，然后就可以做了。

7.5

CF1334D Minimum Euler Cycle

欧拉回路。

当我们没有思路的时候，一定要去打暴力，可以为正解提供思路。当把一些回路输出来之后我们可以发现规律：回路是形如 $1,2,1,3,1,4,\cdots,1,n-1,2,3,2,4,2,n-1,\cdots$，然后根据规律打就好了。

CF1328D Carousel

构造、贪心。

我们发现颜色最多只用涂三种。但所有点类型都相同时，只用涂一种。当 $n$ 是偶数时交替涂 $1$ 和 $2$ 就行了。还有若中间有相同的，我们从中间断环成链，把后面的颜色都翻一下，也可以只用两种颜色涂完。否则的话，那就只能用三种颜色了，把最后一个涂成 $3$。

CF1327E Count The Blocks

组合计数。

就是一道计算贡献的题目。考虑长度为 $i$ 的块在左右两边的话，那么首先自己有 $10$ 种可能，而相邻的只能选 $9$ 种，剩下的 $n-i+1$ 个随便选，就是 $10^{n-i+1}$，所以这部分的贡献就是 $2\times 10 \times 9 \times 10^{n-i+1}$。再考虑长度为 $i$ 的块在中间的话，块的起始点一共有 $n-i-1$ 种可能，自己有 $10$ 种可能，相邻两个只有 $9$ 种可能，剩下 $n-i-2$ 中随便选，那么这部分的贡献就是 $(n-i-1)\times 10 \times 9 \times 9 \times 10^{n-i-2}$。

P3079 [USACO13MAR]Farm Painting S

我用暴力勉强过了……正解似乎要用什么 cdq 分治，之后再说吧。

7.4

CF1335E1 Three Blocks Palindrome (easy version)

前缀和。

直接前缀和记录出现次数，然后发现 $a_i$ 很小，我们考虑枚举 $a_i$ 为中间的最大值。

CF1338B Edge Weight Assignment

贪心、树。

首先最小的话显然若都是偶数只用一种就行了，否则的话需要用三种。至于最大的话，我们发现若几个叶子节点它们的父亲相同，那么它们连向父亲的边权一定相同。

CF1355C Count Triangles

差分。

本题就是不断优化。$n^3$：直接枚举三条边统计合法的答案。$n^2$：枚举两条边就行了，然后开个桶记录一下，最后算答案。$n$：发现是一个区间在移动，那么差分一下最后统计答案。

CF1367D Task On The Board

构造、贪心。

首先发现为 $0$ 的那个填最大的一定没问题，然后一直这样做下去就行了。

CF1381B Unmerge

性质、背包。

现在我很纠结，在思考问题本质和找规律中我似乎无法平衡，只能说在充分思考本质后再找规律吧。思考半天想不出来，但是找规律发现对于 $a_i$ 来说，一直到后面第一个大于它的数之前这一段，一定是在同一个排列中的，那么我们找出这些段，然后用背包判断能否刚好填满即可。不过其实自己还是想到这方面的，但是没有敢确定这点性质。

CF460C Present

二分。

看到最大化最小值就想到二分，关键是我们怎么判断我们二分的值 $mid$ 是否符合条件。首先贪心的思想，我们要让小于 $mid$ 的值都要至少等于 $mid$，那么我们从前往后扫，对于小于 $mid$ 我们都要进行数次洒使得它等于 $mid$。不过因为洒的是一个区间，我们还要维护一下区间洒了多少，就不用多洒了。维护一个 $num$，表示剩下的洒的次数，若在中途出现 $num < 0$，$mid$ 就不合法。

7.3

CF1408D Searchlights

dp。

因为所有海盗是一起移动的，我们设 $f_i$ 表示所有海盗向上 $i$ 步后最少向右移动几步，然后从大到小枚举同时维护后缀最大值 $maxn$，答案就是 $\min(i+maxn)$，因为这样才能保证所有的海盗都脱离。

CF1401D Maximum Distributed Tree

dfs、贪心。

像这种求 $\sum f_{i,j}$ 的题目的套路一定要记住！一般都是转化为求单条边的贡献，每条边被计算的次数是 $size_u\times (n-size_u)$。然后就是很套路的，大的值乘上大的值一定最大，那么就从小到大匹配就行了。至于 $m> n$ 的情况，多的都乘到 $p_n$ 就行了。

CF1329A Dreamoon Likes Coloring

构造、贪心。

首先我们可以假设所有颜色都铺满，若这时候还是小于 $n$ 那么无解。否则的话我们我们需要通过调整颜色使得每个颜色至少出现一次以及刚好铺满 $n$，那么我们计算总和和 $n$ 的差值，然后考虑每一个颜色都调整即可。

CF1400D Zigzags

前缀和。

看范围知道复杂度最多是 $O(n^2)$，那么显然是让我们枚举两个东西，然后剩下的可以直接 $O(1)$ 求。发现我们只能去枚举 $j,k$ 这样我们既可以知道 $a_i,a_l$ 的值，同时也知道它们的范围，那么直接前缀和维护一下就好了，然后乘法原理统计答案。

T183639 操作（2021 CoE III A）

贪心。

简单贪心，显然逮着最小的那个一直减是最优的，因为这样异或出来加上的就是 $0$。然后判一下无解的情况就好了。