竞赛讨论区 > 【题解】wannafly挑战赛8
头像
牛客网小运营
编辑于 2018-12-27 14:45
+ 关注

【题解】wannafly挑战赛8

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)

T1 Y和小B睡觉觉
模拟题,先把秒数 / 86400,再看看余数能不能凑够一天。
T2 LBJX的三角形
答案为a * b * c,因为满足条件的三角形一定是从红点、蓝点和绿点中分别取一个点。
T3 C打比赛

f[S][j]表示已经做的题的集合是S,一共用了j分钟的情况下,期望还能再做几道题。

枚举做哪道题以及做完的时间即可。

时间复杂度:O(2^n*n*m^2)

T4 AliceBob赌糖果
随机游走题http://www2.math.uu.se/~sea/kurser/stokprocmn1/slumpvandring_eng.pdf有系统介绍,直接算会炸,所以要用到一点小技巧 。
T5 G的项链
暴力枚举k,对于一个确定的k,可以发现以模k相同的位置为起点,最后产生的新项链都是同构的。因此可以枚举O(k)的枚举起始点,起点固定后,可以用前缀异或和来O(n/k)的得到新的项链,之后把新项链复制一遍,原问题等价于这个复制了一遍之后的字符串之中是否存在一个长度为【n/(k-1)/2】*2+1的回文串,可以用manacher判定一下。对于一个确定的k,检验的时间复杂度为O(k*n/k)=O(n),因此总时间复杂度为O(n * (n的因数个数)。如果用n的因数个数不超过n^0.5 *2个来估计的话会显得复杂度有些大,暴力跑一下可以发现当n 不等于200000时,n取196560时n*(n的因数个数)有最大值,仅为31449600。
T6 白云的树

树是随机树,所以树高是log级别的,可以直接考虑O(树高)的暴力。

使用树形DP,对于一个连通块我们在深度最小的结点进行统计。

k的某个孩子t的子树加入时的DP转移式

首先O(n*10^3)预处理子树DP值,对于每次修改,可以O(树高*10^2)地把子树DP值更新。 修改的方法是先撤销这个结点造成的影响,再把这个点重新加入。 消除影响的方法是把DP转移式倒过来

既然知道了如何消除一棵子树的影响,那么希望时就可以进行换根DP。

可以做到O(树高*10^2)。

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐