题解：AT_abc370_f [ABC370F] Cake Division

· · 题解

题目翻译

你有一个圆形的蛋糕，被分成了 n 块，每一块都有美味程度 a_i。第 i 条分割线位于第 i 块和第 i+1 块之间。

你需要选择 k 条分割线分出 k 段交给 k 个人，满足每个人都收到了一段连续的蛋糕块，且不存在有块没有交给任何人。

你需要解决两问。设 w_i 表示第 i 个人得到的连续的蛋糕块的美味程度。第一问需要求出 \min\{w_1,w_2,\dots,w_k\} 的最大值。第二问需要求出，在满足 \min\{w_1,w_2,\dots,w_k\} 最大的所有可能划分方案中，有多少分割线从没被使用过。

# 题目思路 先破环成链两条链拼一起。 最大化最小值可以考虑二分答案。设二分需要 check 的是 $mid$，我们就是问能不能凑出 $\geq k$ 段满足每段和都 $\geq mid$。 我们先处理 $nxt_i$ 表示从 $i$ 开始在 $nxt_i-1$ 的位置结尾，也就是 $[i,nxt_i)$ 的区间和 $\geq mid$。如果不存在这样的 $nxt_i$ 就把 $nxt_i$ 设为极大值。 之后我们就是要判断跳 $k$ 次 $nxt_i$ 是否会跳到边界外。这里认为边界是 $i+n$。 直接暴力跳肯定不行，考虑倍增优化跳的过程。设 $nxt_{i,j}$ 表示 $i$ 开始往后跳 $2^j$ 步到了哪里。倍增转移显然。 之后我们枚举开头的 $i$，倍增跳至多跳 $\log n$ 次，这样单次 check 复杂度降为了 $\mathcal O(n\log n)$。加上二分是 $\mathcal O(n\log^2 n)$。 第一问做完了，考虑第二问。我们发现这个有 $i$ 的分割线就代表从 $i$ 开始跳是合法的。我们重复上面判定『跳 $k$ 次 $nxt_i$ 是否会跳到边界外』的过程，如果有一个没跳出的就说明在 $i$ 位置可以成为分割线。 找出所有可能成为分割线的位置用 $n$ 减掉这个个数即可。 --- upd on 20250826： 本题可以做到 $\mathcal O(n\log V)$。我们把 $i\to nxt$ 连边，这样子显然构成一棵树，其实我们要求的就是 $k$ 级祖先。但是可以离线，所以我们维护一个搜索的目前栈，然后找倒数第 $k$ 个即可。 # 代码链接 $\mathcal O(n\log n\log V)$：<https://atcoder.jp/contests/abc370/submissions/57561975> $\mathcal O(n\log V)$：<https://atcoder.jp/contests/abc370/submissions/68820574>