UOJ Logo Melania的博客

博客

Goodbye Jiachen 题解

2025-01-27 21:05:11 By Melania

梅花侍从

idea, solution, std, data from GeZhiyuan

直接做肯定不好做,我们考虑分析一下结构。对于划分出来的两组,我们观测其在 $x$ 中的相对位置关系,分别用 XO 表示两组内元素的位置,发现有意义的只有 XXOOOXXXXOOO 两种。其他的可以进行如下替换:

XXOXOO -> XXXOOO
XXOOXO -> XXOOOX
XOXXOO -> XXOXOO -> XXXOOO
XOXOXO -> XXOOXO -> XXOOOX
XOXOOX -> XXOOOX
XOOXXO -> OXOXXO => XOXOOX -> XXOOOX
XOOXOX -> XOOXXO -> OXOXXO => XOXOOX -> XXOOOX
XOOOXX -> OXOOXX => XOXXOO -> XXOXOO -> XXXOOO

如上的每一次转变都显然严格不劣,至此我们分析出了所有可能的位置关系,实际上也正对应这前两组小样例的情况。由于可行的两种相对位置较为特殊,于是直接区间 dp 即可,记录 $f_{l, r}$ 表示 $x_l , x_{l+1}, \dots, x_r$ 划分的答案。复杂度 $O(n^3)$。

方片骑士

idea, solution, std, data from GeZhiyuan

小插曲

本题为我在验 Problem - 2006E - Codeforces 时看错题得到的产物,并在当时进行了查重,但由于跨度的时间过长,没想到在最近的一场 CF Div.2 中出现了此题的弱化版 Problem - 2031E - Codeforces。但是好在那题的做法虽然是正解的一部分,但也只能多通过 Sub2 获得 $15$ 分,并且作为萌萌的第二题本来也是希望能给大家送足够的分。但作为出题人的查重失误还是在此处给被影响到的所有人深深致歉。

算法 I

不难看出最终的树每个结点实际上都对应了原树的一个连通块。因此我们先假设定好根,然后进行如下动态规划:

  • $f_u$ 表示 $u$ 这棵子树,以 $u$ 为根的树至少需要多大的满二叉树收缩得到,同样的大小为 $s$ 则记录 $\log_{2}{(s+1)}$ 的值。

直接合并即可,有:

  • 如果 $u$ 只有一个儿子 $v$,则 $f_u = f_v + 1$。
  • 否则令 $u$ 的儿子集合为 $S$,$f_u = \lceil \log_2 (\sum_{v \in S} 2^{f_v}) \rceil$

直接枚举根并进行动态规划,可以做到 $O(n^2)$,如果不拼链和菊花,预计得分 $30$。

算法 II

考虑进行换根,记录:

  • $g_u$ 表示去除 $u$ 这棵子树,并以 $u$ 的父亲为根的树至少需要多大的满二叉树收缩得到,同样的大小为 $s$ 则记录 $\log_{2}{(s+1)}$ 的值。

考虑换根时动态维护 $\sum_{v \in S} 2^{f_v}$,相当于先将所有信息加入进去,然后每次查询如果删除一个的贡献是什么。

直接暴力找前驱后继可以做到 $O(n \sqrt n)$,预计得分 $50$ 至 $75$;也可以用线段树维护,复杂度 $O(n \log n)$,预计得分 $75$ 至 $100$。

也可以先将所有信息加入,然后记录二进制下的最高位,次高位,次次高位的位置,通过一系列分类讨论可以做到 $O(n)$。

算法 III

算法 II 实际上非常愚蠢,因为可以观察到,本题不需要询问每个根的答案,只需要知道所有根的最小值。

因此考虑换根时递归到 $u$ 时,对于所有 $u$ 的儿子 $v$,只有 $f_v$ 最大的才可能成为更优的根,其他的无需递归,因此这样暴力做就是 $O(n)$ 的,常数优秀的同时非常好写,预计得分 $100$。

算法 $\pi$

这题好像处理的方法非常多,欢迎大家在下方讨论。

可能有一些极快或者我没有料到的 $O(n \sqrt n)$ 也通过了此题。(真实性存疑)

还有高手

正如 小插曲中 所说,本题为我在验 Problem - 2006E - Codeforces 时看错题得到的产物。与那题相同,本题也可以支持像那题一样每次添加一个叶子并进行询问!但由于过于毒瘤还是选择了当下的版本。 你可以试试能解决 $n \leq 2 \times 10^5$ 并动态增加叶子的版本吗?

以下是来源于 huahua 的做法:

我们先把询问离线,把最终树的结构拿到,然后对树进行树剖,进行 ddp。

考虑 ddp 需要什么,我们对于每个结点 $u$,先对其所有轻儿子建立一棵线段树,维护轻儿子的 $\sum 2^{f_v}$ 在二进制下的值。

然后我们再考虑加入重儿子,对于没有轻儿子的显然好处理,否则假设重儿子的 dp 值为 $x$,而 $\sum 2^{f_v}$ 的最高位为 $a$,次高位为 $b$。

对于不存在 $b$ 的情况:

  • 如果 $x > a$ 则 $f_u = x+1$。
  • 否则如果 $x \leq a$ 则 $f_u = a+1$。

对于 $b = a - 1$ 的情况,我们令 $c$ 为最小的满足 $\sum 2^{f_v}$ 在二进制下第 $[c, a]$ 都为 $1$ 的非负整数:

  • 如果 $c$ 不是最低位:
    • 如果 $x > a$ 则 $f_u = x+1$。
    • 如果 $c \leq x \leq a$ 则 $f_u = a+2$。
    • 如果 $x < c$ 则 $f_u = a + 1$。
  • 如果 $c$ 是最低位:
    • 如果 $x > a$ 则 $f_u = x+1$。
    • 如果 $c < x \leq a$ 则 $f_u = a+2$。
    • 如果 $x \leq c$ 则 $f_u = a+1$。

对于 $b < a-1$ 的情况:

  • 如果 $x > a$ 则 $f_u = x+1$。
  • 如果 $x = a$ 则 $f_u = a+2$。
  • 如果 $x < a$ 则 $f_u = a+1$。

不难发现在所有情况下,$f_u$ 始终是一个关于 $x$ 的至多三段的分段函数,始终为最后一段为 $x$ 上系数为 $1$ 的一次函数,且除最后一段外为常函数。

然后我们再次观察这个转移的特点,我们尝试观察对于一段重链,令链首为 $t$,而我们在链末传入的 $x$ 和最终 $f_t$ 是什么关系呢?实际上仍然是满足如上条件的至多三段分段函数!

于是我们就解决了非换根的问题,对于每条重链我们也建立一棵线段树去维护函数的复合,总复 $O(n \log^2 n)$。利用全局平衡二叉树的技巧可以做到 $O(n \log n)$。

对于换根的问题实际上是简单的,这种 ddp 本身也支持换根,且不难发现在加入叶子的过程中,最优的根只有两种可能,不动或者沿着原根到新加入的叶子的路径移动 $1$ 步。至此我们在 $O(n \log n)$ 或 $O(n \log^2 n)$ 内解决了该问题。

红桃王后

idea, solution, std, data from xianhz

子任务 I

我会暴力枚举/分类讨论!

直接枚举每轮是哪些人获胜,或者直接把 $n\leq 3$ 的情况画出来逐一判断,这些都是可行的。

总之只要是正确的做法大概都能通过这档部分分。

子任务 II

我会观察性质!

考虑建图 $G$, 对于所有关系 $u$ 战胜 $v$ 连一条有向边 $u\to v$。

注意到对于一个合法的图,必要条件有:

  • 是个 DAG。(若 $u$ 战胜 $v$ 则 $u$ 的排名会严格比 $v$ 高)
  • 有恰好一个点没有入边只有出边。(即第一名是全胜的)
    • 实际上易发现有 $i$ 条入边的有恰好 $\binom ni$个人。
  • 第一名直接或间接战胜了所有人,其中 $u$ 直接或间接战胜 $v$ 可以理解为图中存在一条从 $u$ 到 $v$ 的路径。

所以对于每一轮的败者,在他们在败者组中决出的第一名(设为 $A$ )在原图中恰有一条入边,且一 个人在败者组当且仅当它在 $A$ 的可达集合中。

所以对于每一轮不再枚举哪些人获胜,而是只在恰有一条入边的点中枚举 $A$ 即可。复杂度 $O(n!2^n)$。

子任务 III

我会对暴力记忆化!

在刚才搜索的过程中加上记忆化,即维护 $f_S$ 表示如果集合 $S$ 内的人参加比赛是否存在合法方案。

这看上去作用有限,甚至是个负优化,但你如果把它加上就会发现自己莫名其妙通过了这个子任务。

你可能会质疑出题人的数据强度。(好吧可能确实需要质疑)但这个做法的复杂度其实是有保证的。

子任务 IV

我知道记忆化为什么是对的!

考虑再建反图 $G_r$,对于所有关系 $u$ 战胜 $v$ 连一条有向边 $v\to u$,由对称性它也满足我们之前推的所有性质。

考虑去分析状态数:注意到对于一个 $f_S=1$ 的 $S$,它一定由 $S$ 中的第一名在 $G$ 中的可达集合$S$ 中的最后一名在 $G_r$ 中的可达集合 的交生成。

说人话一点就是:如果你知道了 $S$ 中的第一名和最后一名你就可以唯一确定 $S$ 了,所以合法的 $S$ 的数量是不超过 $O(2^{2n})$ 的,这也是对刚才记忆化的复杂度的证明。

所以你去拿 $dp_{i,j}$ 表示:由 $i$ 和 $j$ 生成的 $S$ 在 $G$ 中的导出子图是否合法。

让我们再分析一下状态数。

最坏情况是:第 $i$ 个人直接或间接战胜了所有 $i\subset j$ 的 $j$,直接或间接输给了所有 $j\subset i$ 的 $j$。(这里将 $i$ 视作的集合就是 0-index 时 $i$ 在二进制下的表出)

这时我们会搜索到一个元素当且仅当 $f_S=1$。而合法的 $S$ 能由一对 $i\subset j$ 的 $(i,j)$ 生成,而对于一对 $(i,j)$ 的转移复杂度应该是 $O(2^{|j\setminus i|}n^2)$

通过组合意义可证明复杂度是 $O(4^nn^2)$,这也给出了该题计数版本的一个多项式级别做法。

当然如果你对于子任务 3 的记忆化直接使用 xor hashing 存储状态,应该也可以通过该子任务,但代价呢?(upd:好吧因为是 IOI 赛制所以没法有什么代价)

子任务 V

我会猜结论! 虽然上面的做法看上去很妙,但只用上述性质的话恐怕没法优化复杂度了。$3^n$ 级别的状态数让我们不得不借助题目本身的性质来优化 dp。

注意到若 $(i,j)$ 能被合法划分成 $(i,k_1),(l_1,j)$ 和 $(i,k_2),(l_2,j)$,则 $dp_{i,k_1}=dp_{l_1,j}=1$ 时必有 $dp_{i,k_2}=dp_{l_2,j}=1$,此时有 $dp_{i,j}=1$(这里合法划分的意思是两个集合间的边是一组完美匹配)

证明是容易的:考虑两个划分分别是 $A\oplus B,C\oplus D$ 和 $A\oplus C,B\oplus D$。

由更低阶的结论我们有 $f_A=f_B=f_C=f_D=1$,然后交换一下划分的顺序即可。

所以结论就是:我们只要能找到一组 $(i,k),(l,j)$ 使得这个划分在当前层没有矛盾,就可以往下递归,因为 $(i,k)$ 和 $(l,j)$ 一定都有合法解。

感性来说,就是我们不停划分会让每个子问题内部的限制更宽松,并且不会让一个之前原本可以使用的匹配变得不合法。(或者说就是无后效性)

所以我们直接枚举第 $2^{n-1}+1$ 名,去看它的可达集合和这个集合的补集之间的边是否是一组完美匹配即可判断。

复杂度 $F(n)=2^nn^2+2F(n-1)=O(2^nn^3)$。

子任务 VI

我会用位运算并行求可达集合与判断完美匹配!

考虑求可达集合无非是在一个有向图中,按一个边的顺序遍历,对于一条边 $(i,j)$,令 vis[j]|=vis[i]

那么如果我们要求 个点的可达集合,就可以用位运算加速这个过程:对于第 $i$ 个点 $p_i$,初始令 $vis_{p_i}=2^i$,然后执行上述算法。

对于判断完美匹配方法也是类似的:对于一条边 $(i,j)$,令 d[i]+=vis[j]&~vis[i]d[j]+=vis[j]&~vis[i],最后判断是否所有 $d$ 都是 $1$ 。 由于我们只在乎 $d$ 是 $0$,$1$ ,还是 $\geq 2$ ,所以用两个值维护 $d_i$ 在第 $j$ 位是否 $\geq 1$ 和是否 $\geq 2$ 即可。

这样我们就将构造和计数复杂度分别优化成了 $O(2^nn^2)$ 和 $O(4^nn)$,足以通过本题。

黑桃国王

idea from wzc_IOI_czw, fast_photon, bunH2O; solution from zhoukangyang, Rainbow_sjy; std, data from LeafSeek, Melania

准备工作

  • 如果一条有向边 $u\to v$ 不出现在任何一个回路中(两个端点处在不同的强连通分量),可以直接删去这条边。
  • 如果一个结点 $u$ 不出现在任何一个回路中(处在单独一个结点的强连通分量并且没有自环),可以直接删去这个结点。

删去这些东西以后,从任何一个结点 $u$ 出发,无论前面怎么走后面一定能走回去。也就是说:对于回路的一个可空的前缀 $u_0\to u_1\to\cdots\to u_i(i\geq0)$,一定能找到一个非空的后续 $u_i\to u_{i+1}\to\cdots\to u_ℓ(ℓ\geq i+1)$,使得 $u_ℓ=u_0$。

最小无穷路径

定义 $s(u,i)$ 表示从 $u$ 开始游走 $i-1$ 步形成的字符串里面字典序最小的那个。

定义 $f(u,i)$ 表示 $s(u,i)$ 在 $s(1,i)\sim s(n,i)$ 里面去重之后的排名。

根据定义 $s(u,i)=a_u+\min\limits_{u\to v}s(v,i-1)$。

因此我们可以递推 $f(u,i)$ 等于二元组 $\left(a_u,\min\limits_{u\to v}f(v,i-1)\right)$ 在所有 $n$ 个(第 $i$ 步的)二元组里面去重之后的排名。

如果递推到了某个 $i$ 我们发现所有 $f(u,i)=f(u,i-1)$,那么 $f(u,+\infty)=\cdots=f(u,i+1)=f(u,i)=f(u,i-1)$。

注意到 $f(u,i)$ 不同的两个 $u$ 后面永远不会合并,而相同的两个 $u$ 后面有可能会分开。因此这个 $i\leq n$。

我们把 $s(u,+\infty)$ 称作 $u$ 的最小无穷路径。上面的算法可以在 $O(mn)$ 的时间内求出所有最小无穷路径。

性质 I

考虑刻画所有 $n$ 个最小无穷路径形成的结构。

假设最后有 $m$ 个不同的最小无穷路径(即 $f(1,+\infty)\sim f(n,+\infty)$ 的值域是 $1\sim m$)。

那么可以建出一个有 $m$ 个结点的根向环套树森林,每个结点上面写有一个字符,同时有唯一的一条出边指向另外一个结点。对于原图中的某个结点 $u$,森林中的结点 $f(u,+\infty)$ 的唯一出边指向的就是 $\min\limits_{u\to v}f(v,+\infty)$。

在这个根向环套树森林当中,(去重之后的)排名为 $i$ 的最小无穷路径等于从结点 $i$ 出发沿着出边一直游走形成的无穷字符串。

由于所有 $m$ 个无穷字符串是两两不同的,我们的根向环套树森林一定满足以下两个性质:

  1. 每个环 $C$ 一定不存在非整串的非空周期。
  2. 每个结点 $u$ 的所有入度 $v_i$,上面写有的字符一定两两不同。

算法 I

固定一个起点 $u$,考虑所有 $u_0=u_ℓ=u$ 的回路生成的无穷字符串构成的集合 $S_u$。

  • 如果最小无穷路径是一个纯循环 $o$ 形(意味着 $f(u,+\infty)=C^\infty$),那么 $S_u$ 有一个 最小值 $C^\infty$​:

    1. 如果 $S_u$ 里面包含唯一一个元素,那么 $C^\infty$ 可以属于序列 $s_1\sim s_k$;

    2. 只要 $S_u$ 里面包含至少两个元素,那么 $C^\infty$ 可以属于序列 $s_1\sim s_k$,但是序列 $s_1\sim s_k$ 里面不能包含任何 $>C^\infty$ 的字符串 $X$。

      (这是因为对于任何一个字符串 $X>C^\infty$,一定存在一个 $Y\in S_u$ 满足 $X>Y>C^\infty$。)

  • 如果最小无穷路径是一个混循环 $\rho$ 形(意味着 $f(u,+\infty)=A+C^\infty$),那么 $S_u$ 有一个 不在 $S_u$ 中的下确界 $A+C^\infty$:

    1. 此时 $S_u$ 里面包含至少两个元素,当然序列 $s_1\sim s_k$ 里面不能包含任何 $>A+C^\infty$ 的字符串 $X$。

      (这是因为对于任何一个字符串 $X>A+C^\infty$,一定存在一个 $Y\in S_u$ 满足 $X>Y>A+C^\infty$。)

对于上述三种情况,我们分别把 $u$ 称作一个第零类/第一类/第二类结点。

最后我们计算答案。我们依次枚举 $i\in\{1,2,\cdots,m\}$,考虑 $f(u,+\infty)=i$ 的所有结点 $u$:

  • 只要其中存在第二类结点,那么确定答案 $=i-1$,跳出循环;
  • 否则如果存在第一类结点,那么确定答案 $=i$,跳出循环;
  • 否则如果全部都是第零类结点,那么继续循环。

这里有一个小问题:我们已知一个结点 $u$ 的最小无穷路径是一个纯循环 $o$ 形,怎么判断它是一个第零类结点还是一个第一类结点?

我们考虑 $u$ 所在的强连通分量。只要这个强连通分量内存在一个生成不同字符串的回路,那么所有 $o$ 形都是第一类结点。

对于每一个强连通分量,我们刻画这个条件:拿出这些结点对应的无穷字符串排名。如果它们形成单独一个环,并且整个强连通分量内的任何一个结点 $u$ 所有出边 $u\to v$ 满足 $f(v,+\infty)$ 全部相同,那么所有 $o$ 形都是第零类结点;否则所有 $o$ 形都是第一类结点。

算法 I 的时间复杂度为 $O(mn)$,可以获得至少 $39$ 分。

枚举每个强连通分量,在其中刻画这个条件:拿出这些结点对应的无穷字符串排名。如果它们形成单独一个环,并且整个强连通分量内的任何一个结点 $u$ 所有出边 $u\to v$ 满足 $f(v,+\infty)$ 全部相同,那么所有 $o$ 形都是第零类结点;否则所有 $o$ 形都是第一类结点。

算法 I 的时间复杂度为 $O(mn)$,可以获得 $39$ 分或者更多。

算法 II

直接把算法 I 中计算 $f(1,+\infty)\sim f(n,+\infty)$ 的过程换成启发式分裂即可。

我们讲的具体一点。固定一个时刻,考虑关于 $s(1,+\infty)\sim s(n,+\infty)$ 的大小顺序我们掌握的信息。

我们开一棵二叉树 $T$ 来记录所有的信息。以下我们说明这棵二叉树 $T$ 的具体结构:

  • $T$ 中的每个结点代表 $G$ 中的一个结点集合。
  • $T$ 中的每个结点代表的集合等于它的两个儿子的并集。特别的,根结点代表全集 $\{1,2,\cdots,n\}$。
  • 对于两个 $G$ 中的结点 $u,v$,如果 $T$ 的 DFS 序中 $u$ 严格位于 $v$ 的左侧,那么说明 $s(u,+\infty) < s(v,+\infty)$。

在上述结构中,$T$ 的所有叶子结点代表的集合一定构成了 $\{1,2,\cdots,n\}$ 的一个划分。我们可以看到:只要两个 $G$ 中的结点 $u,v$ 处在不同的集合中,它们的大小顺序就是已知的。同一个集合内部的结点,它们的大小顺序在这个时刻是未知的。

对于一个 $G$ 中的结点 $u$,如果 $T$ 中的结点 $x$ 代表的集合包含了 $u$,我们就认为 $u$ 属于 $x$ 这个 等价类(这刻画了一个等价关系)。

每次进来一个新的信息,我们分裂 $T$ 的某个叶子结点 $x$ 产生左右两个子结点 $y,z$,表示我们已经知道 $y$ 等价类小于 $z$ 等价类。

最初的时候我们只根据 $a_u$ 建一个毛毛虫,每次把拥有最小字母的结点集合扔到左边,把剩下的结点集合扔到右边继续建毛毛虫。

我们希望持续使用 $T$ 作为证据更新自身,直到得到 $T$ 不能再更新的最终形态为止。

我们另开一棵二叉树 $T'$ 表示我们已经处理的结点。$T'$ 一直是 $T$ 包含根结点的一个连通块(最初 $T'$ 只包含根,最终 $T'=T$)。

考虑尽量简洁的储存 $T,T'$ 的形态。经过一番探索,我们发现维护以下三个数组是最好的办法:

  • $f_u$ 表示结点 $u$ 所在的 $T$ 等价类编号;
  • $g_u$ 表示结点 $u$ 的所有出度 $v$ 所在的 $T'$ 等价类当中(字典序)最小的等价类编号;
  • $\text{cnt}_u$ 表示拥有这个最小值的出度 $v$ 一共有多少个。

对于一个静止的时刻(没有正在处理的结点),一定有 $f_u$ 等于二元组 $(a_u,g_u)$ 在所有 $n$ 个二元组中(去重之后的)的排名。

我们维护一个队列 $Q$。每次 $T$ 的某个叶子结点 $x$ 被分裂,我们立刻把它推入队列的队尾。

我们每次取出队头结点 $x$(现在 $\in T'$),假设它的两个儿子叫做 $y,z$(现在 $\not\in T'$)。

第一步是正确更新所有 $g_u,\text{cnt}_u$ 的值。对于每个 $g_u=x$,更新之后 $g_u=y/z$ 都有可能:

  • 如果结点 $u$ 的 $\text{cnt}_u$ 个出度 $v$ 中存在一个属于 $y$ 等价类,那么更新 $g_u=y$;
  • 如果结点 $u$ 的 $\text{cnt}_u$ 个出度 $v$ 全部都属于 $z$ 等价类,那么更新 $g_u=z$。

第二步是正确更新所有受影响的 $T$ 等价类。一个等价类内的所有结点都拥有相同的 $f_u$,本来拥有相同的 $g_u=x$,现在 $g_u=y/z$。

  • 这个等价类内 $g_u$ 等于 $y$ 的,$f_u$ 新建一个白色结点作为 $f_u$ 的左儿子。
  • 这个等价类内 $g_u$ 等于 $z$ 的,$f_u$ 新建一个白色结点作为 $f_u$ 的右儿子。

最后我们实现启发式分裂。启发式分裂的含义是把较小的集合分裂出去,留下较大的集合。每次在 $T$ 中划分一个叶子结点 $x\to y/z$ 的时候,我们让 $y,z$ 之一等于 $x$。然后我们对于 分裂出去的是左儿子 和 分裂出去的是右儿子 两种情况,分别采用不同的实现方法。实现的时候,对于 $x\to y/z$,我们枚举那个被分裂出的集合的每个结点,再枚举它们的所有入度,即可更新到所有需要更新的等价类。

算法 II 的时间复杂度为 $O(m\log n)$,可以获得 $100$ 分。

珍珠守卫

idea, solution, std, data from LeafSeek, Melania

算法 :)

写一些似是而非的区间 DP。对于 sub 1~4,我已经拿了许多选手赛时提交的代码与搜索对拍,很容易拍出 hack 数据。

时间复杂度 $O(n^3 \text{poly}(m,k))$,赛时数据可以获得 $1 \sim 40$ 分。

算法 I

操作模型 I

我们假设存在一个最优操作方案同时符合以下两个描述:

  1. 如果两颗相邻珠子颜色相同,我们一定不会把它们分隔开。
  2. 我们只会进行一种加长操作。加长操作首先选定一颗珠子 $(a_i, c_i)$,然后不断插入一颗质量为 $1$ 的同色珠子,目的是以它为中心开启一个消除过程。我们不断地对剩余序列进行这种加长操作直到删空序列。

我们首先刻画所有符合操作模型 I 的方案统一具有的结构,然后针对这种结构设计一个区间 DP 计算出最小的操作次数 $q$。

结构模型 I

根据假设 1,对于所有极长同色区间 $[l, r]$,我们可以把 $(a_l, c_l) \sim (a_r, c_r)$ 这些珠子合并成一颗珠子 $\Big( a_l, \min \Big( \displaystyle\sum_{i=l}^r c_i, k-1 \Big) \Big)$。

合并同色区间简化了我们的问题,现在我们在所有 $a_i \neq a_{i+1}$ 的新序列上刻画结构。

考虑一个消除步骤同时消除掉的珠子。排除掉最后插入的几颗质量为 $1$ 的珠子,剩下的一定是初始序列的一个子序列,我们用一个集合 $S$ 表示它包含了原序列中的哪些位置。对于一个方案,我们用一个集合族 $\boldsymbol{\Omega}$ 表示所有消除步骤对应的 $S$ 构成的集合。

以下我们列出了 $\boldsymbol{\Omega}$ 一定满足的五个性质(必要条件)。事实上,只要一个集合族 $\boldsymbol{\Omega}$ 同时满足所有五个性质,那么它一定能够还原一个符合操作模型 I 的方案(充分条件)。具体怎么还原方案读者可以自己思考。

  1. $\boldsymbol{\Omega}$ 一定形成了 $\{ 1, 2, \cdots, n \}$ 的一个划分,每个位置恰好属于 $\boldsymbol{\Omega}$ 中的一个集合 $S$。
  2. 对于两个不同集合 $S, T \in \boldsymbol{\Omega}$,一定不会存在四个位置 $a < b < c < d$ 使得 $a, c \in S$,$b, d \in T$。
  3. 对于一个集合 $S \in \boldsymbol{\Omega}$,假设 $S = \{ p_1, p_2, \cdots, p_t \}$($p_1 < p_2 < \cdots < p_t$),那么 $a_{p_1} = a_{p_2} = \cdots = a_{p_t}$。
  4. 对于一个集合 $S \in \boldsymbol{\Omega}$,假设 $S = \{ p_1, p_2, \cdots, p_t \}$($p_1 < p_2 < \cdots < p_t$),那么以下两个一定成立一个:
    • $ \displaystyle\sum_{i=1}^t c_{p_t} \leq k-1$。
    • $ \displaystyle\sum_{i=1}^t c_{p_t} \geq k$。但是存在一个整数 $t' \in [1, t-1]$ 使得 $ \displaystyle\sum_{i=1}^{t'} c_{p_t} \leq k-1$,$ \displaystyle\sum_{i=t'+1}^t c_{p_t} \leq k-1$。
  5. 对于两个不同集合 $S, T \in \boldsymbol{\Omega}$,如果 $ \min(T) - \max(S) = 1$,我们连一条有向边 $S \to T$。那么 $\boldsymbol{\Omega}$ 中的所有集合被串成若干有向链。对于每一条有向链,以下两个一定成立一个:
    • 有向链的长度 $= 1$。
    • 有向链的长度 $\geq 2$,并且至少包含两种除了 $a_{l-1} = a_{r+1}$ 以外的颜色。

根据性质 4,我们又注意到一个操作方案的代价只跟 $\boldsymbol{\Omega}$ 有关,因此通过描述所有的 $\boldsymbol{\Omega}$,我们的区间 DP 当然就能计算出最小操作次数 $q$。

区间 DP 实现 I

我们可以使用以下几个 DP 数组进行区间 DP,具体转移留给读者自行思考。

  • 开一个 DP 数组 $C(l, r)$ 表示 $(a_l, c_l)(a_r, c_r)$ 形成一个集合 $S$ 的两端,区间 $[l, r]$ 内部的最小代价。
  • 开一个 DP 数组 $D(l, r)$ 表示 $(a_l, c_l)(a_r, c_r)$ 形成一个合法有向链的两端,区间 $[l, r]$ 内部的最小代价。
  • 开一个 DP 数组 $F(l, r, x, 0/1)$ 辅助 $C$ 的转移。其中 $x$ 表示当前 $c_{p_i}$ 的和,$0/1$ 表示最后一步吃掉的是一个区间还是一个同色 $a_{p_i}$。
  • 开一个 DP 数组 $G(l, r, x, 0/1)$ 辅助 $C$ 的转移。其中 $x$ 表示当前 $c_{p_i}$ 的和,$0/1$ 表示最后一步吃掉的是一个区间还是一个同色 $a_{p_i}$。
  • 开一个 DP 数组 $P(l, r)$ 辅助 $D$ 的转移。表示当前有向链还没有出现除了 $a_{l-1}, a_l$ 以外的颜色。
  • 开一个 DP 数组 $Q(l, r)$ 辅助 $D$ 的转移。表示当前有向链已经出现了除了 $a_{l-1}, a_l$ 以外的颜色。

时间复杂度 $O(n^3k)$,可以获得 $7$ 分。

第一类反例

1 1 2 1 1 3 4 1 1 1

1 1 2 1 1 3 4 1 [2] 1 1
1 1 2 1 1 3 4 1 2 1 1

1 1 2 1 1 3 [3] 4 1 2 1 1
1 1 2 1 1 3 3 4 1 2 1 1

1 1 2 1 1 3 3 [3] 4 1 2 1 1
1 1 2 1 1 >!< 4 1 2 1 1
1 1 2 1 1 4 1 2 1 1

1 1 2 1 1 4 [4] 1 2 1 1
1 1 2 1 1 4 4 1 2 1 1

1 1 2 1 1 4 4 [4] 1 2 1 1
1 1 2 1 1 >!< 1 2 1 1
1 1 2 >!< 2 1 1
1 1 2 2 1 1

1 1 2 2 [2] 1 1
1 1 >!< 1 1
>!<
win

第二类反例

11 222 3 4444 3333 22 1111 22 3333 4444 3 222 11

11 222 3 4444 3333 22 1111 [1] 22 3333 4444 3 222 11
11 222 3 4444 3333 22 >!< 22 3333 4444 3 222 11
11 222 3 4444 3333 22 22 3333 4444 3 222 11

11 222 3 4444 3333 22 [1] 22 3333 4444 3 222 11
11 222 3 4444 3333 22 1 22 3333 4444 3 222 11

11 222 3 4444 [4] 3333 22 1 22 3333 4444 3 222 11
11 222 3 >!< 3333 22 1 22 3333 4444 3 222 11
11 222 >!< 22 1 22 3333 4444 3 222 11
11 >!< 1 22 3333 4444 3 222 11
11 1 22 3333 4444 3 222 11

11 1 22 3333 4444 [4] 3 222 11
11 1 22 3333 >!< 3 222 11
11 1 22 >!< 222 11
11 1 >!< 11
>!<
win

算法 II

时间复杂度 $O\big(n^3\max(m,k)^3k^4\big)$,可以获得 $88$ 分。

算法 III

可以优化矩阵乘法。时间复杂度 $O\big(n^3\max(m,k)^2k^3\big)$,可以获得 $100$ 分。

Goodbye Jiachen 公告

2025-01-21 22:06:54 By Melania

再见,甲辰!

我们将于 1 月 27 日下午 13:00 到 18:00 举办一场 Goodbye Jiachen 比赛。比赛将进行 5 个小时,共五道题。

2024 年是中国农历甲辰龙年,除夕这一天将标志着龙年的结束。下一年是乙巳蛇年,蛇象征着智慧和循环的重生。

随着时间的推移,UOJ 迎来了新的发展阶段。从 Goodbye JiawuGoodbye Jiachen,我们共同见证了 UOJ 十年间的成长与变化。

本次比赛的题目带你进入扑克王国的世界。你将与五个扑克牌角色一同挑战,书写属于你的胜利篇章。

比赛链接:https://uoj.ac/contest/93

出题人:GeZhiyuanxianhzMelania

本次比赛将采用 IOI 赛制,每道题最多提交 50 次,可以实时查看成绩,最终取分数最高的提交,如果有多个分数最高的提交,那么取时间最早的。选手可以查看排行榜。

  1. 获得 UOJ 抱枕的获奖条件 SHA256 码是(503a7a6b9101f93d3ae46ed966fb655da144ef1387e6c802652caf50bd208512)。
  2. 获得 GeZhiyuan 固定小礼品的获奖条件 SHA256 码是(63549ae1c059533da2d3b98bff147f3585776242cbebe7b65741a3ff1cb535f4)。
  3. 获得 Melania 固定小礼品的获奖条件 SHA256 码是(0ad9e4b14d0fe0350a486f88dc762753a35793bd57938a06bfb1a692ed917297)。

为了与 NOI 保持一致,UOJ 从创立以来一直采用 OI 赛制(只取最后一次提交计算得分)。

然而,随着 NOI 在 2023 年部署了 SelfEval 评测系统,选手可以实时查看程序在每个测试点上的分数与用时,赛制变得更加透明且便于调试。在这一背景下,UOJ 也决定在本次比赛中采用 IOI 赛制,让比赛更加符合现代的评测需求。


UPD: 恭喜前5名的选手!

  1. liuhengxi
  2. hhoppitree
  3. znstz
  4. hos_lyric
  5. qiuzx

获奖条件:

  1. 最终得分减去每道题只取第一次非 CE 的提交得分之和最大的选手,如果有多个取排名最小的。
  2. 前两道题任意一题没有满分的选手,其中排名最小的。排除 UOJ 抱枕的获奖选手。
  3. 第五道题得分最大的选手,如果有多个取罚时最小的。排除 UOJ 抱枕的获奖选手。

恭喜 lgvc 获得 UOJ 抱枕!

恭喜 Lqxbh 获得小丑牌周边。

恭喜 hhoppitree 获得小王子旅行音箱。

lgvc 80 70 90 0 6 = 246
wsc2008 100 85 50 0 1 = 236
adam01 20 100 70 0 25 = 215
liuhengxi 0 60 80 70 0 = 210
ridiculos 60 90 50 9 1 = 210

UOJ Round #28 题解

2024-11-17 22:17:07 By Melania

偷吃蛋糕

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$ 只存在两个本质不同的排列方式:

  1. $i \to j \to k \to i$,其能量值等于 $(a_i \bmod a_j) + (a_j \bmod a_k) + a_k$。
  2. $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)$ 的暴力:

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

  1. 对于每个 $i$,从右向左扫描 $l = i, i-1, \cdots, 1$。
  2. 维护当前排除掉的最大元素 $a_t$。
  3. 如果 $a_l > a_t$,则用 $(a_i \bmod a_t) + a_t$ 更新 $F([l, i], i)$,然后设置 $t = l$。
  4. 如果 $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 之间十分的相契。最后算法的实现步骤如下:

  1. 使用 vector<pair<int, long long>> 存储满足 $F([l, i], i) > F([l+1, i], i)$ 的位置 $l$,并记录对应的 $F([l, i], i)$。
  2. 使用一个栈存储尚未被移除的元素。
  3. 针对 $a_i$ 向左扫描的过程中:
    • 从栈顶到栈底枚举所有元素 $a_k$。
    • 如果 $a_k > a_i / 2$,则计数器 cnt++
    • 如果 $a_k \leq a_i / 2$,则给 $a_k$ 新增一个删除标记。
    • 如果 cnt 达到 $2$,立刻停止扫描。
    • 移除累积了两个删除标记的元素。
    • 将具有一个或零个删除标记的元素按照原顺序压回栈中。
  4. 最后将 $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$ 的历史字符串,由 TF 组成:

  • 如果 $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$。

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

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

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

结论 1 的证明

  1. 从根结点出发,直接沿着树边行走可以到达所有合法结点。
  2. 从任何一个合法结点出发,通过长度不超过 $\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$ 的由 TF 组成的字符串 $t$ 的数量,使得 $s + t$ 是合法的,其中 $s$ 是对应于结点 $u$ 的 TF 字符串。

对于所有合法结点 $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$ 如果存在通过 FT 从 $u$ 到 $v$ 的直接一步转换,否则 $A_{u,v} = 0$。

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

  1. 存在一个实数 $\lambda > 0$($A$ 的谱半径),其值超过任何其他特征值的绝对值。
  2. 存在对应于 $\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)。这些必须支持加法、减法、比较,以及通过 uint128uint64 的乘积进行初始化。

收敛性考虑: 定义相对误差 $$ 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

UOJ Round #28 公告

2024-11-11 17:45:57 By Melania

2024-11-17 14:15:57 更新:获奖条件发生了变化。

UOJ Round #28 将于 11 月 17 日星期日晚上 19:00 举行!比赛将进行 3 个小时,共三道题。

这是 UOJ 第二十八场 UOJ Round,还是一如既往的省选及以上难度,欢迎大家来玩!

公元 2014 年 11 月 17 日,vfleaking 发布了 UOJ Round #1 的公告,开启了 UOJ 历史的序章。

从那一天开始,跳蚤王国面临了许多难题,但凭借选手们的智慧与努力,这些困难都被一一克服。十年后的今天,跳蚤国王下令它的得力助手伏特举办一场盛大的庆典,向那些在 UOJ 上书写辉煌的选手们致敬。

然而,随着跳蚤王国规模的扩大,十周年庆典的筹备也遇到了一些意料之外的小插曲。你能否协助伏特解决筹备中的三个难题,确保庆典顺利举行,为跳蚤王国留下一次难忘的回忆?

比赛链接:https://uoj.ac/contest/92

出题人:GeZhiyuanDemeanorMelaniazhoukangyang

参加本次比赛将有机会获得 UOJ 抱枕!获奖条件的 SHA256 码是(a4e74c7f7c60925a248f74f4ba7beb16bad10af1be4e600da461377d27b58c92)(41a280d89209338f7277c553110fb5efdfa5932b7dcc5476268ec36cb23b2a73)。比赛结束后将公布条件。再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD: 恭喜前5名的选手!

  1. liuhengxi
  2. Pub
  3. xuanxuan001
  4. hos_lyric
  5. Flamire

获奖条件:时间限制除以运行时间最小的 AC 代码,如果有多个取提交记录编号最大的。

恭喜 cmk666 (A 题 600ms/505ms)获得 uoj 抱枕!

Melania Avatar