PUZZLEUP 2015

〇〇

lugionline 发表于 2015-9-25 07:53
试试 M 的文档功能，比Word好用么，纯手工计算过程

太长了，奥数可以讲一堂课

〇〇

newkid 发表于 2015-9-24 23:10
我写了两种SQL都是1908。CONNECT BY搞不定，得用递归WITH。还是老办法，用BITAND判断是否一条边已经遍历过。 ...

答案有多次经过a的吗

cszxheap

newkid 发表于 2015-9-24 23:10
我写了两种SQL都是1908。CONNECT BY搞不定，得用递归WITH。还是老办法，用BITAND判断是否一条边已经遍历过。 ...

花了多久？

solomon_007

newkid 发表于 2015-9-24 23:10
我写了两种SQL都是1908。CONNECT BY搞不定，得用递归WITH。还是老办法，用BITAND判断是否一条边已经遍历过。 ...

递归with碰到环路,就退出了,后面不再继续连接了; 我卡在这里了,能给一点提示莫?

newkid

〇〇 发表于 2015-9-25 08:03
答案有多次经过a的吗

当然有，题目又没有限制A点。

newkid

cszxheap 发表于 2015-9-25 16:24
花了多久？

       CNT
----------
      1908

Elapsed: 00:00:00.01

newkid

第9题的SQL：

WITH v0 AS ( --------将第一个方块上层顶点编号1234,下层6785, 这样的编号是为了让两个斜对角顶点之差为7，第二个方块的顶点只需在第一个之上加7
  SELECT 1 v1,2 v2 FROM DUAL   -----枚举出第一方块每个点可以到达的所有相邻顶点(单向，令V1<V2，下面用UNION ALL构造出反向)
         UNION ALL SELECT 1,4 FROM DUAL
         UNION ALL SELECT 1,6 FROM DUAL
         UNION ALL SELECT 2,3 FROM DUAL
         UNION ALL SELECT 2,7 FROM DUAL
         UNION ALL SELECT 3,4 FROM DUAL
         UNION ALL SELECT 3,8 FROM DUAL
         UNION ALL SELECT 4,5 FROM DUAL
         UNION ALL SELECT 5,6 FROM DUAL
         UNION ALL SELECT 5,8 FROM DUAL
         UNION ALL SELECT 6,7 FROM DUAL
         UNION ALL SELECT 7,8 FROM DUAL
)
,v AS (
SELECT v1,v2,POWER(2,ROW_NUMBER() OVER(ORDER BY v1,v2)-1) e  ---- 每条边用二进制的一位表示, 以便用BITAND检查重复
  FROM (
        SELECT v1,v2 FROM v0 ---- 第一方块
        UNION ALL  SELECT v1+7,v2+7 FROM v0  ---- 第二个立方体所有顶点编号为第一立方体响应顶点编号之上加7, 比如2号点对应9号点
      )
)
,all_v AS ( ------合并上反向的所有边
SELECT v1,v2, e
  FROM v
UNION ALL
SELECT v2,v1, e
  FROM v
)  
,p(v,all_e,path) AS ( ---- 所有起点为1的遍历路径
SELECT v2,e,CAST(v1||','||v2 AS VARCHAR2(40)) FROM all_v WHERE v1 =1
UNION ALL
SELECT all_v.v2
      ,p.all_e+all_v.e
      ,p.path||','||all_v.v2
  FROM all_v,p
WHERE p.v=all_v.v1 AND BITAND(p.all_e,all_v.e)=0 AND p.v<>15 ----到达终点15就停止
)
SELECT COUNT(*) FROM p WHERE v=15;

  COUNT(*)
----------
      1908

Elapsed: 00:00:00.12

-----------只考察一个方块的路径的解法
WITH v AS ( --------将第一个方块上层顶点编号1234,下层6785
SELECT v1,v2,POWER(2,ROW_NUMBER() OVER(ORDER BY v1,v2)-1) e  ---- 每条边用二进制的一位表示, 以便用BITAND检查重复
  FROM (
  SELECT 1 v1,2 v2 FROM DUAL   -----枚举出第一方块每个点可以到达的所有相邻顶点(单向，令V1<V2，下面用UNION ALL构造出反向)
         UNION ALL SELECT 1,4 FROM DUAL
         UNION ALL SELECT 1,6 FROM DUAL
         UNION ALL SELECT 2,3 FROM DUAL
         UNION ALL SELECT 2,7 FROM DUAL
         UNION ALL SELECT 3,4 FROM DUAL
         UNION ALL SELECT 3,8 FROM DUAL
         UNION ALL SELECT 4,5 FROM DUAL
         UNION ALL SELECT 5,6 FROM DUAL
         UNION ALL SELECT 5,8 FROM DUAL
         UNION ALL SELECT 6,7 FROM DUAL
         UNION ALL SELECT 7,8 FROM DUAL
      )
)
,all_v AS ( ------反向的所有边
SELECT v1,v2, e
  FROM v
UNION ALL
SELECT v2,v1, e
  FROM v
)  
,p(v,all_e,path) AS (
SELECT v2,e,CAST(v1||v2 AS VARCHAR2(20)) FROM all_v WHERE v1=1
UNION ALL
SELECT all_v.v2
      ,p.all_e+all_v.e
      ,p.path||all_v.v2
  FROM all_v,p
WHERE p.v=all_v.v1 AND BITAND(p.all_e,all_v.e)=0
)
,all_p AS (SELECT * FROM p WHERE v=8) ------- 找出所有终点为8的路径
SELECT COUNT(*) ---- 第一方块中终点为8的路径数量
      *COUNT(CASE WHEN INSTR(path,'8')=LENGTH(path) THEN 1 END)  ---- 第二方块中终点为8的路径数量, 并且8只能经过一次
      -----上面是1号块->2号块的所有组合
      -----下面是1号块->2号块->回到1号块->再进入2号块的所有组合
      ---------(a)1号方块从起点到终点
      ---------(b)2号方块中兜圈绕回起点再次进入1号方块
      ---------(c)1号方块中兜圈绕回终点再次进入2号方块
      ---------(d)到达2号方块终点
      +COUNT(CASE WHEN INSTR(path,'8')<LENGTH(path) THEN 1 END) --- 1方块8号点出现多次的那些路径(上述路径的(a)和(c)组合)
      *COUNT(CASE WHEN INSTR(path,'1',2)>0 AND INSTR(path,'8')=LENGTH(path) THEN 1 END) cnt  --- 2方块的1号点出现多次（绕回去），8号点只出现一次的那些路径(上述路径的(b)和(d)组合)
  FROM all_p
;

       CNT
----------
      1908

Elapsed: 00:00:00.01

newkid

#10

16-DIGIT NUMBER

Using the digits 1, 2, 3, 4, and 5 you will form a 16-digit number such that for every adjacent two digits either both of them will be the same or at least one of them will be 1.

How many different numbers can be formed?

你用数字1，2，3，4，和5构成一个16位数，使得对于任意相邻的每两个数字，或者它们相等，或者至少有一个数是1。

总共可以构成多少个不同的数？
----------
虽然没有明确说明，这5个数应该是至少出现一次。用SQL轻松搞定。

〇〇

newkid 发表于 2015-10-2 22:26
#10

16-DIGIT NUMBER

这些数字必须都用到,还是可以只用一部分

lugionline

我的理解是这5个数不必要一定出现，111.....111这种也算

SQL如果硬拼数字统计的话估计机器要响上半天了