杂题题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了杂题题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

UOJ 21 缩进优化
题目链接
记 $M=\max(a_i)$
从反面考虑，考虑 $x$ 让答案减小的量。即为 $\sum_{i=1}^n \lfloor \frac{a_i}{x} \rfloor\times(x-1)=(x-1)\sum_{i=1}^n \lfloor \frac{a_i}{x} \rfloor$。
只需要快速计算 $S=\sum_{i=1}^n \lfloor \frac{a_i}{x} \rfloor$。
可以直接枚举 $\lfloor \frac{a_i}{x} \rfloor$ 的值，记为 $t$，则 $x\times t\le a_i< x\times t+x$。
统计值为 $j$ 的 $a_i$ 的个数，再做一次前缀和，记为 $sum$, 则每一个 $t$ 对 $S$ 的贡献，即为
$t\times (sum_{x\times t+x-1}-sum_{x\times t-1})$。
注意到 $t\le \frac{M}{x}$，所以对于每一个 $x$ ，只需要枚举 $\frac{M}{x}$ 个 $t$。总复杂度为
$\sum_{x=1}^n \frac{M}{x}=\Theta(M \log M)$

实现简单，小坑点：$x\times t+x-1$ 可以达到 $2\times M$，$sum$ 也需要算到 $2\times M$。

Luogu P3549 [POI2013] MUL-Multidrink
题目链接
初步观察题目，发现可以把过程大致理解为跳 $1$ 到 $n$ 的链，中途路过其他点。

可以先把 $1$ 到 $n$ 的链抽出来，再把链上的点的作为树根，得到一条每个结点上都挂了一棵树的结构。

我们初步考虑，应当要让从链走入子树时可以“返回”，所以我们树形 dp，记

$f_{u,1}$ 表示子树 $u$ 从 $u$ 进入，可否遍历后返回 $fa_u$；

$f_{u,0}$ 表示子树 $u$ 从 $fa_u$ 进入，可否遍历返回 $u$。

考虑如何进行转移：

先考虑 $f_{u,1}$：

（我们称一个点为”单点“，当且仅当这个点没有儿子,记 $u$ 的儿子构成的集合为 $son(u)$）

如果 $son(u)$ 中没有非单点， $f_{u,1}=1$。这是显然的，只需从 $u$ 进入，遍历儿子结点即可。
如果 $son(u)$ 中有且仅有一个单点，不妨设为 $k$，则 $f_{u,1}=f_{k,0}$。若 $f_{k,0}=1$, 从 $u$ 进入子树 $k$ 再返回到 $k$ 遍历其他单点即可。反之，若 $f_{k,0}=0$，一旦进入子树 $k$，就无法返回，可得$f_{u,1}=0$。
如果 $son(u)$ 中有多个非单点，$f_{u,1}=0$。不妨设有非单点 $k1,k2$。因为进入子树 $k1$ 后，只能终结在 $k1$，跳单点只能从 $k2$ 进入 $k2$ 的子树，然后就无发返回了、

$f_{u,0}$ 差不多同理，结论唯一的不同是 “如果 $son(u)$ 中有且仅有一个单点，不妨设为 $k$，则 $f_{u,0}=f_{k,1}$”。

计算完 $f$ 后，我们考虑如何求答案。

我们记 $g_{u,1}$ 表示从一出发可以跳链到达 $u$ ( $u$ 为链上节点），此时 $1-u$ 的所有结点上挂的子树都被访问， $u$ 所在子树亦被遍历，目前位于 $u$ 结点是否可行。

$g_{u,1}$ 表示从一出发可以跳链到达 $u$ ( $u$ 为链上节点），此时 $1-u$ 的所有结点上挂的子树都被访问， $u$ 所在子树未被遍历，目前位于 $u$ 结点是否可行。

记 $x$ 为 $u$ 前一个结点。

$g_{u,1}$ 大部分转移显然($g_{u,1}=g_{x,1} \vee (g_{x,0} \wedge f_{x,1})$)，可以看代码。有一种比较特别：$x$ 有两个非单点子节点 $s1,s2$。可以从 $x$ 的前一个结点进入 $s1$ ，遍历完毕回到 $x$, 跳到 $s2$，遍历子节点中的单点，进入 $u$。

$g_{u,0}$ 在 $size(u)=1$ 时转移与 $g_{u,1}$ 相同，$size(u)>1$ 时，$g_{u,1}=g_{x,1} \wedge f_{u,0}$。
最终答案即为 $g_{n,1}$。

找方案其实是简单的，就是正常的 dp 回溯。

代码：实现的不太好，很长。

代码

ARC164E Segment-Tree Optimization
题目链接

先考虑第一问，如何求 $d$。我们发现一个区间 $[l,r]$ 在深度为 $x$ 的层次停止遍历，意味着 $[l,r]$ 可以用该层的区间恰好拼出。这即等价于 $l-1,r$ 都是 $x$ 层区间的“断点”。

所以，在第 $d$ 层中，$\forall i \in [1,q], l_i-1,r_i$ 均为断点。由于第 $d$ 层至多有 $2^d-1$ 个断点，统计不同的 $l_i-1,r_i$ 即可（要排除 $1,n$）。

现在考虑如何最小化 $c$。我们发现，如果一个区间的一个端点在第 $d$ 层产生，就会对 $c$ 产生 $2$ 的贡献。反之，没有贡献。

我们进行 dp。先统计每个位置的端点个数。将有端点的位置记录在 $a$ 中（设共有 $tot$ 个这样的位置）。

设 $dp_{i,j}$ 表示在第 $d$ 层中，前 $i$ 个断点计算到了前 $j$ 个有端点的位置时的总贡献最小值。因为在第 $d$ 的断点中，只有奇数位的断点是在该层新产生的，即有贡献的，可以得到以下转移方程：

$dp_{i,j}=\min(dp_{i-1,j},dp_{i-1,j-1}+a_j[i 为奇数])$

最终答案即为 $dp_{2^d-1,tot}$

小坑点：$d=1$ 需要特判。

Luogu P8162 [JOI 2022 Final] 让我们赢得选举
题目链接

首先得到几条简单的贪心结论：

所有的协作者（包括本人）在同一城市演讲一定是不劣的。
选完协作者后，一定选择 $a$ 比较小的城市获取选票。
选完协作者后，协作者一定按一定按照 $b$ 从小到大的顺序获得。

证明都十分简单，略。
由于结论3，我们先把城市对 $b$ 排序，然后假设目前要获得 $t$ 个协作者，进行 dp。

排序后，还可以得到一条结论：如果一个前面的城市 $i$ 没有获得选票，后面的所有城市都不会获得协作者。

证明：
若后面的城市 $j$ 获得协作者，也一定获得了选票，花费的时间 $b_j$ 一定大于 $b_i$，故改为获得 $i$ 的协作者，放弃 $j$，一定是不劣的。

据此可以设计状态 $dp_{i,j}$ 表示前 $i$ 个城市均获得选票，其中 $j$ 个获得协作者的最小时间花费。可以得到转移方程
$dp_{i,j}=\min(dp_{i-1,j}+\frac{a_i}{t+1},dp_{i-1,j-1}+\frac{b_i}{j})$

为了求得答案，我们再求出后 $i$ 个城市中 $a$ 前 $k$ 小的的数的和，记为 $suf_{i,k}$。

答案即为 $\min dp_{i,t}+\frac{suf_{i+1,k-i}}{t+1}$

Luogu P8163 [JOI 2022 Final] 铁路旅行 2
题目链接

观察数据范围，$Q\times m$ 已经很大了，所以单次询问一定不能依靠一条一条路径跳来得到答案，所以想到倍增，一次跳多条路径。

我们记
$le_{i,k}$ 表示从 $i$ 出发，跳 $2^k$ 步可以到达的最左位置
$ri_{i,k}$ 表示从 $i$ 出发，跳 $2^k$ 步可以到达的最右位置

可以进行转移：

$le_{i,k}=\min le_{j,k-1}$，其中 $j\in [le_{i,k-1},ri_{i,k-1}]$。

这可以用线段树/ ST 表维护。

同时，$le_{i,0},ri_{i,0}$ 可以简单得用线段树/单调队列求出。

至此，我们得到 $le,ri$ 的值。

现在考虑如何处理询问。

按照倍增的普遍做法，我们进行倒序拓展可范围 $[l,r]$，如果终点 $t$ 被覆盖，放弃该次拓展，否则接受该次拓展。

最后一次拓展后如果终点 $t$ 未被覆盖，则可断定无解。

具体的，倒叙枚举单次跳跃得长度 $2^k$，每次拓展即为：

$l$ 拓展为 $\min le_{j,k}$，其中 $j \in [l,r]$
$r$ 拓展为 $\min ri_{j,k}$，其中 $j \in [l,r]$

这样一次拓展需要 $2^k$ 步，求和即为答案。

Luogu P8164 [JOI 2022 Final] 沙堡 2
题目链接

考虑如何判断一个矩形是合法的。显然，遍历矩形的这条路径一定呈降序。

如果目前位于位置 $(x,y)$，那么下一步一定到达 $(x,y+1),(x,y-1),(x+1,y),(x-1,y)$ 四个位置中权值小于 $a_{x,y}$ 的，或者 $(x,y)$ 为路径的终点。
不妨记这个位置为 $(x1,y1)$，我们记 $val_{x,y}$ 表示 $a_{x,y}-a_{x1,y1}$，如果 $(x,y)$ 为路径终点，记 $val_{x,y}$ 为 $a_{x,y}$

可以证明，一个矩阵存在合法路径当且仅当该矩阵内所有点的 $val$ 和为矩阵所有点的 $a$ 的 $\max$。证明方法类似差分。

显然一个合法的矩阵只会有一个起始点，所以我们把起始点的 $val$ 记为，$inf-a_{x1,x2}$，那么可以得到：一个矩阵存在合法路径当且仅当该矩阵内所有点的 $val$ 和为 $inf$。

现在考虑如何解决原问题。

总体来说，我们枚举矩阵的上下两行，记为 $l1,l2$。再对每一列 $l1,l2$ 内的权求和，简单前缀和+扫描即可。

但是，由于一个点可能位于矩阵的边，角，中间，所以需要分 $9$ 种情况讨论 $val$，导致码量巨大。

CF1844G Tree Weights
题目链接

设 $u$ 到 $1$ 的路径上边权和为 $d_u$。
显然的，第 $i$ 条信息可以表示为 $d_i+d_{i+1}-2\times d_{lca(i,i+1)}=val_i$。

如果直接对 $n$ 个式子做高斯消元，复杂度 $\Theta(n^3)$，显然不行。

注意 $d_1=0$，发现问题难点在于 $d_{lca(i,i+1)} $，而它带有一个系数 $2$，所以把式子两边同时对 $2$ 取模，有 $d_i\mod 2+d_{i+1}\mod 2=val_i\mod 2$。

可以递推得到每一个 $d_i\mod 2$ 的值。

已知 $d_i\mod 2$ 的值后，再把原式对 $4$ 取模，有 $d_i\mod 4+d_{i+1}\mod 4-2\times d_{lca(i,i+1)}\mod 2=val_i \mod 4$

以此类推，可以求出每一个 $d_i$。

最后判断 $d_i$ 是否满足要求，以及边权是否为负即可。复杂度 $\Theta(n\log W)$。

CF1285F Classical?
题目链接
考虑 $lcm(x,y)=\frac{x\times y}{\gcd(x,y)}$。考虑如何固定 $g=\gcd(x,y)$。

此时，先找出所有 $g$ 的倍数（注意到至多有 $\frac{A}{g}$ 个）。自然的，把每个数都除去 $g$。
我们需要得到的数中互素的数对 $(x,y)$ 计算贡献 $x\times y\times g$。发现 $x\times y$ 具有一定的单调性，所以从大到小考虑这些数，如果出现 $\gcd(x,y)=1，x<y$，那么显然的，所有 $x<z<y$ 的 $z$ 不再对答案产生贡献。可以维护一个栈，将其弹出。

现在只需快速判断栈内有无与某个数互素的数即可。由莫比乌斯函数的性质，$[x=1]=\sum_{d|x}{\mu(d)}$，所以 $\sum{[gcd(x,y)=1]}=\sum_{k|x}{\mu(k)\times cnt_k}$，其中 $cnt_k$ 表示 $k$ 作为栈中的数的因数的出现次数。

又因为 $\sum_{i=1}^N d(i)=\Theta(N\log N)$，而每个数在一轮操作中只需要计算 $2$ 次对 $cnt$ 的贡献（一次进栈，一次出栈）所以总的复杂度为 $\Theta(A\log^2 A)$。

LOJ 2395 火车旅行
题目链接

看到这种多次询问两点间的最短路径的题，容易想到倍增。我们设 $le_{x,k}$ 表示从 $x$ 出发，走 $2^k$ 步，可以到达的最左边的位置，$le_{x,k}$ 表示从 $x$ 出发，走 $2^k$ 步，可以到达的最右边的位置。

容易得到转移 $le_{x,k}=\min(le_{le_{x,k-1},k-1},le_{ri_{x,k-1},k-1}),ri_{x,k}=\max(ri_{le_{x,k-1},k-1},ri_{ri_{x,k-1},k-1})$。

难点在于如何进行决策。我们发现，从出发点 $s$ 到终点 $t$，产生贡献的站点 $p_1,p_2,...p_k$ 满足 $\exists t,L_{p_1}\le L_{p_2}\le... \le L_{p_t} \ge L_{p_{t+1}} \ge... \ge L_{p_k}$。而我们知道，从一个位置 $x$ 向左右拓展，第 $i$ 到达的最有位置 $r_i$ 必然使得 $L_{r_i}$ 单增。

不妨设 $s<t$，我们设 $p$ 表示 $r_p<t<r_{p+1}$ 的数。从 $t$ 拓展，如果 $step$ 可到达 $r_{p+1}$，$step+1$ 步一定能到达 $r_p$。所以，从 $s$ 拓展到 $p$ 是不劣的，所以只需倍增拓展 $s$，到达一个位置 $plc$，再从 $t$ 拓展到大于 $plc$ 且最接近的位置即为一个最优策略。

LOJ 2393 门票安排
题目链接

显然需要二分答案。设答案为 $ans$，考虑如何检验其可行性。

先把问题转化为：初始时，有 $n$ 条线段，可以任意翻转其中一些线段，最小化一个位置被覆盖的次数的最大值。

首先可以得到一个性质：所有被翻转的线段的交集不为空集。
证明：若存在两条线段 $(l_1,r_1)$ 和 $(l_2,r_2)$ 不交且均被翻转，$(l_1,r_1)$ 和 $(l_2,r_2)$ 内被覆盖 $1$ 次，其余部分被覆盖 $2$ 次。那么同时不翻转两条线段一定是不劣的，因为线段内覆盖次数不变，而其余部分不被覆盖。

据此，我们尝试枚举被线段的交集中的一个元素 $t$。那么，一条线段只有在 $l_i\le t$，$r_i\ge t$ 时才可能被翻转。考虑一个在 $[1,t]$ 内的位置 $p$ 被覆盖的次数。

设 $a_i$ 表示所有线段在不被翻转时，位置 $a_i$ 被覆盖的次数。考虑翻转造成的变化量。则 $t$ 的变化量为 $-pre_i+(cnt-pre_i)$，其中 $pre_i$ 表示位置在 $i$ 之前的被翻转的线段的条数，$cnt$ 为翻转的线段的总数。

我们必须进一步枚举 $cnt$。自此之后，控制 $[1,t]$ 内的所有数 $a_i-cnt-2\times pre_i\le ans$。若不满足，尝试增加 $pre_i$。在左端点位于 $[1,t]$ 内的线段中，优先翻转右端点大的线段。者可以简单的用一个优先队列维护。操作完毕后，计算 $[1,n]$ 内每一个数新的被覆盖次数 $b_i$，检验其时是否大于 $ans$，若大于则这一组 $(t,cnt,ans)$ 不合法。至此，我们得到了一个 $\Theta(n^3\log n)$ 的做法。文章来源地址https://www.toymoban.com/news/detail-659814.html

到了这里，关于杂题题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！