Tips

仅含题解,代码详见github喜欢的话点个star

1001. Army Formations

感觉题意有点绕。。。其实就是每个节点一开始就有整个子树的序列,那么这个序列一定是先输入小的再输入大的才能最优。

不过这个事情也不是两个有序表合并这么简单,因为对于两个序列,只有把某个序列的数一个一个地插入到另一个才能算出答案。这时候就要用到启发式合并,什么是启发式的策略,通俗来讲就是人脑比较倾向于选择的策略。比如在这里就是把短的序列一个一个插到长的里面,比赛的写的线段树合并结果写了一大坨还没调出来,太蠢了😂。。。然后照着题解写了一个树状数组。。。

代码见附录,dfs用来得到轻重儿子,solve就是插入和合并,要递归重儿子时直接把轻儿子的全部删掉就行了。

1002. Battlestation Operational

求 $f(n)=\sum_{i=1}^{n}\sum_{j=1}^{i} \left\lceil \frac{i}{j} \right\rceil \left[ (i, j) = 1\right]$ 。

比赛的时候算是瞎猜了一下。。。其实这题反演的理论性还是很好的。

以下 $n,i,j,k,d$ 均为正整数,且用 $(i,j)$ 表示 $i$ 和 $j$ 的最大公约数

记 $h(i)=\sum_{j=1}^{i} \left\lceil \frac{i}{j} \right\rceil \left[ (i, j) = 1\right]$,显然 $f(n)$ 为 $h(i)$ 的前缀和。
考虑到 $h(i)$ 中与互质有关,不易直接求解,直接令 $g(i)=\sum_{j=1}^{i} \left\lceil \frac{i}{j} \right\rceil$ 。

将 $g(i)$ 中的 $\left\lceil \frac{i}{j} \right\rceil$ 按 $(i,j)$ 分类。枚举可能的 $(i,j)=d$,则有 $d|i,j=kd,k\le \frac{i}{d}$ 且 $(i,kd)=d$(注意, $k$ 不是从 $1$ 到 $\frac{i}{d}$ 的全集)。现只对这一类求和:
$$ \begin{equation}\begin{split}
&\sum_{k=1}^{\frac{i}{d}}\left\lceil \frac{i}{kd} \right\rceil \left[ (i, kd) = d\right] \
=& \sum_{k=1}^{\frac{i}{d}}\left\lceil \cfrac{\frac{i}{d}}{k} \right\rceil \left[ (\frac{i}{d}, k) = 1\right] \
=&\ h(\frac{i}{d})
\end{split}\end{equation}$$
当 $d$ 取遍 $i$ 的约数,我们有 $g(i)=\sum_{d|i}h(\frac{i}{d})$。
由约数的性质,也即 $g(i)=\sum_{d|i}h(d)$ 。
这是标准的莫比乌斯反演形式,可以得到 $h(i)=\sum_{d|i} \mu(d) g(\frac{i}{d})$ 。

小结一下。

如何求解 $f(n)$:$h(i)$ 的前缀和;

如何求解 $h(i)$:莫比乌斯反演;

如何求解 $\mu(i)$:线性筛模板;

如何求解 $g(i)$:按常规考虑枚举分母($j$),则对于 $i=j$ 的 $g(i)$ 要+1,对于 $i=j+1…2j$ 的 $g(i)$ 要+2,……,也就是说一个 $j$ 相当于多次区间加法;但是这里不需要动态维护,只需要最终结果,所以利用差分的思想,即 $g’(i)=g(i)-g(i-1)$,回顾上述过程就是对 $g’(i)$ 在 $j,j+1,2j+1…$ 的单点修改,容易很多,最后再对 $g’(i)$ 求和即可。

鸣谢 quailty, forever97

1008. Hybrid Crystals

1011. Killer Names

dp[i][j]表示前i个字符恰好用到j种字符的方案数,然后把组合数表和dp表预处理一下,每次 $O(m^2)$ 回答。