UOJ Logo whzzt的博客

博客

UOJ Round #18 题解

2019-08-12 08:12:43 By whzzt

惨啊。。感觉延续了 UOJ Easy Round 的传统变成 UOJ Super Hard Round 了?

本来这比赛里的一些题是打算出在 UOJ NOI Round 的,但是当时题目数量也比较紧张,类型也不太和 NOI 类似,感觉强行出出来只会被喷,而且当时时间也在二招边上。。所以鸽着鸽着就鸽没了啊。。

欢迎大家给 UOJ 投题啊,感觉管理员缺乏生产能力是真实痛苦啊。。

这个 T1 本来是看了投给 NOI Round 的几个题都有点难不太签到就想换个签到的,然后就去找网友要了个题,网友和我讲了个听起来很真实的做法,听起来也挺 T1 的就安排了上来。然后实现的时候发现。。是个和暴力拍不上的假做法。。

然后稍微修了一下做法,个人感觉难度没有太大增加结果看起来大家并不这么认为?

还有今天的题目背景都是 ztr 小哥哥写的~ 大家觉得题面怎么样呢,虽然主题似乎已经写过一次了。

绝对不鸽

from bulijiojiodibulido, 标程、题解、数据 by whzzt

算法一

当 $ a = b = 1 $ 时,显然答案就是 $ \max(a_i) + 1 $。当然如果没看出来的话写个暴力也是可以的~

期望得分 $ 17 $ 分。

算法二

考虑这是一个什么样的问题,实际上我们可以当成我们现在有 $ \infty $ 个数,其中只有 $ n $ 个数的值是给定的,其他的数都是 $ 0 $。我们要不断删去最大的 $ B $ 个数,并将剩下的前 $ n $ 个数的和增加至多 $ A $。我们想要最大化历史最大值。

不妨枚举我们要最大化的是哪一个数,如果是第 $ k $ 大的数,我们可以贪心求得最后的答案:我们将这 $ k $ 个数取出来,在我们整个操作过程中,我们可以保证这些数的大小关系不发生变化(每个数不能加到超过前一个数)。问题变为最大化此时最终序列中剩下的数,也就是最小值。

显然我们每次增加的 $ A $ 都一定会增加到最小的若干个数,因此我们可以进行模拟,这样的时间复杂度是 $ O(k) $。

当 $ n \le 100, A \le 100, a_i \le 100 $ 时,可以证明 $ k \le 3000 $,因此模拟到 $ 3000 $ 即可。期望得分 33 分。

算法三

可以发现这样一个事情:序列中超过 $ \lfloor \frac{A - 1}{B} \rfloor $ 的数是在不断变少的;而当序列中只存在不超过 $ \lfloor \frac{A - 1}{B} \rfloor $ 的数时,我们可以轻松将序列变为 $ n - B $ 个 $ \lfloor \frac{A - 1}{B} \rfloor $ 以及 $ B $ 个 $ 0 $ 的形式:每次将 $ B $ 个 $ 0 $ 均变成该值,我们还能增加其他数。

因此当输入序列全 $ 0 $ 时,问题就相当于是给定一个 $ n - B $ 个 $ \lfloor \frac{A - 1}{B} \rfloor $ 以及 $ B $ 个 $ 0 $ 的序列的问题。

而此时我们也无法在每个数都不超过 $ \lfloor \frac{A - 1}{B} \rfloor $ 的情况下做更多的改进。那么我们仍然考虑算法二中的贪心,显然有 $ k = x B + 1 $,不妨假设 $ k_0 $ 是第一个满足 $ k > n - B $ 的 $ k $,考虑贪心的过程,容易证明 $ k \le k_0 $,因为多一个 block 的操作实际上没有任何意义。

因此我们只需要检查 $ O(\frac{n}{B}) $ 个 $ k $,这样暴力做的时间复杂度是 $ O(\frac{n^2}{B}) $,期望得分 44 分。

算法四

现在我们有了一个初始序列,但我们同样可以意识到,如果序列中不再存在超过 $ \lfloor \frac{A - 1}{B} \rfloor $ 的数,接下来的部分就和初始全是 $ 0 $ 一样,我们就可以直接套用算法三来解决了。

不妨假设 $ k_1 $ 是第一个满足 $ k > n $ 的 $ k = xB + 1 $,我们同样可以证明 $ k \le k_1 $:

如果我们在 $ k_1 $ 之后再补一个 block,那么在我们不断给较小的数增加 $ A $,删去较大的数的过程中,总会到达一个数字被填平的时刻:即和 $ S $ 被均匀地分给 $ n $ 个数。考虑最终的 $ \frac{S}{n} $ 的值,显然必有 $ \frac{S}{n} > \lfloor \frac{A - 1}{B} \rfloor $,否则其答案不会比初始全 $ 0 $ 的情况更优。

但我们多的这个 block 只会让我们在达到同一长度时多增加 $ A $ 的值,首先考虑 $ \lfloor \frac{S}{n} \rfloor > \lfloor \frac{A - 1}{B} \rfloor $,在这样的情况下我们增加的 $ A $ 还不够填平的耗费,因此均值减小,填平时间推迟,答案变小。而在 $ \lfloor \frac{S}{n} \rfloor > \lfloor \frac{A - 1}{B} \rfloor $ 的情况下,由于我们要多删去 $ B $ 个数,因此这多余的不超过 $ B $ 的收益也会被删去,均值不会增大,答案也不会增大。

有了 $ k \le k_1 $,我们就可以同样 $ O(\frac{n^2}{B}) $ 解决问题了,期望得分 71 分。

算法五

接下来问题变成了,如何对一个序列,维护每次将较小的数增加上总和不超过 $ A $,并删去最大的 $ B $ 个数的过程。我们可以二分求出在什么时候序列被填平了,即和 $ S $ 被均匀分给 $ n $ 个数的情况。而对于这样被填平的情况,我们可以再二分答案 $ T $,并求出 $ f_i $ 表示序列长度为 $ i $ 时最小的满足条件的 $ S $。

总时间复杂度 $ O(n \log n \log A) $,期望得分 100 分。

没这种事

from djq_cpp, 标程、题解 by djq_cpp,数据 by whzzt

这个题的idea来源是这样的:某个名为 MagicSpark 的初一小朋友问我一道他看错的题,然后我发现可以数数,然后就变成现在这个题了。

接下来我们不妨假设 $ n < m $。

算法一

暴力整个矩阵。时间复杂度 O(2^(n * m))。

期望得分 0 分。

算法二

观察发现每个元素只会出现在四个位置上:原位置、沿中间一列对称、沿中间一行对称、沿中心对称。n, m 为奇数时中轴线上的元素单独处理。

直接对满足【每四个对称位置构成的 multiset 都相同的 $ (S, T) $】计数,再乘上中轴线的贡献。

看起来很不靠谱,但是发现居然过了 subtask 1 和 2。

期望得分 13 分。

算法三

冷静一下,分析存在一种方案从 S 变成 T 的条件。

先假定 $ n, m $ 均为偶数。

既然每个元素只会出现在四个位置上,那就可以把它们单独提取出来,并只考虑与它们有关的行/列 reverse 操作。

注意到每次行/列 reverse 都会使得这四个位置元素逆时针排列构成的置换奇偶性取反。那么,对于固定的 S, T,可以根据每四个对称位置元素置换的奇偶性列出一个有关【每行 reverse 操作奇偶性】和【每列 reverse 操作奇偶性】异或方程组作为存在操作序列的必要条件。(另外,当这四个元素有重复时,不会产生任何约束。)

与此同时,该方程组有解也是充分条件:把对应变量为 1 的行和列 reverse 之后,会发现每四个对称位置都构成一个偶置换。手动构造可以说明:通过行列 reverse 操作,一定可以在不影响其它位置的情况下对某四个对称位置作用任意偶置换。

另外,对称的两行(列)的变量可以合并。由此,每个异或方程只有两个未知数。联想到构建一张二分图。

枚举连边情况再计算答案。时间复杂度 $ O\left(2^{\frac{nm}{4}}\right) $ 。

结合算法二,期望得分 23 分。

(上述推导也解释了算法二的正确性。)

算法四

算法三最后一步明显可以不暴力。

长度为 4 的奇偶置换数量是相同的,所以对于每一种连边情况,贡献就是【每条边填上 0 1 的方案数】乘上【异或方程构图与这张图相同且边上全填 0 的方案数】。前者就是 $ 2^{n+m-\text{联通块个数}} $, 后者则是 $ F_0(k)^{\text{边数}} * F_1(k)^{n m – \text{边数}} $,其中 $ F_0 $, $ F_1 $ 分别是的有约束和无约束(即有重复) pair(四元组, 四元组) 个数。

令 $ dp_{i, j} $ 表示 $ n = i, m = j $ 时的答案。转移减法原理,复杂度 $ O(nm) $。总复杂度 $ O(n^2 m^2) $ 。

结合算法二,期望得分 45 分。

算法五

当 $ n $ 很小时,可以枚举 $ n $,对 $ m $ 那一维进行多项式优化。

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

结合算法二、四,期望得分 65 分。

算法六

把算法四贡献中的 $ F_1^{nm} $ 除掉(最后再乘),再令 $ F_2 = \frac{F_0}{F_1} $。

注意到算法四的本质,是对【所有 $ n-m $ 二分图的 $ F_2(k)^{\text{边数}} $】关于 $ n, m $ 的二元生成函数取 $ \ln $, 除以 $ 2 $ 再取 $ \exp $。

这其实就是开方。

关于二元多项式开方:

方法一:直接牛顿迭代,像一维一样。需要二元多项式乘法。时间复杂度 $ O(nm \log(n + m)) $, 常数巨大。主元并二维牛顿迭代同理。

方法二:主元 $ x[0, n) $,使用 $ O(n^2) $ 的暴力 $ \text{sqrt} $。看作一个关于多项式的 $ dp $,发现转移需要 $ O(n) $ 次 $ m $ 次多项式乘法。记录这些多项式在 $ [0, 2m) $ 的点值可以做到 $ O(n^2 m + n m \log(m)) = O(n^2 m) $。

虽然方法一复杂度较小,但其实被方法二吊打(也许真实原因是我常数太大 →_→)。 其实我一开始没有考虑方法二。多谢 _rqy 神仙提(diao)醒(da)(

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

在路上了

from peehs_moorhsum, 标程、题解 by peehs_moorhsum,数据、交互库 by whzzt

在路上了。

啊呜..这题其实是..IMO培训题魔改的

我对这题还比较满意。emmm..可能因为我觉得,算法竞赛更应当是思维竞赛,而非码力或知识竞赛?

而这大概算比较纯粹的思维题了?希望这种题在CNOI中能多一点

算法一

询问全图,用各种暴力找最长链

期望得分 0 分

(因为许多点问不了全图,能问到的图 $ n $ 太大了)

但由于我们造数据时,默认 $ n $ 为 $ \frac{3k}{2} $ 上取整,所以这个做法过了subtask 1

算法二

想到出题人很菜,你开始冷静分析

假如不考虑 $ \frac{3k}{2} \le n $ 的条件,那你可以一直调用find_longer_path,直到找到最长链

所以你会了一个多项式求最长链的算法!

尽管图有特殊性质,但这看上去很不科学?

所以你大胆猜结论,当 $ \frac{3k}{2} \le n $ 的时候,一定有长为 $ k $ 的同色链

于是你只读入前 $ \lceil \frac{3k}{2} \rceil $ 个点内部的连边,然后用dp求最长链,即可有理有据地通过subtask1

期望得分:13分

算法三

由于你是未来的图灵奖得主,你求最长链的水平十分高超

在算法二的基础上,加入一些奥妙重重的最长链算法(比如搜索),可以通过subtask2

期望得分:20分

算法四

考虑 $ n = 2k $ 的部分分

假如你能知道每条边的颜色,你可以用红边构造出一个生成森林,每个联通块是一棵dfs树,且满足$1$是$2$的父亲,$2$是$3$的父亲,……,$ k-1 $是$k$的父亲,$1$是根

如果有某棵树的深度大于等于$ k $,已经结束 (根节点深度为$0$)

否则将其他所有点按深度分成$r$组(未出现在树上视作深度为0),设为$S_1$到$S_r$,其中$S_i$的深度是$A_i$

则你考虑序列 ($S_1$中所有点),($A_1+1$号点),($S_2$中所有点),($A_2+1$)号点,……

由dfs树的性质,容易发现这是一条长度 >= k 的蓝色路径

可以通过subtask 3

期望得分:15分

算法五

结合算法三、四,可以得到40分

在算法四的基础上,假如有特殊的方法,不需要询问所有边便可构建出类似dfs树的东西,那么可以通过subtask 4

算法六

称 $2$ 到 $k - 1$ 为红点(注意,不是 1 到 k )

称 $k + 1$ 到 $3n$ 为蓝点

定义“交错路径”为一条全蓝的简单路径,满足第一个点和最后一个点都是蓝点,且红蓝点交错 (单个蓝点也算)

交错路径的大小为路径上蓝点数目

我们维护两条交错路径 $u, v$

初始时,各取一个蓝点即可

任何时刻,记$u, v$大小分别为$a, b$

(1)如果 $ 2(a + b) \ge k $

则 $1\ u\ k\ v$ 构成一个大小为$ 2 (a + b)$ 的蓝圈,称为 $s$

如果 $2 (a + b) > k$ 已经结束

否则 $2 (a + b) = k $

考虑$1$到$k$中相邻两个不属于$u, v$的点 $i, i + 1$

考察他们到$s$上同一蓝点r连边,容易构造出长为$ k $的蓝路 或者 $1 \ldots i\ r\ i + 1 \ldots k $的红路

这一部分的询问次数是 $ 2 $

(2)如果 $ 2(a + b) < k $

我们试图让 $ a + b $ 变得更大

利用 $ (a + b) < k / 2 $ 容易发现,存在 $ 1 \sim k $ 中的相邻两点,均未在$u\ v$中出现过 记作$i\ i + 1$

取不在$u\ v$里的蓝点 $r$ (由于$a + b + k < \frac{2k}{3}$,这可以做到)

一种暴力的想法是,检验 $r$ 到 $1,k$ 的连边

记$u\ v$的一个端点为$x\ y$,检验$r,x,y$到$i,i+1$的六条连边

如果有某个蓝点 $g$ 到 $i\ i + 1$连边都是红色 则 $1\ 2 \ldots i\ g\ i + 1 \ldots k $为长度为$k$的红色路径

故不妨 $r\ x\ y$ 到 $i\ i + 1 $ 均连至少一条蓝边 故有其中两个点向同一个点 $ s $ ($ s $ 为 $ i $ 或 $ i + 1 $)连蓝边

如果这两个点是 $x\ y$ 则 $u,v$ 可通过 $s$ 串联起来 取新的 $u$ 为串联后的路径,新的 $v$ 为 单点 $r$,则$ a + b $增加$1$

如果这两个点是 $r\ x$ 则 $r$ 可加入到 $u$ 中

如果这两个点是 $r\ y$ 则 $r$ 可加入到 $v$ 中

总询问次数是 $ 8 (k / 2 - 2) + 4 + 2 $

可以通过subtask 1 至 subtask 5

期望得分:70分

算法七

容易发现,算法六的瓶颈在于扩大u v链时询问过多

我们试图精细一些。

我们默认 $r$ 到 $1\ k$ 连边为蓝色,默认$r\ x\ y$到$i, i + 1$均连至少一条蓝边(求出最后的蓝圈时,检验一遍所有边均为蓝色即可)

先询问$x\ y$ 到 $i$ 的连边颜色

如果均为红色,将$u\ v$通过$i + 1$串联,取新的$v$为$r$即可

如果均为蓝色,将$u\ v$通过$i$串联,取新的$v$为$r$即可

这两种情况下,均只询问了两次。

如果一红一蓝,不妨$x$红 $y$蓝

我们询问$r$到$i + 1$的颜色

若为红色,将$r$ 通过 $i$ 与 $y$ 连在一起

若为蓝色,将$r$ 通过 $i + 1$ 与 $x$ 连在一起

这两种情况下均询问了三次,但蓝圈上均有一条边不用被验证

故总询问次数不超过 $k + (k / 2 - 2) * 2 + 2 = 2k - 2$,可以获得100分。

UOJ Round #18 公告

2019-08-08 20:40:39 By whzzt

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

这是 UOJ 第十八场 UOJ Round。由于这一届管理员贡献不出好的 idea,UOJ 已经很久很久没有比赛了 :(

本次 UOJ Round 的难度和以往的一些 UOJ Round 难度相近,欢迎大家来玩,来玩就能上分由于已经很久没有比赛了所以还希望大家互相转告一下 UOJ 活了(

公元 2016 年 8 月 11 日,中国选手马龙获得 2016 年里约奥运会乒乓球男子单打冠军。

2019 年 8 月 11 日,跳蚤国奥运会鸽王大赛经过数次延期后,如期举行。作为跳蚤国的全国最鸽跳蚤的码农同学,自然会为了捍卫这一宝座而继续奋斗。鸽了一个小时后,码农同学到达了赛场。然而,他仍然是他所有队友中最早到的。事实上,他所有的队友都鸽了,因此他只能独立面对接下来的挑战。

因此,本次 UR 将以码农接下来参赛的经历为主题。

出题人:bulijiojiodibulido, djq_cpp, peehs_moorhsum

这场成绩将计入 rating。

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

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

UPD: 比赛好像已经结束好几天了= =,恭喜前五名的选手!

  1. pink_rabbit
  2. supy
  3. JOHNKRAM
  4. Infleaking
  5. luoyuchu

话说…感觉这次的抱枕条件不太有趣啊,感觉已经没有有趣的想法了= =

import hashlib
s='每题罚时的秒数的乘积在模998244353意义下以3为底取离散对数后值最小的,如有多个取罚时最多的'
m=hashlib.sha256()
m.update(s.encode('utf-8'))
print(m.hexdigest())

a927266c42a71c44137bb33ebf86f392c9d90b9b0f9d872a02a752b52f9468c7

恭喜 supy 获得 uoj 抱枕!

Goodbye Wuxu 题解

2019-02-09 23:45:13 By whzzt

由于一些…我也不知道是什么原因吧,似乎 UOJ 现在干活的管理员只剩我和 AwD 了o(╥﹏╥)o,这次正好过年离 WC 比较近,我到家的时候离过年也没几天了,比赛这么鸽还是要道歉 = =

感谢本次救 UOJ 于题不全办不出比赛之中的各位出题人 laofu, matthew99, zhouyuyang, WuHongxun, Picks

特别感谢将 E 题从 WC 的课件中移到 UOJ 的比赛中的 Picks 老师,牺牲了 WC 第一课堂上大家冬眠的时间,换来了一个超有趣的 E 题!

同时感谢 AwD 一天写出约 1 sdn (1 sdn = 11.7KB, 关于这一单位的来源见【集训队作业2018】蜀道难) 代码的精彩表演!

接下来是这场比赛的题解,这次的 A 题比往常的 Goodbye Round 的 A 题更难一点,这是因为 ABC 三个题都觉得挺好的有点舍不得扔,在 A 前面再加一个题又和传统不太符合。一直担心大家 A 题会出现惨案,不过从比赛中大家通过了 40 人并且大多数人都拿到了可观的分数(>0)这一点来看还是比较成功的!

新年的拯救计划

from laofu, 标程、数据和题解 by whzzt

最早AC: ridiculos (0:14:21)

最短提交: luhong 提交代码

算法一

手玩 $ n = 5, 6 $ 即可通过第一个子任务,期望得分 17 分。

算法二

直接套用求最多边不相交生成树的方法(见李煜东“图连通性若干问题探讨.pptx”),时间复杂度 $ O(n^4) $,期望得分 27 分。

算法三

显然我们会发现构造出的树的数量不超过 $ \lfloor \frac{n}{2} \rfloor $,因为一棵树有 $ n - 1 $ 条边。

咦这个 A 题怎么这么难?咦怎么有个 Subtask 部分分这么多?肯定是用来平衡题目难度造成的平均分下降的,总之就是这个部分分肯定很水!

容易发现,当 $ n $ 是素数时,$ \forall 0 \le k < n, \exists 0, k, 2k, 3k \ldots (n - 1)k $ 在$ \bmod n $ 意义下互不相同。我们可以构造 $ \lfloor \frac{n}{2} \rfloor $ 棵树,第 $ i $ 棵树只考虑满足 $ |u - v| = k $ 或 $ |u - v| = n - k $ 的边 $ (u, v) $,这样我们可以构造出 $ \lfloor \frac{n}{2} \rfloor $ 棵树,达到上界。

期望得分 44 分,结合之前的算法可以获得更高分数。

算法四

我们尝试构造一种恰好为 $ \lfloor \frac{n}{2} \rfloor $ 的方案,这意味着当 $ n $ 是偶数时所有边都会被用上。

如何构造 $ \lfloor \frac{n}{2} \rfloor $ 棵树?可以尝试先构造一棵树 $ T_0 $。接下来对于 $ T_0 $ 中的每条边 $ (u, v) $,我们向 $ T_i $ 中添加边 $ ((u + i) \bmod n, (v + i) \bmod n) $。我们定义一条边 $ (u, v) (u < v) $ 的长度为 $ \min(v - u, u - v + n) $,那么在 $ T_0 $ 中一定恰好包含了 $ 2 $ 条长为 $ 1 $ 至 $ \frac{n}{2} - 1 $ 的边和一条长为 $ \frac{n}{2} $ 的边。

考虑提出那条长为 $ \frac{n}{2} $ 的边,不妨假设其端点为 $ 1 $ 和 $ \frac{n}{2} + 1 $,我们只要让 $ 1 $ 和 $ 2 $ 至 $ \frac{n}{2} $ 之间的点连边,$ \frac{n}{2} + 1 $ 和 $ \frac{n}{2} + 2 $ 至 $ n $ 之间的点连边即可。

当 $ n $ 是奇数,我们可以采用同样的构造,容易发现是合法的。

当然本题的构造方法有多种,一些不同的方法也可以通过 = =

新年的Dog划分

from matthew99, 标程和数据 by matthew99, 题解 by whzzt

最早AC: peehs_moorhsum (1:23:44)

算法一

注意到图是二分图时,若我们将图划分成两个非空部分 $ A $ 和 $ B $,只保留图中 $ A $ 和 $ B $ 之间的边并进行询问,一定有至少一组这样的 $ A $ 和 $ B $ 返回的结果是联通。

考虑返回值为联通的情况。不妨假设最终二分图两侧的点集分别为 $ S $ 和 $ T $,其中 $ S \cap A \ne \emptyset $,若 $ T \cap A \ne \emptyset $,那么 $ S \cap A $ 和 $ T \cap A $ 不可能联通。因此会有 $ T \cap A = \emptyset $,同理 $ S \cap B = \emptyset $,于是有 $ S = A, T = B $。

因此当图是二分图时,我们只要枚举点集进行询问即可。

询问次数 $ 2^n $,期望得分 13 分。

算法二

为了获得最终二分图的两部分,我们尝试获得原图的一棵生成树。

我们可以考虑尝试删掉二分图中所有的边,如果一条可能的边删除后连通性发生了改变,我们就保留这条边,否则删去这条边。最终图中一定会剩下恰好 $ n - 1 $ 条边,它们构成了一个生成树。

于是我们只要将生成树黑白染色就可以得到二分图的一个部分了。

询问次数 $ \frac{n(n - 1)}{2} $,期望得分 37 分。

算法三

刚刚的寻找生成树的方法实在是太暴力了,我们可以对刚刚的方法进行一些优化:二分查找下一次保留边会发生在什么时候。由于这样的事件只会发生 $ n - 1 $ 次,我们只需要进行这么多次二分。

注意到我们找到了原图的一个生成树,只靠这个生成树是可以让原图联通的。那么我们可以保留生成树上的边,删去其它连接二分图两侧的边。如果图不是二分图,那么图中一定存在环,于是一定存在剩余的某条树边删去后仍然连通。

每次二分需要 $ \log(n^2) = 2 \log n $ 左右次查询,因此询问次数 $ 2 n \log n $,期望得分 67 分。

算法四

为了去掉 2 的常数,我们需要将对边二分优化为对点二分。

考虑从 1 号点开始,使用 BFS 进行上述过程,就只要对点二分了。

询问次数 $ n \log n $,期望得分 100 分。

新年的小黄鸭

from zhouyuyang, 标程、数据和题解 by zhouyuyang

最早AC: supy (3:06:13)

算法负二

大胆猜想直接树剖答案最优。

获得$0-5$分好成绩。

算法负一

大胆猜想在子树size过大的时候可以钦定重儿子。

获得$0-20$分好成绩。

算法零

大胆猜想在子树深度和过大的时候可以钦定重儿子。

获得$0-20$分好成绩。

算法一

直接暴力枚举哪些是重边。

时间复杂度$O(2^n\times n^2)$或$O(2^n\times n)$

算法二

假设我们已经知道了你的轻重边划分方案$T$,考虑如何计算答案。

显然如果一条边是轻边我们直接把它扔进$f(x)$里是没有问题的。

如果遇到了轻边,那么在这个轻边父亲节点向上的重链长度显然不会改变,也可以扔进$f(x)$里面

设$h(x,v1,v2)$表示在$x$号节点,已经确定在$f(x)$里的权值为$v1$,向上的连续重链长度为$v2$,子树内的最优解。

转移直接枚举重儿子,并且更新当前状态。

时间复杂度$O(n^4)$或$O(n^3)$

空间复杂度$O(n^3)$

算法三

观察DP状态,我们发现我们可以使用某些技巧干掉$v1$这一维。

我们考虑在产生$v1$贡献的时候,直接在这个节点将他的贡献算进答案,而不是在子树上每个节点上计算答案。

这样子直接设$h(x,v2)$表示在$x$号节点,向上的连续重链长度为$v2$,子树内的最优解。

转移仍然直接枚举重儿子。

时间复杂度$O(n^2)$

空间复杂度$O(n^2)$

算法四

继续观察DP状态,我们发现我们可以尝试只存下来$log_2v2$的值,这样子状态就变成$O(nlogn)$了。

转移我们枚举在$x$所在重链上第一个满足$f$的值不同于他的父亲节点的点,或者是叶节点,设其为$y$

观察算法三中的DP转移方程,不难发现在钦定重儿子的时候转移方程形如$h(y,v2+1)+\Sigma h(x到y路径上所有的轻儿子,0)+自己的权值 \to h(x,v2)$

因为在转移的重链上的点$f(x)$相同,所以我们可以假设这些点有点权,为$v(x)=\sum h(x父亲除了x之外的所有儿子)+自己附带的权值$

此时转移方程就可以看成路径点权和加上$y$子树的权值(如果$y$不是叶节点,否则为$0$)

对于叶节点的情况,我们可以维护$logn$颗动态开点线段树维护深度在某一范围内的叶节点的点权和最大值。

对于非叶节点的情况,不难发现合法转移只有$O(nlogn)$种,直接找到所有可能出现的情况,暴力转移。

非叶节点的点权和可以在确定$dfn$序之后使用树状数组维护。

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

空间复杂度$O(n\log^2n)$

算法五

出题人卡内存怎么办???

考虑通过一些操作把$log_2v2$拆开,使得他在他的$1$代祖先,$2$代祖先,$\dots$ ,$2^k$代祖先的地方恰好被算一次。

此时我们每个点的点权就唯一了,线段树就只需要一颗了。

其于基本同算法四。

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

空间复杂度$O(n\log n)$

算法六

from: matthew99

算法四,五我听不懂怎么办?

考虑对于每一个节点x维护一个分段函数表示$f[x]$

我们可以发现分段函数的段数的上界是$O(子树大小\times \log n)$的。

直接启发式合并维护即可。

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

空间复杂度$O(n\log n)$

算法七

from: matthew99

在审题的时候@whzzt说分段函数段数$O(子树深度\times \log n)$的。

此时在算法六的基础上套长链剖分,暴力合并,时间复杂度可以做到$O(n\log n)$

但是因为出题人 zhouyuyang和审题人whzzt咕咕咕了,没有实现过这个算法,也没有想过算法细节。

时间复杂度$O(n\log n)​$

空间复杂度$O(n\log n)$

新年的族谱树

from WuHongXun, 标程和题解 by AwD, 数据 by whzzt

whzzt: (;´д`)ゞ因为懒得写 spj 加了个权值,为了让问题描述看起来更合理一点加了一大堆废话= = 似乎大家没怎么看懂的样子

算法一

枚举族谱树所有的形态,找一个字典序最大的输出来。

时间复杂度不明。

算法二

怎样的老家族集合是合法的?

最终选择的集合确定了一棵有根树,选出的集合作为有根树的子树,两两之间要么是包含的,要么是分离的。

要求字典序最大的方案,也就是要尽量选择权值大的老家族的集合。

按照套路,显然可以得到一个简单的贪心:沿权值降序依次考虑每个集合,若它与之前选择的集合没有冲突,则选择该集合。

一共有 $O(nk)$ 个集合,每次判断合法性的时间复杂度为 $O(n^2)$ 。

使用 bitset 可以将判断合法性的复杂度优化至 $O(\frac{n^2}{w})$

时间复杂度为 $O(n^3k)$ 或 $O(\frac{n^3k}{w})$。

算法三

在后文中,我们将会把一类有根树称作族谱树 —— 族谱树的叶子节点都是元素,非叶节点都是一个包含了其子树中的元素的集合,每个非叶节点至少有两个孩子。

由于族谱树它真的是一棵树,因此并不用依次检测当前集合 $S$ 与树上的所有集合是否有冲突 —— 当 $S$ 合法时,考虑族谱树上最小的包含它的集合 $T$, $T$ 的每个孩子 $W_i$ 要么是 $S$ 的子集,要么与 $S$ 分离,并且是 $S$ 子集的孩子的并恰好是 $S$。

于是就可以提高判断合法性的效率了:

首先,找到包含 $S$ 的最小集合 $T$ —— 找到 $S$ 中的任意一个节点 $a$,考虑节点 $a$ 到根的链,一定是一串 $S$ 包含的集合接着一串包含 $S$ 的集合,因此可以简单的二分出 $T$。

对于 $S$ 中的每个元素 $a$,找到是它祖先也是 $T$ 的孩子的集合。这些集合显然就是 $W_i$ 了,由于这些集合两两不交,因此只需要看看它们的大小之和是否为 $|S|$,就知道它们的并是否为 $S$ 了。

于是就可以在 $O(n \log n)$ 的时间复杂度下检测一个集合是否合法。(使用长链剖分可以做到 $O(n)$,然而并没有什么卵用)。

当合法的时候,大力重建族谱树。

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

算法四

在上一个算法中,第一步的时间复杂度可以做到 $O(\log n)$ —— 可以直接以集合大小作为关键字二分。瓶颈在第二步上。显然,通过枚举 $S$ 中每个元素的方法得到 $W_i$ 过于缓慢,我们需要更快的做法。

在静态的树上维护动态的树是很困难的,不妨在动态的树上维护静态的树。

不失一般性的假设 $S$ 来源于老族谱树 $a$ 上的子树 $b$ ,对于子树 $W_i$ ,如果 $W_i$ 是 $S$ 的子集,$W_i$ 中所有节点在树 $a$ 中的 LCA 就是节点 $b$ 的孩子了。显然,只有当所有 $W_i$ 要么是 $S$ 的子集要么与 $S$ 分离时,LCA 是节点 $b$ 的孩子的 $W_i$ 的大小之和才恰好为 $|S|$,不然一定会小于 $|S|$,因为那些不合法的元素并不会被统计到。我们可以通过这个来判断 $S$ 是否合法。

具体来说,对于每个族谱树中的集合 $T$,按子树的 LCA 的 DFS 序号,一共以 $k$ 种顺序维护 $T$ 的孩子。当询问老族谱树 $a$ 上子树 $b$ 构成的集合 $S$ 的合法性时,只需要先找到 $T$,再看看 LCA 是 $T$ 的孩子的大小之和是否为 $|S|$ 即可。这些孩子在第 $a$ 个顺序上是一个区间,二分找到这个区间即可。

于是检测一个集合是否合法的复杂度就降到了 $O(\log n)$。

瓶颈成了每次修改族谱树,理论上应该能做到 $O(nk)$。

时间复杂度为 $O(n^2k^2)$。(好像变慢了 …… )

算法五

考虑修改族谱树的过程 —— 我们只是增加了一个节点,并将该节点父节点的一些孩子移动给了它。这个操作在第 $a$ 个顺序上是很容易完成的,需要移动的孩子是个区间(就是算法四中判断合法性的区间),只需要将这个区间 split 出来就行了。然而对于其他顺序来说,需要移动的节点是无序的。

平衡树启发式合并 $n$ 个元素的时间复杂度是 $O(n \log n)$ 的,类似的,平衡树启发式分离 $n$ 个元素的时间复杂度也是 $O(n \log n)$ 的。于是可以直接跑个启发式分离 —— 如果需要移出来元素少于一半,则直接依次删除并把删掉的元素重新建一棵树,不然就依次删除不需要移出来的元素同样建棵树就行了。

这个东西实现出来就是 $k$ 棵 LCT 上套 splay。($k$ 棵 toptree ?)

插入节点的时候需要知道集合的 LCA 的序号,因此在 toptree 上还需要维护一个子树的 LCA。当然,这里并不需要强上一个 $O(1)$ LCA,可以仅仅维护子树 DFS 序的最小值与最大值。当真的需要 LCA 的序号时,再去通过最小值与最大值计算 LCA,这样常数应该会小一点 ?

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

为什么 $k$ 这么小?动态开空间多麻烦啊 ……

新年的A+C Problem

from Picks, 标程和数据 by whzzt, 题解 by Picks

本题中的模型其实是来源于量子计算的模型。题中可使用的门是三元可逆逻辑门,而在真实的量子计算中是Hilbert空间中的线性变换,其中可逆逻辑门可以在量子计算中实现。

题目的任务是求对于长度为l的输入整数a进行加常数c的可逆电路,其中可利用的资源有三类额外位:

  1. 泄露位:初始为0,输出可以为任意值的位。由于可逆运算中信息是守恒的,当输出为任意值时,输入的信息会泄露到这些额外位中。当有人获取了额外位的输出,是可能获得额外位的信息的。
  2. 干净位:初始为0,输出时也为0的位。这些位可以视为一个资源池,从中取出时是0,放回时也是0。
  3. 脏位:初始时不知,输出时需要还原为初始状态的位。这些位可以从系统的任意无关位置取出,在过程中利用完之后放回原位。

显然这三类额外位存在支配关系,泄露位的利用严格容易于干净位,干净位的利用严格容易于脏位。

子任务一、二

有许多泄露位可以利用时,有很多种做法都可以解决这个问题。

最简单的方法是从低到高枚举每一位,用一位存下当前的进位。但由于 $ 0 + 1 = 1 + 0 $ 会造成不是一个一一映射,我们可以利用一个泄露位(值一定是0)来解决这个问题。

根据实现的不同需要 l 左右个泄露位。

子任务三

当我们有 $ 2l $ 个干净位可以利用时,我们考虑实现一个加法器 $ (A,B,q)→(A+B+q,B,q) $,其中 $ q $ 是一个干净位,我们用来向后传递信息。

注意到我们无法绕开进位,我们不妨使用 $ q $ 位置来传递进位信息。对于 $ A,B $ 的对应位 $ a,b $ ,我们设计可逆门 $ \mathrm{MAJORITY}:(i,j,k)\rightarrow(i\oplus k,j\oplus k,\mathrm{MAJ}(i,j,k))$,其中 $\mathrm{MAJ}(i,j,k)$ 表示的是 $ i,j,k $ 中存在至少两个的逻辑值,逻辑关系为 $ \mathrm{MAJ}(i,j,k)=(i\ \mathrm{and}\ j)\mathrm{or}(i\ \mathrm{and}\ k)\mathrm{or}(j\ \mathrm{and}\ k) $,可以验证这是一个可逆门。

同时,当我们用 $a,b,q$ 表达当前位与进位时,它们的多数值即为进位。使用一个依此从低位到高位的操作序列,我们可以在过程中获得临时进位,并将临时进位信息递归传给后方变量操作。当递归结束时,我们可以将之前的门取反(即输入输出对调)来将操作取消,额外添加 $ \mathrm{TRIXOR} $ 门 $(i,j,k)\rightarrow (i\oplus j\oplus k,j,k) $,来得到当前位的答案。

即如下过程:

fixpoint adder(a[i], b[i], q) :=
    MAJORITY(a[i], b[i], q);
    adder(a[i+1], b[i + 1], q);
    reverse(MAJORITY)(a[i], b[i], q);
    TRIXOR(a[i], b[i], q).

回到问题,我们一开始将常数 $ c $ 写入变量 $ b $ 中,调用加法器,再将变量 $ b $ 中的 $ c $ 擦除即可。

子任务四

此时我们只有 $ l $ 个额外干净位,不过好在 $ c = 1 $,我们仍能比较简单地解决。

在上一个子任务中,我们发现最关键的问题即是进位问题,我们考虑如何比较好地解决进位问题。注意到 $ c=1 $,则第 $ i $ 位的进位实际上是输入变量前 $ i $ 位进行与操作的结果。我们只需要利用额外的 $ l $ 个干净位依此计算逻辑与 $ (i,j,k)\rightarrow(i,j,k\oplus(i\ \mathrm{and}\ j)) $ 即可。实际上我们只需要 $ l-2 $ 个额外位来存储每一位的进位信息,因为最后一位无作用,第一位无需存储。计算出进位之后我们可以利用 $(i,k)→(i\oplus k,k)$ 来获得答案,之后将计算逻辑与的过程取消掉即可。

子任务五

该子任务中我们仅有 $ l $ 个额外脏位,此时难度显著上升了。

这时我们需要利用一个补码的性质:在模 $ 2^l $ 的意义下,整数 $ b $ 逐位取反的结果即是 $-b-1$。

我们利用一个技巧来处理加 $ 1 $ 操作。考虑加法器 $ (A,B,q)→(A+B+q,B,q) $,如果我们将 $ B $ 取反,我们可以计算得到 $ (A,B,q)\rightarrow (A-B-1+q,-B-1,q) $。将之串在一起并将B还原,可以得到 $ (A,B,q) \rightarrow (A+2q-1,B,q) $ 过程。但 $ q $ 同样是脏位,如果 $ q=1 $,则我们计算完成。如果 $ q=0 $,我们实际上计算了 $ A-1 $ 的结果,那此时我们预先将 $ A $ 取反,在其后再次将 $ A $ 取反,则实际完成的仍是 $ A+1 $ 的计算。那么我们只需要在上述过程前后均加上由 $ q $ 操控的 $ A $ 取反过程。对应到位上即是门 $ (a,q)\rightarrow (a\oplus q\oplus 1,q) $。

粗略观察,此时我们使用了 $ l+1 $个额外脏位。但是注意到 $ B $ 的最高位其实可以不使用,将其取出用作进位 $ q $ 即可。

子任务六

现在我们仅有一个额外位了。我们先考虑一些可能的子任务。

你需要对利用计算过程 $P:(A,y)\rightarrow(A,y\oplus f(A))$ 的一位结果 $f(A)$ 来控制一个对 $B$ 变量的操作 $O:B\rightarrow g(B)$,其中$g(g(B))=B$,但除 $A,B$ 外你仅有 $ 1 $ 个额外脏位 $ q $ 。

我们可以构造如下过程:

Definition dirtyControl(P, O, A, B, q) :=
    controlled(O)(q, B);
    P(A, q);
    controlled(O)(q, B);
    reverse(P)(A, q).

注意到当 $ f(A) $ 是 $ 1 $ 时,$ \mathrm{controlled}(O)(q, B) $ 仅作用了一次。反之,则作用了 $ 0 $ 次或 $ 2 $ 次,均不影响变量 $ B $ 的值。

当你有 $l$ 个额外脏位,还有一个输入位 $p$ 存有 $0$ 或者 $1$,你需要计算 $ a + p $。

这个与子任务五非常相似。我们提供两种方法来完成。

一种是非常粗暴的方法,即使用 $ p $ 作为控制变量去控制是否进行子任务 $ 5 $ 的加 $ 1 $ 操作。只需要将子任务 $ 5 $ 中的所有门额外加一个控制变量 $ p $,当且仅当 $ p=1 $ 时执行门操作即可。对于二元门,扩展成三元门是容易的。对于三元门,添加额外控制变量变为四元门之后需要将三元门进行分解。分解方法是取一个额外的脏位(随意找一个无关位即可),将前两位的信息利用小问题1中的方法存储在脏位中,再将后两位与脏位一起运算得到结果。

另一种是灵巧一点的方法,我们考虑子任务五中 $ 1 $ 的来源,实际上是 $ B $ 的取反操作。那我们使用输入位 $ p $ 控制 $ B $ 的取反操作,当 $ p = 1 $ 时才进行该取反即可。

当你有 $ l-1 $ 个额外脏位 $ Q $ ,你要获得 $ a+c $ 的最高进位,输出在干净位 $ s $ 中。

还是利用小问题1中的方法,我们用第 $ i $ 个脏位来储存第 $ i $ 个进位的信息(即若第 $ i $ 位进位为1,则对应脏位取反)。逻辑形式为:

Fixpoint dirtyAdd(a[i], c[i], q[i]) :=
    If c[i]=1 then ( (controlled(NOT)(a[i], q[i])); NOT a[i]. )
    controlled(controlled(NOT))(q[i-1], a[i], q[i]);
    dirtyAdd(a[i-1], c[i-1], q[i-1]);
    controlled(controlled(NOT))(q[i-1], a[i], q[i]);

即当更低位的脏位不变时,该位进位由 $ a[i], c[i] $ 控制,否则联合控制。同样的,最高位不需要存储进位,故只需要 $ l-1 $ 个脏位。注意最低位和最高位需要特殊处理,最低位不需要低位进位的控制,最高位运算的结果存入 $ s $ 中。

现在我们利用一个额外干净位 $ s $ 来计算 $ a+c $。首先我们将输入 $ a $ 均分成两半 $ p,q $,若总长度是奇数则使 $ p $ 比 $ q $ 长。

我们先利用小问题3,视 $ q $ 为脏位,计算出 $ p $ 部分加上对应的部分 $ c $,结果的最高进位,存储在额外干净位 $ s $ 中。然后我们利用小问题2,视 $ p $ 为脏位,将 $ s $ 中的值加到 $ q $ 中去。最后重复第一步,将 $ s $ 中信息擦除。此时我们发现,输入的两部分不再产生关联了,只需要递归下去分别解决 $ p $ 和 $ q $ 的计算问题即可。

子任务七

此时额外位是一个脏位g。我们再次利用小问题1中的方法来解决这个问题。 最终的方法为:

Fixpoint addC(a, g) :=
    Let p, q as described;
    P2(g, q, p);
    controlled(allNOT)(g, q);
    P3(g, p, q);
    P2(g, q, p);
    P3(g, p, q);
    controlled(allNOT)(g, q);
    addC(p, g);
    addC(q, g);

扩展

如果我们不局限于三元逻辑门,而是可以使用量子门,则额外的一个脏位也是可以省去的。参见参考资料【3】。

参考资料

  1. Craig Gidney. Constructing Large Increment Gates. http://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html
  2. Thomas Häner, Martin Roetteler, Krysta M. Svore. Factoring using 2n+2 qubits with Toffoli based modular multiplication.
  3. Craig Gidney. Trouble Adding Constants into Qubit Registers. http://algassert.com/post/1701

Goodbye Wuxu

2019-02-04 23:54:15 By whzzt

再见,戊戌!

转眼间 2018 年也已经过去了,在去年的大战中 SingleDog 击败了 AlphaGo,夺回了狗群的控制权。然而它们并没有达成主要目标——狗群的公母比仍然堪忧!但没有了 AlphaGo 这样的共同敌人,狗群已经难以拧成一股绳,也丧失了再进行改革的能力。

然而,狗群面临着更大的挑战:由于没有共同的敌人,狗群社会欣欣向荣,社会福利不断提升。然而众多 SingleDog 因为无所事事逐渐变懒,已经变成 SinglePig 了,而足不出户的 SinglePig 们甚至丧失了辨别种群的能力!

新的一年即将来临,狗群中的战斗狗——DoubleDog 们正力主改变这一现状!然而 SinglePig 们足不出户,因此 DoubleDog 们需要主动出击!为了改变狗群的现状,DoubleDog 需要再次请求它们的跳蚤朋友的帮助!

这场变革将会在大年初四的下午 13:00 到 18:00 正式启动!

即 2 月 8 日下午 13:00 到 18:00 会举办 Goodbye Wuxu 比赛,比赛时间5个小时,一共五题,祝大家玩的开心!

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

赛制采取OI赛制,这也意味着只计入最后一次提交结果。这场比赛有很多有意思的题目,大家一定不要错过!

出题人:laofu, matthew99, zhouyuyang, WuHongxun, Picks

这场成绩将计入rating。

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

UPD1: 比赛结束啦,恭喜前五名的选手!

  1. peehs_moorhsum
  2. supy
  3. fjzzq2002
  4. tqyaaaaang
  5. zx2003
import hashlib
s='罚时的秒数模2019的值最大的,如有多个取得分最高的,如仍有多个取罚时最小的'
m=hashlib.sha256()
m.update(s.encode('utf-8'))
print(m.hexdigest())

27c87d04e69de78a6be9a0889f4530547cbdce78a7952ce2c6f02248dd503853

恭喜 Bartholomew 获得 uoj 抱枕!

UPD2: 题解

UOJ Easy Round #8 题解

2018-12-22 22:30:34 By whzzt

似乎大家反映觉得是 UOJ Extremely Hard Round? 其实出题的时候是觉得没有 UR 难所以叫 UER,不过得分分布好像打出了 UR 风范(

打雪仗

出题人 matthew99, whzzt, vfleaking

数据和题解 whzzt

咦为什么有三个出题人呢?其实是 myy 在群里扔了个 idea 我们觉得太简单了就稍微改了改,vfk为了方便选手通信又改了改,就变成现在这样了。看起来大家做这题还是很开心的。

算法零

提交样例程序,似乎通过了第一个测试点。

期望得分 $ 0 $ 分。

算法一

咦我们有很多雪球!那我们直接让小 $ A $ 把整个串 $ S $ 传给小 $ B $ 就好啦!

通信次数 $ 2n $,期望得分 $ 20 $ 分。

算法二

小 $ A $ 和小 $ B $ 商量了一下,小 $ B $ 倾向于算法一——自己连雪球都不用扔。小 $ A $ 不服:你闲着也是闲着,不如给我点有用的信息?

小 $ B $ 想了想觉得小 $ A $ 没必要在那些混淆视听的位置上浪费雪球,于是他告诉小 $ A $:“你扔第 $ i $ 个雪球给我时,我告诉你下一次是扔第 $ i + 1 $ 个雪球还是第 $ i + 2 $ 个雪球!”小 $ A $ 一想觉得有理:你和我扔一样多的雪球,随后还要和小 $ C $ 大战,这账怎么算都是赚了。于是小 $ A $ 也爽快地同意了。

这样做要通信多少次呢?

咦我们发现这个方案非常优!容易发现,如果最后不被选择的段中有 $ a $ 个长度为奇数的段,我们花费的通信次数就是 $ \frac{3n - a}{2} $。

不幸的是,小 $ C $ 可能恰好选择了 $ n + 1 $ 至 $ 2n $ 这 $ n $ 个下标,这时我们就得花 $ \frac{3}{2} n $ 轮通信才能解决问题了。

算法三

小 $ A $ 和小 $ B $ 很快感受到了被小 $ C $ 支配的恐惧,为了摆脱这样的恐惧,小 $ A $ 和小 $ B $ 决定先约定好一个随机种子,然后将整个序列按照这个随机种子随机打乱!这样小 $ C $ 的编号顺序就不会影响到我们的通信次数了。

这时的期望通信次数是 $ \frac{4n}{3} $ 的,因为奇数段差不多有 $ \frac{n}{3} $ 个。实现时我们可以让 $ B $ 找到一个合适的随机种子传给 $ A $,由于不会严谨证明这个方法并没有作为 std 。期望得分 $ 100 $ 分。

算法四

from vfleaking

考虑将原本的01串等分成三份长度约为 $ \frac{2}{3} n $ 的段,那么必然有一段中对小 $ B $ 有用的元素不少于一半。我们让小 $ B $ 告诉小 $ A $ 在另两段中自己需要知道的位置,小 $ A $ 将这一段整段和其他段中小 $ B $ 需要的元素扔给 $ B $ 就可以了!

显然这样做小 $ A $ 和小 $ B $ 都不会传递超过 $ \frac{4}{3} n $ 位的信息,期望得分 100 分。

算法五

from vfleaking, WuHongxun

不妨考虑只进行一次通信,若小 $ B $ 给小 $ A $ 发送了 $ x $ 个 bit,那么必定有 $ \binom{2n}{n} 2^{-x} $ 个下标集合是无法被区分的,于是小 $ A $ 只能将这些下标集合的并集发给小 $ B $ ,我们不允许消耗超过 $ x $ 个 bit,不妨设 $ x = \alpha n $ ,于是有

$$ \binom{\alpha n}{n} 2^{\alpha n} \ge \binom{2n}{n} $$

即有

$$ \alpha \ln \alpha - (\alpha - 1) \ln (\alpha - 1) + \alpha \ln 2 \ge 2 \ln 2 + o(1) $$

我们发现满足条件的最小 $ \alpha = 1.20559733891046 + o(1) $ ,于是我们得到在只有一次传输时确定性算法的下界。

我们有一个概率算法可以达到这个界:考虑随机选择这样的 $ 2^{\alpha n} $ 个大小为 $ \alpha n $ 的集合,小 $ B $ 将包含当前下标集合的最小集合发给小 $ A $ ,那么我们有极高的概率能够使得小 $ B $ 得到想要的答案。

不过在本题中由于时间复杂度太高,无法实现。

雪灾与外卖

出题人 laofu

数据 whzzt

题解 laofu

算法一

爆搜,没啥好说的。

算法二

这是一个二分图匹配的模型。

可以发现一个显然的性质,餐馆和送餐员的匹配是不会相交的,即对于任意 $1 \le a_1 < a_2 \le n$,$1 \le b_1 < b_2 \le m$ 我们有 $$|x_{a_1}-y_{b_1}|+|x_{a_2}-y_{b_2}|\le|x_{a_1}-y_{b_2}|+|x_{a_2}-y_{b_1}|$$

这样就给我们提供了一个DP的顺序。

用$f_{i,j}$表示把标号$1 \ldots i$的送餐员匹配标号$1 \ldots j$的餐馆的最小总代价。转移时枚举第$j$个餐馆匹配了几名送餐员,则转移式为:$f_{i,j}=\min_{k=0}^{\min(c_{j},i)}f_{i-k,j-1}+w_{j}\times k+\sum_{t=1}^{k}|x_{i+1-t}-y_{j}|$。复杂度$O(n^2m)$。

算法三

使用单调队列优化上述DP即可在$O(nm)$内完成。

算法四

保证了餐馆的总容量,且 $ w_i = 0 $ ,我们可以看成若干个容量为$1$的餐馆。

把餐馆和送餐员放在一起按照坐标排序,从前往后考虑,当考虑到一名送餐员$i$时,我们先让它与前面的一个空的餐馆$j$匹配。费用为$x_i-y_j$,那么我们就是要找一个最小的$-y_j$。(如果没有空的餐馆我们可以视为在$-\infty$处有无穷个餐馆)。

匹配完之后,我们可能进行调整,把这名送餐员改为匹配后面的餐馆。那么我们就可以撤销这次操作,然后把这名送餐员当做没有使用过,那么往堆中丢入$−(x_i-x_j) − x_i$,即减去之前这组匹配的贡献,然后寻找新匹配。 扫到餐馆时也类似,先可以匹配一名送餐员,然后可以撤销这组匹配,寻找新匹配。

对所有餐馆和送餐员分别建一个堆来维护这个操作。复杂度$O((n+\sum c_i)\log(n+\sum c_i))$ 。

算法五

咋一看,是不是直接套之前的模型就好了呢?然而有一个问题:如果送餐员$a$匹配了餐馆$b(x_a < y_b)$,

那么,接下来$a$可能反悔去匹配餐馆$c(x_a < y_c)$,$b$也可能反悔去匹配送餐员$d(y_b < x_d)$。

比如,如果送餐员在坐标$1$处,两个餐馆在坐标$2,3$处,$w$分别为$100,0$,则,扫到第一个餐馆时,会把送餐员和第一个餐馆进行匹配。之后扫到第二个餐馆时,会把之前的匹配给撤销,增加一组送餐员和第二个餐馆的匹配。

所以我们既要能够支持$a$的反悔,也要能够支持$b$的反悔。那么每进行一组匹配时,要往两个堆中分别添加反悔的操作。

复杂度仍然是$O((n+\sum c_i)\log(n+\sum c_i))$

算法六

当餐馆的总容量无限制时,不能再把每个餐馆拆成一个一个单位容量的了。

考虑这样一个简化版的问题:

1.每名送餐员只能匹配在它左边的餐馆。我们求出最佳匹配的餐馆集合$S$。

2.每名送餐员只能匹配在它右边的餐馆。我们求出最佳匹配的餐馆集合$T$。

然后有一个结论:当 $ w_i = 0 $ 时,原问题的最优解$U$满足$U \subseteq S \cup T$

证明:我们对于数轴上任意一条边$e​$,令匹配$T​$下从左向右经过这条边的送餐员数量减去从右到左经过这条边的送餐员数量为$f(T,e)​$,匹配$U​$下从左向右经过这条边的送餐员数量减去从右到左经过这条边的送餐员数量为$f(U,e)​$。则$f(U,e) \le f(T,e)​$。(如果$f(U,e)>f(T,e)​$对于子问题$2​$而言,送餐员只能往右走,所以$f(T,e)​$可以调整到$f(U,e)​$,$U​$是无限制的,那么$f(U,e)​$也可以调整到$f(T,e)​$,那么显然两种方案可以都变成代价小的方案)。那么,对于一个餐馆而言,从$S​$到$U​$,左边匹配它的送餐员不会变多,从$T​$到$U​$,右边匹配它的送餐员也不会变多,所以上述结论成立。

而$|S \cup T|\le 2n$,套用算法四解决即可。

算法七

我们试想,能不能继续沿用subtask6的那个贪心,从而把问题从subtask7转化为subtask5呢?

然而有这样一个反例:两名送餐员中间夹着两个餐馆,其中一个餐馆$w$很小,容量为$1$,另一个$w$很大。在subtask6的两个子问题中,$S \cup T$都只会包含那一个$w$小的餐馆。这样我们转化之后就从有解变成了无解。

为什么呢?因为我们在subtask6中证明的时候,在子问题$2$中,对于任意一个餐馆$i$(这里是把餐馆和送餐员按坐标排序放在一起考虑)如果$g(T,i-1 \rightarrow i) \ge c_i$,则$S \cup T$会包含第$i$个云的所有容量,否则这$g(T,i-1 \rightarrow i)$名送餐员肯定都会匹配餐馆$i$。而现在不一定了,因为餐馆带了权,可能左边的送餐员会选择在$i$右边的权值更小的餐馆。

不过我们可以加一点小技巧:

1.在子任务六的子问题$1$的基础上,把已经匹配的那些餐馆$S$的容量给扣除,然后求一遍子问题$2$的解$S'$。

2.在子任务六的子问题$2$的基础上,把已经匹配的那些餐馆$T$的容量给扣除,然后求一遍子问题$1$的解$T'$。

猜想:原问题的最优解$U \subseteq S \cup S' \cup T \cup T'$

关于该猜想,我们并没能给出证明或反例(基于对拍认为该猜想有较大概率正确)。如果能在WC之前证明做法的正确性或者举出反例的同学可以在WC中获得出题人提供的小礼品一份。

算法八

考虑算法五的过程。在过程中我们维护了两个堆,一个维护待匹配的送餐员,一个维护待匹配的餐馆。之前复杂度不对的原因是送餐员堆的复杂度没有保证,因为一个餐馆匹配了一名送餐员之后,这名送餐员可能反悔,所以这名送餐员又会重新丢入送餐员堆中。

但是注意到,对于送餐员 $ x, y $ 和餐馆 $ a, b $ 来说,若 $ x < y < a < b $ ,那么当送餐员x和送餐员y现在匹配了餐馆$a$时,题它们两个往堆中丢的元素都是$ -x_a-w_a $,因为$match(y,b)-match(y,a)=match(x,b)-match(x,a)$,也就是说每次餐馆匹配了若干名送餐员之后,往送餐员堆中丢的东西都是等权的。因此我们只要丢一次就好了,这样复杂度就是正确的了,时间复杂度为 $ O(n \log n) $。

插播小广告:欢迎大家来听WC2019清新小课堂:模拟费用流问题。

许愿树和圣诞树

出题人、数据和题解 zx2003

算法一

直接模拟题意,每次有操作三的时候暴力dfs整棵树。

时间复杂度为$O(n^2)$,可以通过第一个数据集。

算法二

每次有操作三的重新dfs获得先序遍历太暴力了,考虑一些简单的优化。

我们在修改操作的时候顺便维护一下子树大小,然后每次操作三时就在树上二分。

这样单次复杂度就是$O(深度)$。

当数据随机时平均复杂度为$O(n\log n)$,可以通过前两个数据集。

算法三

让我们思考一下,对于一棵二叉搜索树,在中序遍历已知的时候,我们还知道哪些信息,就可以唯一地确定它的形态呢?

根据操作三的提示,我们容易想到直接维护树的先序遍历。

通过简单的观察,我们可以发现,当一个点$x$单旋到根的时候,所有权值比它小的点都在它的左子树,权值比它大的点都在右子树。

并且对于任意两个小于$x$的点,它们的在先序遍历里的相对位置保持不变。

根据这个性质,我们可以定义“段”为权值为区间$[l,r]$的节点,按照原树中先序遍历的相对顺序,所构成的新树。

对于子任务三,我们考虑对时间分块,每过一段时间就暴力重构整棵树的先序遍历。

然后我们暴力维护“段”构成的树结构即可。

复杂度$O(n\sqrt n)$

这个做法可拓展性有点差。

如果一定要拓展,那么就要用到后面的性质,然后效果相当于给后面的做法强行套上对时间分块。

算法四

让我们再思考一下,对于二叉搜索树,还有哪些信息可以用来辅助确定它的形态呢?

我们联想到了treap,或者说笛卡尔树。

我们可以给每一个节点赋一个键值,这样,上旋操作就等价于将键值调大至一个合适的值。

对于子任务三,由于每次都是上旋为根节点的儿子,所以每次可以轻易计算键值应该调为多少。

最后求遍序列的笛卡尔树即可。

时间复杂度为$O(n)$,可以通过子任务三。

算法五

让我们思考一下一个点在笛卡尔树里的父亲是什么。

或者更一般化,一个点在笛卡尔树里的祖先是什么。

冷静分析一下,可以证明,一个点在笛卡尔树里的祖先就是这个位置对应的前缀单调栈和后缀单调缀。

然后,对于子任务四,我们只要使用线段树简单维护每个点每个时刻的键值。

然后每次查询一个点的父亲时,就找出在序列中该点的前面第一个和后面第一个键值比它大的点,取键值较小者即可。

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

算法六

首先,由于每次不一定单旋到根,所以我们需要一个动态标号法,具体可以参考2013年陈立杰的集训队论文。

当然,由于本题不强在,所以我们可以离线后用个链表来维护。

然后对于前后缀单调栈的维护,这是个经典问题。

具体方法是对于线段树的某个节点,update的时候,用右儿子的最大值在左儿子的子树里二分,以计算左儿子的单调栈有多少被弹掉了。

这样就可以维护前后缀单调栈的长度。

至于询问第$k$级祖先,我们可以二分答案后再在前后缀的单调栈上查询。

直接写时$O(n\log^3n)$的,实际上可以用点小技巧优化到$O(n\log^2n)$的。

这样就可以通过子任务五了。

算法七

借助外界信息来维护树形态都不够优美。

实际上树的形态是可以直接维护的。

观察到如果是连续的三点共线的单旋,树的形态改变是很小的,直接把旋转的点提根即可。(HNOI2017单旋)

继续观察,发现一个点上旋的时候,树的形态变化大概是把这个点到根的左链和右链分别合并后作为点$x$的左右儿子。

并且,((这个点,该点的父亲,该点的祖先)三点不共线)的单旋次数是很少的。

可以证明是均摊$O(\log n)$。

证明思路是,在splay的复杂度证明里,每次如果((这个点,该点的父亲,该点的祖先)三点共线),那么把单旋代价(1+势能变化)中的1给扔掉。

现在问题就变成了,如何$O(拐点次数 * poly(\log n))$来维护。

考虑直接用LCT维护整棵树,上旋x->y的时候,就提取出$x$到$y$的路径。

然后通过在splay上二分来将x到y的路径分割成若干个权值单调的连续段。

将这些连续段分别拆开来后,按照一定顺序合并起来即可。

询问的时候在上LCT简单二分就行了。

复杂度直接算是$O(n\log^2n)$的。 但实验表明更像是$O(n\log n)$,可能可以通过一些高超的技巧来分析吧。

whzzt Avatar