31 条题解
-
4
小岛 LV 10 @ 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
yzl609271536 LV 10 @ 2009-11-03 18:16:02
ID-DFS即可
不过还是不明白为什么是
A:=A+A[J];
那位大牛能解释一下 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms我和大家有点不一样，我用的是宽度优先搜索。
-
0
-
0
编译通过...
├ 测试数据 01：运行时错误...| 错误号: 221 | 无效的变体操作
├ 测试数据 02：运行时错误...| 错误号: 221 | 无效的变体操作
├ 测试数据 03：运行时错误...| 错误号: 221 | 无效的变体操作
├ 测试数据 04：运行时错误...| 错误号: 221 | 无效的变体操作
├ 测试数据 05：运行时错误...| 错误号: 221 | 无效的变体操作
├ 测试数据 06：运行时错误...| 错误号: 221 | 无效的变体操作
├ 测试数据 07：运行时错误...| 错误号: 221 | 无效的变体操作
├ 测试数据 08：运行时错误...| 错误号: 221 | 无效的变体操作
---|---|---|---|---|---|---|---|-这是什么错？
-
0
suikongdao LV 3 @ 2007-10-27 21:24:37
不是唯一的ba
-
0
LiShuo_Com LV 3 @ 2007-10-21 18:54:05
这个数列好像不是唯一的
-
0
Fallen-Angel LV 3 @ 2007-10-20 19:39:16
A[D]=A[D-1]+A[K](K=D-1 downto 1)
迭代加深就OK了
1遍AC~~~~~~搜索越写越好了
小岛
LV 10
@ 2009-04-23 00:04:27
