2018.10.11 滴滴笔试

发表于 |

总结：这两道题目的题意表述得也太差了吧，明明几句话能说清楚的东西我不知道这是在写什么。
共两道算法题：1 give up, 1 AC

1. DIST(give up)

在平面直角坐标系上，问从(x1,y1)到(x2,y2)有多少条路径，使得
1）对路径上经过的每一点(x,y)，x和y至少有一个是整数。
2）路径的长度为 |x1 - x2| + |y1 - y2|
3）对于路径的每一点(x,y)，都保证x <= y
答案可能很大，输出其mod 1e9+7的结果

输入描述：
每组测试数据一行，包括x1, y1, x2, y2__四个整数__，且-1e6 <= x1, y1, x2, y2 <= 1e6
其中20%的数据：max(x1, x2) <= min(y1, y2), 0 <= x1, y1, x2, y2 <= 100
其中20%的数据：(x1, y1) = (0,0), 0 <= x2, y2 <= 100
其中20%的数据：-100 <= x1, y1, x2, y2 <= 100
其中20%的数据：(x1, y1) = (0,0), 0 <= x2, y2 <= 1e6
其中20%的数据：-1e6 <= x1, y1, x2, y2 <= 1e6

输出描述：
每行一个数字，代表路径的数量

样例输入：
0 0 0 0
0 0 1 1

样例输出：
1
1

这道题也是天秀啊，我都得靠猜“出题人应该是这个意思吧”来做这道题，后面发到论坛上去求助，大家都没人敢说‘这道题肯定是xx意思’，都只能说 ‘应该是xx意思，否则这道题没意义’
让我恶心的不想写题解。

2. Hilert曲线

在数学分析中，有这样一个问题：能否用一条无限长的线，穿过任意维度空间里面的所有点？答案是肯定的，而且不止有一种这样的曲线，hibert曲线就是其中的一种，它在边长n = 2,4,8的图上的索引效果如下：

以边长为2的图像举例，左下角的方格编号为1，左上角为2，右上角为3，右下角为4，其余图像也可以一次找到遍历网格的顺序。
下面我们希望给定任何边长为2的乘方的网格矩形，给出基于Hilbert曲线索引的网格顺序，全部以左下角第一个被索引的元素，索引值为1，输出完整矩阵的索引值

输入描述：
一个数字N（N <= 256）

输出描述：
一个矩阵，矩阵中包含了每一个元素的索引顺序

样例输入：
4

样例输出：
6 7 10 11
5 8 9 12
4 3 14 13
1 2 15 16

思路分析：
以边长从2到4变换进行分析，边长为2的矩阵定义为矩阵A，边长为4的矩阵定义为矩阵B
可以把矩阵B分为4个部分，左下，左上，右上，右下
可以发现左上右上两个部分和矩阵A的索引顺序完全一致。
左下和右下则是矩阵A的某种转置
这个规律也适用于边长从4到8的矩阵变换过程

在代码中，我定义new_1,new_2,new_3,new_4，分别代表左下、左上、右上、右下的四个矩阵，它们都可以从A变换而来

这道题中有一个关键点，那就是矩阵切片赋值（a = b[::]）后，修改赋值矩阵会使原矩阵变动，这是我之前一直没注意到的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
N = int(input())
res = [[1]]
a = 1
while a < N:
    m,n = len(res), len(res[0])
    new_1 = list(zip(*res[::-1]))[::-1]
    new_1 = list(map(list,new_1))

    new_2 = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            new_2[i][j] = res[i][j] + a*a

    new_3 = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            new_3[i][j] = res[i][j] + 2*a*a

    new_4 = list(zip(*res))
    new_4 = list(map(list,new_4))
    for row in new_4:
        for i in range(len(row)):
            row[i] += 3 * a*a
    # 合并矩阵
    for i in range(len(new_1)):
        new_1[i].extend(new_4[i])
        new_2[i].extend(new_3[i])
    new_2.extend(new_1)
    # 将新矩阵赋值给res，重新迭代
    res = new_2
    a *= 2

for row in res:
    print(' '.join(map(str,row)))