UOJ Logo qingyu的博客

博客

标签
暂无

UOJ Round #26 公告

2023-10-20 16:45:18 By qingyu

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

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

公元2002年10月29日,青藏铁路清水河特大桥主体工程顺利竣工,也因此成为了世界上最长的高原冻土铁路桥。

然而,时光飞逝,如今跳蚤国迎来了藏蓝铁路碧水湖大桥的竣工,整个国家沉浸在欢乐和骄傲之中。随着庆祝声不断响起,一些问题也在悄然而至。作为杰出的数学家伏特,您受到跳蚤国王的邀请,前来协助解决这些问题。

您是否能够接受跳蚤国王的请求,并以您的智慧和能力来帮助解决这些问题,从而让整个国家都充满快乐和幸福呢?

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

出题人:1kri, myee, zhoukangyang

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


UPD: 恭喜前5名的选手!

  1. Melania
  2. tricyzhkx
  3. keyijing
  4. gqh
  5. qiuzx
Qingyu@mainhost:~$ echo -n "得分 * 排名 最大的选手,如果有多个取用户名字典序最大的" | sha256sum
008fdd52c55f2d4e985ab13bef57bab4bb50151e03e6e334076757316f216689  -

恭喜 Nesraychan 因为第一题挂分而获得 uoj 抱枕!

暂别

2023-08-22 15:01:27 By qingyu

一年接一年,又到了 UOJ 管理员的换届时刻!

我们这一届管理员(127, csy2005, ix35, qingyu)在过去的一年中举办了两场 UR,一场 UER,以及年度活动 Goodbye Round 与 UNR。多亏了 vfk vfleaking 与前管理 djq_cpp, he_____he, hehezhouskip2004 为我们提供的指导与帮助,以及这一年来为 UOJ 分享自己有趣的题目的 Alex_Wei, huahua, JohnVictor, Kubic, MelaniaSooke。在无数的命题、造题、传题与修锅的过程中,是这个大家庭对 UOJ 共同的热爱,指引着我们又走过了一年。

在我是刚学 OI 的小朋友时,我便与 UOJ 第一次邂逅。当时的自己对 UOJ 的感觉仅仅停留在「这个地方好厉害,这些题我怎么一个都不会!」。后来在偶然间,我读到了 vfk 所写的博客(csdn / uoj),并被其文字中的热情深深打动。随着我渐渐长大,一代一代的管理员用自己纯粹的热情传递着 UOJ 的精神,让 UOJ 成为一代一代选手的乐园。

在 NOI 2022 结束后,戴老师与 hhz 找到了我,问我有没有兴趣来当 UOJ 管理员。出于对这个伟大 OJ 的热爱,我毅然决定接下了这个大锅。在这一年的管理工作中,我们经历了各种跌宕起伏的时刻。还记得在 Goodbye Renyin 前,我与花花一起对着 C 题的若干份错误代码卡了一整个通宵,最终在 Polygon 上留下了 57 份 revisions 与 9 份不同的 generator;还记得在 UR #24 前,我们与 Sooke 一起针对这道趣题改编了若干不同的版本,并最终将我们最满意的版本放了出来;还记得许许多多为我们投题的同学,愿意将自己脑海中有趣的 idea 贡献出来,让大家一起享受其中的乐趣。最数我难忘的便是在每次比赛后,hos_lyric 老师都会告诉我自己比赛的心路历程以及对题目的评价,即使有着语言的隔阂,也无法阻挡大家对算法竞赛的热爱……这些历历在目的情景,也让我第一次深刻体会到了强子、钱哥、邓老师,以及无数 UOJ 的前辈在写下自己的暂别时对这些回忆的感情。

在这一年的工作中,我们也暴露出了许多问题。管理员们对题目往往有着强烈的个人喜好,这导致了在诸如 UOJ NOI Round #7 Day1 中大家对选题风格的不满;我们对题目准备的时间预留仍有不足,过去一年时有出现在比赛前一晚还在准备题目编写题面的事故;在如今 UOJ 比赛中大量使用的捆绑测试,也被大家认为是一种坏文明。在这一场 UNR 中的 Day 1 成为了 UOJ 历史上第一场被点到了差评的比赛,这让所有的出题人与管理员感到了深深的自责。我们在赛后邀请选手们填写了一份调查问卷,大家对此提出了很多一针见血的建议,例如部分分的梯度不足;使用捆绑测试让大家在无反馈的比赛中容易丢失大量的分数;一些「结论题」与当今 NOI 的题风有些格格不入…… 我们将所有的这些真诚的建议都看在了眼里,我们希望 UOJ 能够变得更好,大家能在 UOJ 享受到更多算法竞赛的乐趣。

又是一年的八月,我们这一届管理员的任期也要结束了。我们相信下一届管理员能够比我们做的更好,将 UOJ 的这份精神继续发扬光大,建设这一算法竞赛的圣地。在接下来的一年中担任 UOJ 的管理员的四位分别是:

1kri, huahua, JohnVictor, zhoukangyang

祝你们四位一切顺利,祝 UOJ 有更光明的未来!

UOJ NOI Round #7 题解

2023-07-16 19:38:11 By qingyu

那些你不要的

idea from 127, data, solution from csy2005

算法一

每次删掉位置为奇数和偶数的数,那么所有位置的奇偶性不会变。

剩下来的数为奇数位置上的数,那么偶数位置上的数就没用了,就相当于每次删掉一个奇数位置上的数。

所以答案就是奇数位置上的数的中位数。

求解中位数可以直接排序,也可以使用 std::nth_element

时间复杂度为 $O(n)$ 或 $O(n \log n)$。

期望得分 $100$ 分。

比特迷宫

idea, data, solution from JohnVictor

算法一

我会直接依次输出 $P$ 的系数!期望得分 $10$。

算法二

我会暴力讨论相邻几位!讨论的多就能获得 $30$ 分。

算法三

考虑爆搜出所有相邻 $k$ 位可以怎么表示。注意这时候可以允许影响到更前面的位。具体的过程类似一个最短路。期望得分 $60$,因为开了 $6s$,有厉害选手选了 $k=24$ 获得了 $100$ 分。

算法四

直接贪心,先通过随机打乱使得 $1$ 的个数不超过一半,然后从后往前,每一步在不把 $0$ 变成 $1$ 的情况下将包括当前位的最多的 $1$ 变成 $0$。时间复杂度分析不清楚,但很多人这样过了。期望得分 ???。

算法五

我们在构造的时候规定 $a,b$ 中二进制的 $1$ 不重合,也就是 $a+b$ 不进位。此时相当于对于 $a\le x \le b$ 操作,这里重定义 $x\le y$ 为 $x\&y=x$。现在把所有数按照二进制中的 $1$ 的个数分组,设含有 $k$ 个 $1$ 的那组为 $S_k$。我们将会对 $k$ 从大到小操作,在现在的限制下,后面的操作不会影响到已经操作完的部分。

一个关键的观察是,对于 $S_k$ 中的一个数,可以对它进行一次合适的操作,使得它在 $S_{k-1}$ 中的邻居(二进制只差一位)中的任意子集 $01$ 反转。这样,如果我们找到若干个 $S_k$ 中的元素,构成 $T_k$,它们的邻居覆盖了 $S_{k-1}$,那么我们就能合理操作这些集合使得可以将 $S_{k-1}$ 中的元素变为任意状态。

现在,我们可以得到如下算法:首先通过至多一次操作将 $n-1$ 位置的数变为 $1$,然后从大到小对于每一个 $k$,对 $T_k$ 操作,使得 $k-1$ 层中恰有 $T_{k-1}$ 中的数为 $1$。这种做法的总操作次数为 $\sum|T_k|$。

通过贪心算法寻找 $T_k$(每一次找一个能解决尽量多未解决的邻居的),得到的界为 $157885$。可以证明这个算法的操作次数的上界为 $\mathcal O(\frac{n\ln \ln n}{\ln n})$。

璀璨宝石

idea, data, solution from he_____he

算法一

首先我们一定是先拿足够多的宝石之后,再去拿所有发展卡。假设我们分别需要 $A,B,C,D,E$ 个宝石,记 $s=A+B+C+D+E$,那么我们需要 $\max(A,B,C,D,E,[(s+1)/2])$ 轮去拿。这是因为如果这五个数中存在绝对众数,不妨设是 $A$,那么我们可以每次拿一个 $A$,再拿一个其他类型的宝石,可以把其他类型的宝石都拿到,轮次瓶颈在于 $A$ 的大小,就需要恰好 $A$ 轮。如果不存在绝对众数,我们每次拿两个需要数量最多的类型的宝石,就可以保证一直不出现绝对众数,也就是每次都能拿到两个宝石,需要 $[(s+1)/2]$ 轮。

暴力枚举每次拿哪张发展卡,对每种情况算出所需的每种宝石数量,复杂度 $O(2^n)$,可以通过子任务 1,期望得分 $20$ 分。

算法二

对于 $b_{i,1}=c_{i,1}=d_{i,1}=e_{i,1}=0$ 的部分,由于对于这四种宝石不会减免消耗数量,我们可以直接算出这四种宝石需要拿取多少。而第一种宝石显然需要拿的越少越好。设计 dp 数组 $d_{i,j}$ 表示:现在桌面上的两张发展卡为 $i,j(j < i)$ 时(此时牌堆顶一定为第 $i+1$ 张发展卡),第一种宝石所需的最少数量。时间复杂度 $O(n^2)$,可以通过子任务 2,结合算法 1 可以获得 $25$ 分。

算法三

对于 $c_{i,0}=d_{i,0}=e_{i,0}=0$ 或 $c_{i,1}=d_{i,1}=e_{i,1}=0$ 的部分,我们同样可以直接算出 $C,D,E$ 三种宝石消耗的数量,设计 dp 数组 $d_{i,j,k}$ 表示:现在桌面上的两张发展卡为 $i,j(j < i)$,第一种宝石目前需要拿取共 $k$ 个,第二种宝石最少需要拿取多少个。时间复杂度 $O(n^2M)$,可以通过子任务 2, 3, 4,结合算法 1 可以获得 $40$ 分。

算法四

如果我们需要的轮次不是 $\max(A,B,C,D,E,[(s+1)/2])$,而是 $A,B,C,D,E$ 与 $[(s+1)/2]$ 中任意一个的话,我们都能很轻松的 dp 得到答案。我们考虑通过数方案数来分辨出最大值是其中哪个情况。记 $d_{t,i,j,k,l}$ 表示:现在桌面上的两张发展卡为 $i,j(j < i)$,第 $t$ 种宝石目前需要拿取 $k$ 个,其余类型宝石目前需要拿取 $l$ 个,有多少种方案。记 $f_{i,j,k}$ 表示:现在桌面上的两张发展卡为 $i,j(j < i)$,目前总共需要拿取 $k$ 个宝石的方案数。

通过 $d$ 数组,我们可以算出所有最大值为 $A,B,C,D,E$ 的方案对答案的贡献。如果最大值为 $[(s+1)/2]$,我们可以通过容斥的方式,用 $d$ 和 $f$ 算出没有绝对众数时,每个 $s$ 的方案数。这样找到没有绝对众数时最小的 $s$ 即可。

时间复杂度 $O(n^2M^2)$,结合算法 3 后期望得分 $60\sim 80$ 分。

算法五

我们抛弃算方案数的计算方法,想办法直接求出这个最大值。考虑这样一个过程:每一次取宝石相当于消了两个不同类型的宝石,我们首先随便消一些,直到出现一类宝石出现次数大于等于一半,我们把所有非这一类的宝石全部留着和这一类宝石相消。考虑用一个 dp 来还原这个过程。记 $d_{i,j,t,k}$ 表示:现在桌面上的两张发展卡为 $i,j(j < i)$,目前随便消的过程中还剩 $k$ 个第 $t$ 类宝石没被消完,目前最少消(拿取)了多少轮。记 $f_{i,j,t,k}$ 表示:现在桌面上的两张发展卡为 $i,j(j < i)$,并且我们认为第 $t$ 类宝石出现次数会在最终大于等于一半,所以我们留了 $k$ 个非第 $t$ 类的宝石用来和第 $t$ 类的宝石相消,目前最少消(拿取)了多少轮。

我们希望在转移过程中,每次消都是消了两个不同的宝石,这样我们得到的答案一定不会好于最优解。同时我们希望能够达到最优解。也就是存在一种转移,能够在前一半模拟出随便消($d$ 数组),并可以在任意时刻转移到存在出现大于等于一半的情况($f$ 数组)。

更进一步的,每次转移都是拿取一张卡,我们可以依次考虑所有宝石种类,所以我们每次要做的就是考虑一些只有 $t,k$ 变化的状态,在需要多拿取若干个某一类宝石后,得到的新的状态是什么。

我们尝试把转移挨个写下来:假设目前是 $d$ 状态中的 $(t,k)$,目前要多拿取 $k'$ 个 $t'$ 类宝石。

  • 如果 $t=t'$,那么第 $t$ 类宝石会多 $k'$ 个,会转移到 $(t,k+k')$。

  • 如果 $t\neq t'$,那么这两类宝石之间可以相消,有以下两种情况:

    • 如果 $k < k'$,那么要么在消的过程中转移到了 $f$ 状态,要么仍然处于 $d$ 状态。

      后者为消(拿取)$k$ 次转移到 $(t',k'-k)$,前者为消(拿取)$x$ 次转移到 $f$ 状态中的 $(t'',k+k'-2x)$,其中 $t''\neq t,t''\neq t'$,表示我们用 $t$ 和 $t'$ 消了 $x$ 次,消之后 $t''$ 出现次数大于等于一半了,剩下的 $t$ 和 $t'$ 都留着以后消 $t''$。

    • 如果 $k\geq k'$,那么要么在消的过程中转移到了 $f$ 状态,要么仍然处于 $d$ 状态。

      后者为消(拿取) $k'$ 次转移到 $(t,k-k')$,前者为消(拿取)$x$ 次转移到 $f$ 状态中的 $(t'',k+k'-2x)$,其中 $t''\neq t,t''\neq t'$,表示我们用 $t$ 和 $t'$ 消了 $x$ 次,消之后 $t''$ 出现次数大于等于一半了,剩下的 $t$ 和 $t'$ 都留着以后消 $t''$。

第二种,假设目前是 $f$ 状态中的 $(t,k)$,目前要多拿取 $k'$ 个 $t'$ 类宝石。

  • 如果 $t=t'$,那么我们正好要用前面留下的宝石消这 $k'$ 个宝石。
    • 如果 $k\geq k'$,直接消(拿取)$k'$ 次转移到 $f$ 状态的 $(t,k-k')$ 即可。
    • 如果 $k < k'$,同样直接消(拿取)$k$ 次转移到 $d$ 状态的 $(t,k'-k)$ 即可(这里相当于剩下 $k'-k$ 个 $t$ 没被消完,回到 $d$ 状态仍然能保证我们不会消两个非 $t$ 的宝石)。
  • 如果 $t\neq t'$,那么直接把这 $k'$ 个也留着消 $t$,转移到 $f$ 状态的 $(t,k+k')$。

转移复杂度 $O(M)$,总复杂度 $O(n^2M^2)$,结合算法 3 后期望得分 $60\sim 80$。

算法六

尝试优化转移。可以注意到,两种情况中,要么是在区间 $[k-k',k+k']$ 中所有同奇偶部分和一个公差为 $-1$ 的等差数列取最小值,要么是在区间 $[k'-k,k'+k]$ 中所有同奇偶部分和一个公差为 $-1$ 的等差数列取最小值。

把区间取最小值用数据结构优化可以做到每次转移 $O(\log M)$。时间复杂度 $O(n^2M\log M)$,结合算法 3 后期望得分 $80\sim 100$。

算法七

想办法把转移做到 $O(1)$。可以注意到,在一次转移中,对于所有状态,要多拿取的 $k'$ 个 $t'$ 类宝石是固定的。所以 $k'$ 是固定不变的。

对于 $[k-k',k+k']$ 这类区间取最小值,区间长度固定,可以类似滑动窗口用单调队列优化,做到所有转移 $O(M)$ 一起处理。

对于 $[k'-k,k'+k]$ 这类区间取最小值,区间一定跨过了 $k'$ 这个位置,可以在两个位置打个标记后求前缀最小值/后缀最小值解决,做到所有转移 $O(M)$ 一起处理。

这样单次转移所有状态就做到了 $O(M)$。总复杂度 $O(n^2M)$,可以通过所有数据,期望得分 $100$。

题外话

Splendor 真的很好玩!推荐大家都去尝试。

火星式选拔

idea, data, solution from ix35

算法一

用堆维护所有当前在队伍中的人,暴力模拟题目中的操作。

期望得分 $25$ 分。

算法二

考虑 $k=1$ 怎么做。

设 $f(i)$ 表示如果 $i$ 在队伍里,那么直到哪个人到来后 $i$ 会被踢出。

我们要求的就是 $f(f(\ldots(l)))$,使得它不超过 $r$,对 $f$ 数组倍增即可。

期望得分 $25$ 分,结合算法一 $50$ 分。

算法三

考虑区间中 $b_i$ 前 $k-1$ 大的人,由于队伍有 $k$ 个人,所以它们都不可能成为 $b_i$ 最小的人,也就是说它们永远不会被踢出。

于是我们只要考虑剩下的最后一个名额即可,这转化为了一个类似 $k=1$ 的问题。

用主席树维护区间前 $k$ 大即可。

期望得分 $100$ 分。

反重:求熵

idea from djq_cpp, solution, data from he_____he

算法一

暴力枚举所有情况。时间复杂度 $O(T^nn^2)$,可以通过子任务 1,期望得分 $5$ 分。

算法二

对于 $n=2$ 的情况,只有限制 $0\leq x_1,x_2\leq T$ 与 $-c_1\leq x_1-x_2\leq c_2$ 的限制,容易算出方案数。结合算法 1 后可以通过子任务 1, 2,期望得分 $10$ 分。

算法三

可以再把 $n=3$ 手玩出来。可以通过子任务 1, 2, 3,期望得分 $25$ 分。

算法四

整一点算法。考虑数位 dp,维护两两之间的两个限制目前处于什么状况,并需要记录每个数是否达到上界。状态最多 $3^{n(n-1)/2}2^n$ 个,但实际上有用的并没有这么多。由于和正解无关,不在此过多描述,时间复杂度约为 $O(3^{n(n-1)/2}2^nn\log T)$。根据赛时情况观察,期望得分 $40\sim 50$

算法五

不从值域的角度考虑,转而尝试一个一个把变量消去。比如我们想要消去 $x_n$。想要消去一个变量,那么和这个变量有关的不等式越少越好。不妨设 $x_0=0$,那么会有一些 $x_n\leq x_i+c_{n,i}$ 的限制,和一些 $x_n\geq x_i-c_{i,n}$ 的限制。我们分别枚举这两类限制中最紧的限制,这样与 $x_n$ 相关的限制就只剩一个了,但由限制是最紧的,会多出一些 $x_0,\ldots,x_{n-1}$ 之间的限制。枚举完之后,和 $x_n$ 相关的限制就只剩一条形如 $x_i-c_{i,n}\leq x_n\leq x_j+c_{n,j}$ 了。那么我们就可以再加一条 $x_i-x_j\leq c_{n,j}+c_{i,n}$ 的限制之后,考虑所有 $x_1,\ldots,x_{n-1}$ 的方案,对所有方案求出 $x_n$ 的方案数,即 $x_j-x_i-(c_{n,j}+c_{i,n})+1$ 的和即可。这样,相当于我们需要维护一个关于 $x_1,\ldots,x_n$ 的多元多项式,每次相当于把所有 $x_n^k$ 替换为 $[x_i-c_{i,n},x_j+c_{n,j}]$ 中所有数的 $k$ 次方和,而这仍然是一个关于 $x_1,\ldots,x_{n-1}$ 的多元多项式。

时间复杂度 $O(n!^2\cdot c^n)$,其中 $c^n$ 为维护多元多项式的复杂度,$c$ 我们认为应该是一个常数,可以通过 $n\leq 6$ 或 $n\leq 7$,期望得分 $70\sim 90$ 分。

算法六

在上一个算法中,我们实际上做的是枚举 $i$,枚举 $j$,把 $x_n^k$ 替换为某个 $f_k(x_j+c_{n,j})-f_k(x_i-c_{i,n}-1)$($f_k(x)$ 应为自然数幂和)。考虑拆开 $i,j$ 的贡献,变为只枚举 $i$,把 $x_n^k$ 替换为 $-f_k(x_i-c_{i,n}-1)$,和只枚举 $j$,把 $x_n^k$ 替换为 $f_k(x_j+c_{n,j})$ 分别统计一次答案。

一个你可能的疑问是,我们不是还需要保证 $x_i-c_{i,n}\leq x_j+c_{n,j}$ 吗?但实际上,我们在枚举 $i$ 之后,我们并不需要再枚举 $j$ 那一侧最紧的限制是什么了,我们只需要保证所有限制都满足就可以。因此我们统计的所有合法的 $x_1,\ldots,x_{n-1}$ 的方案仍然是满足 $x_i-c_{i,n}\leq x_j+c_{n,j}$ 的,只是我们并不知道具体哪个是最紧的限制 $j$,只知道对所有 $j$ 都满足这个限制。

这样复杂度就变为了 $O(n!2^n\cdot c^n)$,其中 $c$ 和算法 6 中同样。可以通过所有数据,期望得分 $100$ 分。

鸽子收费站

idea, solution from hehezhou, data from 127

考虑按时间顺序维护所有询问,对每个收费站依次处理。通过简单处理,题意即可转化为维护一个序列,支持:

  1. 单点修改
  2. 单点查询
  3. 将 $[l_1, r_1]$ 中值在 $[l_2, r_2]$ 的元素全部置为 $r_2$

以下均在描述转化后题意的解法,且认为 $n,Q$ 同阶。

算法一

我会暴力!

直接 $O(n^2)$ 暴力做修改操作。

期望得分 $10$。

算法二

若保证了 $r_2\leq 20$,则由于操作 $3$ 只会使元素变大,可以暴力修改需要修改的位置。在线段树上维护区间中是否有 $0,1,\cdots,20$ 中的值,即可在 $O(实际修改个数\times \log n)$ 时间内完成修改。

总复杂度 $O(n\log n\max r_2)$,期望得分 $20$。

算法三

依然是考虑线段树。主要考虑第三种操作。如果我们能做到:仅当 当前节点区间与操作区间相交而不包含 或者 当前节点区间中有两种及以上的值需要修改 时,才继续递归,则所有修改访问的线段树节点数是 $O(n\log n)$ 的。定义一个节点的势能是区间中元素种类数,总势能定义为每个节点的势能之和,不难分析得到这个复杂度。

怎么判断 当前节点区间中有两种及以上的值需要修改 呢,这看起来没啥高论,考虑在每个线段树节点维护一棵平衡树,代表区间元素排序并去重后的结果。此时判断只需在平衡树上二分即可。但是不难发现这么做的问题:如果一个线段树节点代表的区间中只有一种值需要修改,但是这种值可能遍布整个区间,我们没法快速修改所有后代线段树节点的平衡树。

怎么做到“牵一发而动全身”呢,答案是把平衡树连起来。实际上对于上述问题,这个区间修改后,区间中值的相对顺序没有任何变化,也就是平衡树的结构并不需要改变。考虑只在线段树根节点的平衡树上维护具体的元素值,对于其他线段树节点的平衡树,每个平衡树点连向线段树上父亲所在平衡树中,值相同的平衡树点。这样一来,如果一个线段树节点代表的区间中只有一种值需要修改,只需要通过某种方式修改当前节点平衡树中对应点代表的值,线段树后代节点无需继续递归修改。

在这个结构上修改,所有操作需要修改的线段树总节点数就是 $O(n\log n)$ 的。接下来只需要考虑一些细节即可。为了方便修改,考虑一个基础操作:对于某个平衡树节点,查询它在线段树上左/右儿子的平衡树上的前驱。这可以通过每个平衡树节点再记录在线段树上左/右儿子的平衡树上对应的节点,并维护平衡树子树中是否有这种向左/向右的链接,将问题转化为查询当前平衡树上向前最近的有左/右链接的节点来完成,称为递归操作,单次操作复杂度 $O(\log n)$。

对于查询操作,直接找到线段树叶子,然后从对应平衡树节点不断在线段树上向上跳到根即可得到真实值,复杂度 $O(\log n)$。

对于单点修改操作,直接通过递归操作不断找到平衡树中应该插入的位置完成,复杂度 $O(\log^2 n)$。

对于区间修改操作,通过递归操作不断求出当前节点 $[l_2, r_2]$ 中最前和最后的节点,并依此判断是否需要递归,若需要插入 $r_2$ 也可以找到插入位置。在操作结束后,及时清理无用节点,通过均摊分析不难得到总复杂度为 $O(n\log^2 n)$。

因此总复杂度 $O(n\log^2 n)$,期望得分 $100$。

UOJ Round #25 题解

2023-06-04 23:36:13 By qingyu

设计草图

idea, solution from he_____he, data from csy2005

算法一

我会暴力!

枚举所有的区间,暴力枚举每个 ? 的取值,检验其是否为合法的括号序列。

时间复杂度为 $O(n \cdot 2^n)$,期望通过子任务 $3$,得到 $15$ 分。

算法二

如果 $S$ 中只含有 ?,那么任意一个长度为偶数的区间都是合法的!

通过计算,发现答案即为 $\left\lfloor \frac{n}{2} \right\rfloor \cdot \left\lceil \frac{n}{2} \right\rceil$。

期望通过子任务 $1$,得到 $5$ 分。结合算法一可以得到 $20$ 分。

算法三

注意到,一个区间合法当且仅当以下条件满足:

  1. 区间长度为偶数
  2. 将所有 ? 替换为 ( 后,把 ( 当成 1,) 当成 -1,所有前缀和均大于等于 0
  3. 将所有 ? 替换为 ) 后,把 ) 当成 1,( 当成 -1,所有后缀和均大于等于 0

第二个条件相当于对每个 $l$,存在一个 $p_l$ 使得在 $l\leq r\leq p_l$ 成立。

第三个条件相当于对每个 $r$,存在一个 $q_r$ 使得在 $q_r\leq l\leq r$ 成立。

在预处理出 $p_i, q_i$ 后,我们可以枚举 $l$ 与 $r$ 并 $O(1)$ 进行判定。时间复杂度为 $O(n^2)$。

期望通过子任务 $3 \sim 4$,得到 $30$ 分。结合算法二可以获得 $35$ 分。

算法四

注意到上述问题是一个二维数点问题,我们可以使用排序后树状数组来解决,时间复杂度为 $O(n \log n)$。

期望通过所有子任务,可以获得 $100$ 分。

见贤思齐

idea, data, solution from ix35

算法一

暴力模拟每一轮的操作。

每一轮模拟的复杂度是 $O(n)$ 的,我们可以将询问离线后按照时间顺序来处理所有询问,这样复杂度即为 $O(nd + q)$。

期望通过子任务 $1 \sim 2$,得到 $40$ 分。

算法二

从 $i$ 到 $p_i$ 连边,将形成一棵基环内向树。我们先考虑比较简单的情形——一棵有根树该怎么做:

假设根的权值一直不变(或者看成每次 $+1$ 也行),将第 $j$ 天黄昏时第 $i$ 个工程师的技术水平是 $f(i,j)$,那么我们有:

$$\begin{cases}f(i,0)=a_i\\ f(i,j)=f(i,j-1)+[f(i,j-1)\leq f(p_i,j-1)]\end{cases}$$

可以发现,对于某个 $j$ 如果 $f(i,j)=f(p_i,j)$ 或 $f(i,j)=f(p_i,j)+1$,那么之后也会始终保持这种关系。为了更好发掘这种性质,我们对 $f$ 进行一个平移,定义:

$$g(i,j)=f(i,j+dep_i)-dep_i$$

其中 $dep_i$ 表示 $i$ 的深度,那么:

$$g(i,j)=g(p_i,j)\to g(i,j+1)=g(p_i,j+1)$$

证明是直接的。

于是我们可以用线段树维护 $g(i,*)$,它可以通过在 $g(p_i,*)$ 的基础上修改一段前缀(修改成一个常数或一个公差为 $1$ 的等差数列)得到,时间复杂度为 $O((n+q)\log V)$,其中 $V$ 是最大时间。

可以通过子任务 $3$,得到额外的 $20$ 分。结合算法一可以获得 $60$ 分。

算法三

再考虑基环树怎么做。事实上我们只需如下观察:设第 $i$ 天所有工程师的技术水平最小值为 $mn_i$,则这一天所有权值为 $mn_i$ 的人一定会增长,从而第 $i+1$ 天所有人的权值最小值就是 $mn_{i+1}=mn_i+1$。

这告诉我们,最小值一定每天都在工作使得自己的水平增长,所以我们找到一个环上 $a_i$ 最小的人,然后断掉 $i$ 与 $p_i$ 之间的边并假设 $f(i,j)=a_i+j$,然后当成树做即可。

时间复杂度为 $O((n+q)\log V)$,期望通过所有子任务,得到 $100$ 分。

装配序列

idea, data, solution from Kubic

出题人原本给的题意是求前缀严格 LIS,不过后来似乎是为了方便写题目背景改成了前缀最小非严格 LDS 划分,显然两者是完全等价的。

算法一

直接拿出前 $10^6$ 项然后用你喜欢的方法计算所有前缀的 LIS 即可。

期望得分:$5$。

算法二

可以发现如果 $x\ge n^2$,那么答案为 $n$。

直接拿出前 $n^2$ 项然后用你喜欢的方法计算所有前缀的 LIS 即可。

时间复杂度 $O(n^2\log n+m)$。

期望得分:$15$。

算法三

考虑 LIS 的一种贪心求法:维护一个递增序列 $b$。假设当前考虑的数是 $x$,找到最小的 $y$ 满足 $b_y\ge x$ 并将 $b_y$ 改为 $x$。如果不存在这样的 $y$ 那么就在 $b$ 的末尾插入一个 $x$。

这个算法通常的实现是按照下标从小到大,每次考虑一个值。但本题中我们考虑按照值从小到大,每次考虑一个下标。

我们考虑维护出这个长度不超过 $n$ 的序列,每次询问的答案即为序列中 $\le x$ 的数的个数。这是因为这个序列可以看作是在维护 dp 数组的差分。

我们可以归纳地认为任何一个时刻每种数保留的都是一个前缀。设当前考虑到的值在排列中的下标为 $x$,下标为 $i$ 的数保留了 $c_i$ 个。那么进行如下过程:

  • 初始 $c_x=0$。
  • 依次访问 $(x,n]$ 中的每一个 $i$,如果 $c_x < c_i$,那么交换 $c_x$ 和 $c_i$。
  • 依次访问 $[1,x)$ 中的每一个 $i$,如果 $c_x < c_i-1$,那么先交换 $c_x$ 和 $c_i$,然后 $c_x\leftarrow c_x-1,c_i\leftarrow c_i+1$。
  • 最后 $c_x\leftarrow c_x+1$。

直接暴力维护即可做到 $O(n^2+m\log n)$。

期望得分:$40$。

算法四

设 $b=a^{-1}$。

我们相当于要将 $b$ 分为 $m$ 段,使得它们的 LIS 之和最大。

可以发现 $LIS(b_{l,r+1})+LIS(b_{l+1,r})\le LIS(b_{l,r})+LIS(b_{l+1,r+1})$,即转移矩阵满足四边形不等式。因此答案关于 $m$ 是下凸的。

因此我们可以使用 wqs 二分,设当前二分的斜率为 $w$。

问题转化为:选出 $b$ 的一个子序列 $p$,最大化 $|p|-w\times\sum\limits_{i=1}^{|p|-1}[p_i>p_{i+1}]$。使用树状数组优化 dp 即可做到 $O(n\log n)$。

因此总时间复杂度为 $O(n\log^2 n)$。

当然,直接使用亚单位蒙日矩阵快速幂科技也可以做到相同的复杂度。

期望得分:$20$。

算法五

通过打表等方式可以发现在 $n=2\times 10^5$ 且数据随机的情况下 $c$ 中非零位置个数大概有 $k=900$ 个左右。猜测 $k$ 可能是 $O(\sqrt n)$ 级别,暂时还没能给出其证明。

实时维护这些非零位置即可做到 $O(n(k+\log n)+m\log n)$。

期望得分:$55$。

算法六

可以发现 $\sum\limits_{i=1}^n c_i\le n$。

设一个阈值 $B$,$\sum\limits_{i=1}^n [c_i>B]\le\dfrac{n}{B}$。

在上面的过程中,每次访问到的 $c_i$ 是严格单调递增的,

考虑上面的过程中第二步的维护方法。

我们对于 $\le B$ 中的每一种数用一个 set 维护它们的出现位置,对于 $>B$ 的数直接维护它们的出现位置。

先对于每一种数找到它们在 $(x,n]$ 中的第一次出现的位置。显然如果某种数在 $(x,n]$ 中的第一次出现没有被访问到,那么这种数一定没有被访问到。这样我们在 $O(B\log n+\dfrac{n}{B})$ 的时间复杂度内筛选出了 $O(B+\dfrac{n}{B})$ 个有用的位置,然后在 $O(B+\dfrac{n}{B})$ 的时间复杂度内模拟上面的操作,最后在 $O(B\log n+\dfrac{n}{B})$ 的时间复杂度内更新位置信息。

因此总时间复杂度为 $O(nB\log n+\dfrac{n^2}{B}+m\log n)$,取 $B=\sqrt{\dfrac{n}{\log n}}$ 时可以得到最优的 $O(n\sqrt{n\log n}+m\log n)$。

期望得分:$100$。

算法六 $+ \varepsilon$

by 127

我们可以进一步分析算法六的复杂度!

我们刚才直接将一次 set 操作的时间复杂度估计为 $O(\log n)$。考虑使用更加精确的分析方法。取 $B=\sqrt n$,设 $d_i$ 表示 $c_j=i$ 的个数。

那么我们有 $\sum\limits_{i=1}^B i\times d_i\le n$,而一次操作的时间复杂度可以估计为 $\sum\limits_{i=1}^B\log(d_i+1)$。

考虑 $\prod\limits_{i=1}^B(d_i+1)$,可以化为 $\dfrac{\prod\limits_{i=1}^B(i\times d_i+i)}{B!}$。

而我们知道:

$$ \sum\limits_{i=1}^B(i\times d_i+i)\le n+\dfrac{B(B+1)}{2}\le 2n $$

根据均值不等式可以得到:

$$ \prod\limits_{i=1}^B(i\times d_i+i)\le\left(\dfrac{2n}{B}\right)^B=(2B)^B $$

因此时间复杂度可以估计为:

$$ \sum\limits_{i=1}^B\log\left(\dfrac{2B}{i}\right)\le\log(2B)+\int_{1}^B\log\left(\dfrac{2B}{x}\right)dx=O(B) $$

因此总时间复杂度为 $O(n\sqrt n+m\log n)$。

期望得分:$100$。

bonus: interval query with $\tilde{O}(n^{1.5})$ time

tips: seaweeds method

by 127

UOJ Round #25 公告

2023-06-01 12:56:23 By qingyu

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

公元 1896 年 6 月 4 日,亨利·福特制造出他的第一辆汽车——福特Quadricycle,这不仅是一部汽车,更是一个时代的标志。它简单的设计包含了车架、一具燃气发动机和四个自行车轮胎,体现了那个时代的独特创新和无畏探索的精神。

如今,跳蚤国面临着同样的挑战。跳蚤国王有一个梦想,那就是在他的国家制造出第一辆属于跳蚤国的汽车——伏特多轮(Polycycle)。他需要一位能够帮助他实现这个梦想的助手,于是他找来了伏特来设计这一辆汽车。你能否与伏特一起,帮助跳蚤国王完成这个历史性的制造任务?

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

出题人:he_____he, ix35, Kubic

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

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


UPD: 恭喜前5名的选手!

  1. huahua
  2. zhoukangyang
  3. wangziji
  4. huzhaoyang
  5. KHIN
Qingyu@mainhost:~$ echo -n "比赛开始前的 Rating 减去比赛中的得分取得最大值的选手,如果有多个取排名最高的一个" | sha256sum
b079b81e1feb810cae657e6add46e2759788059274dd7a464ab509ca4e582915  -

恭喜 mcfxmcfx 获得 uoj 抱枕!

UOJ Round #24 题解

2023-02-19 23:30:46 By qingyu

比特跳舞

idea, data, solution, std from csy2005

算法负二

对于特殊性质 A,长度为 $l$ 的元素互不相同的序列的本质不同子序列数为 $2^l$,只有当 $l=0$ 时为奇数。故 $(x,y)$ 合法的充要条件为 $x=y$,答案为 $n$。

可以通过子任务一,期望得分 $5$ 分。

算法负一

对于特殊性质 B,长度为 $l$ 的元素全部相同的序列的本质不同子序列数为 $l+1$。故 $(x,y)$ 合法的充要条件为将树黑白染色后,$x$ 和 $y$ 同色。答案为黑点个数平方加白点个数平方。

可以通过子任务二,结合算法负二期望得分 $10$ 分。

算法零

根据题意模拟,枚举每一对 $(x,y)$,再枚举这条链的每个子序列,把它们插进 std::set 里判断奇偶性即可。

时间复杂度为 $O(2^n\times \text{poly}(n))$,可以通过子任务三,结合算法负二、算法负一期望得分 $15$ 分。

算法一

考虑怎么求一个给定的序列 $a$ 的本质不同子序列个数。

为了避免算重,对每个本质不同子序列,我们只在其最后一次在原序列中出现时计算它。

记 $f_{i,j}$ 表示考虑序列的前 $i$ 个元素,以元素 $j$ 结尾的本质不同子序列个数。

当 $j=a_i$ 时:

$$f_{i,j}=1+\sum_{1\leq k< n}f_{i-1,k}$$

当 $j\neq a_i$ 时:

$$f_{i,j}=f_{i-1.j}$$

总共的本质不同子序列数即为 $1+\sum_{1\leq i< n} f_{n,i}$。

对于子任务四,枚举 $x$ 从左往右扫维护 dp,即可求出每一对 $(x,y)$ 的答案。

时间复杂度为 $O(n^3)$,可以通过子任务四,结合算法负二、算法负一、算法零期望得分 $35$ 分。

算法二

考虑把算法一放到树上。

枚举 $x$,以 $x$ 为根进行 dfs,每次记录下从 $x$ 到当前点的路径中每个前缀的 dp 值,结束对一个点的 dfs 时把它的 dp 值扔掉即可。

时间复杂度为 $O(n^3)$,可以通过子任务五,结合算法负二、算法负一期望得分 $40$ 分。

算法三

发现实际上每次在序列末尾插入一个元素时,$f_i$ 和 $f_{i-1}$ 实际上只有一个元素有区别。考虑使用滚动数组优化这个 dp。

由于是树而不是链,我们仍需支持 dp 值的回退。但由于每访问一个点只修改一个值,我们只需记录这个值原来是多少即可,而无需记录整个 dp 数组。

时间复杂度为 $O(n^2)$,可以通过子任务六,结合算法负二、算法负一期望得分 $50$ 分。

算法四

我们还没有用到只需求出本质不同子序列个数的奇偶性而不是具体值这个性质。

观察我们刚才的 dp。记 $f_{i,0}=1+\sum_{1\leq j< n}f_{i,j}$。答案就是 $f_{n,0}$。

考虑新增一个值 $a_i$ 的影响。 $$f_{i,a_i}=1+\sum_{1\leq k< n}f_{i-1,k}=f_{i-1,0}$$

$$f_{i,0}=1+\sum_{1\leq j < n}f_{i,j}=1+\sum_{1\leq j < n,j\neq a_i}f_{i-1,j}+f_{i-1,0}=2f_{i-1,0}-f_{i-1,j}$$

而 $2f_{i-1,0}-f_{i-1,j}$ 与 $f_{i-1,j}$ 的奇偶性相同。

也就是说,新增一个值 $a_i$ 就相当于交换了 dp 数组中下标为 $0$ 的位置和下标为 $a_i$ 的位置的值!

初始时,$f_{0,j}=[j=0]$。于是任意时刻,dp 数组中正好有一个奇数,一个序列的本质不同子序列个数为奇数,当且仅当最终这个奇数在下标 $0$。

于是我们就有了一个暴力做法,每次枚举 $x$ 开始 dfs,dfs 时维护当前奇数在哪个下标。

时间复杂度为 $O(n^2)$,和算法三相同,可以通过子任务六,结合算法负二、算法负一期望得分 $50$ 分。但这个算法显然更有前途。

算法五

由算法四中的结论可以得出,一个序列的本质不同子序列个数为奇数,当且仅当它可以划分为若干个长度至少是 $2$ 的子串,使得每个子串的开头和结尾的数相同,且这个数没有在子串中其它位置出现过。我们称每个这样的子串为极短合法序列。

考虑点分治。对于每一层,从分治中心开始 dfs,对每个点,求出其到分治中心的路径经过尽可能地删去是极短合法序列的前缀后,剩下的串的开头(或者这个串被删空)。对于两个在不同子树中的点,合法当且仅当它们剩下的串的开头相同或它们均被删空。

时间复杂度为 $O(n\log n)$,可以通过子任务七,期望得分 $65$ 分。

算法六

我们发现,$(x,y)$ 合法这种关系是一个等价关系。即满足自反性($(x,x)$合法),对称性($(x,y)$ 和 $(y,x)$ 合法性相同),传递性(若 $(x,y)$、$(y,z)$ 均合法则 $(x,z)$ 合法)。

自反性和对称性是显然的,以下是传递性的证明:

根据算法五开头的判定方式,合法序列的拼接是合法序列,从合法序列中去掉一个合法的前/后缀得到的是合法序列。

设路径 $(x,y)$ 和路径 $(y,z)$ 的交是路径 $(y,u)$,$(x,u)$ 的极长合法前缀是 $(x',u)$,$(y,u)$ 的极长合法前缀是 $(y',u)$,$(z,u)$ 的极长合法前缀是 $(z',u)$。

若 $y'=u$,即 $(y,u)$ 本身合法,那么 $(x,u)$、$(u,z)$ 均是合法的,所以 $(x,z)$ 是合法的。

否则 $(x',y')$、$(z',y')$ 均是合法序列,于是得到 $(x'->u)$ 路径上的第一条边、 $(y'->u)$ 路径上的第一条边、 $(z'->u)$ 路径上的第一条边的边权均相等,且这三条路径上没有其他边的权值和它们相等,于是 $(x',z')$ 是合法的,那么 $(x,z)$ 也是合法的。

于是我们只需尽可能得合并等价类,然后计算每个等价类大小的平方和。

首先进行第一轮合并。考虑一个点 $x(x>1)$,若 $f_x$ 的祖先中存在边权与 $a_x$ 相同的边,找到与 $f_x$ 最近的边 $(y,f_y)$,那么 $(x,y)$ 是合法的,可以把 $x$ 和 $y$ 合并到一个等价类中。

第一轮合并后,令每个等价类中最浅的点为这个等价类的代表(显然唯一),那么每个代表 $x$ 都满足 $f_x$ 的祖先中不存在边权与 $a_x$ 相同的边。根据这个性质,我们发现对于两个代表 $x,y$,$(x,y)$ 合法当且仅当 $x\neq 1,y\neq 1,a_x=a_y$。于是我们可以再进行第二轮合并,把所有 $a$ 相同的等价类合并起来。第二轮合并后属于不同等价类的 $x,y$ 一定两两不合法。

实现时,我们通过自顶向下的 dfs 可以直接计算出每个点属于哪个等价类,故不需要使用并查集之类的数据结构来维护。

时间复杂度为 $O(n)$,可以通过所有子任务,期望得分 $100$ 分。

比特智慧

idea, data, solution, std from Sooke, solution2 from 127

题外话

出题人自以为设置了良心的部分分,未顾虑到临场选手的时间安排,对造成的不佳体验实感抱歉!

本题背景是抽芽游戏的变种 Planted Brussels Sprouts。鄙人不通现代处理技巧,仅给出些许古老但巧妙的推法,并不代表本题局限于此,请诸位尽情各显神通。

算法一

把题目的计数拆成两部分,我们相当于求所有能操作出的平面图的染色数之和。

手玩 $n \le 4$ 的所有情况,可以以 $O(1)$ 时间复杂度优雅地通过子任务 $1$,得到 $5$ 分的好成绩。

算法二

有染色就有对偶图。不妨从 $m = n - 1$ 开始研究,每次铺设操作会将一块区域分为两块,反过来,整个对偶图即两侧对偶图加上若干条边。根据新生成的接口后续是否被使用,讨论三种情况:

  • “二分”:两侧接口均不使用,则两侧对偶图一定是孤立点,加边后对偶图仅一条边。
  • “三分”:有一个接口不使用,则该侧对偶图是孤立点,加两条边,给另一侧对偶图接了个三角形。
  • “四分”:两侧接口均被使用,加两条边,相当于拼接两侧对偶图,中间形成了个四边形。

稍加归纳,我们得出 $m = n - 1$ 的对偶图应是三角四边剖分图,即,三角剖分图去掉等于“四分”数量的边。

进一步地,$m < n - 1$ 时单独考虑某个道路连通块对偶图同上,现 $n - m$ 个连通块会共用区域,整个对偶图即各个对偶图通过 $n-m-1$ 对共用点合成的图。

显然,用 $k$ 种方式固定一个点的颜色后,$n$ 边形三角剖分图的染色方案数等于 $(k-1)(k-2)^{n-2}$,与剖分细节无关。每因“四分”去掉一条边,便少计算了两个点同色的情况,染色方案数只需乘上 $r = 1 + \frac{k-1}{(k-2)^2}$。而每多一个连通块,相当于固定共用点的颜色,其余和上面无差别。写出来就是 $k \prod (k-1)(k-2)^{s}r^t$,$s$ 为连通块大小,$t$ 为“四分”个数。

故暴力枚举所有能操作出的平面图,用上式统计答案,可以通过子任务 $1$ 与子任务 $2$,得到 $15$ 分。

算法二点五

我们希望找到一种对应关系,能够描述操作结果而不计过程,从而使计数不重不漏。注意到操作不改变空接口的数量,由此想到为初始的接口顺次标号 $1 \sim n$,每铺设道路,新生成的接口按顺时针方向继承消耗的接口的编号,从而使空插槽永远有各自的编号。考虑构建一棵操作树(森林):圆上顺次排布 $1 \sim n$ 号点,每继承了编号 $i,j$,给点 $i,j$ 间连边。圆上的区域一一对应原平面图的区域,因此连边不于圆内相交。

1.png

那么任意时刻的操作局面,都能映射为边不交叉的操作树(森林)。这是否构成双射?答案是肯定的。圆上连边情况亦可实现反推,对于圆上点 $i$,按照 $i-1,\ldots,1,n,\ldots,i+1$ 顺序寻找与之连边的 $j$,指针指向第一个找到的 $j$。显然存在一对 $i,j$ 互指向对方,那么便确定了一次铺设操作,$i,j$ 的指针分别指向下一个,如此反复。

由算法二的式子得知,“四分”是影响最终局面染色的关键,我们需要迁移“四分”的定义至操作树(森林)上。回顾后发现,编号为 $i$ 的空接口所在的道路一定不为“四分”,而这条道路正是圆上按照 $i-1,\ldots,1,n,\ldots,i+1$ 顺序与最后一个找到的 $j$ 间的边。对于所有 $i$,我们同时标记 $i$ 与对应 $j$ 间的边,“四分”数等价于未被标记的边数。

算法三

该算法是出题人最原始的做法,但是与正解相差甚远,有需要者请跳到算法 4!之所以单独列出,是因为该算法同样极具趣味性。

还是从 $m=n-1$ 开始。若未被标记的边数为 $t$,不妨分别列出满足条件的操作树数量的表达式,核心思想是:先不考虑圆,直接枚举树的结构(称未被标记的边为“桥边”,其将树划分成 $t+1$ 块,故先枚举各块缩点后桥边构成的树,再枚举各块内的树及桥边的分配),计算有多少于圆上排列的顺序使得边不交叉,最终总和除以 $n!$。

将块编号为 $0 \sim t$,块内点是有序的,确定以下关键量:

  • $A=[a_0,\ldots,a_t]$ ($a_i\ge 1$, $n=\sum_i a_i$):表示第 $i$ 个块的点数
  • $B=[b_0,\ldots,b_t]$ ($b_i\ge 1$, $2t=\sum_i b_i$):表示第 $i$ 个块缩点后的度数,即连接的桥边数
  • $D_i=[d_{i,1},\ldots,d_{i,j}]$ ($d_{i,j} \ge 1$, $2a_i-2=\sum_j d_{i,j}$):表示第 $i$ 个块内各点的度数,不计桥边
  • $P_i=[p_{i,1},\ldots,p_{i,j}]$ ($p_{i,j} \ge 0$, $b_i=\sum_j p_{i,j}$):表示第 $i$ 个块内各点被分配到的桥边数

分配标号,系数为 $\frac{n!}{\prod_i a_i}$。使用 Prufer 序列计数缩点后树的形态,系数为 $\frac{(t-1)!}{\prod_i (b_i-1)!}$。

考虑第 $i$ 个块内的贡献。计数块内树的形态,系数为 $\frac{(a_i-2)!}{\prod_j (d_{i,j}-1)!}$ 。分配桥边,系数为 $\frac{b_i!}{\prod_j p_{i,j}!}$。各点需要标记一条块内边,不论树形态如何,一定恰有一条边被标记两次,系数为 $a_i-1$。

接下来是最重要的圆上排列部分。在 CF1172B - Nauuo and Circle 中,我们知道排列方案数等于各点度数的阶乘之积乘上 $n$ 。在本题中,由于各点都有标记的边,其在排列时固定会把标记的边放在最旁边,因此贡献并非 $(d_{i,j}+p_{i,j})!$,而是 $(d_{i,j}+p_{i,j}-1)!$。

最终总和乘上上述结论的 $n$,除以 $n!$,注意块之间实际无序,还应再除以 $(t+1)!$,得到以下计算式:

$$\frac{n}{n!(t+1)!}\sum_A{\frac{n!}{\prod_i a_i!}}\sum_B{\frac{(t-1)!}{\prod_i (b_i-1)!}}\prod_i\left(\sum_{D_i}\sum_{P_i}\frac{(a_i-2)!}{\prod_j (d_{i,j}-1)!}\frac{b_i!}{\prod_j p_{i,j}!}(a_i-1)\prod_j{(d_{i,j}+p_{i,j}-1)!}\right)$$

我们先作一些初等的简化:

$$\frac{n}{t(t+1)}\sum_A\sum_B\prod_i\frac{b_i}{a_i}\left(\sum_{D_i}\sum_{P_i}\prod_j{\frac{(d_{i,j}+p_{i,j}-1)!}{(d_{i,j}-1)!p_{i,j}!}}\right)$$

看似无法再推下去,但有趣的是,括号内的式子存在组合意义。将分式写成组合数 $\binom{d_{i,j}+p_{i,j}-1}{d_{i,j}-1}$,其表示 $d_{i,j}-1$ 个黑球,$p_{i,j}$ 个白球的排列方案数。$a_{i}$ 个点对应 $a_i-1$ 个隔板,黑球共 $\sum_j {d_{i,j}-1} = a_i-2$ 个,白球共 $\sum_j {p_{i,j}}=b_i$ 个,括号内等价于求隔板、黑球、白球的排列方案数,即 $\binom{2a_i+b_i-3}{a_i-1,a_i-2,b_i}$。

于是原式可再度简化为:

$$\frac{n}{t(t+1)}\sum_A\sum_B\prod_i \frac{(2a_i+b_i-3)!}{a_i!(a_i-2)!(b_i-1)!}$$

里面还是三项式系数。我们如法炮制,$t+1$ 个块对应 $t$ 个隔板,黑球共 $\sum_i a_i=n$ 个,灰球共 $\sum_i a_i-2=n-2t-2$ 个,白球共 $\sum_i b_i-1=t-1$ 个。然而黑球、灰球都与 $a_i$ 有关,难以直接统计排列方案,但我们仍可以提取出白球,也即:

$$\frac{n}{t(t+1)}\binom{2n-3}{t-1}\sum_A\prod_i \binom{2a_i-2}{a_i}$$

现在试图表示总答案。令 $l = k(k-1)(k-2)^{n-2}$, $C(x)=\sum_{i=2}^{\infty} \binom{2i-2}{i} x^i$,则有:

$$\text{ans}=l\sum_{i=0}^{n}\frac{n(2n-3)!}{(i+1)!(2n-i-2)!} \left([x^n] C(x)^{i+1}\right)r^i$$

奇迹般地,我们整理出二项式系数,对上式作最后的化简:

$$\text{ans}=\frac{nl}{(2n-2)(2n-1)r}[x^n]\sum_{i=0}^{n}\binom{2n-1}{i+1} (rC(x))^{i+1}=\frac{nl}{(2n-2)(2n-1)r}[x^n](1+rC(x))^{2n-1}$$

实现多项式快速幂即可,时间复杂度 $O(n \log n)$,期望通过子任务 $3 \sim 6$,得到 $40$ 分。结合算法二,期望得到 $55$ 分。

算法四

算法三的遗憾在于只能求单点,而难以批量处理所有 $n=1 \ldots N $ 的 $m = n - 1$,看来我们对问题的理解还未到达本质。下面将再运用一个经典双射,将题意演变成容易解决的传统多项式问题。

不妨钦定操作树的 $1$ 号点为根,点 $i$ 的子结点 $j$ 分两类:

  • L 儿子:$j < i$,即在圆上 $j$ 位于 $i$ 的逆时针方向。
  • R 儿子:$j > i$,即在圆上 $j$ 位于 $i$ 的顺时针方向。

然后我们构造一棵三叉树,各点的三叉具体包含:

  • 一或零条 / 边:连接第一个 L 儿子,若无 / 边则无 L 儿子。
  • 一或零条 | 边:连接第一个 R 儿子,若无 | 边则无 R 儿子。
  • 一或零条 \ 边:若自己是某个点第 $x$ 个 L 儿子,则连接其第 $x + 1$ 个 L 儿子,否则连接其第 $x + 1$ 个 R 儿子,若无 \ 边则自己其是最后一个 L 或 R 儿子。

2.png

由于原根结点 $1$ 的儿子一定均为 R 儿子,所以三叉树上其一定仅有 | 边。我们不妨删之,用 | 边连接的儿子作为新的根结点。于是我们成功将 $n$ 个点的操作树对应到了 $n-1$ 个点的三叉树。反推以上过程,不难发现二者形成双射。

下一步自然是再次迁移“四分”的定义。显然,圆上每个点的标记规律是:若有 R 儿子,标记与第一个 R 儿子间的边,若无 R 儿子,则标记父边。那么三叉树上一条边欲代表“四分”,首先自身不能是 | 边,否则会被父结点标记,其次子结点必须有 | 边,否则会被子结点标记。也即,“四分”数等价于三叉树符合以下结构的边的子集数:

3.png

于此多项式的引入便不言而喻了。定义一个三叉树的权值为 $r$ 的“四分”数次方,$F(x)$ 表示不同大小的所有三叉树的权值和,$G(x)$ 表示不同大小的根结点无 | 边的三叉树的权值和,则有:

$$\left\{\begin{aligned}F(x)&=1+F(x)(G(x)-1)\\G(x)&= 1+x\left(G(x)+r(F(x)-G(x))\right)^2\end{aligned}\right.$$

稍加化简可得:

$$r^2 xF(x)^4+(4-4r) xF(x)^3+((6r^2-10r+4)x-1)F(x)^2+((4-4r)(r-1)x+1)F(x)+(r-1)^2x=0$$

套用经典的牛顿迭代即可。时间复杂度 $O(n \log n)$,同样期望得到 $40$ 分。

实际上,若将算法三中的 $\binom{2i-2}{i}$ 解读为二叉树计数,正是 $F(x)$ 的某种展开。我们只是从另个方向上,更为宏观地解读了 $F(x)$。另外,在 127 群友的指点下,朴素精妙的 dp 设计能直接跳过算法二点五导出类似的三叉树结构,正确性也得到了验证。

算法五

从 $m=n-1$ 到 $m < n-1$ 的实际瓶颈在于,操作森林有多少种圆上排列方式,使得多个连通块的操作树间边不交叉。

惊人结论是,排列方案数等于 $n^{\underline{m-1}}=\frac{n!}{(n+1-m)!}$,与各连通块的大小无关。首先破环成链,设连通块大小分别为 $a_1, \ldots, a_m$,同时,我们临时加入 $a_0 = 2$,将其置于链的两端。考虑构建一棵包含关系树:各连通块代表的点的父结点为在包含自己的极小连通块。包含关系树的结构数可在枚举度数后用 Prufer 序列计算,而对于大小为 $a_i$ 的连通块,需要在其间插入 $j$ 个带标号的儿子,系数显然为 $\binom{a_i-2+j}{j}j!$。由此列得: $$ (m-1)![x^{m-1}]\left(\sum_{j=0}^{+\infty}\frac{\binom{j+1}{j}j!}{j!}x^j\right)\prod_{i=1}^{m}\sum_{j=0}^{+\infty}\frac{\binom{a_i-2+j}{j}j!}{j!}x^j $$ 运用生成函数化简即证: $$ (m-1)![x^{m-1}]\frac{1}{(1-x)^2}\prod_{i=1}^m\frac{1}{(1-x)^{a_i-1}}=(m-1)![x^{m-1}]\frac{1}{(1-x)^{n-m+2}}=(m-1)!\binom{n}{m-1}=\frac{n!}{(n+1-m)!} $$ 因此我们实现多项式快速幂,求单个连通块答案多项式的 $n-m$ 次方,取出第 $n$ 项乘上一定系数则为答案。

时间复杂度 $O(n \log n)$,可以通过全部子任务,期望得分 $100$ 分。

另解

下面为 zhoukangyang 所分享的 B 题题解: https://www.cnblogs.com/zkyJuruo/p/17136175.html 。在此表达感谢!

另·另解

下面为 hos_lyric 所分享的 B 题题解: https://hos-lyric.blog.uoj.ac/blog/8415 。在此表达感谢!

比特之地

idea, data, solution, std from 127

算法一

对于第一个子任务,使用暴力 BFS 计算点对间距离。

时间复杂度为 $O(nq)$,期望通过子任务一,得到 $5$ 分。

算法二

按照路径经不经过根进行分类讨论,距离即为曼哈顿距离。

期望通过子任务二,得到 $8$ 分。结合算法一可得到 $13$ 分。

算法三

对于第三个子任务,可以使用沿中线分治/线段树维护矩乘的方法解决。

期望通过子任务三,得到 $10$ 分。结合算法一、二可得到 $23$ 分。

算法四

对于第四个子任务,图等价于网格图,按任意行列切开均可,如果想要刨去根,只需先对根做一次bfs,再算经过根对答案的贡献即可

期望通过子任务二、三、四,得到 $45$ 分。结合算法一可得到 $50$ 分。

算法五

原本四年前出的这题,直到找到了separator theorem才发现可做。

可以认为是平面图最短路Oracle,存在更优的做法,而像是有时遇到的像高分子聚合物一样的图都可以使用。

按照separator theorem的想法,我们要去找尽可能优的separator,但是此图有一个好处,即bfs树就是原树。

因此我们可以获取很大的便利。

首先若树高不超过$\sqrt{n}$,我们可以竖着劈一刀,具体来说,我们先找到处于dfs序中间的点,其到根的路径将树分为左右,且非常平均,但是我们知道这并没有分开整棵树(即使这个点是叶子,由于有横向边,其下方也有可能穿过),于是我们不断找到$dfs$序上的下一个比当前点的深度要大的点,然后选择其到根的链上比当前点深度要大的部分合并到separator中。

考虑为什么这样是separator,在dfs序上,这些点将序列分为很多个部分,则每两个部分之间的点的深度的max在所选的separator中取到,则跨过最初的中位点的到根链的部分之间的所有深度被separator取到,即一定会经过我们选择的separator。

若树高高于$\sqrt{n}$,我们按照separator theorem的方法去选择,具体的按层算出每层$siz_i$,找到其前缀和的中位数$p$,其在第$mid$层,并向前向后找到$l,r$满足条件$siz_l+mid-l\leqslant 2\sqrt{p},siz_r+r-mid\leqslant 2\sqrt{all-p}$。

然后我们中间的设计不按照原定理去做,按照我们上面所述的树高不高的方法做即可。

找到了separator我们按照其分裂原图,分治下去,并计算经过这些点的最短路贡献答案。

时间复杂度是$T(n)=2T(\frac{n}{2})+O(n\sqrt{n})=O(n\sqrt{n})$。

不过这样可能会导致一些问题,比方说其实我们当前分治到的部分不是一个原树上的连通块,而应当用很多个原树上的连通块及其之间的横边表示,需要进行一些处理。

多使用vector进行找separator的过程会好写,不是瓶颈。

期望通过所有子任务,得到 $100$ 分。

算法六

实际上,笔者观察到选手所写的代码,发现非常有道理。

这是因为,实际上separator定理在本题中不需要是一整个separator,也就是分成三部分完成separator的构造,只不过三次取的界限应当比较一致。

因此简单认为每次只分横竖都是有道理的。

期望通过所有子任务,得到 $100$ 分。

UOJ Round #24 公告

2023-02-16 11:46:21 By qingyu

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

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

公元 1972 年 2 月 19 日,中国与阿根廷建交。

最近,跳蚤国与比特国正式建交,双边关系发展顺利。跳蚤国王希望派出它的得力助手伏特,前往比特国进行一次考察。你能不能帮助伏特,完成这次考察途中所遇到的各种问题?

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

出题人:127, csy2005, Sooke

参加本次比赛将有机会获得 UOJ 抱枕!获奖条件的 SHA256 码是 353c68937d197fea673794b95a28e0f9c21ca72d0ffba5f8db89e6518cd8888a。比赛结束后将公布条件。

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


UPD: 恭喜前5名的选手!

  1. zhoukangyang
  2. Kubic
  3. QwQcOrZ
  4. Rainbow_sjy
  5. tricyzhkx
echo -n "比赛中最后一个得分非零的B题提交记录的提交者" | sha256sum
353c68937d197fea673794b95a28e0f9c21ca72d0ffba5f8db89e6518cd8888a

恭喜 dead_X 获得 uoj 抱枕!

Goodbye Renyin 题解

2023-01-21 12:39:03 By qingyu

新年的平衡兔环

idea, data, std, solution from 127

算法 1

对于前两个子任务,容易发现 puts("Yes") 即可。

期望通过子任务 $1$、$2$,得到 $40$ 分。

算法 2

容易发现,条件即能够形成一个多边形,因此充要条件为$R\cdot (\sum a_i-\max a_i)\geqslant r\cdot \max a_i$。

期望得到 $100$ 分。

新年的搜索记录

idea, data, std, solution from ix35.

算法 1

每次 $O(|S|\log |S|)$ 求最大后缀并接到后面。

期望通过子任务 $1,2$,得分 $40$ 分。

算法 2

我会猜答案!

打个表发现,每次加的最大后缀长度要么是等差数列,要么是等比数列(每次翻倍)。

所以只要求出前三项,就可以简单推出后面部分的情况了。

期望通过所有子任务,得到 $100$ 分。

算法 3

我会 Border 理论!

设 $T=g(S)$,则 $f(S)=ST$,考虑 $g(ST)$ 会是什么样子的。由于 $T$ 是 $ST$ 的后缀,所以肯定 $g(ST)\ge T$,同时由于 $T=g(S)$,所以 $g(ST)$ 肯定形如 $RT$,其中 $R$ 既是 $T$ 的一个后缀(因为 $R$ 是 $S$ 的后缀,又不可能比 $T$ 长,否则肯定 $RT < T$),又是 $T$ 的一个前缀(否则比较 $T$ 和 $RT$ 中的 $R$ 部分就可以知道 $RT < T$),所以是 $T$ 的一个 Border。

设 $R_0$ 是 $T$ 的最短 Border,通过比较 $RT$ 和 $R_0T$ 可以归纳证明 $R=R_0^l$(每次剥掉一个 $R_0$),显然 $l$ 越大越好,所以这里 $R$ 就应该取最短 Border 的最大整数次重复。

有了上面的结论,容易证明,如果 $R=T$,那么 $f^k(S)$ 的最大后缀为 $T^{2^k}$;如果 $R\ne T$,那么 $f^k(S)$ 的最大后缀为 $R^kT$,于是模拟 $k$ 次操作后的结果就很简单了。

期望通过所有子任务,得到 $100$ 分。

算法 4

我会 Lyndon 理论!

考虑将字典序反转,将 $S$ Lyndon 分解(按照反转后的字典序),设为 $S=w_1^{p_1}w_2^{p_2}\ldots w_k^{p_k}$,可以证明原来的最大后缀一定形如 $s_i=w_i^{p_i}\ldots w_k^{p_k}$,并且 $s_{i+1}$ 是 $s_i$ 的前缀,但 $s_i$ 不是 $s_{i-1}$ 的前缀。可以用 Duval 算法求出这个 $s_i$,它就是 Duval 算法第一次遍历完 $S$ 的最后一个字符时的后缀。

设 $S$ 的最大后缀为 $A=s_i$,再设 $B=w_k^{p_k}$,那么 $f(S)=SA$。现在考虑 $SA$ 的 Lyndon 分解应该是怎样的,模拟 Duval 算法可以发现最前面的 $w_1^{p_1}\ldots w_{k-1}^{p_{k-1}}$ 应该是不变的(这跟 $S$ 后面的部分根本没关系),但是到了 $w_k^{p_k}(=B)$ 就不一样了,注意 $C=Bw_i^{p_i}w_{i+1}^{p_{i+1}}\ldots w_{k-1}^{p_{k-1}}$ 是一个 Lyndon 串,并且 $A'=CB$ 是一个近似 Lyndon 串(因为 $B$ 是 $C$ 的前缀),所以最后部分的 Lyndon 分解应该是一个 $C$ 和一个 $B$。

因此新串 $f(S)=SA$ 的最大后缀是 $BA$,而 Lyndon 分解的最后一段则不变,仍是 $B$(如果 $B=A$ 则是 $B^2$ 了)。

所以 $f^k(S)$ 的最大后缀就是 $B^kA$,当然 $B=A$ 需要特判,此时为 $A^{2^k}$,我们得到了和正解 2 相同的结论。

如果利用 Lyndon 分解求最大后缀,可以做到 $O(|S|)$ 复杂度,当然用后缀数据结构或哈希来替代也可以通过本题。

期望通过所有子任务,得到 $100$ 分。

新年的双区间操作

idea, data from qingyu; solution, std from huahua, std2 from csy2005

算法一

题目太难了,写个暴力跑路吧。

我们每次暴力进行所有操作,时间复杂度为 $O(nmq)$,可以通过子任务 $1$,得到 $5$ 分。

算法二

我们注意到所有操作都形如求一个区间的最大值,或者将整个区间与某个值取 max,这是可以直接通过线段树解决的。

因此我们使用线段树优化算法一中的暴力,通过子任务 $1$ 与子任务 $2$,得到 $15$ 分。

算法三

一个重要的想法是,一个操作执行多次和执行一次的效果是一样的,因此目的是不漏的找到所有被触发了的操作,而无需关系是否找重复的问题。

一个操作$i$可以被触发,要么是因为 $\max_{k=l_i}^{r_i} a_k \ge x_i$,要么是因为存在一个操作 $j < i$,满足操作$j$被触发了并且$[l'_j,r'_j] \cap [l_i, r_i] \not= \varnothing, y_j \ge x_i$。

我们分开考虑这两部分贡献。

考虑 $l = r = l' = r'$,每个位置独立。因此不需要考虑区间有交的限制。

注意到第二个部分的条件是形如 $j$ 能触发且 满足某些要求,那么$i$ 能触发的形式。那么可以很自然的定义出 $f_i$ 表示如果$i$能触发,那么包括$i$以及可以因此触发的操作$y$ 的 $\max$。

考虑如何转移 $f$。暴力转移为 $f_i = \max( \max_{i < j , y_i \ge x_j} f_j, y_i)$,相当于一个二维偏序,也就是按照$x_j$排序,$f_j$作为权值的一个前缀$\max$,需要动态修改,用树状数组维护即可。

考虑对 $a$ 修改等价于 $O(n+q)$ 次查询 $a_i$ 能在 $i$ 位置上触发哪些操作。也就是按照 $x_i$ 排序后的一个前缀,区别是没有修改,可以线性计算前缀 $\max$。

时间复杂度 $O(m\log n + n+q)$,期望得分 $10$ 分。结合暴力可以得到 $25$ 分。

算法四

每个位置之间不互相独立了,但是不太影响。我们仍然采用算法2中的 $f$ 转移。区别是我们不能对于每一个位置扫描他的操作,而是强制在线的同时处理 $n$ 个位置上总计 $m$ 个操作。数据结构部分需要离散化/动态开点线段树/平衡树等技巧解决。

时间复杂度 $O(m\log n + n+q)$,期望得分 $25$ 分。结合暴力可以得到 $40$ 分。

算法五

接下来需要正面面对区间有交的限制。一种方法是直接上树套树,这个做法非常好写,但是常数较大。

具体来说,我们对长度为 $n$ 的序列建立线段树。把每个操作看成一次查询和一次修改。对于线段树节点$[l, r]$维护两个 map,分别表示所有和$[l, r]$有交但不包含的修改的 $(x_i, f_i)$ 点对;表示包含 $[l, r]$ 但不包含其线段树上父亲节点的修改的所有 $(x_i, f_i)$ 点对。 具体来说,前者可以形象的理解为线段树维护子树信息,后者可以理解为需要标记永久化的懒标记。

修改在会在 map 上插入一个点对,查询则是要支持查询前缀 $\max$。这个可以很好的利用 stl 的 map 完成。注意到只有按照 $x$ 排序后 $f$ 是前缀最大值的位置有用,因此 map 里只保留前缀最大值的位置,查询 lowerbound 一下即可。

时间复杂度 $O((m + n + q) \log n \log m)$,期望得分 $60$ 分。

按照算法四的思路继续优化,可以做到 $O(m \log n \log m + (n + q) \log n)$,不过就失去了其好写的优势,因此不多赘述。

算法六

考虑直接对操作序列 cdq 分治,对权值扫描线。

具体来说, $[l, mid]$ 里的操作按照 $y_i$ 排序,$[mid + 1, r]$ 里的操作按照 $x_i$ 排序。对于每个左侧的操作能触发的对应右侧一个前缀与其有交的区间。仍然是触发多次不会影响思想,将其转化成对于每个位置,如果两个区间都包含了这个位置那么形成一次转移。因此右侧的每个操作可以看成对线段树区间 checkmax,左侧的操作相当于查询区间max,都可以很好的用线段树解决。

注意到后面 $O(n+q)$ 次查询,没有时间维度,可以不扔到 cdq 分治里,而是直接进行 cdq 分治内部的扫描线线段树。

时间复杂度 $O(m \log n \log m + (n + q) \log n)$。期望可以通过所有子任务,得到 $100$ 分。

新年的传火仪式

idea, data, std, solution from Melania

出题人谢罪

首先要承认,这题在比赛的时候没能提供足够的区分度,在此我深表歉意!

这题的数据范围分成了 $\text{A}$ 和 $\text{B}$ 两种类型,这样的出题方式我肯定是不欣赏的,我要自我检讨,大家以后也千万不要效仿我这么做!主要是一开始觉得两个做法各有特点就都想保留,可是我大大低估了实现难度和细节处理的复杂程度。

大家如果要补题的话,我建议只补数据类型 $\text{B}$ 的做法。我数据类型 $\text{A}$ 的设置,实在是背离了当今 $\text{OI}$ 健康的发展方向。

问题分析

我们首先对问题做一个重新表述。拿出 $[l,r]$ 中的所有 > 操作,依次编号为 $1,2,\cdots,t$。设火炬所处位置为 $i$,枚举 $j$,若第 $j$ 个 > 操作进行时 $i$ 在座则令 $i$ 加 $1$,否则 $i$ 不变。初始时 $i=1$,要求 $j$ 扫完 $t$ 时 $i$ 的值。

设一共有 $\text{width}$ 个 > 操作,令 $a(i,j)\in\{0,1\}$ 表示 $i$ 在第 $j$ 个 > 操作进行时在不在座。考虑一个 $n$ 行 $\text{width}$ 列的表格,其中 $(i,j)$ 可能是黑格或白格,对应 $a(i,j)=1/0$。

想象一枚棋子初始时放在第 $1$ 行,若当前处于黑格就向右下走 $1$ 步,否则就向右走 $1$ 步。设 $c_i$ 表示第 $i$ 个操作后首个 > 操作,则棋子初始在 $(1,c_l)$,向右向下不断游走,我们要求出首次游走到第 $c_{r+1}$ 列时所处的行。

称上述这个结构为「黑白表格」,接下来我们的讨论均在黑白表格上进行。注意到黑白表格是要随着 $l$ 发生变化的。

算法一

从 $1\sim n$ 枚举表格的行,维护 $q$ 枚棋子首次到达该行时所在的列。那么每枚棋子都要寻找该行内的下一个黑格。

$l$ 从 $m$ 到 $1$ 扫描线,每遇到一个该行的 1 操作就将 $[c_{该操作},c_{下一个同行的0/1操作})$ 内的格子都变成黑格。这样一来,我们只需要对颜色已经确定的一个后缀从后往前递推出下一个黑格的位置即可。预先将询问按 $l$ 排序与该行的操作归并以保证在正确的时间处理询问。

实现的时候为了方便起见,我们认为表格有 $n+1$ 行和 $\text{width}+1$ 列,其中最后一行一列均永远全为白格。

时间复杂度 $\mathcal{O}\big(n(m+q)\big)$,应能通过子任务 $1$ 得到 $10$ 分。

算法二

注意到随着 $l$ 减小,表格上的黑格有增无减。同时初始格子也单调变左。因此我们有单调性,具体地:随着 $l$ 的减小,棋子首次到达某行时所在的列单调向左变化

枚举行,设 $\text{cur}(l)$ 表示从 $l$ 开始的询问首次到达该行时所在的列。我们用线段树维护 $\text{cur}(1)\sim\text{cur}(m)$ 的序列。‘

有两种修改:区间赋值、全局 $+1$。区间赋值是指寻找下一个黑格:下一个黑格一定是某个 1 操作的 $c$,必须有 $\text{cur}(l)\leq c$。另外下一个黑格还不能更早,设上一个 1 操作是 $i$,则要么 $l>i$ 要么 $\text{cur}(l)$ 在上一个 1 操作的影响范围的右侧。

由于对 $l$ 的限制和对 $\text{cur}(l)$ 的限制均构成一段区间,利用单调性可知它们的交也一定是一段区间。利用线段树二分找到这个区间,直接区间赋值即可。

现在考虑回答询问。对于询问 $[l,r]$,我们需要在 $\text{cur}(l)$ 首次 $\geq c_{r+1}$ 的行将其回答掉。我们预先将所有在 $l$ 的询问按 $r$ 排序,再用一棵线段树维护 $r$ 最小的那个询问的 $c_{r+1}$。如果只有区间赋值操作,我们可以不断取出该区间的最小值直到最小值都不能被回答为止,每次取出一个询问要更新 $l$ 处最小的 $c_{r+1}$。这样均摊复杂度是正确的,然而无法处理全局 $+1$ 操作。

我们可以直接忽视全局 $+1$ 操作的存在。到第 $i$ 行时一共加了 $i-1$,据此调整我们对线段树里 $\text{cur}$ 值的认知即可。我们希望只在区间赋值操作时回答询问,然而有的询问是在全局 $+1$ 操作时被回答的。我们只需要做一些微调:设询问 $[l,r]$ 在第 $i$ 行作为最小值被取出。考虑 $\text{cur}(l)$ 的实际值。若 $\leq c_{r+1}$ 则答案就是 $i$,否则答案 $=i-\big(\text{cur}(l)-c_{r+1}\big)$。

其实类似于坐标系变换,我们将第 $i$ 行整体向左推 $i-1$ 格,将原先的向右/向右下 $1$ 格变为向右/向下 $1$ 格,跨行时 $\text{cur}(l)$ 就无需改变。

时间复杂度 $\mathcal{O}\big((n+m)\log m+q\log q\big)$,应能通过子任务 $3$ 得到 $50$ 分。

算法三

初始在座情况的存在和 ! 操作的存在都破坏掉了单调性,这显著提高了问题的复杂程度。

我们考虑带权分块,令 $i$ 的权值 $=$ 针对 $i$ 的修改操作个数 $+1$。设定一个值 $B$,将 $[1,n]$ 划分为若干个权值和 $\leq B$ 的不交区间。当然可能有权值 $>B$ 的单个行,我们希望在 $\mathcal{O}(m+q)$ 内处理单个行,在 $\mathcal{O}(m+q+B^2)$ 内处理一个块。

首先是处理单个行,这部分做法和子任务 $1$ 类似。倒着归并操作和询问,每遇到一个该行的 ! 操作就将 $[c_{该操作},c_{下一个同行的0/1操作})$ 内的格子都黑白反转。遇到该行的与初始在座情况不同的 0/1 操作时也一样。

每个时刻该行的格子分为三个部分:尚未被反转过的部分,已经被反转过的部分和已经确定下来的部分。找下一个黑格时枚举三个部分看要找的黑格是否落在其内。对于第三部分,逆推出下一个黑格即可。对于第二部分,我们每做一个反转就在反转区间的左端点打 $1$ 个反转标记,维护反转标记的后缀和。逆推出下一个后缀和的奇偶性与当前不同的格子即可。

更重要的是如何处理整个块。一个块有两个任务:一是根据 $q$ 枚棋子首次到达块首行时所在的列推出它们首次到达下一块首行时所在的列;二是回答所有撑不到下一块的询问。两个任务都需要对棋子在该块内的运动情况进行刻画。

对于所有针对该块的操作 $i$ 在 $c_i$ 处设置一个关键点。从关键点出发会到达另一个关键点,我们连一条有向边。那么棋子会沿着关键点形成的内向森林行走。另外,从关键点出发还可能直接运动到某行的第 $\text{width}+1$ 列,或者直接走到下一块的首行。

$l$ 一定时黑白表格一定。我们做一个坐标系变换,将第 $i$ 行整体向左推 $i-1$ 格。相当于对一个格子,要求其下方第一个白格,并进一步求其右方第一个黑格。注意到我们的列被划分为了 $\leq B$ 个区间,每个区间内的列每行的黑白情况均相同。我们将一个区间缩成一个格子可以得到一张「浓缩表格」。我们即是要在浓缩表格的每行每列上做动态后继问题。

由于权值和 $\leq B$,我们的 $l$ 也被划分为了 $\leq B$ 个区间,每个区间内 $l$ 的表格在该块内相同。倒着枚举 $l$ 的等价类,维护浓缩表格。新增一个操作的影响是浓缩表格上的区间反转。我们用压缩 $\text{Trie}$ 来维护列的动态后继,每次修改暴力重构行的动态后继。这里由于序列长度 $\leq B$ 压缩 $\text{Trie}$ 只需要开两层。当然这很不优美,实际上我们有严格根号的做法。

将 $l$ 的等价类与询问做归并。对一个等价类我们用上面的做法预处理出关键点的后继。然后我们递推出从每个关键点开始走到达的最后一个关键点。对于一个询问我们也需要求一次后继得出其到达的首个关键点。利用这些信息,加以一些较为复杂的分类讨论,即可得出每枚棋子运动的轨迹。对于那些运动不到下一块的棋子,我们则需要暴力跳这棵树。

上文提到的严格根号的做法基于这样一个事实:我们会问动态后继的格子只有 $\mathcal{O}(B)$ 个。这些格子将每列切成一些连续段,我们只需要分别在这些连续段内做动态 $\text{mex}$ 问题即可。这可以离线用线性并查集做到线性。$\text{not practical}$。

时间复杂度 $\mathcal{O}\big((n+m)\sqrt{m+q})$,应能通过子任务 $5$ 得到 $50$ 分。结合算法二,可以获得 $100$ 分。

新年的找对

idea, data, std from 127

solution1 by 127

此即tech round:E

subtask1,2

暴力,状压,乱搞均可。

subtask3

一般图最大匹配是这个问题的特殊情形,因此如果写组合算法将如同带花树。

subtask4

最大流是这个问题的特殊情形,因此如果写组合算法也会类似网络流。

正解

Part I

matroid parity problem,又称matchoid,拟阵奇偶问题。

普通的matchoid问题是NPC的,但在此处我们需要考虑的是线性拟阵奇偶问题,已有多项式复杂度算法,此即拟阵可在域上线性表出。

拟阵奇偶问题的特化有拟阵交,网络流,一般图最大匹配等等,还有被称为$\Delta$拟阵的版本。

线性拟阵的问题可以简单表述:在一线性空间中取值,有$m$对向量,选出最多的对数$k$,使得选出的这$2k$个向量线性无关。

代数算法不同于组合算法,通常使用线性代数的工具进行分析和构造。

此问题中,有一种称为稀疏型构造的构造:

$$ \begin{bmatrix} - & A \\ A^T & T \end{bmatrix} $$

其中$A$为$[a_{1}^1,a_{1}^2,a_{2}^1,a_{2}^2...,a_{i}^1,a_{i}^2,...,a_{m}^1,a_{m}^2]$。

$T$为$A$的匹配矩阵:

$$ \mathrm{diag}\left\{\begin{bmatrix}0 & x_1 \\ -x_1& 0\end{bmatrix},\begin{bmatrix}0 & x_2 \\ -x_2& 0\end{bmatrix},...,\begin{bmatrix}0 & x_m \\ -x_m& 0\end{bmatrix}\right\} $$

其中$x_i$为线性空间基域上代数无关的未定元,可以理解为扩域下代数无关的元素。

记$\nu(A)$为元素对集$A$的答案,我们有:

$$ 2\nu(A)=\mathrm{rank}\left(\begin{bmatrix}- & A \\A^T & T\end{bmatrix}\right)-m $$

我们需要一个引理:

对于混合斜对称矩阵$K+T$,$K$为数值斜对称矩阵,$T$为代数斜对称矩阵,$K+T$非奇异当且仅当存在$K$的主子矩阵$K[S]$有$K[S]$和$T[U\backslash S]$均非奇异。

其中$K[S]$表示$K$行列集合均为$S$的主子矩阵,$U$为全集。

证明只需对斜对称矩阵展开Pfaffian即可。

然后我们考虑构造的正确性,设集合$S$所表示的主子矩阵线性无关,即$\mathrm{rank}=|S|$,显然此主子矩阵包含矩阵$T$,设此主子矩阵为$W$,则由引理,有子集$V$使得$W$被分解为$K+T$形式后$K[S\backslash V]$与$T[V]$均非奇异,由$K$的形式知$K$为对称矩阵,且有分块形式使左下右上均为方阵,方阵对应$S\backslash V$,且由$T$的形式知,$T[V]$为很多对的并,那么$S\backslash$也由很多对的并组成,故知$S\backslash V$构成一组合法方案,反之亦然。

稀疏型矩阵过于庞大,使用经典的打洞技巧,用$Schur$补的秩恒等式即可转化得到紧凑型:

$$ 2\nu (A)=\mathrm{rank} \sum_{i}x_i\cdot a_i^1 \wedge a_i^2 $$

其中$\wedge$为楔积$a\wedge b=ab^T-ba^T$

接下来所有的构造将在此基础上进行。

Part II

首先路径不符合构造的想法,即图拟阵,我们将路径松弛为树,那么考虑尽量大的边集构成生成树,每棵树不含超过两种颜色的点即可。

而我们容易从最多的边数推得答案,以及从边集的方案构造答案。

考虑生成树本身需要一个图拟阵,因而边拟阵的线性表出需要本身需要设计为$[x,-x]$的形式,而我们则需要设计另一个向量的形式以保证颜色数不超过$2$。

考虑到仍有不同色的限制,因此我们可以选取一些二维子空间来实现这一点。

取空间$(F^2)^n$,为每条边$e(u,v)$选取一二维子空间$L_e=\{(0,0,...,0,x_u,0,...,0,x_v,0,...)\}$,其中$x_u+x_v=0$,$x_u\in F^2$,基由两个向量组成。

我们还剩为数不多的方法引入点的限制,为每种颜色$c$的点选取$F^2$上的一维子空间$Q(c)$使其之间独立,对颜色$0$单独选取$Q(0)=0$,设其基为$q_c$。

令每个点$v$有$R(v)=(0,0,...,0,q_{c_v},0,...)$,令$Q$为所有$R(v)$的张成。

那么我们以商空间的形式引入点的限制:对于边的子集$S$,$L_S/(L_S \cap Q)$无关,即$L_S\cup Q$无关。

边的连接相当于一种传递的作用,手动消元可知同一棵树内既不存在相同颜色的两点,也不存在三种不同的颜色。

由于可假设除去连接相同颜色的边,我们可知$\dim{L_e/Q}=2$,但有可能某些边集的空间的张成可以交$Q$非平凡。

那么怎么可知$L_S\cup Q$独立?这看起来是一个经典的线性代数问题,即几个与$Q$独立的空间与$Q$合起来不独立。

我们的想法是提前让其他向量在$Q$中商干净,即先将空间分解为$Q$与$Q$的补的直和,那么独立当且仅当向量在$Q$的补中的部分独立。

如果有内积结构,取正交补则是容易的(内积空间,Schmit),如何取$Q(c)$,取$L_e$,如何取补之上的分解,读者可自行尝试,只须满足条件即可,笔者的标算和_rqy的题解中所提到的可以作为参考。

Part III

求出答案是容易的,若设答案为$r$,则我们可用经典手段做到$O(mr^3)$甚至$O(mr^2)$,注意到楔积在矩阵中的位置关系,以及答案的级别,我们再一次尝试使用打洞方法用分治优化复杂度。

关于这一点的实现细节,_rqy 的题解有更详细的论述。

Part IV

实现以及说说话,标算采用了动态矩阵优化空间复杂度,好像可以直接复用矩阵,然后在矩阵乘法,求逆处均有优化,特别是对于$AB^{-1}$的求解,将$B$的求逆过程复用在一起。

笔者出这个问题,一是为了压轴,二是为了宣传代数算法,最主要的目的还是让选手对于较为学术的研究有一个熟悉,这是OI避不开的问题,何时自己研究何时找寻背景,我想OI中独自研究的时间并不会多,大量的问题都是在重复甚至很多看起来不可解的问题其实都早已有了答案,这时就不可能以"毒瘤,论文"等方式避开这样的问题(浪费了时间,你会难过),而在了解更多内容之后,以OIer的水平,可以较为容易甚至轻易地做出自己的结果,这样一来,从两边都改善了学术界和普通竞赛之间的关系(OIer是很强的劳动力)。

Part V

还有很多matchoid的应用,我来列举一下,免得其他老哥(以及我)拿原题出:

Xuong tree,Pinning number,3-degree Feedback Vertex Set,3-hypergraph maximum spanning tree。

会作为模板题添加一些到uoj。

solution2 by _rqy

详见 https://uoj.ac/blog/8048

UOJ Easy Round #11 题解

2022-11-20 00:08:32 By qingyu

切割冰片

idea, data, solution, std from ix35

在题解中,我们用横光 $i$ 表示从上到下第 $i$ 条横向光束,纵光 $i$ 表示从右到左第 $i$ 条纵向光束(与题面相反)。

称一根光束被阻塞,当且仅当它最终没有延申到其最远距离。

算法一

暴力枚举所有 $n+m$ 条光束的激活顺序。

时间复杂度为 $O((n+m)!\times \operatorname{Poly}(n,m))$。

期望可以通过子任务 1,获得 15 分。

算法二

我们对该问题做一些基本的观察。

  • 观察 $1$:横光 $1$ 和纵光 $1$ 中,一定存在一个没有被阻塞。

    证明:假设二者都被阻塞,则第一种情况是横光 $1$ 被纵光 $1$ 阻塞,那么纵光 $1$ 就没有被阻塞,矛盾;第二种情况是横光 $1$ 被纵光 $x\ (x>1)$ 阻塞,纵光 $1$ 被横光 $y\ (y>1)$ 阻塞,那么横光 $y$ 和纵光 $x$ 就会相交且穿过对方,这是不合题意的,矛盾。

据此,我们就可以推得更强的结论:

  • 观察 $2$:可以假定所有横光从上到下依次激活,所有纵光从右到左依次激活,不会漏掉任何一种可能的最终结果。

    证明:由于横光 $1$ 和纵光 $1$ 中存在一个没有被阻塞,所以可以认为那一根光束是第一个被激活的,然后对剩余的光束归纳。

于是我们只需要枚举满足上述规则的方案,当 $n=m$ 时时间复杂度为 $O(2^{2n})$。

期望可以通过子任务 1 与子任务 2,获得 30 分。

算法三

我们可以考虑按照激活的顺序进行动态规划。

设 $f(i,j)$ 表示只考虑横光 $1,\ldots,i$ 和纵光 $1,\ldots,j$,共能得到多少种不同的光束排布方法,那么转移如下:

  • 如果 $l_{n-i+1} < m-j+1$,那么横光 $i$ 即使伸到最远也够不着纵光 $j$,所以我们可以认为横光 $i$ 是最后一个被激活的(因为把所有纵光激活的时间移到它前面不影响结果),也就是 $f(i,j)=f(i-1,j)$;
  • 如果 $l_{n-i+1}\ge m-j+1$,那么横光 $i$ 是可能挡住纵光 $j$ 的,所以最后一个激活的是横光 $i$ 还是纵光 $j$ 就是两种不同的情况,也就是 $f(i,j)=f(i-1,j)+f(i,j-1)$。

初始状态为 $f(0,i)=1,\ f(i,0)=1$,答案为 $f(n,m)$。

直接计算,时间复杂度为 $O(nm)$。

期望可以通过子任务 1 ~ 4,获得 80 分。

算法四

我们需要针对 $m$ 这一维进行优化。

考虑从 $f(*,x-1)$ 推到 $f(*,x)$,设 $S_x$ 表示满足 $l_{n-i+1} < m-x+1$ 的 $i$ 的集合,那么对于 $i\in S_x$ 有 $f(i,x)=f(i-1,x)$,而对于 $i\notin S_x$ 有 $f(i,x)=f(i-1,x)+f(i,x-1)$。

显然 $S_x\subseteq S_{x-1}$,不妨先考虑 $S_x=S_{x-1}$ 的特殊情况:

  • 这时,我们将所有那些 $i\notin S_x$ 的 $i$ 写出,排序后记为 $0=a_1 < \ldots < a_k$,那么对于 $i\in S_x$,找到最大的 $a_j$ 使得 $a_j < i$,就有 $f(i,x)=f(a_j,x)$,所以我们可以只关心所有 $f(a_j,x)$。
  • 而对于 $j>1$,我们有 $f(a_j,x)=f(a_j-1,x)+f(a_j,x-1)=f(a_{j-1},x)+f(a_j,x-1)$,也就是说 $f(a_j,x)\ (j=1,\ldots,k)$ 这个序列实际上是由 $f(a_j,x-1)\ (j=1,\ldots k)$ 这个序列做前缀和得到的。

扩展上面这个结果,如果有 $S_x=S_{x+1}=\ldots=S_{x+t}$,那么 $f(a_j,x+t)$ 这个序列就应该是由 $f(a_j,x)$ 这个序列做 $k$ 次前缀和得到的,利用路径计数的模型,通过预处理组合数可以 $O(n^2)$ 计算长度为 $n$ 的序列做若干次前缀和得到的结果。

再考虑 $S_x\ne S_{x+1}$ 的情况,由于 $S_{x+1}\subseteq S_x$,所以这样的 $x$ 只有 $O(n)$ 个,我们可以对于这些 $x$ 暴力进行转移。

所以总的时间复杂度为 $O(n^3)$。

期望可以通过所有子任务,获得 100 分。

科考工作

idea from JohnVictor; data, solution, std from csy2005; solution2 from 127

算法一

考虑如下做法:如果众数出现至少 $n$ 次,直接输出众数;否则考虑每一次将众数和第二多的数配对,可以配出 $n-1$ 对不同的对子。

我们证明存在一组解,使得选了剩下一个数和这 $n-1$ 对中每一对中的一个数。这等价于说,对于任意 $n-1$ 个非零数,他们的子集和取遍 $\bmod n$ 的完系。

实际上,我们可以归纳的找出 $\{0\}=S_0\subseteq S_1\cdots\subseteq S_{n-1}=\mathbb{Z}_{n}$,并且 $|S_i|=i+1$,且由前 $i$ 个数的子集和构成。

令第 $i$ 个数为 $a_i$,我们只用证明 $(S_{i-1}+a_i)\setminus S_{i-1}$ 非空,实际上两者大小相同,并且模素数意义下如果 $S_{i-1}+a_i=S_{i-1}$,那么对于 $S_{i-1}$ 中任意一个元素 $t$ 和任意的 $k$,$t+ka_i$ 都在 $S_{i-1}$ 中,那么 $S_{i-1}$ 就是全集,矛盾。

我们可以很方便的用 set::bitset 来维护每一次加进去的数,也很好根据维护好的数组来逆推答案。时限很松,$O(\frac{n^2}{w})$ 的做法基本都能获得 $90$ 分。

为了获得 $100$ 分,有很多乱搞可以通过。例如在上面一步中将所有相同的数写在一起的前提下 random_shuffle 大概率能找到一个区间作为解。

算法二

经典的modular subset背包,考虑对于一个当前的 $x$ 找到一个 $t$ 在当前的背包中而 $t+x$ 不在,这在 bitset 上就相当于把一个 0/1 串移位与自己作或,而要均摊地找到那些对应位置不同的元素(在模意义下不同的元素是我们要找的元素的两倍),可以发现我们可以使用二分 + hash 来跳过一段完全相同的部分,而动态的修改需要使用一个树状数组来维护hash,于是复杂度为 $O(n\log^2n )$,可以通过本题 。

谢罪环节

今天比赛的B题是来源于 UNR d2t1,经典的数学问题,给出了存在性证明,但是复杂度不够好,需要找到一个构造性的算法。

JV 出这题主要是希望讨论MO中剩余类递推的思想,也就是对于一个集合 S,如果 S 和 S+x 在模素数意义下是相同的,那么 S 必定是全集。从这里很好给出一个配对,然后给出 n^2/w 的背包,这是 JV 投题时给出的做法。

后半部分,如果直接用位运算优化,那么可以获得 90 分。最后的 10 分数据范围较大,主要还是因为我们朴素地想,要出题就尽可能出到最大可能的范围。

由于获得这最后 10 分需要知道一点论文上的解题套路(虽然近期也出现在了其他模拟赛中),所以对于不熟悉这一解题套路的同学来说不太公平。对此我们深表歉意,下次出题时我们会尽量避免这种情况,比如魔改题意使得论文上的结果无法被使用。

企鹅游戏

idea, data, solution, std from Alex_Wei; data2, std2 from djq_cpp, csy2005

算法一

暴力匹配,时间复杂度 $\mathcal{O}(L ^ 2)$。

期望通过子任务 1,得到 20 分。

算法二

注意到对每个 $t_j$ 最多只有 $|t_j|$ 个 $|s_i|$ 产生贡献,因此问题转化为 $\mathcal{O}(L)$ 次求某个模式串在文本串中的出现次数。对 $s$ 建出 AC 自动机(相当于对最长的 $s_i$ 建出 KMP 自动机),将 $t_j$ 放在自动机上跑一遍,则 $s_i$ 在 $t_j$ 中的出现次数相当于它在自动机上对应节点在失配树上的子树内所有节点被经过的次数之和。树形 DP + 快速幂或光速幂即可。

时间复杂度 $\mathcal{O}(L\log P)$ 或 $\mathcal{O}(\sqrt P + L)$,其中 $P = 2 ^ {32}$。

期望可以通过子任务 2,获得 20 分。结合算法 1 可以获得 40 分。

算法三

容易证明 $|s_i|$ 至多只有 $\mathcal{O}(L ^ {1 / 2})$ 种取值。

因为 $s_i$ 互不相同,所以对于每个 $t$ 的前缀 $t[1, j]$,对于每个不同的长度 $len$,至多有一个长度为 $len$ 的 $s_i$ 和 $t[1, j]$ 的后缀匹配。因此和 $t[1, j]$ 的后缀匹配的 $s_i$ 数量不超过 $|s_i|$ 的取值种类数,即 $\mathcal{O}(L ^ {1 / 2})$。

建出 $s_i$ 的 AC 自动机,对每个状态预处理最近的代表某个单词的祖先,那么每跳一次祖先就会找到一个和当前前缀的后缀匹配的单词。暴力统计所有出现单词的 $cnt_i$,最后光速幂算出 $v_i$ 即可。时间复杂度 $\mathcal{O}(L ^ {3 / 2})$。

期望可以通过子任务 1 与子任务 3,获得 50 分。结合算法 2 可以获得 70 分。

算法四

我们还有另一用于解决子任务 3 的算法:

根号分治,对于串长 $\leq \sqrt L$ 的 $t$,枚举所有子串更新 $cnt_i$。对于串长大于 $\sqrt L$ 的 $t$,对每个 $s_i$ 求出其在 $t$ 中出现次数,算出 $v_i$ 并求和。时间复杂度 $\mathcal{O}(L ^ {3 / 2})$。

同样地,期望可以通过子任务 1 与子任务 3,获得 50 分。结合算法 2 可以获得 70 分。

算法五

结论:每个文本串包含的 不同 单词数之和的级别为 $\mathcal{O}(L ^ {4 / 3})$。

证明:长度超过 $L ^ {1 / 3}$ 的单词最多有 $L ^ {2 / 3}$ 个,每次出现对应一个长度超过 $L ^ {1 / 3}$ 的文本串,所以在所有文本串中最多出现 $L ^ {2 / 3}$ 次。对于长度不超过 $L ^ {1 / 3}$ 的串,每个长度的所有单词出现次数之和不超过 $L$,因此总和不超过 $L ^ {4 / 3}$。

也就是说,在 Subtask 3 的做法中,若将重复经过的点去掉,则总共只会遍历 $\mathcal{O}(L ^ {4 / 3})$ 个点。基于此结论,建出 $s_i$ 的 AC 自动机,为避免重复经过同一点,有两种做法:

  • 将 $t$ 在 AC 自动机上经过的所有点建出虚树,树形 DP + 暴力枚举。
  • 从 $t$ 在 AC 自动机上经过的每个点向上跳父亲,如果当前点被经过,说明它的祖先一定被经过,退出。这个过程给予所有相关点形成的树的形态,对其做拓扑排序即可。

配合光速幂,时间复杂度 $\mathcal{O}(L ^ {4 / 3})$。为了卡掉所有 $L ^ {3 / 2}$ 的做法,时限设置较小(但是在两倍 std 以上)。不使用光速幂会被卡,常数较大也有概率被卡。

期望可以通过所有子任务,获得 100 分。

Bonus

本题可以做到 $\mathcal{O}(L\sqrt {\log L})$,但常数较大。

对于单次询问,考虑将对应虚树建出,问题形如求一条链上所有单词节点出现 $k$ 次的权值之和。将所有链离线按 $k$ 分类处理,则通过树上差分可将处理的复杂度降至所有 $cnt = k$ 的链的并的大小之和,严格优于 Subtask 4。

通过上述分析,可知时间复杂度为每个单词在所有文本串中的不同出现次数之和。

如果一个单词的贡献为 $x$,那么它至少出现了 $\mathcal{O}(x ^ 2)$ 次。

设长度为 $i$ 的单词有 $c_i$ 个,它们在文本串中的出现次数之和不超过 $L$。根据 $\sqrt x$ 的上凸性,这 $L$ 次平均分配给 $c_i$ 个单词再求平方根后最优。因此 $c_i$ 的贡献为 $c_i\times \sqrt {\dfrac L {c_i}}$ 即 $\sqrt {Lc_i}$。

将 $\sqrt L$ 提出,设 $d = ic_i$,我们需要在 $\sum d_i\leq L$ 的限制下最大化 $\sum \sqrt {\dfrac {d_i} i}$。根据 $\sqrt {\dfrac {d_i} {i}}$ 的上凸性,我们会分配 $d_i$ 使得 $\sqrt {\dfrac {d_i} i}$ 的导数相同,即 $\sqrt {\dfrac {1} {i\times d_i}}$ 相等。因此 $d_i$ 正比于 $\dfrac 1 i$,得 $d_i = L \times \dfrac {\frac 1 i} {\sum \frac 1 i} = \dfrac {L} {i \ln L}$。

因此时间复杂度为 $\displaystyle\mathcal{O}\left(\sqrt {L} \times \sum \sqrt {\frac {L} {i ^ 2 \ln L}}\right) = \mathcal{O}(L\sqrt {\log L})$。

谢罪环节

出题人没想到有依赖模数性质的 $32L$ 做法,在这里拜谢 skip2004 哥哥!

有一位同学写正解被卡常了,还有一位同学 $O(L\sqrt L)$ 极限卡常通过此题,出题人为没卡掉暴力反倒把正解卡了表示遗憾,并在此谢罪 QAQ。欢迎各位选手发挥自己的聪明才智卡掉根号的做法!

出题人出题时就感觉很难区分 $O(L\sqrt L)$ 和 $O(L ^ {4 / 3})$。在标算只有 $O(L\sqrt L)$ 时,出题人本打算将此题投到西安区域赛来着,后来写题解写着写着发现有 $O(L ^ {4 / 3})$ 做法,觉得很高妙,想分享给大家,所以就投 UOJ 了。

出题人尽自己最大的努力将这两个复杂度已知的所有算法卡满了。出题人的想法是,既然投到了 UER,那就尽量符合 “Easy” 的原则让大家乐呵乐呵。更重要的是借此机会把这个有趣的结论推广给大家,希望大家喜欢!

共 9 篇博客