puzzleup 2021

newkid

〇〇 发表于 2021-10-19 15:30
还原结果create table chess2 asWITH-------- 先把10个棋子放置在6X6，使得每行每列不超过两个（满足尽量均 ...

这个改得不错！
在做上一题的时候我有想过，当时因为有斜线的要求所以放弃了，这题完全可以用上。

solomon_007

〇〇 发表于 2021-10-19 19:55
最后复原的代码难看，你用connect by 写一个？

newkid 的还有你这优化的，还没来得及细看，周末试一试。。

〇〇

〇〇 发表于 2021-10-18 09:04
将最后一个改成postgres的语法D:\pgsql140\bin>psql -d testpsql (14.0)输入 "help" 来获取帮助信息.test=# ...

改为mysql8的语法，cast有问题

with RECURSIVE t6(n) as (select 1 union all select n+1 from t6 where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(1<<(a.n-1))+(1<<(b.n-1))+(1<<(c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*((1<<(r.a-1)*6)+(1<<(r.b-1)*6)+(1<<(r.c-1)*6)) from b3 c,b3 r)
,
t(n,c,x,y)
as(select 1,cast('1' as char(100)),1,1 union all select n+1,cast(n+1 as char(100)),n/6+1,n%6+1 from t where n<6*6)
,
s(lv,n,nlist,blist,px,py)
as(select 1,t.n,t.c,1<<(t.n-1),pow(10,t.x),pow(10,t.y) from t where t.n<=6
union all
select lv+1,b.n,trim(nlist)||','||trim(c),blist+(1<<(b.n-1)),px+pow(10,b.x),py+pow(10,b.y)
from s,t b
where lv<10 and s.n<b.n
and(blist%19<14)
and (instr(px+pow(10,b.x),3)=0 and instr(py+pow(10,b.y),3)=0)
and b.n  between lv/2*6+1 and lv/2*6+6*2
)
select * from s where lv=10 and (lv<3 or not exists(select 1 from b9 where  (blist & b9.b) =0))
limit 10;

+------+------+-------+------------+---------+---------+
| lv   | n    | nlist | blist      | px      | py      |
+------+------+-------+------------+---------+---------+
|   10 |   31 | 1     | 1344948364 | 2122210 | 2122210 |
|   10 |   31 | 1     | 1381024416 | 2222200 | 1222210 |
|   10 |   31 | 1     | 1377970452 | 2212210 | 2212210 |
|   10 |   31 | 1     | 1378485012 | 2221210 | 1222210 |
|   10 |   31 | 1     | 1378403616 | 2222200 | 1222210 |
|   10 |   31 | 1     | 1414047756 | 2222110 | 1222210 |
|   10 |   31 | 1     | 1414055946 | 2222110 | 1222210 |
|   10 |   31 | 1     | 1411982112 | 2222200 | 1222210 |
|   10 |   31 | 1     | 125**8892 | 2221210 | 2122210 |
|   10 |   31 | 1     | 1246364940 | 2221210 | 1222210 |
+------+------+-------+------------+---------+---------+
10 rows in set, 2 warnings (8.55 sec)

mysql> show warnings
    -> ;
+---------+------+-------------------------------------------------------------------------------------------------------+
| Level   | Code | Message                                                                                               |
+---------+------+-------------------------------------------------------------------------------------------------------+
| Warning | 1287 | '|| as a synonym for OR' is deprecated and will be removed in a future release. Please use OR instead |
| Warning | 1287 | '|| as a synonym for OR' is deprecated and will be removed in a future release. Please use OR instead |
+---------+------+-------------------------------------------------------------------------------------------------------+
2 rows in set (0.00 sec)把||操作符改为concat（）函数可以了
with RECURSIVE t6(n) as (select 1 union all select n+1 from t6 where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(1<<(a.n-1))+(1<<(b.n-1))+(1<<(c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*((1<<(r.a-1)*6)+(1<<(r.b-1)*6)+(1<<(r.c-1)*6)) from b3 c,b3 r)
,
t(n,c,x,y)
as(select 1,cast('1' as char(100)),1,1 union all select n+1,cast(n+1 as char(100)),n/6+1,n%6+1 from t where n<6*6)
,
s(lv,n,nlist,blist,px,py)
as(select 1,t.n,t.c,1<<(t.n-1),pow(10,t.x),pow(10,t.y) from t where t.n<=6
union all
select lv+1,b.n,concat(trim(nlist),',',trim(c)),blist+(1<<(b.n-1)),px+pow(10,b.x),py+pow(10,b.y)
from s,t b
where lv<10 and s.n<b.n
and(blist%19<14)
and (instr(px+pow(10,b.x),3)=0 and instr(py+pow(10,b.y),3)=0)
and b.n  between lv/2*6+1 and lv/2*6+6*2
)
select * from s where lv=10 and (lv<3 or not exists(select 1 from b9 where  (blist & b9.b) =0))
limit 10;

+------+------+-----------------------------+------------+---------+---------+
| lv   | n    | nlist                       | blist      | px      | py      |
+------+------+-----------------------------+------------+---------+---------+
|   10 |   31 | 6,8,10,15,16,21,23,26,29,31 | 1381024416 | 2222200 | 1222210 |
|   10 |   31 | 3,5,9,12,14,18,22,26,29,31  | 1377970452 | 2212210 | 2212210 |
|   10 |   31 | 3,5,9,10,18,20,22,26,29,31  | 1378485012 | 2221210 | 1222210 |
|   10 |   31 | 6,9,11,15,16,20,22,26,29,31 | 1378403616 | 2222200 | 1222210 |
|   10 |   31 | 3,4,12,14,16,20,23,27,29,31 | 1414047756 | 2222110 | 1222210 |
|   10 |   31 | 2,4,12,15,16,20,23,27,29,31 | 1414055946 | 2222110 | 1222210 |
|   10 |   31 | 3,4,8,12,17,21,24,26,28,31  | 125**8892 | 2221210 | 2122210 |
|   10 |   31 | 3,4,9,11,18,20,23,26,28,31  | 1246364940 | 2221210 | 1222210 |
|   10 |   31 | 6,8,11,15,16,21,23,26,28,31 | 1246807200 | 2222200 | 1222210 |
|   10 |   31 | 2,4,11,14,18,21,24,27,28,31 | 1284645898 | 2222110 | 2122210 |
+------+------+-----------------------------+------------+---------+---------+
10 rows in set (7.55 sec)

cast as char实际上达到了varchar的效果
mysql> select concat(cast(1 as char),cast(32 as char));
+------------------------------------------+
| concat(cast(1 as char),cast(32 as char)) |
+------------------------------------------+
| 132                                      |
+------------------------------------------+
1 row in set (0.00 sec)

mysql> select concat(cast(1 as char(10)),cast(32 as char));
+----------------------------------------------+
| concat(cast(1 as char(10)),cast(32 as char)) |
+----------------------------------------------+
| 132                                          |
+----------------------------------------------+

除法也需要改为floor,和oracle差不多，也能检测出第一个t6写成t的错误，速度和postgresql差不多

mysql> with RECURSIVE t6(n) as (select 1 union all select n+1 from t6 where n<6)
    -> ,
    -> b3(a,b,c,bit)as(select a.n,b.n,c.n,(1<<(a.n-1))+(1<<(b.n-1))+(1<<(c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
    -> ,
    -> b9(b)as(select c.bit*((1<<(r.a-1)*6)+(1<<(r.b-1)*6)+(1<<(r.c-1)*6)) from b3 c,b3 r)
    -> ,
    -> t(n,c,x,y)
    -> as(select 1,cast('1' as char(100)),1,1 union all select n+1,cast(n+1 as char(100)),floor(n/6)+1,n%6+1 from t where n<6*6)
    -> ,
    -> s(lv,n,nlist,blist,px,py)
    -> as(select 1,t.n,t.c,1<<(t.n-1),pow(10,t.x),pow(10,t.y) from t where t.n<=6
    -> union all
    -> select lv+1,b.n,concat(nlist,',',c),blist+(1<<(b.n-1)),px+pow(10,b.x),py+pow(10,b.y)
    -> from s,t b
    -> where lv<10 and s.n<b.n
    -> and (instr(px+pow(10,b.x),3)=0 and instr(py+pow(10,b.y),3)=0)
    -> and b.n  between floor(lv/2)*6+1 and floor(lv/2)*6+6*2
    -> )
    -> select count(*) from s where lv=10 and not exists(select 1 from b9 where  (blist & b9.b) =0)
    -> ;
+----------+
| count(*) |
+----------+
|    32400 |
+----------+
1 row in set (2 min 59.69 sec)

〇〇

No: 08       October 20, 2021

POINTS AND COLOR LINES

POINTS AND COLOR LINES

There are X points on a plain paper such that no three of them are collinear. Using four different colors, you will draw lines connecting each point with every other point. The condition is that none of the triangles formed by these connections (and having these points as corners) would be monochromic.

What is the maximum possible value for X?


点和色线

在一张普通纸上有 X 个点，它们中没有三个共线。 使用四种不同的颜色，您将绘制连接每个点与其他点的线。 条件是由这些连接（并以这些点为角）形成的三角形都不是单色的。

X 的最大可能值是多少？

〇〇

感觉穷举就可以

newkid

老题目。

http://www.itpub.net/thread-2104263-1-1.html
156 楼

http://www.itpub.net/thread-1324198-8-4.html
293楼

solomon_007

〇〇 发表于 2021-10-19 10:09
找到原因了，计算位图的power括号写错了--oracle sqlcreate table chess6f aswith t6(n) as (select 1 from ...

with t6(n) as (select 1 from dual union all select n+1 from t6 where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(power(2,a.n-1))+(power(2,b.n-1))+(power(2,c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*(power(2,(r.a-1)*6)+power(2,(r.b-1)*6)+power(2,(r.c-1)*6)) from b3 c,b3 r)

这里 b3 好理解，b9 我知道你算的400个组合的掩码，但这为什么是掩码 c.bit*(power(2,(r.a-1)*6)+power(2,(r.b-1)*6)+power(2,(r.c-1)*6))   能细将一下吗？

newkid

第八题似乎还没有定论，网上可以查到论文，只是证明出现单色三角形的上限不超过62。

〇〇

b9是b3在3行出现，如果出现在第一行，保持不变，第二行就乘以2的六次方，以此类推

〇〇

newkid 发表于 2021-10-21 05:05
第八题似乎还没有定论，网上可以查到论文，只是证明出现单色三角形的上限不超过62。

假定这些点都在圆周上，从一个顶点连到其它顶点有n-1个弦，总共有n(n-1)/2个弦，
从一点引出两条弦，总共有c(n-1,2)个∠，加上第三边，可组成c(n-1,2)个三角形