/ Vijos / 题库 / C数列 /

题解

31 条题解

  • 4
    @ 2009-04-23 00:04:27

    我们可以用迭代加深搜索解这道题...

    具体的方法是不断延展这个序列的长度...

    直到得到我们需要的数字...

    可惜的是...我在vijos上跑过的程序没能过TJU的评测..

    后面的一半...都超时了...

    不得已..我采用了一种较为折中的办法...避免迭代......先用O(1000)的时间

    预处理出每个数据需要的长度...再回去用dfs构造出这组解..

    (我当然想既然打表嘛还不如打的彻底一点- -...但是...

    1000以内的数据我貌似还运行了不少时间..洗完澡回来才出结果..

    而且还得给每个数据加一个逗号...还好我用Lazarus的替换功能..

    替换空格和逗号...再把那些变成逗号的..原本用来缩进的空格变回来就好..#83)

    ...我觉得这道题还有一点不太好的地方..

    除了n为2的方幂...大多数情况下有许多序列都会是合法的...

    例如当n=7时....不妨先看这两组..

    1 2 3 4 7 (字典序最小的)...

    1 2 4 6 7 (字典序最大的)..

    ..题目并没有明确的对方案作出要求...

    似乎我们会默认字典序比较小的情况...(并且其实我一开始就是这么以为的..)

    可是如果用迭代加深算法的话...我们会更自然的给出字典序最大的结果..

    (因为这样的话先搜出大的数字出解会快很多..#83...可是这是什么说法呀..)

    Links:

    超时的那份code..迭代加深的比较清晰..

    http://oi.tju.edu.cn/status/code/12395/

    这一份是后来AC的...

    http://oi.tju.edu.cn/status/code/12394/

    Vijos的题..

    http://www.vijos.cn/Problem_Show.asp?id=1350

    TJU的题目..

    http://oi.tju.edu.cn/problem/view/1108.html

    OIBH的讨论贴..(#- -)

    http://www.oibh.org/bbs/viewthread.php?tid=29926&highlight=%BC%D3%B7%A8%C1%B4

  • 0
    @ 2009-11-13 17:00:26

    编译通过...

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-11-07 15:37:26

    真惭愧,这题搜索我还卡了时

  • 0
    @ 2009-11-03 18:16:02

    ID-DFS即可

    不过还是不明白为什么是

    A:=A+A[J];

    那位大牛能解释一下

  • 0
    @ 2009-10-29 15:22:08

    同ls,不太理解

  • 0
    @ 2009-10-19 20:45:15

    实在有点不懂 为什么是

    A[D]=A[D-1]+A[K](K=D-1 downto 1)

    A[D]不是应该由 A[i]+A[j] 推出

    但为什么一定是 D-1 推出?

  • 0
    @ 2009-05-23 16:33:12

    编译通过...

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

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

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

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

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

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

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

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

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

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

    我和大家有点不一样,我用的是宽度优先搜索。

  • 0
    @ 2009-03-27 15:19:10

    当N为7时

    是(1):1 2 3 5 7

    是(2):1 2 4 6 7

  • 0
    @ 2008-08-26 09:30:10

    看来真的不是唯一的

    我是从小到大搜的……

  • 0
    @ 2008-08-26 00:03:45

    ID-DFS

    注意搜索顺序,

    从大到小枚举,无需剪枝。

  • 0
    @ 2008-08-09 06:59:18

    j=k-1

    证明不会

  • 0
    @ 2007-11-08 22:31:53

    编译通过...

    ├ 测试数据 01:运行时错误...| 错误号: 221 | 无效的变体操作

    ├ 测试数据 02:运行时错误...| 错误号: 221 | 无效的变体操作

    ├ 测试数据 03:运行时错误...| 错误号: 221 | 无效的变体操作

    ├ 测试数据 04:运行时错误...| 错误号: 221 | 无效的变体操作

    ├ 测试数据 05:运行时错误...| 错误号: 221 | 无效的变体操作

    ├ 测试数据 06:运行时错误...| 错误号: 221 | 无效的变体操作

    ├ 测试数据 07:运行时错误...| 错误号: 221 | 无效的变体操作

    ├ 测试数据 08:运行时错误...| 错误号: 221 | 无效的变体操作

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

    这是什么错?

  • 0
    @ 2007-11-06 16:50:50

    Yours 说的没错。。

    这个数列显然不是唯一的。。。

    大家可以参考分蛋糕。。

  • 0
    @ 2007-11-03 20:58:56

    是唯一的

    这个题可用递推来解决,由A[1]逐步通过BFS推出An;如1-2-4;

    剪枝时大于An的节点和重复节点桶桶减掉,最后找出最短路径,可用树结构来查询(A[k]=A[i]+A[j])

  • 0
    @ 2007-10-27 21:24:37

    不是唯一的ba

  • 0
    @ 2007-10-26 20:50:45

    是唯一的.

  • 0
    @ 2007-10-21 18:54:05

    这个数列好像不是唯一的

  • 0
    @ 2007-10-20 19:39:16

    A[D]=A[D-1]+A[K](K=D-1 downto 1)

    迭代加深就OK了

    1遍AC~~~~~~搜索越写越好了

  • 0
    @ 2007-10-21 14:34:47

    同yours牛...

    不需要太深奥的算法..直接搜然后剪如果有心情就掐=AC..

    貌似这题还有一个更强的版本..

  • 0
    @ 2007-10-17 16:39:23

    BFS+可行性剪枝+最优性剪枝

信息

ID
1350
难度
6
分类
搜索 点击显示
标签
(无)
递交数
226
已通过
58
通过率
26%
被复制
4
上传者