偷吃蛋糕
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 ≥ 强连通分量个数的时候一定有解