补丁

♿蓝题思路概括♿

#1 P1074

#2 P1120

1. 长的先放，因为长的留到后面更不好放
2. 如果某个木棍放在目前位置不行，那么所有长度和它相等的也不行（可以加“当前弧优化”）

#3 P1262

#4 P1272

#5 P1278

#6 P1343

#7 P1350

#8 P1412

#9 P1437

#10 P1450

#11 P1463

1. 质因数指数不升（否则可以将大的指数交换到小的质因子上，以获得更小的大小和不变的因数个数）
2. 质因数使用连续（同理，否则可以移到更小的质因数上）

#12 P1491

#13 P1640

#14 P1879

#15 P1896

#16 P1950

#17 P1966

#18 P2034

#19 P2055

#20 P2272

#21 P2107

#22 P2158

#23 P2205

#24 P2202

#25 P2290

#26 P2303

#27 P2491

#28 P2512

#29 P2518

#30 P2520

#31 P2567

1. 是别的幸运数字倍数的幸运数字不用算
2. 目前搜到的$lcm$超出了就不用继续算
3. 可以降序幸运数字，使得$lcm$能更快超越限制。

#32 P2569

朴素转移

1. 何もしないで，$f_{i, j} = f_{i - 1, j}$
2. 买入。$f_{i, j} = \max\limits_{k \in [j - AS_i, j)} f_{i - W, k} - (j - k) \times AP_i$
3. 卖出。$f_{i, j} = \max\limits_{k \in (j, j + BS_i]} f_{i - W, k} + (k - j) \times BP_i$

单调队列优化

#33 P3942

#34 P2657

#35 P2680

#36 P2698

#37 P2704

#38 P2740

#39 P2751

#38 P1471

#39 P2831

#40 P2860

#41 P2882

#42 P2915

#43 P3017

#44 P3066

#45 P3072

#46 P3076

#47 P3118

#48 P3119

#49 P3155

#50 P3177

#51 P3225

1. 图是一条链：建两个，方案数为$\frac{n(n-1)} 2$
2. 图是一个巨大的点双：建两个，$\frac{n(n-1)} 2$

#52 P3365

#53 P3469

#54 P3694

#55 P3857

#56 P3966

#57 P4090

#58 P4145

#59 CF438D

#60 CF165E

#61 P4185

#62 P4186

#63 P4188

#64 P4180

#65 P4269

#66 P4268

#67 P4281

#68 P4380

#69 P4377

#70 P4376

#71 P4408

#72 P4513

#73 P4550

#74 P4910

\begin{bmatrix} f_{n, 0} & f_{n,1} \end{bmatrix} = \begin{bmatrix} f_{1, 0} & f_{1,1} \end{bmatrix} \times \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} ^ {n - 1}$$ 最后的答案为$f_{n+1,0}+f_{n+1,1}$ ### #75 P5058 缩vDCC。从$a$开始dfs。若找到一个割点$p$，且其一个子节点$v$满足$dfn_v \le dfn_b$，则可以说明$b$在$v$的子树里。 下面考虑反证。假设$b$不在$v$子树里： 1. 若$b$先于$v$搜到，则与 $dfn_v \le dfn_b$ 矛盾。 2. 若$b$在$v$子树被搜完以后搜到，则此时 $dfn_b$ 仍然为$0$，同样与 $dfn_v \le dfn_b$ 矛盾。 ### #76 P5122 巧妙的图论建模题 先以$n$为源点跑一次最短路，记$n$到点$p$的距离为$dis_p$ 考虑建一个虚点$n+1$，将$k$个有干草块的点$p$与$n+1$连边一条长为$dis_p - y_p$的边。再以$n+1$为源点跑一次最短路。若此时到点$i$的距离不大于原来的距离，则证明$i$会去某个干草块觅食。 ### #77 P5123 bitset作法。 可以用bitset记录喜欢冰激凌$x$的牛的集合$S_x$。对于某个牛$i$,和它不能和平相处的牛的个数即为: $$\overline {\bigcup\limits_{j\in[1,5]} S_{a_{i,j}}}$$ ### #78 P5505 组合数学+容斥 计数难点在于“需要保证所有人都有特产”。 我们先考虑一下如果没有“所有人都要有特产”这条限制该怎么做。 我们可以依次把$a_{1 \dots m}$分给$n$个人（允许为空）。则插板法可做。 现在我们考虑设$f_i$为至少有$i$个人拿不到特产的方案数。考虑这也比较好算，我们直接少$i$个板子就好了。有： $$f_i = \prod\limits_{j \in [1,m]} \binom{a_j + n - i - 1}{n - i - 1}$$ 设$g_i$为正好有$i$个人拿不到特产的方案数。那么有了$f_i$这就可以容斥了。 $$g_i = \sum\limits_{j\in [i, n]} (-1)^{j - i} f_j$$ 最后的答案就是$g_0$ ### #79 P5521 首先考虑为什么DP不行：子树之间的答案不是独立的。一个子树剩下的花可以用于别的子树。所以一个子树的答案是依赖于先于它的子树的答案的。转移会有后效性，于是DP就被毙掉了。 根据上面我们对问题的分析，可以发现将每个子节点放上花的花费是和解决子节点的顺序相关的。记$f_u$为将$u$放上$w_u$朵花的费用，则可以给出如下式子： $$f_u = \max\{\max\limits_{v\in son_u}\{f_v + \sum\limits_{k\in son_u, k先于v} w_k \}, \sum\limits_{v\in son_u} w_v \}$$ 所以我们需要确定一个$v$的顺序使得$\max\limits_{v\in son_u}\{f_v + \sum\limits_{k\in son_u, k先于v} w_k \}$最小。 考察两个$u$的子节点$x,y$，现在考虑若$x,y$相邻，哪个放在前面。记$x,y$前的子节点$w$值之和为$s$ $x$在前时，这两个点的贡献是$\max\{f_x + s, f_y + s + w_x\}$ 同理，$y$在前时这两个点贡献是$\max\{f_y + s, f_x + s + w_y\}$ 若$x$在前，则需满足: $$\max\{f_x + s, f_y + s + w_x\} \le \max\{f_y + s, f_x + s + w_y\}$$ 两边同时消去$s$得： $$\max\{f_x, f_y + w_x \} \le \max\{f_y, f_x + w_y \}$$ 考虑有$f_x + w_y > f_x$，故只需$f_x + w_y > f_y + w_x$，即$f_x - w_x > f_y - w_y$即可 所以所有节点按照$f_x - w_x$降序，即可得到最优序列。 ### #80 P5664 容斥+DP 发表一下感言。其实计数问题没有那么难，要抓住导致直接计数难算的关键矛盾。 比如说这道题：如果没有每列不能选超过$\lfloor \frac k 2 \rfloor$个这个限制，就很好算了。 我们先考虑把这种情况算出来再容斥。记$f_{i,j}$为在前$i$行选$j$个菜做的方案数。则有转移： $$f_{i, j + 1} = f_{i - 1,j} + \sum\limits_{l\in [1, m]} a_{i,l}$$ 注意到$\lfloor \frac k 2 \rfloor$这个限制，注定了**只能有一列超限**。我们可以枚举这个超限的列$p$。记$g_{i,d}$为前$i$行中在第$p$列中选出的比在别的列选出的多$d$的方案数。则有转移 $$g_{i,d} = g_{i - 1,d} + g_{i - 1, d + 1} + \sum\limits_{l\in [1, m], l \neq p} a_i,l + g_{i - 1, d - 1} + a_{i,p}$$ 则$p$超限的方案数和为$\sum\limits_{l\in[0,n]} g_{n,l}$ 从$\sum\limits_{l \in [1, n]}f_{n,l}$中刨掉即可。 ### #81 P2748 ### #82 P6268 将跳过舞的人建边并染色，建出二分图。答案即为二分图最大独立集大小。考虑独立集中不能存在任意两个可以匹配的点。所以有最大独立集 = 点数 - 最大匹配边数 ### #83 P6554 ### #84 P6475 考虑如果一段楼高不降/不增，并且最高和最低的楼确定，那么方案数可以简单插板计算。 讨论$x,y$是否在$n$的同侧。分别计算即可（） 实际上可以是高考题 ### #85 P7077 因为没有递归，故函数调用关系成一个DAG。可以将全局乘法转换为**将所有已调用过的加法函数调用次数翻倍**。 故可以先在反图上拓扑，求出每个函数调用后会使全局乘法标签翻多少倍。 然后在正图上拓扑，求出每个加法函数的调用次数。 大体思路是这样的，然而代码比较难写（ ### #86 P7687 缩eDCC。考虑一条边$u\rightarrow v$如果是关键的，那么必然会出现$v$子树中的所有点或$v$子树外的所有点将所有提供A/B服务的点独占的情况。求割边时判断一下即可。 ## ♿紫题思路概括♿ ### #1 P1848 动态规划优化DP。 可以给出naive的转移： $$f_i = \min\limits_{\sum\limits_{l \in (j, i]} w_l \le L} (f_j + \max\limits_{l\in(j,i]}h_l)$$ 发现$\min$中和$i$有关的项可以被线段树维护。具体方法为：用单调栈维护$i$左侧第一个$j$满足$h_j > h_i$。加入$h_i$时将$(j,i]$区间赋值为$h_i$，就可以维护$\max h_l$。计算完$f_i$后将$f_i$加入线段树。再维护$f_j + \max h_l$的区间最值即可 ### #2 P2045 费用流典中典。 拆点，将一个位置拆成入点和出点。出点向邻接点的入点连流量为$k$，费用为$0$的边。入点向相应的出点连一条流量为$1$、费用为$a_{i,j}$的边，再连一条流量为$k - 1$、费用为$0$的边。跑最大费用最大流即可。 ### #3 P2048 典中典了。 主要矛盾在于我们没法枚举所有子段。 但是如果我们确定了一个区间的左端点和右端点的选取区间，那最优解可以通过在前缀和数组上RMQ得到。 形式地说，记$sum_i$为到$i$的前缀和。如果确定左端点为$o$，右端点的选取区间为$[l,r]$，则对于这一组条件$(o,l,r)$最优解为： $$\max\limits_{i\in[l,r]} sum_i - sum_{o - 1}$$ 考虑对于一组条件$(o,l,r)$，若最优解在$t$取到，那么次优解只能在$(o,l,t - 1)$或$(o,t+1,r)$中取到。 解法就呼之欲出了。先把所有$(o,o+L,o+R)$以最优解的值为关键字放到堆里。每次取出堆顶$(o,l,r)$，并将$(o,l,t-1)$和$(o,t+1,r)$放回堆。注意对于条件$(o,l,r)$如果$r<l$，那就不用再进队。 ### #4 P2123 邻项交换法典中典。 ### #5 P3647 换根DP 其实这个游戏规则的限制只有**一个点不能作为两条以上蓝线的中点**。 现在我们规定蓝线的方向只能是从祖先到后代。即不允许$u,v\in son_p$，$u\rightarrow p \rightarrow v$这样的线。那么我们只需要枚举每个点分别作为根的时候的答案即可。 现在考虑求解根确定时的答案。设$f_{p,0/1}$为$p$是/不是蓝线中点时$p$子树的最大贡献。 考虑转移： $$f_{p,0} \leftarrow \max(f_{v,0}, f_{v,1} + w_{p\rightarrow v})$$ 定义$r_{p\rightarrow v} = {f_{v,0} + w_{p \rightarrow v} - \max(f_{v,0}, f_{v,1} + w_{p\rightarrow v})}$，其意义为$v$对$f_{p,1}$的贡献 $$f_{p,1} = f_{p,0} + \max\limits_{v\in son_p}r_v$$ 现考虑$O(1)$换根。设$f_{p,0/1}$为在$1$为根意义下的答案，$g_{p,0/1}$为在$p$为根意义下的答案，$up_{p,0/1}$为在$1$为根意义下$p$子节点$v$子树外的答案。 记$p$父亲为$z$，定义$r_{p\rightarrow z} = up_{z,0} + w_{z\rightarrow p} - \max(up_{z,0}, up_{z,1} + w_{z\rightarrow p})$ 那么从$p$转移到$v$的过程中： $$g_{v,0} = f_{v,0} + \max(up_{p,0}, up_{p,1} + w_{p\rightarrow v})$$ $$g_{v,1} = g_{v,0} + \max(\max_{u\in son_v} r_{u \rightarrow v}, r_{v \rightarrow p})$$ $$up_{p,0} = g_{p,0} - \max(f_{v,0},f_{v,1} + w_{p\rightarrow v})$$ $$up_{p,1} = up_{p,0} + \max(\max\limits_{u \in son_p, u \neq v} r_{p \rightarrow v}, r_{p\rightarrow z})$$ 关于$\max\limits_{u \in son_p, u \neq v} r_{p \rightarrow v}$，可以维护$r_{p \rightarrow v}$的最大值和次大值$O(1)$解决。 换根思路就是去子树贡献。其实很套路。 ### #6 P2480 数论模板全家桶，无需多盐。 题目大意：求$\large g^{\sum_{d|n} \binom{n}{d}}$，对合数$999911659$取模 质数がないなら、わたし↑ 没有质数没法Lucas，急。所以把模数分解，得到$999911659 = 2 \times 3 \times 4679 \times 35617$。 考虑分别在四个质数模数意义下算出解，然后发现只需要一次CRT就可以求出原模数意义下的解了。 ### #7 P3622 状压DP好题 设$f_{i,S}$为考虑到$i$，从$i$开始后$5$个状态为$S$的最优解。 気付け！$S$的低位存储的是$i$，高位存储的是$i+4$。不要搞反了。 可以先预处理出来$w_{i,S}$表示站在第$i$位置我们的方案を楽しめる子的个数。有转移： $f_{i,S} \leftarrow \max(f_{i-1,(S \& 15) << 1}, f_{i - 1, ((s \& 15) << 1) |1}) + w_{i,S}$ （latex爆炸致歉。 为了符合环的要求，需要$0$和$n$填写的状态能接上。可以枚举开始几位填的状态$T$。将$f_{0,T}$设为$0$，其余设为$-inf$。最后只用$f_{n,T}$更新答案。 ### #8 P3629 $k=1$，一定连直径两端，可以少走一次直径。 $k=2$，考虑如下贪心：第一条还是连直径。然后把直径上的边权设为$-1$，再求一次直径。第二条连第二个“直径”的两端。 ### #9 P2857 网络流建模一道，比较好理解 考虑建一个虚源点和一个虚汇点。将源点和每头牛之间连一条流量为$1$的边，将汇点和牛棚之间连流量为牛棚容量的边。 那么假如我们确定了每头牛愿意接受哪些牛棚，那存在解的判据就是**最大流为n** 于是我们可以二分座次的跨度，check时枚举座次的范围并据此建图跑最大流即可。 ### #10 P2868 分数规划+spfa判负环 我们先二分答案$d$，检查是否存在环使得$\large\frac{\sum F_u}{\sum T_e} \ge d$ 由于$T$为正，我们可以稍微移个项，得到： $$\sum F_u - d \times \sum T_e \ge 0$$ 即 $$\sum F_u - dT_e \ge 0$$ 我们发现可以用spfa判负环解决 具体来说，我们将$u\rightarrow v$的边权修改为$F_u - d \times w_{u\rightarrow v}$，然后跑SPFA判负环即可。 关于SPFA并不能判复杂负环的问题：发现有复杂负环必定有简单负环，从中拽出一个就好了（）并不存在什么问题。 关于SPFA判的是严格负环而不能取$0$的问题，我们只要提高二分的精度就可以解决了。 ### #11 P3117 ### #12 P3121 AC自动机+栈 先对模式串建AC自动机，在主串上匹配。用栈记录每次AC自动机上的指针位置。 如果匹配到了模式串$t$，就将栈顶$|t|$个元素弹出。然后将AC自动机指针重置到栈顶位置，继续匹配。 ### #13 P3959 状态设计比较有意思 数据范围提示状压。关键问题在于：如何处理代价$L\times K$中的$K$。我们考虑将树高这一维写进状态，按照深度顺序加点。 即设$f_{S,h}$为加入点集合为$S$，目前树高为$h$的最小代价。设$S$中的叶子节点经过一次图上的边能够达到的点集为$Z$，可以得到以下转移： $$f_{S \cup s, h + 1} \leftarrow f_{S, h} + \min (w_{(u, v)}) \times h \\(s \subseteq Z, v\in s, u\in S, (v, p) \in E)$$ 解释：$v$是由$S$中叶子点经一条边可达的点。我们只需要贪心地选择一个连到$S$中点的边权最小的边即可。虽然我们并没有要求，但我们可以认为点$v$的深度是$h+1$（因为$v$深度更小的情况也会被枚举到）。 最后的答案就是$\min\limits_{h\in (1,n)} f_{U, h}$ ### #14 P3354 主要矛盾是我们需要知道木料运输的终点才方便计算答案。 不妨把终点设计到状态里。设$f_{u,t,j,0/1}$为在$u$的子树中，离$u$最近的伐木场为$t$且子树中建了$j$个伐木场的情况下，$u$建/不建伐木场的最小花费。 设$f_{u,t,j,2} = \max(f_{u,t,j,0}, f_{u,t,j,1})$，因为转移完$u$我们就不关心$u$建没建了。 转移就是树上背包： $$f_{u,t,j+l,0} \leftarrow f_{v,t,l,2} + f'_{u,t,j,0}$$ $$f_{u,t,j+l,1} \leftarrow f_{v,u,l,2} + f'_{u,t,j,1}$$ (注意此时并没有计算$u$的贡献) 合并时： $$f_{u,t,0,2} = f_{u,t,0,0} + dis_{t\rightarrow u} \times w_u$$ $$f_{u,t,j,2} = \max(f_{u,t,j,0} + dis_{t\rightarrow u} \times w_u, f_{u,t,j - 1,1})$$ ### #15 P3162 我们假设生产第$i$个零件的车间中对答案有贡献的车间坐标为$f_i$，最优解为$x$，则花费为： $$\sum(x - f_i)^2 \\ = nx^2 - 2x\sum f_i + \sum f_i ^ 2$$ 可以发现，$x$最优位置为$\large\frac {\sum f_i}{n}$，取到最小花费$\sum f_i^2 - \large\frac{(\sum f_i) ^ 2}{n}$ 那么我们就得到了40分做法：直接枚举$f_i$是哪些，求出$\sum f_i, \sum f_i^2$并依照上式计算费用即可。 #### 贪心 但是这其中有些枚举是不必要的。我们转而考虑一个贪心策略： 将生产每种零件的车间坐标升序排序。每次考虑将生产某种零件的一个车间替换为它后面的一个。记将在$x$位置的车间替换为$y$的操作为$x \rightarrow y$。将所有$x \rightarrow y$按照$x + y$升序，再依次操作即可。 每个车间只被考虑一次，再加上排序，复杂度$O(n \log n)$ #### 正确性 我们考虑这种贪心策略忽略了哪些状态的枚举： 假如先后有两次操作$x_1 \rightarrow y_1$，$x_2 \rightarrow y_2$，那么$x_1,y_2$同时选取的情况就被我们忽略了。 假设$x_1, y_2$同时选取的情况在最优解里。设最优解的位置是$p$，则$p$满足$p - x_1 < y_1 - p$，$p - x_2 < y_2 - p$，即$\frac{x_2 + y_2}{2} < p < {\frac{x_1 + y_1}{2}}$，这与$x + y$升序矛盾。 ### #16 P3226 ### #17 P3237 唯一真史。 #### 人话题意 给一棵树，每个点有一个权值，要求修改一些点的权值，使得： 1. 同一个父亲的儿子权值必须相同 2. 父亲的取值必须是所有儿子权值之和 哈希。发现只要根节点的权值确定，整棵树就确定了。 我们可以枚举维持点$p$权值不变条件下根节点的权值$f_p$。最后只用统计$f$的众数，即为可以保留不变的位置的最大值。 根据定义给出$f_p$表达式: $$f_{p} = a_p \times \prod_{z\in anc_p} |son_z|$$ 但这样$f_{p}$一定会乘飞。考虑全体$f$对$2$取对数，将乘法转化为加法。 ### #18 P3239 ### #19 P3533 一生に、基环树をやれる。 显然内向树森林。 假如$a,b$不在同个连通块，寄 假如在同一个子树，会合点为LCA 不在同一个子树，分别尝试从$a$的根走到$b$的根和从$b$的根走到$a$的根，按照题目要求取最优解即可。 ### #20 P4083 非常好的建图题，使我读谱旋转。 #### 朴素做法 考虑将送馅饼的过程反过来，考虑收到一个馅饼前上一个人送来的馅饼可能是哪些。 将某人评价为$0$的点设为起点。将一个点它的合法前驱连边。则从某个点$i$开始最少要传递的次数相当于从某个起点到$i$的最短路长度。$01$ bfs可做。 #### 优化 其实已经呼之欲出了。考虑不带边权的话一个点最多被松弛一次。用$set$维护没有被松弛的节点。每次二分前驱在$set$中的区间，将每个点松弛后入队并在$set$中删除即可。 每个点只进出$set$各一次，$O(n \log n)$ #### code $set$中存储对方对自己做的馅饼的评价。 假如说现在的馅饼$p$是人$0$做的，人$0$对它的评分为$x$，它的前驱一定是人$1$做的馅饼中人$0$评分在$[x - d, x)$区间中的。在$set_1$中二分即可。 ```cpp #include <bits/stdc++.h> #define int long long #define inf 100000000ll #define endl '\n' using namespace std; const int maxn = 1e5 + 5; int n, d, a[maxn * 2][2], dis[maxn * 2]; set<pair<int, int> > rem[2]; //存储对方对自己的馅饼的评价 signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> d; for (int i = 1; i <= (n << 1); ++i) { cin >> a[i][0] >> a[i][1]; } queue<int> q; for (int i = 1; i <= (n << 1); ++i) { if (!a[i][i <= n]) { //如果对方评分为0，作为起点入队 dis[i] = 1; q.push(i); } else { rem[i > n].insert(make_pair(a[i][i <= n], i)); //在自己的集合中加入对方的评分 } } while (!q.empty()) { int now = q.front(); q.pop(); int tp = (now > n); set<pair<int, int> >::iterator st = rem[tp ^ 1].lower_bound(make_pair(a[now][tp] - d, -inf)); set<pair<int, int> >::iterator en = rem[tp ^ 1].upper_bound(make_pair(a[now][tp], inf)); //在对方做的馅饼中找目前点的前驱 if (st == rem[tp ^ 1].end()) continue; for (set<pair<int, int> >::iterator it = st; it != en;) { dis[it->second] = dis[now] + 1; q.push(it->second); rem[tp ^ 1].erase(it++); //松弛，入队，删除。 } } for (int i = 1; i <= n; ++i) { if (!dis[i]) { cout << -1 << endl; } else { cout << dis[i] << endl; } } return 0; } ``` ### #21 P4135 そろそろ詩も終わる時間だ、やっと君の番だからさ。 我本来是要莫队的啊，但是这小子，啪的一下，很快啊，就给我强制在线了。 本来以为要用什么奇技淫巧但实际上还挺板的。 对于一个询问$(l,r)$，如果我们能知道包含在$[l,r]$中的整块中每个数的出现次数，和只考虑这些整块的答案，那合并散块就很好做了。 而这些东西也很好维护。可以维护$f_{i,j}$表示计算整块$i$到整块$j$中哪些数出现了偶数次。再维护$cnt_{i,v}$表示$v$出现的次数的前缀和，便可知道整块部分中每个数出现了多少次。 合并散块时在桶里计数，统计出现在这个数出现了多少次。如果奇变偶就增加答案，否则就减少答案。 对于没有整块的情况暴力计算即可 复杂度$O(n^{\frac{3}{2}})$ ### #22 P8867 纯难。 ### #23 P4182 ### #24 P4187 非常好数学题 首先需要掌握判据：合法的充要条件是必须存在一段长度不小于$k$的同色区间。 直观的做法是枚举同色区间的位置，然后容斥。但发现假如有多个同色区间没法去重。 #### 正难则反 从所有颜色序列中减去不合法的，即没有任何一个同色区间长度$\ge k$ 记$f_i$为长度为$i$的不合法序列数量。 若$i < k$，$f_i = mf_{i-1}$（随便填） 若$i \ge k$，$f_i = (m-1)\sum\limits_{l \in [i - k + 1]} f_l$（接上颜色不同且长度$<k$的一段） ### #25 P4211 $\sum\limits_{v \in S} dep(\operatorname{lca}(u,v))$求法： 树剖，将$S$中的点的到根链上点权全部$+1$，答案即为$u$到根链上的点权和 这道题离线询问，按端点升序。按顺序染色到根链并处理询问即可。 ### #26 AT_agc018_c 转化题意：先让所有人选金币。再选$y$个人换成银币（收获为$b-a$，记为$e$），选$z$个人换成铜币（收获为$c-a$，记为$f$）。求最大收获 邻项交换法确定哪些人选银币，哪些人选铜币。 假设$x$选银，$y$选铜。不交换的条件为： $$e_x + f_y \ge e_y + f_x$$ 即： $$e_x - f_x \ge e_y - f_y$$ 按照$e-f$降序，显然严格弱序。 只需维护每个位置前缀选$y$个，后缀选$z$个的最大值即可。 ### #27 AT_arc018_c 不妨设$x < y$ 分讨最大值和最小值是否同色。 #### 不同色 $x$全红，$y$全蓝显然最优 #### 同色 不妨设最大和最小都涂的蓝色。现在要最小化红色的极差。 首先最大值位置相对的$x$和最小值位置相对的$y$是肯定要染红的。（这两个位置也要进队） 让剩下的元素按照$x$升序。将所有$x$插入优先队列。枚举将所有的$x$逐步替换为$y$，即将$x$出队，再将$y$加入。查询队列最大值和最小值即可。这个有优先队列可以用```multiset```实现。 #### code ```cpp #include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 2e5 + 5; struct node { int x, y; } z[maxn]; signed main() { int n; cin >> n; int bmin = 1e18, bmax = 0, rmin = 1e18, rmax = 0; multiset<int> pq; for (int i = 1; i <= n; ++i) { cin >> z[i].x >> z[i].y; if (z[i].x > z[i].y) swap(z[i].x, z[i].y); bmin = min(bmin, z[i].x); rmin = min(rmin, z[i].y); bmax = max(bmax, z[i].x); rmax = max(rmax, z[i].y); pq.insert(z[i].x); } int ans = (bmax - bmin) * (rmax - rmin); sort(z + 1, z + 1 + n, [](node n1, node n2) { return n1.x < n2.x; }); for (int i = 1; i < n; ++i) { pq.erase(pq.find(z[i].x)); pq.insert(z[i].y); auto bg = pq.begin(), ed = pq.end(); ans = min(ans, (rmax - bmin) * (*(--ed) - *bg)); } cout << ans << endl; return 0; } ``` ### #28 P8819 和哈希判基环树森林。 给每个点$p$随机一个权值$w_p$ 定义$r_p = \sum\limits_{v\rightarrow p \in E} w_v$ 可以$O(1)$实时维护$r_p$。 图是基环树森林的判据是$\sum r_p = \sum w_p$ ### #29 P4381 唯一真史。 基环树直径。 先找环。对于每个联通分量，将其每个子树的直径（别忘了用它更新答案）和最长到根链处理出来。然后再在环上考虑。选定一个环上的点$s$将环断开并复制一遍。记环上点$p$子树中的最长到根链长度为$f_p$，$p$到$s$的前缀距离为$d_p$。则$p$的贡献为： $$\max_{p - v < n}{f_v + f_p + d_p - d_v}$$ 整理 $$f_p + d_p + \max_{p-v < n}{f_v - d_v}$$ 单调队列即可。 ### #30 P4516 无意义卡空间卡读写卡常数的送去出演新一季奶龙。 树形DP底力题 #### 状态设计 设$f_{p,j,0/1,0/1}$在$p$的子树中放了$j$个监视器，$p$不放/放，$p$没被监听/被监听的方案数。 考虑分讨并转移。 转移到$f_{p,j,0,0}$，$v$一定不能放，并且得被监听。故$f_{p,j + l,0,0} \leftarrow f'_{p,j,0,0} \times f_{v,l,0,1}$ 转移到$f_{p,j,0,1}$。讨论$p$先前的状态。如果之前就被监听了，那$v$放不放都可以。如果之前没被监听，$v$需要放监听器。而且无论如何$v$都需要被监听。故$f_{p,j+l,0,1} \leftarrow f'_{p,j,0,0} \times f_{v,l,1,1} + f'_{p,j,0,1} \times (f_{v,l,0,1} + f_{v,l,1,1})$ 转移到$f_{p,j,1,0}$。所有$v$都不能放。但是被不被监听都行。故$f_{p,j+l,1,0} \leftarrow f'_{p,j,1,0} \times (f_{v,l,0,0} + f_{v,l,0,1})$ 转移到$f_{p,j,1,1}$。讨论$p$以前的状态。假如$p$之前就被监听。那$v$爱咋放咋放。假如$p$之前没被监听，那$v$得放，被不被监听无所谓。故$f_{p,j+l,1,1} \leftarrow f'_{p,j,1,0} \times (f_{v,l,1,0} + f_{v,l,1,1}) + f'_{p,j,1,1} \times (f_{v,l,0,0} + f_{v,l,0,1} + f_{v,l,1,0} + f_{v,l,1,1})$ 卡空间，全```long long```开不下。クソ！ 建议单写一个加法函数。并且每次转移的时候把$f$复制一遍，避免$f'$被更新 ### #31 P4597 哎这回真是典中典了。 按顺序遍历，将元素放入优先队列。新元素如果比堆顶小，就把堆顶弹出并强行改成当前元素大小。 关于非降：使$a_i \leftarrow a_i - i$，转成递增。（非常好trick使我码量旋转 ### #32 P4819 缩SCC。发现我们只用查证$0$入度点即可。 同时，假如我们能找到一个大小为$1$的SCC满足它所有后继点的前驱不唯一，那我们可以不查证它（其他SCC查证完了它自然就是杀手了）。此时需要查证的点数$-1$ 最后如果我们至少要查证$t$个点那我们的安全概率就是$1 - \frac{t}{n}$，即危险点不在这$t$个中的概率。 ### #33 P4785 贪心，无需多盐。 很容易发现交换成一个二叉树结构。 对于每个位置$p$，讨论最小值在$p$，$lch_p$还是$rch_p$ 若最小值在$p$，则不交换最优。 若最小值在$lch_p$，则只能交换一次$p$和$lch_p$a_ 若最小值在$rch_p$，则需要考虑$p$和$rch_p$的顺序。不妨设$a_p \le a_{rch_p}$。考虑记忆化搜索$p$在左子树还是右子树更优（因为最多跳$\log$层不会有问题）。