娱乐 算法挑战三则——构造之美

[jas]

p1:

剧透

one-hot编码，a_i = 2的i次方？

p2:

剧透

1.动作1，申明x=n+1
2.动作1，申明x=n+2
————这时所有数都联通，且路径唯一

3.动作2，申明x=2~n，y=1，记查到的距离为d1(x)
4.动作2，申明x=3~n，y=2，记查到的距离为d2(x)
————根据a_x到a_1、a_2的距离,以及a_1、a_2之间的距离，可以判断a_x、a_1、a_2三个数谁在中间

构造数列c(x)
c(x) =     0,     if  x=1
          d1(x),     if  d2(x)-d1(x)=d1(2)
         -d1(x),     else

5.动作3，申明b(x) = c(x) - min_c + 1, 其中min_c是数列c(x)的最小值
如果猜错，翻转一下，申明b(x) = n - c(x) + min_c

一共操作2n+1次 

----------

 fix:
 b(x)的顺序是[1, n, 2, n-1, 3,...]。还要取奇偶次项，才能拼成[1, 2, ..., n]

 

 

p3:
 

剧透

n=13的示意图，每根红线分别提供2^0~2^6种路线。控制红线通断，就能组合出0~127之间任意路线数

n=60时，能画30条红线，最大路线数2^30-1大于10^7，所以能构造刚好为 k的路线数

----------

update:

 

五月 2, 2023，由jas修改