2022 PUZZLEUP

newkid

如果没有很好的推理结论做基础，一个SQL是不可能跑出来的。

〇〇

newkid 发表于 2022-12-5 00:01
如果没有很好的推理结论做基础，一个SQL是不可能跑出来的。

发现一个规律，如果要求两两异或4个及以上1，那么选出来的4个数的异或结果为0

with recursive n as (select i-1 n from generate_series(1,64)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,6)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and (n1.n#n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)>=4)
,t as(select 1 lv,array[n1,n2]a from p
union all
select lv+1,a||array[n] from t,n where a[lv+1]<n and lv+1= ( select count(*) from p q, unnest(a) u(c) where n1=c and n2=n)
)
select a from t where lv=3;


{13,16,38,59}
{13,16,42,55}
(240 行记录)


postgres=# select 13#16#42#55;
?column?
----------
        0
(1 行记录)


postgres=# select 13#16#42;
?column?
----------
       55
(1 行记录)


postgres=# select 13#16#38;
?column?
----------
       59
(1 行记录)
with recursive n as (select i-1 n from generate_series(1,64)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,6)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and (n1.n#n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)>=4)
,t as(select 1 lv,array[n1,n2]a from p
union all
select lv+1,a||array[n] from t,n where a[lv+1]<n and lv+1= ( select count(*) from p q, unnest(a) u(c) where n1=c and n2=n)
)
select distinct a[1]#a[2]#a[3]#a[4] from t where lv=3;

?column?
----------
        0
(1 行记录)

〇〇

如果知道结果最大是4，可以这么验证
with recursive n as (select i-1 n from generate_series(1,8)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,3)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and (n1.n#n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)>=2)
,t as(select n1,n2,n1#n2 n3,cnt from p)
,t2 as(select t.*,t1.* from t,t t1 where t1.n1>t.n2 and t1.n3=t.n3
and (t.n1,t1.n1) in (select n1,n2 from p)
and (t.n1,t1.n2) in (select n1,n2 from p)
and (t.n2,t1.n1) in (select n1,n2 from p)
and (t.n2,t1.n2) in (select n1,n2 from p)
)
select * from t2 limit 4;

〇〇

如果x在结果中，那么全1-x必定不能在结果中，因为xor(x,全1-x)=0，所以8个数最多取4个，在拼接时直接丢弃，比如二进制位为3时：有1 没 6 ，有3 没 4

newkid

这是怎么回事：
xor(x,全1-x)=0

这个异或难道不应该全是1吗？怎么变零了?

〇〇

是全1，我错了，但是从结果看，确实是94楼那样互斥

〇〇

同一个数，和全零异或得a，和全一异或得b，ab中必有一个数1的位数少于总位数的一半，题目要求大于总位数一半，所以全零和全一必有一个不能用，同理，其他和为全一的数对，也只能取其一。

〇〇

因为数都是对称的，任取一个数开始，第二个数有2^(n-1)种选择，到第n-1个数只有一种选择

〇〇

把数对压缩为正好有所需的1的，并且把98楼的思路加入，6行取4个，比90楼快了点
with recursive n as (select i-1 n from generate_series(1,64)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,6)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and (n1.n#n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)=4)
,t as(select 1 lv,array[n1,n2]a from p
union all
select lv+1,a||array[n] from t,n where n>a[lv+1] and array_position(a,63-n)is null  and lv+1= ( select count(*) from p q, unnest(a) u(c) where n1=c and

n2=n)
)
select max(lv)+1 from t;
?column?
----------
        4
(1 行记录)


Time: 2871.206 ms (00:02.871)

〇〇

再把99楼第一步限制为0（根据对称性不影响结果总列数），就很快了
with recursive n as (select i-1 n from generate_series(1,64)t(i))
    ,b as (select 1<<(i-1) b from generate_series(1,6)t(i))
,p as(select n1.n n1,n2.n n2
      ,count(*) cnt
  from n n1, n n2, b
where n1.n<n2.n
       and (n1.n#n2.n)&b.b>0
group by n1.n ,n2.n
having count(*)=4)
,t as(select 1 lv,array[n1,n2]a, n1#n2 n3 from p where n1=0
union all
select lv+1,a||array[n],n3#n from t,n where n>a[lv+1] and n<>63-n3 and array_position(a,63-n)is null  and lv+1= ( select count(*) from p q, unnest(a) u

(c) where n1=c and n2=n)
)
select max(lv)+1 from t;