Po7ed's Blog

2024-10-13

Tasks

cdq 分治、扩欧拉。

Problems

概率、构造、Ad-hoc、数数。

P1397 [NOI2013] 矩阵游戏

一眼矩阵乘法。 $n,m$ 很大需要直接写快读，在快读里取模。但是矩阵的费马小定理比较奇怪。

P1545 [USACO04DEC] Dividing the Path G

又是线段树优化 dp。题面有点模糊不清。

设 $dp(i)$ 表示 $[1,i]$ 的答案， $dp(i)=\min_{j=i-2b}^{i-2a}dp(j)+1$ 。

对于每个奶牛的草区 $[S_i,E_i]$ ， $[S_i+1,E_i-1]$ 中的每个点都不能作为喷灌器覆盖区间的端点，标记这些点。我们可以总结出： $[l_1,r_1]$ 包含 $[l_2,r_2]$ 的充要条件为 $l_1<l_2\land r_2<r_1$ ，即 $l_1,r_1\notin [l_2+1,r_2-1]$ 。

依次枚举未被标记的点，线段树转移即可。

P1654 OSU!

期望好题，题解很有误导性，写的都很 rubbish。

三次方的期望可以用经典套路降幂。

考虑设 $f_3(i)$ 表示 $[1,i]$ 的答案（即连击次数的立方和的期望）， $f_2(i)$ 表示 $[1,i]$ 中后缀连击次数的平方的期望， $f_1(i)$ 表示 $[1,i]$ 中后缀连击次数的期望。注意「后缀」，也就是说 $f_1,f_2$ 所期望的连击是形如 $[j,i]$ （ $1\le j\le i\le n$ ）。 $f_3$ 则不同，下面的递推式可以看出区别。

\begin{aligned} f_1(i)&=\big(f_1(i-1)+1\big)\times p_i+{\color{blue}0}\times (1-p_i)\\ f_2(i)&=\big(f_2(i-1)+2f_1(i-1)+1\big)\times p_i+{\color{blue}0}\times (1-p_i)\\ f_3(i)&=\big(f_3(i-1)+3f_2(i-1)+3f_1(i-1)+1\big)\times p_i+{\color{red}f_3(i-1)}\times (1-p_i) \end{aligned}

相比之下， $f_3$ 有一个类似前缀和的累加。这是绝大多数题解没有提到的，或者直接化简，好看又难以真正理解。~~还有一堆灰蓝绿一遍过，他 * 的。~~

答案就是 $f_3(n)$ 。

P2424 约数和

约数和入门题。

显然要考虑求 $\sum_{i=1}^{n}\sigma(i)$ ，即约数和的前缀和。直接求是困难的，反过来考虑每个数对倍数的贡献。

$i$ 在 $[1,n]$ 内有 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 个倍数，每个倍数贡献 $i$ 的值，即 $i$ 的总贡献为 $\left\lfloor\dfrac{n}{i}\right\rfloor\times i$ 。转化为求

\sum_{i=1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor\times i

显然可以用数论分块 $O(\sqrt{V})$ 计算。

形式化的推式子：

\begin{aligned} \sum_{i=1}^{n}\sigma(i)&=\sum_{i=1}^{n}\sum_{j\mid i}j\\ &=\sum_{j=1}^{n}\sum_{j\mid i}j\\ &=\sum_{j=1}^{n}j\times \sum_{i=1}^{n}[j\mid i]\\ &=\sum_{j=1}^{n}j\times \left\lfloor\dfrac{n}{j}\right\rfloor\\ \end{aligned}

P2487 [SDOI2011] 拦截导弹

三维偏序 dp。设 $f_1(i),g_1(i)$ 分别表示 $[1,i]$ 中选，强制选 $i$ ，最大的数量和对应方案数。 $f_2,g_2$ 为后缀，同理。

f_1(i)=\max_{\substack{j<i\\h_j\ge h_i\\v_j\ge v_i}}\{f_1(j)\}+1

用 cdq 分治解决三维偏序，在分治过程中更新 $f,g$ 。正反做两遍 cdq。

ans=\max\{f_1(i)\},sum=\sum_{\mathclap{f_1(i)=ans}}g_1(i)\\ P_i=[f_1(i)+f_2(i)-1=ans]\times\dfrac{g_1(i)\times g_2(i)}{sum}

注意直接 dp 概率是不可行的，没有考虑后继路径的影响。

cdq 分治的顺序由题目决定，每道题的分治顺序可能不一样。同时可能需要添加额外的排序。

P5358 [SDOI2019] 快速查询

操作数 $qt$ 最大是 $10^7$ ，所以只能 $O(1)$ 处理每个操作。 $n$ 最大 $10^9$ ，所以不能保存每个数。操作只有单点、全局，考虑打标记。

考虑分成两类位置：平凡和非平凡。我们称一个位置是平凡的，当且仅当从上次全局赋值以来没有单点修改过。反之为非平凡的。不难发现，所有平凡位置上的数均相等，我们称其为平凡值。

我们使用 $fill$ 表示上次全局赋的值（初始为 $0$ ）， $mul$ 为乘法标记， $add$ 为加法标记。于是可以用 $fill\times mul+add$ 表示平凡值。这样就解决了平凡位置。

开一个哈希表（unordered_map） $imp$ ，存储非平凡位置上的值。一种常见的想法是：单点修改时直接令 $imp(p)\gets v$ 。但这样一来，如果后续有全局乘法或全局加法，无法快速更新 $imp$ 中的值。

解决方案也很简单，修改时令 $imp(p)\gets (v-add)\times mul^{-1}$ ，这样就可以满足 $imp(p)\times mul+add=v$ 。全局乘、加只需更新标记，访问非平凡位置上的值时，乘、加标记即可还原出真正的值。

为了全局求和，需要维护 $sum$ ，并在操作时更新。要特判全局乘以 $0$ 的情况。记得预处理逆元。

P6146 [USACO20FEB] Help Yourself G

以左端点排序，设 $1\dots i$ 的答案为 $f_i$ ，则第 $i$ 条线段有两种可能：

不取，复杂度之和仍为 $f_{i-1}$ ；
取，考虑哪些子集复杂度有变化（ $+1$ ）。显然，这些子集必须满足其中没有任何一个元素（线段）与第 $i$ 条线段相交。即这些子集必定是所有不与第 $i$ 条线段相交的线段（的集合）的子集。我们可以用前缀和求出右端点 $\le j$ 的线段数量 $s_j$ ，那么那些子集的数量即为 $2^{s(j)}$ 。每个子集贡献为 $1$ ，复杂度之和为 $f_{i-1}+2^{s(j)}$ 。

于是 $f_i=2f_{i-1}+2^{s(j)}$ ，递推计算即可。

P6649 「SWTR-5」Grid

可以发现对于每一行必然有：在这一行走到的最左边 $(i,j)$ ，走到下一行的位置 $(i,k)$ ，从上一行来到这一行的位置 $(i,l)$ ，同时 $j\le k\le l$ 。

考虑设 $dp(x,y)$ 表示现在在 $(x,y)$ 的最优解，发现无法转移：因为不知道第一次来该行的位置，可能走出不合法的路径。于是设 $dp(i,k)$ 表示现在在 $(i,k)$ 准备走到下一行，此时的最优解。求出最小子段和 $(i,j)\sim (i,k)=\sum_{o=j}^{k}a(i,o)$ ，同时计算向后的最小子段和 $(i,k)\sim (i,l)+dp=dp(i+1,l)+\sum_{o=k}^{l}a(i,o)$ 。相加即为答案。

P7074 [CSP-J 2020] 方格取数

只能考虑 dp。若设 $dp(i,j)$ 表示从 $(1,1)$ 走到 $(i,j)$ 的最大和，可以发现无法保证不重复，无法转移。

考虑再细分状态。发现如果从 $(i-1,j)$ 走到 $(i,j)$ ，则不能往回走。也就是说，状态可以保存来时的方向，这样就能保证不重复。具体看代码。

P7167 [eJOI2020 Day1] Fountain

可以发现流水的关系是一棵树，可以使用单调栈求出。问题即转化成跳多少次父亲，使得路径上水被消耗完。

暴力跳不行，考虑倍增。用倍增数组求出点 $i$ 向上跳 $2^j$ 步跳到哪个点、途中消耗水量。询问时直接从大到小尝试 $j$ 跳即可。细节小多。

P7402 [COCI2020-2021#5] Sjeckanje | 9019 #85587446. 传情伞（emotion）

很好想到线段树优化 ddp。区间加难以处理，考虑差分。

观察可以发现选的区间必然单调，否则可以拆成多个单调的区间，比原方案更优。

观察对应情况下差分数组上的情况。在原数组上最大化极差，在差分数组上对应类似最大子段和（差分值要取绝对值）。

case 1
id | 1 2 3 4| 5 6
a  | 1 1 4 5| 1 4
d  |   0 3 1|-4 3
       ~~~~~    ~
case 2
id | 1 2 3|4  5|6
a  | 1 1 4|5  1|4
d  |   0 3|1 -4|3
       ~~~   ~~

可以发现分割后的位置上的差分值不能取。因为它们跨块了。其他位置表示的是单调区间相邻两项的极差，故整个区间的极差为这些位置上的差分值之和。

设 $dp(l,r,i,j)$ 表示对于差分数组上的 $[l,r]$ ， $i$ 表示取不取左端点， $j$ 表示取不取右端点，二者均为合并服务。

mid=\dfrac{l+r}{2}\\ dp(l,r,i,j)= \begin{cases} dp(l,mid,i,1)+dp(mid+1,r,1,j)&\operatorname{sgn}(d_{mid})=\operatorname{sgn}(d_{mid+1})\iff a_{mid-1}<a_{mid}<a_{mid+1}\\ \max\big(dp(l,mid,i,0)+dp(mid+1,r,1,j),dp(l,mid,i,1)+dp(mid+1,r,1,0)\big)&\text{otherwise} \end{cases}

按上式在线段树上合并两个区间即可。

是不是要好好学一下 ddp。

P7913 [CSP-S 2021] 廊桥分配

先忽略廊桥数量的限制。维护一个空闲的廊桥队列，每到达一架航班，就给它安排编号最小的廊桥供其使用，求出每个廊桥停靠的飞机数 $cnt_i$ 。

加上廊桥数量的限制，可以发现直接就解决了问题。枚举国内分配几个，求出国际有几个。对廊桥停靠的飞机数前缀和 $s_i=\sum_{j=1}^{i}cnt_j$ ，代表停靠廊桥编号小于等于 $i$ 的飞机个数，也即分配 $i$ 个廊桥时停在廊桥的飞机数。国内、国际相加取最大值即为答案。

P7914 [CSP-S 2021] 括号序列

分讨区间 dp。注意方案数可能算重：一个方案被多次统计，要分类以避免。

P7915 [CSP-S 2021] 回文

可以发现如果第一次取出 $a$ 开头元素，则另一次出现该元素的位置一定是最后一个出队的，因为该元素需分别处于 $b$ 的开头、结尾来实现回文。取出 $a$ 结尾元素同理。

该元素另一个出现位置将 $a$ 划分为两个栈，栈底分别为上述位置的两侧。

具体来说，若有 $a_1=a_i$ ，则两个栈（栈底到栈顶）分别为：

$a_{i-1}\sim a_2$ ；
$a_{i+1}\sim a_n$ 。

若 $a_n=a_j$ 同理：

$a_{j-1}\sim a_1$ ；
$a_{j+1}\sim a_{n-1}$ 。

问题转化为：每次从两个栈顶中选一个出栈，放入 $b$ 末尾，使 $b$ 回文。

类似的，注意到如果取出了某个元素 $x$ ，则另一个 $x$ 必须最后一个出栈。即 $x$ 必须同时存在于栈顶和栈底（具体在哪个栈、是否在同一个栈并不重要）。这样，如果删去 $x$ 对最优解没有影响。

于是，可以将栈改为双端队列，只需寻找这样的 $x$ ，将它们两个同时出队，保存答案即可。如果找不到 $x$ 则无解。如果有多个 $x$ 取使字典序最小的。

第一个元素有两种取法，需分别求解。

P8675 [蓝桥杯 2018 国 B] 搭积木

对于每个方案，可以由 $(l_1,r_n)\dots,(l_n,r_n)$ 表示。 $l_i,r_i$ 分别表示第 $i$ 层的左右端点。

自然的 dp：设 $dp(i,l,r)$ 表示已摆了下面 $i$ 层，第 $i$ 层摆放为 $(l,r)$ 的方案数。转移方程：

dp(i,l,r)=\sum_{j=1}^{l}\sum_{k=r}^{m}dp(i-1,j,k)\qquad\text{（第 $i$ 层的 $[l,r]$ 没有 \texttt{X}）}

边界

dp(0,1,m)=1

答案即枚举搭 $i$ 层，累加即可。

ans=\sum_{i=0}^{n}\sum_{l=1}^{m}\sum_{r=l}^{m}dp(i,l,r)

注意 $i$ 从 $0$ 开始，即包括啥都不搭的方案。

代码实现略有不同。

P8815 [CSP-J 2022] 逻辑表达式

表达式求值，考虑栈模拟（其实没有栈）。

如果前面已经短路，
- 有左括号跳括号，跳完为止；
- 若为右括号，则短路结束；
- 如果为 0& 型短路且当前为 |，即 0&...|...，则有 0|...，短路结束；
- 反之为 1| 型短路且当前为 &，即 1|...&...，则无关紧要；
- 若 0& 型短路且当前为 &，即 0&...&...，直接丝滑小连招继续短路；
- 若 1| 型同理。
反之前面没有短路，则前面都没有影响，另起炉灶，
- 若遇到数，则将值暂时置为该数；
- 若有短路，则设置为相应短路状态。

P9209 不灭「不死鸟之尾」

最小化 $W_i-l\times L_i-r\times R_i$ 即最大化 $l\times L_i+r\times R_i$ 。当 $L_i\ge R_i$ 时发现应让 $l$ 尽量大，即放在最右边，反之亦然。故每次只可能停最左和最右边。故停第 $i$ 辆时，有 $\max l/r=n-i$ ，直接计算即可。

答案为

\begin{aligned} ans&=\sum_{i=1}^{n}W_i-(n-i)\times\max(L_i,R_i)-0\times\min(L_i,R_i)\\ &=\sum_{i=1}^{n}W_i-(n-i)\times\max(L_i,R_i) \end{aligned}

P9345 夕阳西下几时回

好题！

重要结论： $[1,n]$ 中任意两个不同的正整数的 $\gcd$ 最大为 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 。故 $\gcd$ 最多 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 个取值，即为 $k$ 的理论上界。

考虑如何构造达到此上界。由于结论中最极端的情况就是 $\gcd\left(\left\lfloor\dfrac{n}{2}\right\rfloor,2\left\lfloor\dfrac{n}{2}\right\rfloor\right)$ ，考虑对于任意 $i$ 向 $2i$ 连边，形成若干条链：

(1,2,4,\dots),(3,6,12,\dots),(5,10,20,\dots),\dots

这样就覆盖了所有可能的 $\gcd$ 值。如果 $k$ 没有达到上界，则舍弃后面的一些数

(1,n,(n−1),\dots,(2k+1)),(2,4,8,\dots),(3,6,12,\dots),(5,10,20,\dots),\dots

这样可以取到 $\forall 1\le i\le k,\gcd(i,2i)$ 。满足条件。

P9474 [yLOI2022] 长安幻世绘

显然存在 $O(n^2)$ 的暴力 dp 做法。

发现有 $12\%$ 的数据，保证 $a_i$ 单调递增，同时因为“不相邻”是一个相对弱的条件，考虑将 $a_i$ 排序（需保留原下标）。可以枚举左端点，求最靠左的右端点，使得区间中可以组成合法子序列。

容易发现右端点是单调的，即若 $l$ 的右端点为 $r$ ，则 $l+1$ 的右端点 $r'\ge r$ 。

接下来考虑怎样快速求一段区间能组成的最长合法子序列长度。如果从值下手，此题类似于最大的独立集问题（即有若干互不相同的元素，有若干条件诸如某两个元素不可在同一集合内，求最大的集合大小。可以抽象成图。），很难下手。不妨换个角度：直接将当前区间内所有元素按原下标填入一个新序列中。新序列可能有位置空出，也有若干连通块。设各连通块长度为 $L_i$ ，则最长合法子序列长度为

\sum_i\left\lceil\cfrac{L_i}{2}\right\rceil

例如：对于 $a=[1,5,0,9,4,8]$ ，排序后 $a'=[0,1,4,5,8,9]$ 。

对于 $a'$ 上区间 $[2,4]$ （即 $[1,4,5]$ ），以原下标填入 $b=[1,5,\ ,\ ,4,\ ]$ ，肉眼可见有两个连通块。第一个连通块可以选出 $\lceil 2/2\rceil=1$ 个数，第二个可以选出 $\lceil 1/2\rceil=1$ 个数，相加即为 $2$ 。

再比如区间 $[1,5]$ （ $[0,1,4,5,8]$ ），填入 $b=[1,5,0,\ ,4,8]$ ，最大长度为 $\lceil 3/2\rceil+\lceil 2/2\rceil=2+1=3$ 。

“填入序列”可以使用类似珂朵莉树（ODT）的方法，维护若干现有区间。移动左端点时即删除左端点，看情况缩小区间或分裂。移动右端点即添加新右端点，看情况扩大区间或合并即可。

P9594 「Daily OI Round 1」Memory

线段树优化 dp 好题！

题目中的条件是 $c_i=c_j$ （颜色相同）或 $[l_i,r_i]\cup [l_j,r_j]=\varnothing$ （不相交）。

可以先将线段按左端点排序，由于我们只关心颜色和相交情况，故可以设 $dp(r_i,c_i)$ 表示满足「选的线段中右端点最大的线段是 $i$ ，其右端点为 $r_i$ 颜色为 $c_i$ 」的权值和的最大值。

或是难以直接处理的，考虑拆成两种情况：必需满足颜色相同、必须满足不相交。

分别对应下面转移转移式中 $\max$ 的后两项：

dp(r_i,c_i)\gets\max\left\{dp(r_i,c_i),\,{\color{red}w_i+\max_{j=1}^{r_i}dp(j,c_i)},\,{\color{blue}w_i+\max_k\max_{j=1}^{l_i-1}dp(j,k)}\right\} \tag{1}

但这样无法解决包含的情况，所以：

\forall j>r_i,\,dp(j,c_i)\gets dp(j,c_i)+w_i \tag{2}

注意， $(2)$ 是在 $(1)$ 之前就完成了的。

不难发现 dp 的状态数是比较少的，只有 $O(m)$ 个，可以直接动态开点线段树维护。

$(1)$ 中红色转移、 $(2)$ 中的转移都不困难，分别区间查最大值和区间加即可。但是 $(1)$ 中蓝色转移需要两层 $\max$ ，无法遍历所有颜色，需要记录新增哪些颜色，一一取 $\max$ 。具体可以看代码。

问：为什么是按左端点排序？能按右端点排序吗？

答：因为左端点排序才能在可接受复杂度内完成蓝色转移，按右端点排序无法实现。

P9751 [CSP-J 2023] 旅游巴士

此题显然不是简单的最短路。去除“边出现时刻”的限制，我们假定现在所有边都存在。

可以发现，由于边权均为 $1$ ，最短路退化为 bfs。

同时由“ $k$ 的非负整数倍”这一表述（以及 $k\le 100$ 的小范围），注意到对于两个状态（路径），如果他们的长度（耗时）在模 $k$ 意义下同余，则它们重复了。即只需保留耗时更短的状态。因为对于耗时更长的状态，其接下来可能的行动都可以“移植”到耗时更短的状态上，从而被替代。

但是对于两个耗时在模 $k$ 意义下不同余的状态，若其中一个状态有解或无解，与另一状态无关。因为它们的余数不同，可行的路径或是否无解也不一定相同。

于是在 bfs 判重的 vis 数组中，需要新增一维属于模 $k$ 同余值。如果队头状态处于终点 $n$ ，且耗时为 $k$ 非负整数倍（即模 $k$ 余 $0$ ），则到达目标状态。

这相当于将每个点拆成 $k$ 个，分别表示余数。

接下来考虑“边出现时刻”的限制。

一个做法是二分开始时间，按条件 bfs，对每次的耗时取 $\min$ 。这样做正确性比较难证。

另一种做法是二分结束时间倒推。

更好的做法：发现能在起点等 $k$ 的非负整数倍相当于能在任意点等 $k$ 的非负整数倍。转移时若时间未到，直接在原地等 $k$ 的负整数倍时间直至可以通过。易证这样一定是最优的。注意到这样边权不全是 $1$ ，跑 Dijkstra 即可。

P10134 [USACO24JAN] Cowmpetency S

https://usaco.org/current/data/sol_prob1_silver_jan24.html

我们定义 $B(k)$ 为第一只严格大于前 $k$ 只牛分数的牛的下标。这很有用，因为 FJ 的记忆限制可以表述为 $B(a_i)=h_i$ 。为了简化公式，我们同时设 $pre_k=\max\limits_{1\le l\le k}c_l$ ，即前缀最大值。

对于 $B$ ，我们显然有

$pre_i=pre_{B(i)-1}$ ；
$c_{B(i)}>pre_i$ 。

对于 $\forall 1\le i<j<B(i)$ ，显然有 $B(i)=B(j)$ ，反之可以证明矛盾。故如果存在两个限制 $i,j$ ，满足 $a_i<a_j<B(a_i)\land B(a_i)\ne B(a_j)$ ，无解。综上所述，对于任意 $i\le j<B(i)=h_i$ ，我们可以得出 $B(j)$ 的值（为 $h_i$ ）。对于其他 $B(j)$ ，我们称它们未知。

这足以使我们得出一个贪心的算法：枚举 $i$ 从 $1$ 到 $n$ ，存储满足 $B(1)\dots B(i)$ 约束条件 $c_1\dots c_n$ 的最小值。

对于一个确定的 $i$ ，如果 $B(i)$ 未知，则无需操作。反之则有两种情况；

$pre_i=pre_{B(i)-1}$ ：可以发现这并没有对 $c_i$ 施加额外的约束，因此我们不必修改它。 $c_{B(i)}$ 有一个相关的变化，我们将在下一个情况后讨论。
反之 $pre_i<pre_{B(i)-1}$ $p r e_{i} < p r e_{B (i) - 1}$ ，我们需要找到一个 $j\le i$ $j \leq i$ 并将 $c_j$ $c_{j}$ 设为 $pre_{B(i)-1}$ $p r e_{B (i) - 1}$ 。但是，
- 首先 $j$ 需要尽可能大，且 $c_j$ 不能被题目给定。因为我们希望答案的字典序尽可能小。
- 其次不应存在 $k$ 使得 $j\le k\land B(k)<B(i)$ 。否则修改后 $pre_{B(i)-1}=c_j<c_{B(k)}\le pre_{B(i)-1}$ ，矛盾。
- 因此如果不存在满足上述二条件的 $j$ ，无解。

对于两种情况，我们都需要保证 $c_{B(i)}>pre_i$ 。若 $c_{B(i)}$ 没有给出，则可设为 $pre_i+1$ 。反之若 $c_{B(i)}$ 已经给出，我们需要保证它至少为此值（即满足 $c_{B(i)}>pre_i$ ）。若无法满足，无解。

这种算法之所以有效，是因为每增加一个约束条件，就只能产生一个等价或更大的词典序列。因此，通过在数组中尽可能靠后的位置进行修改，得到的序列就是词典最小序列。最后，只需遍历序列，确保所有值小于等于 $C$ ，以检查问题中的最后一个约束条件是否满足。

时间复杂度 $O(n^2)$ ：https://www.luogu.com.cn/record/164344021。考虑优化。

第一部分即填写 $B$ 可以使用双指针优化。具体的，枚举 $1\le i\le n$ ，维护 $j$ ，如果需要，则令 $j$ 从 $i+1$ 移动 $B(i)-1$ 填写。如果发现 $j$ 需要倒退并填写不同的值，则无解。

第二部分即构造 $c$ 。可以发现如果满足了 $B(i)$ 的条件，那么 $B(i+1),\dots,B(B(i)-1)$ 都可以跳过。于是我们有了时间复杂度 $O(n)$ 的算法：https://www.luogu.com.cn/record/165903355。

P10190 [USACO24FEB] Target Practice II S

https://usaco.org/current/data/sol_prob1_silver_feb24.html

首先可以发现右上角的顶点只能使用负斜率牛射，右下角的顶点只能用正斜率牛，反之会穿过目标内部。也就是说，我们至少分别需要 $n$ 值正、负斜率牛，否则无解。

剩下的 $2n$ 头牛分给左侧顶点。可以对左侧所有点按纵坐标排序，纵坐标大的分配负斜率牛，纵坐标小的分配正斜率牛。可以证明这样一定最优。

发现正斜率牛决定下界，负斜率牛决定上界。将两种牛（上界、下界）分开考虑。以下界为例，二分下界，求出每个点与下界连线的斜率，即射这个点的牛斜率必须不大于该值，反之会超出下界。将所有限制排序，与牛排序后斜率一一对应，若无法满足则当前下界不可取。反之可取。

P10309 「Cfz Round 2」Max of Distance

奇妙期望 + 构造题。

对于构造题，为减轻构造难度，一般构造 特殊的情况。

容易通过期望推出和，但是难以通过和推出每条边的边权。干脆设边权均为 $w$ 。当边权都为 $1$ 时，求出此时期望 $E_1$ 。那么我们有

\begin{aligned} E&\equiv E_1\times w\\ w&\equiv\times E_1^{-1} \end{aligned}\pmod P

若 $E_1\equiv 0\pmod P$ ，则不存在乘法逆元，需要特殊处理，很不优美，这里不讲。

P11036 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题

可以直接打表找规律。

当 $a$ 为奇数时，有 $b=1,c=2,d=a+2$ 。两边同乘 $\operatorname{lowbit}(a)$ 也成立，所以解决偶数。

[AGC005D] ~K Perm Counting | 9019 #85587454. 错排 (perm)

考虑容斥，拆完之后需要求对于任意 $0\le j\le n$ ，使得存在 $j$ 个位置满足 $|P_i-i|=k$ 的方案数。

相当于 $n\times n$ 的网格上，对于所有点形如 $(i,i+k),(i,i-k)$ 中选出 $j$ 个点不在同行同列。

限制转化为类似这样（ $n=5,k=1$ ），即 $(i,i+k),(i,i-k)$ 不能同时选， $(i,i+k),(i+2k,i-k)$ 也不能同时选。限制条件连成一条链，相邻节点不能同时选。染色后，类似于链森林版本的「没有上司的舞会」，我们可以求出选择的方案数。

demo

直接在网格上 dp 是困难的，必须将每条链拆开考虑（因为每条链上的点互不干扰）。

9019 #85587522. 「2024-10-12 联考」原神 (genshin)

神！分块 + 凸包。

首先对 $d$ 做前缀和 $s$ 。

考虑如何查询。将 $s_i$ 看做点 $i$ 的纵坐标， $m_i$ 看做点 $i$ 的横坐标，用一条斜率 $-v$ 的直线 $l$ 从第 $3$ 象限往第 $1$ 象限扫，扫到的第一个点即为（贡献了）答案。

为什么？ $l$ 的 $y$ 轴截距为 $s_i+m_iv$ ，正好为答案；扫描时 $y$ 轴截距不断增大，第一个扫到的答案就最小。

如何实现扫描？维护下凸包，扫描时二分凸包边的斜率，找到相切的那个点。

考虑修改。使用分块，每块维护一个凸包，单点修 $d_p\gets f$ 就是对 $[p,n]$ 的 $s$ 做区间加 $f-d_p$ 。单点修 $m_p\gets f$ 就暴力重构 $p$ 所在块的凸包。

求凸包使用 Graham 算法，单调栈维护边的斜率即可。

块长取 $\sqrt{n}$ ，总复杂度差不多 $O(n\log\sqrt{n}+q\sqrt{n}\log\sqrt{n})$ ，总之能过。

我家鸡子（Intel® Core™ i5-2400 CPU @ 3.10GHz）上跑了 10s 什么意思？！

#85587509. 数水果 (fruit)

可以发现题目要求 $dis(x,y)+dis(x,z)>dis(y,z)$ ，而显然有 $dis(x,y)+dis(x,z)\ge dis(y,z)$ ，故统计不合法的情况（即相等，又即在同一条链上），用所有方案减去不合法的即可。\xk

#85587510. 视频 (video)

破环为链，发现到达的点（可以看的视频）必然包括 $1$ ，即可以分成 $[n-l+1,n],[1,r+1]$ 这两个前缀、后缀的并。其中 $0\le l,r<n,\,r+1<n-l+1$ 。

将按按钮分为两类：移动和播放。移动次数显然是 $l+r+\min(l,r)$ ，即先「走短的一边，回来，走长的一边」。

剩下次数设为 $k=m-l-r-\min(l,r)$ ，用于播放。将视频 $i$ 视为 $m$ 个物品，第 $j$ 个物品代表播放第 $j$ 次的收益。对于一个前 / 后缀，我们只关心前 $k$ 大物品，故归并维护即可。注：std::merge() 好用！用 std::vector 存前 $k$ 大及其前缀和。

对每个前 / 后缀对应的前 $k$ 大物品做前缀和，因为降序排序后取前缀最优。

我们遍历每个 $r$ ，然后依次增加 $l$ 。设决策 $p,q$ 分别表示在前 / 后缀中取 $\cdot+1$ 个（为对应 std::vector 中下标）。增加 $l$ 时，前缀越来越优，尽可能缩减 $q$ 即可。但 $q$ 更优时增加 $q$ 。最后更新答案。

#85587511. 训练 (train)

容斥好题。