题解

传输数据

可以看出，第 i 秒时，有数据的电脑的数量是 (k+1)^i，于是我们暴力枚举 i ，找到最小的使得 (k+1)^i >=n 的 i，时间复杂度：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)