杂题题解

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

实现简单，小坑点：(xtimes t+x-1) 可以达到 (2times M)，(sum) 也需要算到 (2times 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))）

1. 如果 (son(u)) 中没有非单点， (f_{u,1}=1)。 这是显然的，只需从 (u) 进入，遍历儿子结点即可。

2. 如果 (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)。

3. 如果 (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] 让我们赢得选举
题目链接

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

1. 所有的协作者（包括本人）在同一城市演讲一定是不劣的。
2. 选完协作者后，一定选择 (a) 比较小的城市获取选票。
3. 选完协作者后，协作者一定按一定按照 (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
题目链接

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

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

可以进行转移：

(le_{i,k}=min le_{j,k-1})，其中 (jin [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)，导致码量巨大。

• 还没有人评论，欢迎说说您的想法！