UOJ Logo WuHongxun的博客

博客

UOJ Round #17 题解

2018-03-18 22:58:56 By WuHongxun

滑稽树上滑稽果

By jiry_2,数据、题解By WuHongxun

写题解之前,我们先来回顾一下上次比赛的A题题解:

这道题可能并没有那么有趣..本来有一道很棒的 A,但是比赛前突然被发现是个假题..然后就临时出了这么个题..感觉送送分还是不错的。

emm 懂我意思吧?

如果看到题面里大大的滑稽还没有察觉事情不太对...请允悲...

子任务一

既然 $n$ 那么小,我们直接枚举每个点的父亲!

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

子任务二

保证是一条链了,我们就只要枚举排列了!

冷静一下马上就会意识到,答案一定是一条链。这个部分分肯定是出题人用来提示大家冷静一下的!

时间复杂度 $O(n!)$。

子任务三

保证滑稽值的字典序最小?那就等于是每次枚举一个和当前的滑稽值and起来最小的值,然后把他加到后面。

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

子任务四

把相同的位拿出来,这些位要么一定是每次没贡献,要么一定是每次有贡献。

那么剩下的位,每次一定会减去一位,从而最多只会用$O(log a)$次就减到0了,每次暴力找最小的就好了。

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

子任务五

chat

出题人给了一个部分分是这个贪心的过程,我们睿(ruo)智(zhi)的分析一下,这个做法一定是错的!

事实上的确是希望考验大家独立思考、小心求证的能力。

我们一样先把每个数都一样的那些位拿出来,剩下的位我们等于是希望尽快把他们变成$0$。

这可以用一个dp来实现,$f[S]$表示$S$集合内的位为1的时候,想要变成$0$还需要多少代价。

dp转移就是每次枚举一个$a[i]$,$f[S] = min(f[S], f[S \& a[i]] + (S \& a[i]))$。

时间复杂度 $O(na)$。

子任务六

我们可以每次不枚举一个$a[i]$,而是枚举一个子集$T$,强制把这个子集$T$变成$0$。

现在的问题就是,判断有没有一个数他和$T$,and起来是0。

这非常好做,只需要每次$cnt[i] |= cnt[i | (2^j)]$,从每个比$i$多一个$0$的位置转移就好了。

事实上dp的时候,我们可以用贪心得到的解来进行剪枝,所以是不卡常数的。

时间复杂度 $O(a^{log_2 3}) = O(a^{1.58})$

滑稽树下你和我

By picks,数据、题解By Scape

算法一

直接输出两起始点距离即可。

期望得分$5$分。

算法二

考虑"保证存在最优方案,在任意时刻至少有一端点位于树的某结点上"这个性质。

我们先考虑二分答案,显然可以设计一个dp即为$f[i][j]$表示是否存在某种方案使得最终一个点在点$i$,一个点在点$j$。直接按照定义转移即可,时间复杂度$O(n^2logn)$

期望得分$15$分。结合算法一可获得$20$分。

算法三

同样我们先考虑二分答案,看答案是否能$\le v$。

我们考虑一条这样的性质。对于两个状态,两个点所在的边都相同,并且两个状态的两点间距离是$\le v$的,那么这两个状态是两两可达的。因为我们考虑是把其中某一条直线摆平,那么另外一条直线肯定是单调的。

那么我们就可以依此设计状态,令$f[i][j]$表示是否存在某种方案使得一个点在点$i$上,一个点在边$j$上距离点$i$最近的那个点上。那么$f[i][j]$为$1$当且仅当点$i$到边$j$的最短距离$\le v$且存在某个$f[k][x]$为$1$,其中$k$是$j$的某个端点,$x$是某个以$i$为端点的边,或存在某个$f[t][j]$为$1$,其中$t$与$i$有边相连。直接BFS转移就可以了。

因为我写完这个东西已经是早上凌晨三点了,所以我当时就认为这个算法是$O(n^3logn)$的,这就是$n\le 200$这个Subtask的由来。(笑

我们仔细分析一下,$f[i][j]$的转移复杂度显然是$O(i的度数)$的。那么加起来的转移复杂度总和显然是$O(n^2)$的,所以整个算法复杂度是$O(n^2logn)$的,你也可以选择不二分答案而是类似最短路那样去做,但还是要sort或者用堆维护,复杂度不变。

期望得分$100$分。

滑稽树前做游戏

By jiry_2

算法一

如果你做过 这个题,你就肯定知道菊花树的情况下答案就是 $\frac{1}{2} + \frac{n-1}{n}$。用快速幂求个逆元就可以了。

期望得分 $10$ 分。

算法二

$n = 4$ 的本质不同的图只有 $11$ 种,如果你有高超的手算水平,相信你可以算出所有 $n \leq 4$ 的图的答案,然后打表。

结合算法一期望得分 $30$ 分。

算法三

这题据我所知有很多种复杂度较高的 DP 算法可以通过 $n \leq 10$ 的数据,但是都没有标算简洁优美,这儿就不进行介绍了。

和大部分期望题一样,令 $g(t) = Pr[f(x) \leq t]$,那么答案显然就是 $2 - \int_{0}^2 g(t) \text{d}t$,因此我们只需要求出函数 $g(t)$,并做一次积分即可。

我们把题目的输入看做一张 $n$ 个点 $m$ 条边的无向图 $G$,那么 $g(t)$ 是一个关于 $G$ 的函数。

定义函数 $h(G,y,t)$,表示在无向图 $G$ 中,所有顶点权值的最大值小于等于 $y$,答案小于等于 $t$ 的概率,并且我们限制这个函数的定义域为 $\frac{t}{2} \leq y \leq \min(1,t)$。现在我们来考虑如何计算得到 $h(G,y,t)$:

  1. 如果所有点的权值都小于等于 $\frac{t}{2}$,那么必定满足顶点权值最大值小于等于 $y$,因此此时的概率为 $(\frac{t}{2})^n$(令 $G$ 的顶点个数为 $n$)。

  2. 如果至少有一个点的权值大于 $\frac{t}{2}$,我们枚举权值最大的点 $i$,设它的权值为 $w$。考虑所有与 $i$ 相邻的点 $j$,所有 $j$ 的出边中,权值最大的就是边 $(i,j)$ 了,因此 $j$ 的权值应当小于等于 $t-w$(又 $w>\frac{t}{2}$,因此不会和其他限制导出矛盾)。我们删去第 $i$ 个点和所有相邻点,得到了图 $G_i$,那么 $G_i$ 中的点应当满足点权小于等于 $w$ 且答案不超过 $t$,即概率为 $h(G_i,w,t)$。

因此,我们得到了关于函数 $h(G,y,t)$ 的递推式:

$$ h(G,y,t) = (\frac{t}{2})^n + \sum_{i=1}^n \int_{\frac{t}{2}}^{y}h(G_i,w,t)\text{d}w $$

显然有 $h(G,y,t)$ 是关于 $y$ 和 $t$ 的 $n$ 次其次多项式,于是我们对 $G$ 进行状压,可以在 $O(2^nn^3)$ 得到 $h(G_0,y,t)$,其中 $G_0$ 为输入的图。那么这时 $g(t) = h(G_0,\min(1,t),t)$,直接积分就可得到答案。

时间复杂度 $O(2^n \times n^3)$,结合算法一可以得到 $70$ 分。

算法四

怎么在算法三种作优化呢,我们发现算法三的复杂度的一个上界是子图个数,但是很多时候又不慢,比如在图是一个团的时候,$G_i$ 均为空,会计算的子图只有 $O(n)$ 个。

那是不是算法三可以直接跑过 $25$ 呢,遗憾的是并不是。不难发现在输入是一棵菊花的时候,算法三就会跑慢 $2^n \times n^3$。但是其中大部分的子图都是不连通的。

不难发现对于一张不连通的图 $G$,它的联通块分别为 $G_1,...,G_m$,那么 $h(G,y,t) = \prod_{i=1}^m h(G_i,y,t)$,因此对于不连通的图,我们可以直接拆分成更小的子问题,而不是和算法三一样递归的搜索。

时间复杂度未知,可以得到满分。

虽然我不会分析复杂度,但是实际上对于所有我能构造的 $n=30$ 的图,这个算法都可以在 $0.2s$ 内出解。于是冷静了一下就把 $n$ 开到 $25$ 出了出来。

这一题目前一共有 $157$ 个测试数据,std 一共只需要跑 $160ms$,所以应该是不存在卡常数的可能性的。

评论

oscar
前排咕咕咕
diamond_duke
前排咕咕咕
Trisolaris
出题的神仙们辛苦了qwq
LadyLex
出题人辛苦了! 这次比赛题目很高(hua)质(ji)啊QAQ 有一个小问题,T2的那个15pts的subtask,为什么不能用类似于最短路那种转移法,而非要二分答案呢? 比如这样: mindis[a][b]=mindis[b][a]=max(mindis[c][b],len(pt[a]-pt[b])); 其中a,c直接有边,然后转移 最后祝UR越办越好!
LiYuLiang
前排咕咕咕
fengchanghn
A可以加一个做法 http://uoj.ac/submission/235428
ryycpp
后排咕咕咕
gaojiaxuan
t3对于最大值的那个积分不用乘上一个(t-w)^c吗?(c是与这个点相连的点的数量)

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。