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

[reflectK]

大家好，这里是reflectK~

在解决某类算法问题的时候，比起繁琐的计算，也许我们可以通过直接构造一组方案或做法来完成问题，让我们来试一下解决下面这三道问题吧！

 

p1：

引用

给出一个数 n，输出一个数列 a_1，a_2 ... a_n 。满足对任意 a _ i，a _ j , a _ k：（ i , j , k 都属于 1~n ）

a_i +a_j != a_k

a_i xor a_j != a_k

其中 xor 是按位异或。

 p2：

引用

给定一个未知数列 a_1，a_2 ... a_n 保证它是 1 到 n 的一个排列。

现在你有最多4*n次操作，每次操作你可以做以下三个动作之一：

1. 申明一个数 x 满足 1<x<2n+1 ，对于 1 到 n 的每个数 i ，如果 x-i 也在 1 到 n 中，在 i 和 x-i 中连接一条边。

2. 申明两个数 x,y 查询 a_x 到 a_y 之间的最短距离，如果两者不联通，返回 -1 。

3.申明 n 个数 b_1,b_2 ... b_n，满足它是 1 到 n 的一个排列，表示这是你对数列 a 的一个猜测。

在所有操作用完之前，请确定给定的数列a_n。

 p3：

引用

From HPCPC2023

假设有一个 n * n 的矩阵，你可以把其中任意地方设置为 0（有障碍），其余为 1 （无障碍）。

现在有栖从左下角的端点开始移动到右上角的端点。    显然有栖不能经过有障碍的地方。

那么，可以计算出有栖有 k 条不同的路线。( k<=10^7 )

现在，给定 k ，请构造一个地图使得路线数刚好为 k，且 n<=60 。

 

第一个发布答案的，T1，T2有100节操奖励，T3有200节操奖励w

[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修改

[reflectK]

9 小时前，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)
————根据一个数到1、2的距离,以及1、2之间的距离，可以判断它、1、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次

p3:
 

  隐藏内容

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

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

 

p1 是正确的，不过独热编码有点杀鸡用牛刀了www有更简单的做法，考虑 n 很大的情况，可以有一种更简单的生成方法。

 

p2 和 p3 都差不多是最佳解法了！不过原题目中 p2 的限制次数是 2n-1 次，p3 有 n<=30 且 k<=1e9 ，不过只要有了这种思想，解决问题还是不难的www

五月 2, 2023，由reflectK修改