如果一个长度a后b(b:=minl)都能取到,那么a就为所要求的解

判断无限解:1 能取到长度1的木条

2 所有木条长度的最大公约数不为1(或当前搜索的长度超过最大的两段木条的最小公倍数)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 41ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 119ms

├ 测试数据 10：答案正确... 150ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：351ms

自己花了两个小时才想出来啊

想法与changdi5一样

哎!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 25ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：100ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

├ 测试数据 11：运行超时...

├ 测试数据 12：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：92 有效耗时：25ms

为什么我N^2的程序会超时啊？。

受不了了。~~

就是用那个剩余类DIJ的思想啊。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

很好,算法见二楼

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 134ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：134ms

还是有差距。。。

第六个点慢。。

第一个点是什么。。我怎么会输出0。。

此题关键在于明白 如果对于一个无法取得的数a 在它后面连续b个都可取得。那么a就是无法取得的最大值（b是所有木头的最小值）

这句赞。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 25ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

原来冬令营也会出如此傻的背包呀！！！！！！！！！

冷得流汗！！

编译通过...

├ 测试数据 01：答案正确... 400ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 353ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

重复背包就是这样慢...而且(当然)还要卡数据，数组最大开到1111111比较好...

这题交了10+次。厄！我的正确率41% ——> 40%...

最短路。。。

orz

ZRN神牛！

参见usaco4.1的麦香牛块

为了不让本题的通过人数停在“38”这个吉利的数字 我决定把它AC

PS 想到用DIJ果然很巧妙 不知道DP怎么做。。。或者这本身就算DP？

谁有数据？

"├ 测试数据 08：运行时错误...|错误号: -1073741571"?????????????????

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 88ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 150ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：413ms

本题类型应该是DP

牛场围栏 (fence)

这道题设计得很巧妙，也很不错。

首先，根据l和m可以计算出所有可以得到的长度，设为S，S中的最小长度为s。

尝试把所有的正整数根据 mod s的余数分成s类，记做Ki=ns+i (0≤i≤s-1)

对于每一类Ki，如果其中的某个长度t可以被生成，那么对于Ki中所有大于t的数也可以被生成，因为Ki中所有数的差为s。

那么，如果我们可以求出每一类Ki中可以被生成的最小长度Qi，那么设r=max{Qi}，大于r的数都可以被生成，从r-1到1递减检查每个数，直到找到一个数i，满足i＜Qi mod s，此时的i就是不能生成的最大的数。

那么如何求Qi呢？

如果把s个类看成s个点，对于任一点i，w∈S，引一条边(i,(i+w) mod s)，边权为w，另外加一个源点source。

如果你细心观察的话，就会发现，Ki中最小的可以被生成的数就是source到i点的最短路长度！

至此本题已经没有难度了，对于无解的判断也很简单，如果source无法到某点，或者在r递减检查到1时仍然找不到一个不能生成的数就无解。

ps.在计算最短路时，不管用邻接表还是前向星表示图都要占用大量的空间（大概17M），事实上只需记录S中的数，然后在Dijkstra求SSSP时实时地生成边就可以了，这样只需开一个3000的数组就行了，具体实现请参见我的程序。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

的确是数论..

此题关键在于明白 如果对于一个无法取得的数a 在它后面连续b个都可取得。那么a就是无法取得的最大值（b是所有木头的最小值）

另外就是只要连续就不会不存在最大值,或者不连续而互质。换句话说只要没有连续的或全是某数的倍数长度就可以直接-1 (当然1除外)

其余参照可重复元素背包...

了结了1年的怨念....

直接递推求解

app[i][j]表示前i个数,j是否能斗出

app[i][j]=app[j] or app[i][j-data[i]]

点击查看程序源码+详细题解