vijos1054牛场围栏 数学+最短路

shinbokuow posted @ Sep 07, 2015 06:37:28 PM in vijos with tags 数学 最短路 , 488 阅读

 

题解:

首先通过题目信息找出所有能用的围栏,这个暴力即可,然后围栏至多有$n$种。

解题的关键在于发现:若令$x_0$为所有能用的围栏中最小的长度,则对于任意长度$L\geq{0}$,若$L$能够表出,则$L+x_0$必定能够表出。

不妨将所有长度都放在$\pmod{x_0}$的意义下考虑。

考虑令$f_i$表示能够被表示的$\pmod{x_0}$恰好为$i$的长度最小的长度是多少。

关于如何求这个东西,我们可以建立最短路求解。

对于剩余系中的每个值都建立一个点即可,相当于是一个以$0$为原点的单源最短路。显然建图再加上Dijkstra时间复杂度为$O(n^2)$。

我们求出所有$f_i$的最大值,不妨设为$r$,则显而易见所有$\geq{r}$的值都能够表出。

而且如果$r\not=\infty$,显然$r\leq{n^2}$。

所以我们再在$O(n^2)$时间里从$r-1$开始往回去找第一个不能表出的值即可。

于是总时间复杂度就为$O(n^2)$。

这道题目的思路确实非常巧妙啊0.0,我反正是想不出来。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter