UOJ Round #28 题解

偷吃蛋糕

idea, solution, std, data from GeZhiyuan

足够暴力的搜索

我们考虑一个足够暴力的搜素：当每次转交蛋糕时，暴力枚举被老鼠偷了哪一层，并递归为多个子问题。

该算法看起来是 $2^n$ 的，但实际上不难发现，如果令 $i$ 为当前已经拿到的蛋糕的层数，然后下一次转交到了第 $j$ 张，即吃掉的蛋糕大小为 $j - i$，那么此时令 $f(i)$ 为当前拿到了前 $i$ 层蛋糕，最大要进行的搜索次数，不难发现 $f(i) = \max_{j>i} f(j) \times (j - i)$。其复杂度为 $O(3^{\frac n 3})$。注意复杂度里不要带 $n$，即搜索时需要记录所有拿到的蛋糕的大小和，以防止当 $i=n$ 时还要进行多轮计算。预期可以通过前两个子任务。根据实现，预期获得 $10$ 到 $25$ 分。

但由于出题人不想让大家轻松拿到 $25$，因此可能需要一些很极限的卡常。

一个明显的剪枝

我们考虑，对于两个不同的下标 $i < j$，如果有 $c_i = c_j$，那么老鼠偷这两层蛋糕并没有区别。即我们搜索时，不需要枚举老鼠具体偷了哪层蛋糕，我们可以转为枚举老鼠偷的蛋糕的大小！并带权向多侧递归。

如何分析复杂度呢？我们考虑根号分治。

如果大小大于 $\sqrt n$ 的至少有 $\sqrt n + 1$ 个，那么考虑吃完第一层蛋糕后，已获得的蛋糕大小和超出 $n$，直接快速计算贡献。否则说明一次可以拿光这些蛋糕，直接 $O(\sqrt n)$ 枚举即可。

对于大小不大于 $\sqrt n$ 的部分，我们不难发现此时只有至多 $\sqrt n$ 个值，那么也就只有 $\sqrt n-1$ 个间隔。那么对于一次转交，假设其转交了下标在 $[l, r]$ 间的蛋糕，那么分叉个数就是 $[c_l, c_{l+1}, \cdots, c_r]$ 内不同值的个数，不超所包含的间隔数 $+1$，那么分析后就可得出总复杂度不超 $O(2^{\sqrt n})$。

这样最终可达的状态数为 $O(\sqrt n \times 2^{\sqrt n})$，如果直接暴力为 $O(n \sqrt n \times 2 ^\sqrt n)$，但不难发现只有 $O(\sqrt n)$ 个值，可以快速跳到下一个有分叉，即区间内有至少两种大小的区间，时间复杂度为 $O(n \times 2^{\sqrt n})$，且也可以分析到 $O(c_1 \times 2^{c_1})$。说明了这个搜索必然可以通过除最后一个子任务的所有包。根据是否使用大小大于 $\sqrt n$ 的至少有 $\sqrt n + 1$ 个的剪枝，代码常数和实现情况，预期获得 $35$ 到 $70$ 分。

加一点神奇的小优化

我们考虑对于一层蛋糕，如果吃这层蛋糕时，主办方已经给你了所有的蛋糕，那么其对答案的贡献一定为其大小，即对于这些吃时，主办方已经给你所有蛋糕的蛋糕层。我们只在意这些层的大小乘以其能拿到手中的概率之和。即如下搜索：

如果已经获得过的蛋糕的大小之和，超出了 $n$。则快速贡献，并计算答案。
否则考虑吃掉一层蛋糕，并枚举转交蛋糕时，老鼠偷的蛋糕的大小，并带权向多侧递归。

并还可以进行如下优化：

考虑 $c_i \leq \frac {2n} {i-1}$ 时，$c_i$ 才有可能在搜索时被吃，即只有 $O(\sqrt n)$ 种可能进入搜索的大小。
于是考虑如果下一次转交，只有一种大小，则可以快速跳过这些转交，直到下一个转交至少两种大小的区间。
即假设当前手上的蛋糕大小为 $x$，有 $d$ 个，接下来的 $z$ 层蛋糕大小相同，且第 $z+1$ 层蛋糕大小与他们不同。
那么此时如果有 $z < dx$，那么我们可以直接快速跳 $\lfloor \frac z x \rfloor$ 次，下一次吃蛋糕时蛋糕大小种类数至少为 $2$。否则我们考虑吃掉大小为 $x$ 的所有蛋糕，此时在后续搜索中，只会吃到大小比 $x$ 小的蛋糕。

假设搜索到达最终状态数个数为 $S$，那么如果不加此优化复杂度为 $O(n \times S)$，而加了此优化后为 $O(\sqrt n \times S)$。但实际上两者都可以轻松通过，但不保证带更多 $n$ 的算法能通过。根据代码常数和实现情况，预期获得 $70$ 到 $100$ 分。

关于此题可行性

pp_orange 指出，我们的搜索可以刻画为一棵多叉树，状态数即多叉树的大小。本题中我们只在意叶子的个数，如果叶子数是 $S$，$c$ 有 $z$ 个不同的值，复杂度就为 $O(z \times S)$。

我们即要找出多叉树叶子个数最大的情况。考虑一个状态有 $k$ 个分叉。叶子数从小到大依次为 $S_1, S_2, \cdots, S_k$，则显然总叶子数为 $\sum_{i=1}^k S_k$，不超 $k \times S_k$。即 $k$ 叉会将问题分成 $k$ 个子问题，其代价不超最坏情况下子问题的 $k$ 倍。

于是我们即只要找到一种最差的分裂情况，最大化代价为分叉数的乘积即可。考虑分叉数依次为 $d_1, d_2, \cdots, d_m$。

不难发现第 $i$ 个区间大小至少为 $d_{i-1}$，而这个区间内最小元素至少为 $1 + \sum_{j=i+1}^n (d_j - 1)$。而能搜索到这个状态显然需要满足蛋糕大小和不超过 $n$。

由于我们经过了缩放，此时不难发现，值域连续且包含 $1$ 一定更优。那我们可以转为枚举每次转交时最小的蛋糕大小，假设末尾元素依次为 $a_0, a_1, a_2, \cdots, a_m$，其中多出来的 $a_0$ 表示 $c_1$。那么对于第 $i$ 个区间，我们保证和最小的情况下为 $[a_i + 1, a_{i-1}]$ 各出现一次，其他的全是 $a_i$，而被偷的蛋糕如果大小变大，状态数只会增加不会减小，我们可以直接认为删除了 $a_{i-1}$ 即可，最后出来的状态数肯定还是不超实际的状态数，于是我们就转为如下限制：

$a_0 \geq a_1 \geq a_2 \geq \cdots \geq a_m = 1$
$a_0 + \sum_{i=1}^m a_i^2 + \frac {(a_{i-1}+a_i) \times (a_{i-1}-a_i-1)} 2 \leq n$

由于值域连续，此时 $z = a_0$，然后我们就是要最大化 $T = a_0 \times \prod_{i=1}^m (a_i - a_{i-1}+1)$。经过动态规划检验，$T$ 最大可以取到 $T = 50429952$，约 $5 \times 10^7$。说明我们的搜索是正确的！

如下是检验用的代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll N = 3000 + 5, M = 100 + 5, Inf = 1e18;

inline void checkmax(ll &x, ll y){
    if(y > x) x = y;
}

ll n = 0, m = 80;
ll dp[N][M] = {}, ans = 0;

int main(){
    scanf("%lld", &n);
    for(ll x = 1 ; x <= m ; x ++) dp[x][x] = x;
    for(ll x = m ; x >= 1 ; x --) for(ll y = x + 1 ; y <= n ; y ++){
        ll d = x * x + (x + y) * (y - x - 1) / 2;
        for(ll c = 0 ; c + d <= n ; c ++) checkmax(dp[c + d][x], dp[c][y] * (y - x + 1));
    }
    for(ll c = 0 ; c <= n ; c ++) ans = max(ans, dp[c][1]);
    printf("%lld", ans);
    return 0;
}

复杂度分析

作为选手可以直接写代码然后通过此题，但是对于出题人显然是另一件事。需要证明更为严谨的复杂度。

通过手玩可能大概猜测在 $\exp (\tilde{O}(n^{\frac 1 3}))$ 左右。可惜出题人并没有手段证明出更紧的界，但是没关系，我们有伟大的 zhoukangyang！

根据公理，询问 zhoukangyang 一个命题是真的还是假的，构成了一个严格的证明。

那我们就只需要询问到底是 $\exp (\tilde{O}(n^{\frac 1 2}))$ 还是 $\exp (\tilde{O}(n^{\frac 1 3}))$ 就可以了！

现在我们已经知道了正确的时间复杂度！让我们尝试给出详细的过程。

假设搜索过程递归了 $m$ 次，即说明我们吃了 $m$ 层蛋糕。

考虑第 $i$ 次获得了下标在 $[l_i, r_i]$ 间的蛋糕，被偷的蛋糕大小为 $x_i$。

那么不难发现有 $\sum_{i=1}^{m-1} (\sum_{j = l_i}^{r_i} c_j) - x_i < n$。

由于我们有 $r_i - l_i + 1 \geq c_{r_i}$，$c_{r_i} \geq x_{i+1}$ 和 $c$ 单调不增，我们有 $\sum_{j=l_i}^{r_i} c_j \geq (r_i - l_i+1) \times c_{r_i} \geq c_{r_i}^2 \geq x_{i+1}^2$。

因此有 $\sum_{i=2}^m x_i^2 - \sum_{i=1}^{m-1} x_i < n$。稍加变换即可得出 $\sum_{i=2}^m x_i^2$ 是 $O(n)$ 的。

即我们现在需要求有多少个递增正整数序列 $d$，满足 $\sum d_i^2 \leq n$。

接下来由 zhoukangyang 全权负责：

先只考虑 $[2^l,2^{l+1}]$ 的元素，这个意思大概是你有 $2^l$ 个 $4^l$ 量级的元素，每个元素可以选任意多个，最终不超过 $n$ 的方案数，这个是 $\binom {\frac n {4^l}+2^l} {2^l}$。
先考虑 $2^l < n^{\frac 1 3}$的情况，设 $d=\frac n {8^l}$。使用斯特林公式，$\binom {\frac n {4^l} + 2^l} {2^l}$ 量级是 $ \frac {(d + 1)^{(d+1) \times 2^l}} {d^{d \times 2^l}}$，即 $(1+\frac 1 d)^{d \times 2^l} \times (d+1)^{2^l}$。
我们已经有 $(1+\frac 1 d)^{d \times 2^l} < e^{2^l}$。主要是 $(d+1)^{2^l}$。这个就是 $\exp(2^l \times \ln(d+1))$。
$\sum_{2^l < n^{\frac 1 3}} 2^l \times \ln(\frac n {8^l} + 1)$ 通过令 $i = \frac {n^{\frac 1 3}} {2^l}$，转为 $n^{\frac 1 3} \sum_i \frac 1 i \ln(i^3+1)$，这个是 $\tilde{O}(n^{\frac 1 3})$ 量级的。
接下来考虑 $2^l \geq n^{\frac 1 3}$ 的情况，设 $d= \frac {8^l} n，v= \frac n {4^l}$，组合数为 $\binom {v+vd} v$，量级是 $\frac {(d + 1)^{(d+1)v}} {d^{dv}}$。
同样有 $(1 + \frac 1 d)^{dv} < e^{v}$，我们只需要分析 $(d+1)^{v}$，即 $\exp (v \times \ln(d+1))$。
$\sum_{2^l \geq n^{\frac 1 3}} \frac n {4^l} \times \ln(\frac {8^l} n + 1)$ 通过令 $i = \frac {2^l} {n^{\frac 1 3}}$，转为 $n^{\frac 1 3} \sum_{i} \frac 1 {i^2} \ln(i^3 + 1)$，也是 $\tilde{O}(n^{\frac 1 3})$ 量级的。

综上所述，复杂度 $\exp (\tilde{O}(n^{\frac 1 3}))$。

百尺竿头，更进一步

from zhoukangyang

这题实际上存在理论复杂度更优的做法。

考虑将获得蛋糕的过程分成若干轮。第一轮获得 $1$ 个蛋糕；接下来每一轮获得的蛋糕为用完上一轮获得的蛋糕后所得到的蛋糕。

考虑提前枚举每一轮被转交了哪些蛋糕（不枚举哪些被老鼠拿走了）。对于每个蛋糕 $x$，设取出这个蛋糕时使用的是第 $y$ 个蛋糕，那么设 fa[x]=y。容易发现这形成了一棵树。

可以在树上 DFS 同时 DP：维护当时 DFS 栈中的元素以及还有几个孩子没被递归。此时大概要记深度个 $O(n)$ 大小的值。

因此考虑深度需要到多少。容易发现，在 $c_i \geq B$ 的时候，深度只会有 $\log_{B-1} n$。而在 $c_i < B$ 的时候，如果存在一轮所有元素都相同，那么使用上一轮时删了什么元素就不重要了，剩下的部分就不用搜了，可以暴力搜索（后面部分复杂度不会超过 $2^B$）。

因此深度是 $B+\log_{B-1}n$ 级别的，取 $B=\log n/\log\log n$ 能得到 $O(\log n/\log\log n)$ 的深度，总复杂度不会超过 $\exp O(\log^2 n / \log\log n)$。

咕咕咕

在 此题可行性 部分中说明了此题搜索上界，但我们没有一组足够强的数据能贴合上界的量级，搜索已经证明的下界和上界差距仍然很大。如果你能将上界分析到更低或给出更强的数据，欢迎在题解下方讨论！

环环相扣

idea from Demeanor; solution, std, data from zhoukangyang, Melania

准备工作

我们的题目要求对于每个查询区间 $[l, r]$ 选择三个不同的下标 $i, j, k \in [l, r]$，最大化能量值 $(a_i \bmod a_j) + (a_j \bmod a_k) + (a_k \bmod a_i)$。

假设我们选择的值 $a_i > a_j > a_k$，下标 $i,j,k$ 只存在两个本质不同的排列方式：

$i \to j \to k \to i$，其能量值等于 $(a_i \bmod a_j) + (a_j \bmod a_k) + a_k$。
$i \to k \to j \to i$，其能量值等于 $(a_i \bmod a_k) + a_k + a_j$。

结论 1：只要 $a_i > a_j$，一定有 $(a_i \bmod a_j) + a_j \leq a_i$。

这是因为 $(a_i \bmod a_j) + a_j \leq (a_i - a_j) + a_j = a_i$。这一事实将在下文中多次使用。

算法 1

结论 2：查询区间内的第一大值和第二大值必须分别作为 $a_i$ 和 $a_j$ 使用，否则能量值一定不优。

这是解决这个问题的突破口。

基于这一结论，可以实现一个时间复杂度为 $O(qn)$ 的暴力：

对于每个询问 $[l, r]$，扫描整个区间确定第一大值和第二大值，分别记为 $a_i$ 和 $a_j$。
枚举 $[l, r]$ 内所有可能的 $a_k$，注意排除 $a_i$ 和 $a_j$ 本身。
对于每个 $a_k$，分别计算两种排列方式 $i \to j \to k \to i$ 和 $i \to k \to j \to i$ 的能量值。
直接输出这 $2(r - l - 1)$ 个能量值中的最大值。

结论 2 的证明如下：

不妨假设区间为 $[1, n]$，其中 $a_1 < a_2 < \cdots < a_n$。
直接选择 $(i, j, k) = (n, n-1, n-2)$ 并使用排列方式 2，可以得到答案的一个下界 $\text{ans} \geq a_{n-1} + a_{n-2}$。
我们利用结论 1：
- 对于排列方式 1：$(a_i \bmod a_j) + (a_j \bmod a_k) + a_k \leq \min\{a_i, 2a_j - 1\}$。对于 $i \leq n-1$ 或 $j \leq n-2$，这一值不会超过下界。
- 对于排列方式 2：$(a_i \bmod a_k) + a_k + a_j \leq a_i + a_j$。对于 $i \leq n-1$，这一值不会超过下界。此外，由于 $a_j$ 只在和式里面出现一次，显然当 $j = i-1$ 时能量值取到最大。

算法 1 的时间复杂度为 $O(qn)$，可以获得 $30$ 分。

算法 2

定义 $F([l, r], i)$ 表示区间 $[l, r]$ 内 $(a_i \bmod a_k) + a_k$ 的最大值，排除 $i$ 本身以及 $[l,r]\setminus\{i\}$ 内最大的那一个 $a_k$。

我们可以把两种排列方式的能量值重写为：

排列方式 1：$F([l, r], j) + (a_i \bmod a_j)$。
排列方式 2：$F([l, r], i) + a_j$。

我们将 $F([l, r], i)$ 拆成 $F([l, i], i)$ 和 $F([i, r], i)$ 左右两个部分。

我们考虑预处理所有的 $F([l, i], i)$：

对于每个 $i$，从右向左扫描 $l = i, i-1, \cdots, 1$。
维护当前排除掉的最大元素 $a_t$。
如果 $a_l > a_t$，则用 $(a_i \bmod a_t) + a_t$ 更新 $F([l, i], i)$，然后设置 $t = l$。
如果 $a_l < a_t$，则用 $(a_i \bmod a_l) + a_l$ 更新 $F([l, i], i)$。

预处理所有的 $F([l, i], i)$ 和 $F([i, r], i)$，时间复杂度为 $O(n^2)$。

由于拆分操作排除了左右两侧的最大元素，我们需要手动加回两侧最大元素当中较小的那一个。

算法 2 的时间复杂度为 $O(n^2 + q)$，结合算法 1 可以获得 $40$ 分。

算法 3

我们可以通过限制向左扫描的长度，减小预处理 $F([l, i], i)$ 的计算量。

结论 3：在扫描过程中，如果遇到两个元素 $a_k > a_i / 2$，我们可以在第二个元素之后立刻停止扫描。

由于有两个这样的元素，排除一个最大元素后仍然有一个元素 $a_k > a_i / 2$。
如果 $a_k > a_i$，则 $i$ 本来就不能成为 $[l, r]$ 内的第一大值或第二大值，因此 $F([l, i], i)$ 的值不会被使用。
如果 $a_i / 2 < a_k < a_i$，则 $(a_i \bmod a_k) + a_k = a_i$，已经达到了上界，继续向左扫描也没有用。

我们使用 zkw 线段树来定位到 $[l, r]$ 内的第一大值和第二大值，以及子区间 $[l, i-1]$、$[i+1, r]$、$[l, j-1]$、$[j+1, r]$ 的最大值。由于这些区间有重叠，实际上只需要进行四个区间最大值查询。

利用结论 3 可以证明总扫描长度为 $O(n \log a_i)$，因此算法 3 的时间复杂度为 $O(n \log a_i + q \log n)$，可以获得 $80$ 分。

算法 4

我们进一步优化算法 3，将总扫描长度减小到 $O(n)$。

结论 4：针对 $a_i$ 从右向左扫描时，如果某个元素 $a_k$ 在其右侧（$[k+1, i-1]$ 内）有两个元素 $a_u, a_v \geq 2a_k$，则 $a_k$ 是无用的。它既不会替换当前排除的最大值 $a_t$，也不能更新 $F([l, i], i)$ 的值。因此，可以直接跳过 $a_k$。

这是因为 $a_k \leq (a_i \bmod a_k) + a_k < 2a_k$，因此只要有 $a_u \geq 2a_k$ 可用，就有 $(a_i \bmod a_u) + a_u > (a_i \bmod a_k) + a_k$。

结论 3 结论 4 之间十分的相契。最后算法的实现步骤如下：

使用 vector<pair<int, long long>> 存储满足 $F([l, i], i) > F([l+1, i], i)$ 的位置 $l$，并记录对应的 $F([l, i], i)$。
使用一个栈存储尚未被移除的元素。
针对 $a_i$ 向左扫描的过程中：
- 从栈顶到栈底枚举所有元素 $a_k$。
- 如果 $a_k > a_i / 2$，则计数器 cnt++。
- 如果 $a_k \leq a_i / 2$，则给 $a_k$ 新增一个删除标记。
- 如果 cnt 达到 $2$，立刻停止扫描。
- 移除累积了两个删除标记的元素。
- 将具有一个或零个删除标记的元素按照原顺序压回栈中。
最后将 $i$ 以初始零个删除标记压入栈中。

这确保了总扫描长度为 $O(n)$，因为每个元素对总扫描长度的贡献至多是 $2+2=4$。

算法 4 的时间复杂度为 $O(n + q \log n)$，可以获得 $100$ 分满分。

水仙平原

idea, solution, std, data from Melania

用 AC 自动机结点表示一个位置距离被 ban 掉还有多少步

每个奇数位置放一个结点，初始化成根

回答 <：左边 append 1，右边 append 0
回答 >：左边 append 0，右边 append 1

每个结点定义一个势能，每次询问左右两边 1 - 0 相等的位置

势能：E(ch[u][0]) + E(ch[u][1]) = k * E(u)

迭代 200 轮来计算 E

维护连续段，每个连续段是同一个结点，每次询问会切开一个连续段

把所有已经寄了的连续段丢掉

O(q*连续段个数)

另外一种不那么暴力的办法是注意到一个位置的当前结点只跟最后 100 个字符有关系，所以可以开一个线段树

需要手写 uint192

证明：这个 k 就是 AC 自动机转移矩阵的特征值。根据 Perron-Frobenius 定理最大的特征值存在且唯一

前提是 AC 自动机把叶子结点拔掉以后强连通，这就是为什么题目保证开头结尾都是 F

如果不强连通的话定理不成立，按照不同强连通分量内部的 k 从大往小分层做。

但是只问 y < x 还是 y > x 没办法同时均匀切开每一层，如果改成允许制造 m 个切分点，问 y 属于奇数区间还是偶数区间，才可以做

根据 Borsuk-Ulam 定理 m ≥ 强连通分量个数的时候一定有解

Melania的博客

博客