vijos1054牛场围栏 数学+最短路
题解：
首先通过题目信息找出所有能用的围栏,这个暴力即可，然后围栏至多有$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，我反正是想不出来。
评论 (0)