滑稽树上滑稽果
By jiry_2,数据、题解By WuHongxun
写题解之前,我们先来回顾一下上次比赛的A题题解:
这道题可能并没有那么有趣..本来有一道很棒的 A,但是比赛前突然被发现是个假题..然后就临时出了这么个题..感觉送送分还是不错的。
懂我意思吧?
如果看到题面里大大的滑稽还没有察觉事情不太对...请允悲...
子任务一
既然 $n$ 那么小,我们直接枚举每个点的父亲!
时间复杂度 $O(n^n)$。
子任务二
保证是一条链了,我们就只要枚举排列了!
冷静一下马上就会意识到,答案一定是一条链。这个部分分肯定是出题人用来提示大家冷静一下的!
时间复杂度 $O(n!)$。
子任务三
保证滑稽值的字典序最小?那就等于是每次枚举一个和当前的滑稽值and起来最小的值,然后把他加到后面。
时间复杂度 $O(n^2)$。
子任务四
把相同的位拿出来,这些位要么一定是每次没贡献,要么一定是每次有贡献。
那么剩下的位,每次一定会减去一位,从而最多只会用$O(log a)$次就减到0了,每次暴力找最小的就好了。
时间复杂度 $O(n log a)$。
子任务五
出题人给了一个部分分是这个贪心的过程,我们睿(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)$:
如果所有点的权值都小于等于 $\frac{t}{2}$,那么必定满足顶点权值最大值小于等于 $y$,因此此时的概率为 $(\frac{t}{2})^n$(令 $G$ 的顶点个数为 $n$)。
如果至少有一个点的权值大于 $\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$,所以应该是不存在卡常数的可能性的。