题解

40 条题解

  • 0
    @ 2009-01-23 11:05:34

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

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

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

  • 0
    @ 2008-10-25 09:52:57

    编译通过...

    ├ 测试数据 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一样

    哎!

  • 0
    @ 2008-10-14 20:14:28

    编译通过...

    ├ 测试数据 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

  • 0
    @ 2008-10-09 15:37:07

    编译通过...

    ├ 测试数据 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的思想啊。

  • 0
    @ 2008-09-18 19:26:18

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    很好,算法见二楼

  • 0
    @ 2008-09-11 17:31:26

    编译通过...

    ├ 测试数据 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
    @ 2008-08-23 16:52:13

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

  • 0
    @ 2007-11-09 09:00:07

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

    这句赞。

  • 0
    @ 2007-11-08 11:44:24

    编译通过...

    ├ 测试数据 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

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

    冷得流汗!!

  • 0
    @ 2007-11-02 21:51:47

    编译通过...

    ├ 测试数据 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%...

  • 0
    @ 2007-10-31 18:31:36

    最短路。。。

  • 0
    @ 2007-10-29 17:33:27

    orz

    ZRN神牛!

  • 0
    @ 2007-10-28 21:04:29

    参见usaco4.1的麦香牛块

  • 0
    @ 2007-10-03 21:18:56

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

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

  • 0
    @ 2007-05-27 22:49:47

    谁有数据?

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

  • 0
    @ 2007-03-27 20:43:47

    编译通过...

    ├ 测试数据 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

  • 0
    @ 2007-03-14 21:59:07

    牛场围栏 (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的数组就行了,具体实现请参见我的程序。

  • 0
    @ 2007-11-12 15:11:54

    编译通过...

    ├ 测试数据 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年的怨念....

  • 0
    @ 2006-05-25 07:54:00

    直接递推求解

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

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

信息

ID
1054
难度
6
分类
其他 | 数学 点击显示
标签
递交数
828
已通过
244
通过率
29%
被复制
10
上传者