ZR2213 sol

sol by wmrqwq

算法 $1$：$m \le 500$

考虑直接结合 $m \le 500$ 这个限制去做背包，时间复杂度 $O(nm^2)$，期望得分 $20$ 分。

算法 $2$：$m \le 10^6$

考虑优化算法 $1$，可以使用区间加，区间求和的数据结构去优化背包，时间复杂度 $O(nm \log m)$，期望得分 $35$ 分。

或者你根据算法 $4$ 直接暴力求交，也是可以获得这 $35$ 分的。

算法 $3$：$l_i = r_i$

发现此时周期就是 $\texttt{lcm}(l_1,l_2,l_3, \dots,l_n)$ 的值，设 $num = \texttt{lcm}(l_1,l_2,l_3, \dots,l_n)$，答案即为 $\lfloor \frac{num}{10^9} \rfloor$，期望得分 $10$ 分，集合算法 $2$ 即可获得 $45$ 分。

算法 $4$：$l_i < r_i$

发现对于每一对数 $l_i,r_i$，可以得到的数字为 $[l_i,r_i],[2l_i,2r_i],[3l_i,3r_i], \dots, [kl_i,kr_i]$，直接求交即可，期望得分 $70$ 分。

算法 $5$

结合算法 $3,4$ 时间复杂度为 $O(nV)$，其中 $V$ 为 $\max(l_i,r_i)$。

期望得分 $100$ 分。

参考代码

link