Offer收割赛68题目简析

1
0

题解

传输数据

可以看出,第 i 秒时,有数据的电脑的数量是 (k+1)^i,于是我们暴力枚举 i ,找到最小的使得 (k+1)^i >=ni,时间复杂度:O(\log_{k+1}{n})

数字游戏

f[x] 表示将 x 变成 1 的方案数,则有:

f[n]=\sum_{d|n,d>1}f[\frac{n}{d}]

我们对于每个 d 去枚举 n ,使得 d|n,d<n,然后让 f[n]+=f[d]

这样复杂度是 \sum_{i=1}^{n}\frac{n}{i}=O(n\log{n})

跳石头

f[x] 表示跳到第 i 个石头需要至少几步

则有 f[x]=1+min(f[x-1],f[pre[x]])

其中 pre[x] 表示前面第一个和他同色的是第几个石头

其中 pre[x] 我们可以扫一遍得出:枚举 i=1..n,开一个数组tmp[x] 表示 c[1..i]x 最后一次出现是在哪个下标。

然后令 pre[i]=tmp[c[i]] 即可

时间复杂度:O(n)

道路建设

可以发现:一开始只有树上距离小于等于 1 的点对 (x,y) 之间有道路

然后第 1 个阶段后,所有树上距离小于等于 2 的点对 (x,y) 之间也有道路了

同理,第 i 个阶段后,所有树上距离小于等于 2^i 的点对 (x,y) 之间都有道路了

于是我们只需要求出树的直径的长度 d,暴力求出几个阶段后有2^i>=d

时间复杂度:O(n)

0 answer(s)

write answer 切换为英文 切换为中文


转发分享