首页 > 代码库 > 牛场围栏(vijos 1054)

牛场围栏(vijos 1054)

题目大意:

给出N种木棍(每种木棍数量无限)的长度(<=3000),每根木棍可以把它切掉[1,M]的长度来得到新的木棍。 求最大的不能被组合出来的长度。 如果任何长度都能组合出来或者最大值没有上限输出-1.    (1<N<100, 0<=M<3000),

 

解题过程:

1.这题就是USACO 4.1的麦香牛块 ,只不过 数据 加强了下。 当时就把它当做 背包 来做,然后确定一个较大的范围(当时就选了60000),求出这个范围里的长度能否都被组合出来,如果能就输出-1. 否则输出最大的不能被组合出来的长度。。     nocow里大多也是如此,但是为什么这样可以,貌似没人给出较好的证明(至少我是没看懂,感觉是错的)

2.再看此题,此题的每根木棍的长度范围变成了3000(麦香牛块那题才10),难以确定一个拿来做的范围。。看了题解(在vijos题解栏里最下面)后大有收获,下面给出做法。

 

首先还是有很多人选了一个范围来做,有点碰运气的味道,而下面的方法 要严谨的多:

 

1.首先预处理出所有能搞出来的原始木棍长度,然后找到一个最小的,记为P。 如果P=1那就不用做下去了,直接输出-1.

2.我们把所有的整数按mod P的值分为P类(mod P=0,1,2,3,4...P-1),记为集合Q0,Q1,Q2...QP-1    如果集合Q中有一个长度len可以被组合出来,那么该集合中所有比len大的数也一定可以组合出来.因为是mod P的,所以len可以不断加P来组合出 比它大的且和它在同一个集合里的数。 根据这个性质 就可以 找到图论模型了。

3.我们抽象出P-1个点,分别表示集合Qi 中最小的能被组合出来的数D[i]。 那么把根据原始木棍的长度,可以在这些点之间连边,表示可以从Qi 中的一个数 加 X 得到 Qj中的一个数。

然后利用spfa算法 就可以 求出 “集合Qi 中最小的能被组合出来的数”了。 具体实现的时候有个小优化可以减少边的数量,就是如果多条边的权值 mod P 相等,那么只要加入其中的一条就可以了(根据同余定理)

4.那么如何根据最后D[i]的值来得到答案呢? 还是利用性质“如果集合Q中有一个长度len可以被组合出来,那么该集合中所有比len大的数也一定可以组合出来”来做。依次检查每一个D[i],如果D[i]>i,那么集合Qi 中最大的不能被组合出来的数 就是 D[i]-P。检查所有的D[i] 取最大值就是答案了。

 

总结:非常灵活的图论+数论题,图论模型的转化非常巧妙,真心好题,收获很大。

 

牛场围栏(vijos 1054)