ACM题(#2634 Collecting Stones)

〇〇

原帖由 rollingpig 于 2011-4-12 17:33 发表
and t.c
and t.c5
==>
and t.c>=4

后来想到了，漏算了4，5列上下移动的

〇〇

用上79 80

1948=〉
SQL> @c:\downloads\26345rp

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,01,09,17,25,33,41,49,57,58,50,59,51,43,35,27,19,11,03,04,12,20,28,36,44,52,60*61,53,45,37,29,21,13,05,06,14,22,30,38,46,54,62,63,55,47,39,31,23,15,07
,08,16,24,32,40,48,56,64,

已用时间:  00: 00: 21.80

〇〇

递归写法不能在拼路径的时候把起点到当前点的石头相同的不同路径剪掉，所以慢了

newkid

原帖由 〇〇 于 2011-4-12 21:51 发表
递归写法不能在拼路径的时候把起点到当前点的石头相同的不同路径剪掉，所以慢了

我昨天在翻译lugionline同学的MSSQL的时候看到MSSQL居然支持在递归的地方使用ROW_NUMBER().
ORACLE这个递归还有很多可以改善的地方，比如增加聚合、分析函数，增加对子查询的支持，丢弃中间结果等等。

影之哀伤

这个帖子看的我快对SQL失去信心了

我是不是得再学点别的编程语言？

perl,php?帮忙推荐下哦

yyp2009

够折腾的了

lastwinner

原帖由 影之哀伤 于 11-4-12 22:40 发表
这个帖子看的我快对SQL失去信心了

我是不是得再学点别的编程语言？

perl,php?帮忙推荐下哦

别，他们玩高精尖的，属于80%的东西解决20%的问题的

〇〇

把4，5列剔出重复石头,比82快4倍
SQL> @c:\downloads\testcte2

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,01,09,17,25,33,41,49,57,50,58,59,51,43,35,27,19,11,03,04,12,20,28,36,44,52,60*61,53,45,37,29,21,13,05,06,14,22,30,38,46,54,62,63,55,47,39,31,23,15,07
,08,16,24,32,40,48,56,64,

已用时间:  00: 00: 04.47

1. 
   
2. wITH d AS (
   
3.   SELECT to_char(ROWNUM,'fm09') id
   
4.         ,CEIL(ROWNUM/8) r
   
5.         ,MOD(ROWNUM-1,8)+1 c
   
6.         ,ROWNUM val
   
7.     FROM DUAL
   
8.    CONNECT BY ROWNUM<=64
   
9.   )
   
10. ,t(r,c,val,total,path) AS (
    
11.   SELECT r,c,val,val,','||CAST(id AS VARCHAR2(1000)) FROM d WHERE r=1 AND c=1
    
12.   UNION ALL
    
13.   SELECT d.r,d.c,d.val,d.val+t.total,t.path||','||d.id
    
14.     FROM t, d
    
15.    WHERE INSTR(t.path||',',','||d.id||',')=0
    
16.          AND (d.r,d.c) IN ((t.r-1,t.c),(t.r+1,t.c),(t.r,t.c+1),(t.r-1,t.c+1),(t.r+1,t.c+1))
    
17.          AND d.val+t.total<:M
    
18.          and t.c<4
    
19.   )
    
20.   ,t4ud (r,c,val,total,path)as (
    
21.   select  r,c,val,total,path from
    
22.   (select r,c,val,total,path ,row_number()over(partition by r,c,val,total,substr(path,-2) order by length(path))rn from t where t.c=4)where rn=1 union all
    
23.   SELECT d.r,d.c,d.val,d.val+t.total total ,t.path||','||d.id path
    
24.     FROM t4ud t, d
    
25.    WHERE INSTR(t.path||',',','||d.id||',')=0
    
26.          AND (d.r,d.c) IN ((t.r-1,t.c),(t.r+1,t.c))
    
27.          AND d.val+t.total<:M)
    
28.   ,t4udd (r,c,val,total,path)as (
    
29.   select  r,c,val,total,path from
    
30.   (select r,c,val,total,path ,row_number()over(partition by r,c,val,total,substr(path,-2) order by length(path))rn from t4ud t where t.c=4)where rn=1)
    
31. ,t2(r,c,val,total,path) AS (
    
32.   SELECT r,c,val,val,CAST(id AS VARCHAR2(1000))||',' FROM d WHERE r=8 AND c=8
    
33.   UNION ALL
    
34.   SELECT d.r,d.c,d.val,d.val+t.total,d.id||','||t.path
    
35.     FROM t2 t, d
    
36.    WHERE INSTR(t.path||',',','||d.id||',')=0
    
37.          AND (d.r,d.c) IN ((t.r+1,t.c),(t.r-1,t.c),(t.r,t.c-1),(t.r+1,t.c-1),(t.r-1,t.c-1))
    
38.          AND d.val+t.total<:M
    
39.          and t.c>5
    
40.   )
    
41.   ,t5ud (r,c,val,total,path)as (
    
42.   select  r,c,val,total,path from
    
43.   (select r,c,val,total,path ,row_number()over(partition by r,c,val,total,substr(path,1,2) order by length(path))rn from t2 t where t.c=5)where rn=1 union all
    
44.   SELECT d.r,d.c,d.val,d.val+t.total total ,d.id||','||t.path path
    
45.     FROM t5ud t, d
    
46.    WHERE INSTR(t.path||',',','||d.id||',')=0
    
47.          AND (d.r,d.c) IN ((t.r-1,t.c),(t.r+1,t.c))
    
48.          AND d.val+t.total<:M)
    
49.   ,t5udd (r,c,val,total,path)as (
    
50.   select  r,c,val,total,path from
    
51.   (select r,c,val,total,path ,row_number()over(partition by r,c,val,total,substr(path,1,2) order by length(path))rn from t5ud t where t.c=5)where rn=1)
    
52. SELECT /*+ ordered use_hash(t t2)   */t.path||'*'||t2.path FROM t4udd t,t5udd t2
    
53. WHERE (t.r=t2.r or t.r=t2.r-1 or  t.r=t2.r+1)AND t.c=4 and t2.c=4+1
    
54. AND t.total=:M-t2.total and rownum=1;  
    
55.   ;
    

复制代码

〇〇

借鉴rollpig的思想
在t4ud和t5ud 中加入条件d.c=4和d.c=5
速度再提高1倍，不过跟74相比还是慢
SQL> @c:\downloads\testcte2

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,01,09,17,25,33,41,49,57,50,58,59,51,43,35,27,19,11,03,04,12,20,28,36,44,52,60*61,53,45,37,29,21,13,05,06,14,22,30,38,46,54,62,63,55,47,39,31,23,15,07
,08,16,24,32,40,48,56,64,

已用时间:  00: 00: 02.04

SQL> @c:\downloads\rp1

N
-
Y
已用时间:  00: 00: 00.13

〇〇

在t t2条件增加d.c>=t.c 和d.c<=t.c
SQL> @c:\downloads\testcte2

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,01,09,17,25,33,41,49,57,50,58,59,51,43,35,27,19,11,03,04,12,20,28,36,44,52,60*61,53,45,37,29,21,13,05,06,14,22,30,38,46,54,62,63,55,47,39,31,23,15,07
,08,16,24,32,40,48,56,64,

已用时间:  00: 00: 01.97