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

在这篇文章中，我们使用 $H$ 表示禁止的字符串集合，其中 $n$ 个禁止字符串记为 $h_1, h_2, \cdots, h_n$。

这个问题只是 CF1924F 的加强版，在这篇文章中对应于 $H = \{$TTT$,$FFF$\}$ 的情况。tzl_Dedicatus545 写的题解描述了针对这个特定情况的做法，掌握那个做法对于理解适用于更一般集合 $H$ 的做法十分有帮助。

排除一个奇数位置

考虑在什么条件下，一个奇数位置 $y$ 可以从小老鼠的潜在藏匿位置集合中被排除。

假设选手已经进行了 $q$ 个询问 $x_1, x_2, \cdots, x_q$，并从交互库那里收到了回答 $o_1, o_2, \cdots, o_q$。

对于每个奇数位置 $y$，定义一个长度为 $q$ 的字符串 $s_y$，称为 $y$ 的历史字符串，由 T 和 F 组成：

如果 $o_i$ 是 < 且 $x_i < y$，或者如果 $o_i$ 是 > 且 $x_i > y$，则 $s_{y,i}$ 为 T。
如果 $o_i$ 是 < 且 $x_i > y$，或者如果 $o_i$ 是 > 且 $x_i < y$，则 $s_{y,i}$ 为 F。

因此，$s_y$ 反映了交互库的每个回答是真话 T 还是假话 F，假设小老鼠实际上位于位置 $y$。

如果 $s_y$ 包含了至少一个禁止字符串 $h_i$，则位置 $y$ 被排除。否则，如果 $s_y$ 不包含任何禁止字符串，$y$ 仍然是一个可能的藏匿位置。

构建 Aho-Corasick 自动机

为了刻画这一条件，我们构建 $H$ 的字典树以及 Aho-Corasick 自动机 $\text{ACAM}(H)$，其中包含 $n$ 个禁止字符串 $h_1,h_2,\cdots,h_n$。

一个由 T 和 F 组成的字符串 $s$ 是不合法的，当且仅当它包含至少一个禁止字符串 $h_i\in H$ 作为连续的子串。直接在 $\text{ACAM}(H)$ 上遍历 $s$ 即可判定其合法性（一个 $s$ 合法当且仅当遍历过程从未到达过不合法结点）。

一部分字典树结点本身就是不合法的。除了直接对应于 $h_1,h_2,\cdots,h_n$ 的结点以外，如果一个字典树结点对应的字符串包含至少一个禁止字符串作为子串，那么这个结点也必须标记为不合法的。

结论 1：$\text{ACAM}(H)$ 中所有合法的结点形成一个强连通有向图。

结论 1 的证明：

从根结点出发，直接沿着树边行走可以到达所有合法结点。
从任何一个合法结点出发，通过长度不超过 $\max|h_i|$ 的一连串 T 边，都可以返回到根结点。
- 由于 $H$ 中的所有字符串都以 F 结尾，追加一系列 T 不会使一个原本合法的字符串变的不合法。
- 由于 $H$ 中的所有字符串都以 F 开头，追加最多 $\max|h_i|$ 个 T 可以确保自动机匹配的最长后缀回退到空后缀。

因此，如果只保留合法结点以及它们在 $\text{ACAM}(H)$ 中的所有转移作为连边，一定能得到一个强连通的有向图。

交互库的实现

我们站在交互库的角度思考问题。作为交互库，我们需要维护哪些 $y$ 仍有可能是小老鼠的藏匿位置。

对于每个奇数 $y \in [1, 2 \times 10^f - 1]$，我们维护一个字典树结点 $u_y$，表示 $y$ 的历史字符串 $s_y$ 当前匹配到的字典树结点。

如果决定对查询 $x$ 回答 <：给所有 $y < x$ 的 $s_y$ 追加一个 F，给所有 $y > x$ 的 $s_y$ 追加一个 T。
如果决定对查询 $x$ 回答 >：给所有 $y < x$ 的 $s_y$ 追加一个 T，给所有 $y > x$ 的 $s_y$ 追加一个 F。

在 $s_y$ 的最后追加一个字符，相当于沿着对应的出边在 $\text{ACAM}(H)$ 中更新 $u_y$。

站在交互库的角度思考，交互库可以自由选择回答 < 还是 >。

一种直接的实现是：选择排除 $y$ 的个数最小的那个答案。

然而，这种直接的实现并不理想，因为某些合法结点比其他结点更接近被排除。例如，距离被排除只差一个 F 的结点被认为是更受威胁的结点。为了解决这个问题，我们引入了结点势能的概念。

势能的定义

为每个字典树结点 $u$ 定义一个势能 $k_u$，表示该结点危险的程度。

结论 2： 设 $F(u, n)$ 为从结点 $u$ 开始的有效长度为 $n$ 的延续的数量。具体来说，$F(u, n)$ 计算的是长度为 $n$ 的由 T 和 F 组成的字符串 $t$ 的数量，使得 $s + t$ 是合法的，其中 $s$ 是对应于结点 $u$ 的 T 和 F 字符串。

对于所有合法结点 $u$，存在一个共同的 $\lambda \in [1, 2)$ 和常数 $k_u > 0$，使得： $$ \lim_{n \to \infty} \frac{F(u, n)}{k_u \lambda^n} = 1 $$ 结论 2 的证明：

使用线性代数来建模自动机。设 $A$ 为 $\text{ACAM}(H)$ 中合法结点的强连通分量的邻接矩阵，其中 $A_{u,v} = 1$ 如果存在通过 F 或 T 从 $u$ 到 $v$ 的直接一步转换，否则 $A_{u,v} = 0$。

由于 $A$ 是一个非负的、原始矩阵，Perron-Frobenius 定理适用：

存在一个实数 $\lambda > 0$（$A$ 的谱半径），其值超过任何其他特征值的绝对值。
存在对应于 $\lambda$ 的正的左特征向量和右特征向量。

函数 $F(u, n)$ 是 $A^n \mathbf{e}$ 的第 $u$ 个分量，其中 $\mathbf{e}$ 是一个全为 1 的向量。随着 $n$ 趋近于无穷，$A^n \approx \lambda^n \mathbf{v} \mathbf{w}^T$，其中 $\mathbf{v}$ 和 $\mathbf{w}$ 分别是全正的右特征向量和左特征向量，且 $\mathbf{w}$ 被标准化使其各项之和等于 $1$。因此， $$ F(u, n) \approx k_u \lambda^n $$ 其中 $k_u$ 包含了 $\mathbf{v}$ 的第 $u$ 个分量，从而证明了结论 2。

势能的使用

定义结点势能的动机如下：如果所有存活结点的当前总势能为 $E$，在回答 < 后，总势能变为 $E_<$，在回答 > 后，总势能变为 $E_>$。我们始终有： $$ E_< + E_> = \lambda E $$ 这同时引出了交互库和选手所使用的策略：

交互库的策略： 交互库计算每种可能回答的 $E_<$ 和 $E_>$，并选择使剩余势能最大的回答（< 或 >）。这确保了： $$ \max(E_<, E_>) \geq \frac{\lambda}{2} E $$ **选手的策略：** 选手旨在最小化 $\max(E_<, E_>)$。由于 $E_< + E_> = \lambda E$ 保持不变，这可以通过尽可能平衡 $E_<$ 和 $E_>$ 来实现，实际上是选择一个查询点以最小化 $|E_< - E_>|$。这个差异被限制在 1 以内，因为在 $0$ 或 $2 \times 10^f$ 处查询会交换 $E_<$ 和 $E_>$。随着查询点的移动，$E_<$ 减少 $d$，$E_>$ 增加 $d$，其中 $d = k_{\text{trans}(u,0)} - k_{\text{trans}(u,1)} \leq 1$。这可以被视为表示 $E_<$ 和 $E_>$ 的分段线性函数的交点。

为了实现这一策略，维护具有相同 $u_y$ 值的连续段，这些段由三元组 $(l_i, r_i, v_i)$ 表示，其中 $l_i$ 和 $r_i$ 是奇数，$v_i$ 是字典树结点。对于每个查询 $x$ 和收到的回答：

如果回答是 <：
- 对于所有 $y < x$，将 $u_y$ 更新为 $\text{trans}(v_i, 1)$。
- 对于所有 $y > x$，将 $u_y$ 更新为 $\text{trans}(v_i, 0)$。
如果回答是 >：
- 对于所有 $y < x$，将 $u_y$ 更新为 $\text{trans}(v_i, 0)$。
- 对于所有 $y > x$，将 $u_y$ 更新为 $\text{trans}(v_i, 1)$。
如果 $x$ 位于一个区间 $[l_i, r_i]$ 内：
- 将该区间拆分为 $(l_i, x, v_i)$ 和 $(x, r_i, v_i)$。
- 按上述方式进行更新。

每个查询都会拆分一个连续的区间，导致时间复杂度为 $O(q^2)$，并获得 84 分。通过标准化 $k_u$ 值（将每个 $k_u$ 按最大值缩放，使最大的值变为 $1$），我们确保 $|E_< - E_>| \leq 1$。

为了进一步优化，排除所有被淘汰的区间并仅保留活动区间，将时间复杂度降低到 $O(qc)$，其中 $c$ 是区间的数量，从而获得满分（100 分）。

或者，实施一个动态区间树，每个结点维护该区间内所有 $u_y$ 是否相同（或为零）并跟踪活动 $u_y$ 的数量。每个操作涉及 $O(\log 10^f)$ 次计算，从而提供更高效的复杂度分析，同样可以获得 $100$ 分满分。

势能的近似计算

计算并使用精确的实数 $k(u)$ 是不切实际的。相反，通过迭代 $F(u, 200)$ 并标准化这些值（将最大的值缩放到 $2^{63}$，其他值按比例缩放，然后四舍五入）来近似 $k(u)$。

由于数轴的长度为 uint128，且势能为 uint64，因此需要实现高精度的无符号整数（例如 uint192）。这些必须支持加法、减法、比较，以及通过 uint128 和 uint64 的乘积进行初始化。

收敛性考虑： 定义相对误差 $$ F_?(u, n) = \left| \frac{F(u, n)}{k(u) \lambda^n} - 1 \right| $$ 表示 $F(u, n)$ 与其渐近近似 $k(u) \lambda^n$ 之间的差异。误差以 $O\left(\left( \frac{|\lambda'|}{\lambda} \right)^n\right)$ 的速率呈指数级下降，其中 $\lambda'$ 是绝对值第二大的特征值。

未解决的问题 1： 我们无法提供 $\lambda - |\lambda'|$（谱间隙）的下界。较大的谱间隙意味着较小的 $\frac{|\lambda'|}{\lambda}$，从而导致更快的收敛，使得使用较少的迭代次数即可获得更精确的近似。

下界和上界 $L$ 和 $R$ 的计算

我们在问题陈述中提到存在两个合理的过程 compute_lower_bound() 和 compute_upper_bound()，用于根据输入数据自动计算 $L$ 和 $R$。实际上，我们使用的过程如下：

计算下界 $L$：
- 从总势能 $N = 10^f$ 开始。
- 在每次迭代中，更新 $N \leftarrow \frac{\lambda N}{2}$。
- $L$ 是第一次迭代使得 $N \leq 10^g$ 的迭代次数。
这是因为在任何剩余存活位置 $\leq 10^g$ 的状态下，总势能必须 $\leq 10^g$。
计算上界 $R$：
- 从总势能 $N = 10^f$ 开始。
- 在每次迭代中，更新 $N \leftarrow \frac{\lambda N + 1}{2}$。
- $R$ 是第一次迭代使得 $N < (10^g + 1)\alpha$ 的迭代次数，其中 $\alpha$ 是所有合法结点中的最小势能。
这是因为在任何总势能 $< (10^g + 1)\alpha$ 的状态下，剩余存活位置必须 $\leq 10^g$。

未解决的问题 2： 我们无法提供 $\alpha$ 的下界，$\alpha$ 表示所有合法结点中最小和最大 $k_u$ 值之间的比率（即 Perron-Frobenius 定理中的特征向量 $\mathbf{v}$ 的最小和最大条目之间的比率）。

Information Chart

Information Chart:
bluff1.in: L = 60, R = 60, h_sum = 1, h_max = 1, ratio = 1
bluff2.in: L = 174, R = 177, h_sum = 2, h_max = 2, ratio = 1.01724
bluff3.in: L = 174, R = 177, h_sum = 2, h_max = 2, ratio = 1.01724
bluff4.in: L = 174, R = 177, h_sum = 2, h_max = 2, ratio = 1.01724
bluff5.in: L = 440, R = 449, h_sum = 3, h_max = 3, ratio = 1.02045
bluff6.in: L = 440, R = 449, h_sum = 3, h_max = 3, ratio = 1.02045
bluff7.in: L = 440, R = 449, h_sum = 3, h_max = 3, ratio = 1.02045
bluff8.in: L = 282, R = 287, h_sum = 3, h_max = 3, ratio = 1.01773
bluff9.in: L = 282, R = 287, h_sum = 3, h_max = 3, ratio = 1.01773
bluff10.in: L = 282, R = 287, h_sum = 3, h_max = 3, ratio = 1.01773
bluff11.in: L = 8008, R = 8185, h_sum = 7, h_max = 7, ratio = 1.0221
bluff12.in: L = 5288, R = 5404, h_sum = 7, h_max = 7, ratio = 1.02194
bluff13.in: L = 4507, R = 4604, h_sum = 7, h_max = 7, ratio = 1.02152
bluff14.in: L = 4379, R = 4474, h_sum = 7, h_max = 7, ratio = 1.02169
bluff15.in: L = 4245, R = 4337, h_sum = 7, h_max = 7, ratio = 1.02167
bluff16.in: L = 4113, R = 4203, h_sum = 7, h_max = 7, ratio = 1.02188
bluff17.in: L = 4113, R = 4203, h_sum = 7, h_max = 7, ratio = 1.02188
bluff18.in: L = 3911, R = 3996, h_sum = 6, h_max = 6, ratio = 1.02173
bluff19.in: L = 2218, R = 2265, h_sum = 6, h_max = 6, ratio = 1.02119
bluff20.in: L = 2085, R = 2130, h_sum = 6, h_max = 6, ratio = 1.02158
bluff21.in: L = 9725, R = 9952, h_sum = 225452, h_max = 31, ratio = 1.02334
bluff22.in: L = 9404, R = 9618, h_sum = 226966, h_max = 32, ratio = 1.02276
bluff23.in: L = 8986, R = 9190, h_sum = 226346, h_max = 32, ratio = 1.0227
bluff24.in: L = 8796, R = 8988, h_sum = 222071, h_max = 31, ratio = 1.02183
bluff25.in: L = 8606, R = 8799, h_sum = 264821, h_max = 41, ratio = 1.02243
bluff26.in: L = 8571, R = 8757, h_sum = 246295, h_max = 37, ratio = 1.0217
bluff27.in: L = 8177, R = 8362, h_sum = 240395, h_max = 36, ratio = 1.02262
bluff28.in: L = 7525, R = 7695, h_sum = 224467, h_max = 31, ratio = 1.02259
bluff29.in: L = 7011, R = 7170, h_sum = 221676, h_max = 31, ratio = 1.02268
bluff30.in: L = 5961, R = 6125, h_sum = 238018, h_max = 35, ratio = 1.02751
bluff31.in: L = 146449, R = 149955, h_sum = 305501, h_max = 41, ratio = 1.02394
bluff32.in: L = 146446, R = 149939, h_sum = 359112, h_max = 49, ratio = 1.02385
bluff33.in: L = 146402, R = 149885, h_sum = 304109, h_max = 40, ratio = 1.02379
bluff34.in: L = 145973, R = 149435, h_sum = 365159, h_max = 48, ratio = 1.02372
bluff35.in: L = 145067, R = 148518, h_sum = 418110, h_max = 55, ratio = 1.02379
bluff36.in: L = 141704, R = 145065, h_sum = 315053, h_max = 42, ratio = 1.02372
bluff37.in: L = 137359, R = 140572, h_sum = 269882, h_max = 34, ratio = 1.02339
bluff38.in: L = 131976, R = 135018, h_sum = 358775, h_max = 49, ratio = 1.02305
bluff39.in: L = 127469, R = 130391, h_sum = 411627, h_max = 54, ratio = 1.02292
bluff40.in: L = 117471, R = 120090, h_sum = 414802, h_max = 55, ratio = 1.02229
ex_bluff1.in: L = 60, R = 60, h_sum = 1, h_max = 1, ratio = 1
ex_bluff2.in: L = 174, R = 177, h_sum = 2, h_max = 2, ratio = 1.01724
ex_bluff3.in: L = 440, R = 449, h_sum = 3, h_max = 3, ratio = 1.02045
ex_bluff4.in: L = 282, R = 287, h_sum = 3, h_max = 3, ratio = 1.01773
ex_bluff5.in: L = 4507, R = 4604, h_sum = 7, h_max = 7, ratio = 1.02152
ex_bluff6.in: L = 9221, R = 9430, h_sum = 224402, h_max = 30, ratio = 1.02267
ex_bluff7.in: L = 145099, R = 148531, h_sum = 416453, h_max = 54, ratio = 1.02365

Melania的博客

博客