考了一套简单题.
$prime$
贪心.
有一个比较明显的贪心策略,即先做若干次除法,再只做加法或只做减法.
做完除法后算答案直接暴力枚举加/减了几步就可以了.
因为 $10^9$ 内的两个相邻质数相差不会超过 $220$ ,所以答案也不会超过 $220$ .
据说质数密度是 $O(\log n)$ 级别的.
$path$
树状数组.
可以发现这个图就是由若干个不相交的链或者环组成的.
因为只有合并操作,所以可以用并查集来维护每条链和每个环,以及它们的大小.
查询 $(l,r)$ 时,可以用长度不超过 $r$ 的答案减去长度不超过 $l-1$ 的答案,只需要考虑如何计算长度不超过 $k$ 的路径数.
考虑一条大小为 $s$ 的链的贡献.若 $s\le k$ ,贡献为 $\frac {s(s+1)} 2$ ,否则,贡献为 $k\cdot s-\frac {k(k-1)} 2$ .
考虑一个大小为 $s$ 的环的贡献.若 $s\le k$ ,贡献为 $s^2$ ,否则, 贡献为 $s\cdot k$ .
用 $5$ 个树状数组分别维护贡献 (还有一个是链的条数) ,每个链/环的贡献加入它的大小的对应位置.
有个地方没开 $\mbox{long long}$ ,爆成 $95$ 了.
时间复杂度 $O(n\log n)$ .
$book$
期望 $dp$ .
设 $f(i,j)$ 表示第 $i$ 个人拿到的从新到旧的第 $j$ 本书的期望排名.
转移时枚举每个人拿了哪本书,时间复杂度 $O(n^3)$ .