图森未来2020校招笔试题官方题解
官方题解：
卷一：https://www.nowcoder.com/test/20723898/summary
题目1、简单卷积：
这道题是本套试卷的签到题，目的是为了给大家热身和测试系统。
同时为了防止大家因为粗心没有看清公式，我们特地调整了题目中卷积的计算方法。
具体解法只需要按照公式写循环即可。
题目2、迷宫难题：
本套试卷的基础考核题，考察的是应用和实现基础算法的能力。
这道题是标准的网格图（稀疏图）最短路的题目，可以使用各种宽度优先搜索或最短路的算法解决。
题目3、旋转数字：
首先可以使用最暴力的做法，即循环计算后k位并从第k位开始依次对比。
其次，因为数字的循环是有规律的，所以我们可以通过数学计算在O(1)的复杂度下对于任意k值获得第k位的数字。这里虽然没有优化暴力做法的复杂度，但是为下面的做法提供了可行的解决方案。
注意虽然k的最大长度有10^9，但是因为t和s的位数最大只有9位，所以两个无限长的数字的循环节最长分别只有9*9=81位，而两个循环节长度（记为T和S）的最小公倍数满足 LCM(T, S) < T*S < 81 * 81 = 6561。所以，只需要从第k位开始反向进行几千次比较，就一定可以结束整个循环（如果这几千次比较都没有比出大小，那么一定是平局）。当然也可以根据数据的具体情况进一步缩小这个上界，不过对最终程序的结果不会有任何影响。
卷二：https://www.nowcoder.com/test/20723906/summary
题目1、寻找十字
这道题是本套题目的签到题。
题目2、卡车牌照
这道题是一道基础考核题，考察的是基础算法的实现和组合的能力。
首先因为这道题需要车牌号是素数，那么首先要考察的一定是如何检查一个数是素数。
首先最简单的方式是每次进行试除，这样单次查找素数的时间复杂度是O(sqrt(n))，对于题目中的情况大概每次需要试除1000个数（sqrt(10^6)=1000）。
但是因为需要试除的次数很多，所以一个更好的方式是预处理一个素数表，这样之后就可以使用O(1)的时间复杂度在表中查找某个数是不是素数。使用试除的办法查找的话复杂度是O(n*sqrt(n))=O(n^(3/2))，对于n=10^6的情况来说太大了。所以这里可以利用筛法预处理素数表，复杂度大概是O(n*lg(lgn))。
以上的求素数方法已经可以通过这道题目的所有数据了。但是实际上我们还可以使用一些其它的素数测试方法来完成，比如Miller-Rabin算法可以让我们不需要预处理素数表也能够使用O(c)的时间复杂度判断某个数字是不是（极大概率是）素数，其中c为常数。因为Miller-Rabin的判断错误率仅有1/(4^c)，所以取一个不是很大的c就可以完成素数判断。具体算法和证明不在这里赘述，有兴趣的同学可以去自行查阅资料。
在拥有了判断素数的方法后，这道题就变成了一道简单的宽度优先搜索，即每个数字的54个可能的后续状态（对于30%的数据是36个）中，只有素数是可到达的，问最少经过多少次转移可以到达最终状态。
题目3、服务器布局：
这道题是一道纯考察代码实现能力的题目，希望考察的是工作中可能遇到的编写复杂逻辑的代码而不出错的能力。
当输入的最深层级为k时，输出的大小为2^k+1行，2^(k+1)+1列。
填充到数组中时可以每次都将四个角填充上“+”，边界填充上“-”和“|”符号。这样虽然会导致某些位置被重复填充多次相同的符号，但是对输出不会有任何影响。带来的好处则是实现更加简单，甚至可以实现函数模块化的完成某个层级中字符的填充。
模块化地实现这个程序而不是把所有代码堆砌到主程序中可以很好的避免代码中小的错误，以及可以更容易地编写测试代码调错。这是我们在工程中追求的“good smell”，我们也希望同学们可以从这道题目中体会到提升代码的工程质量对于复杂代码编写的重要性。
第三套：https://www.nowcoder.com/test/20723913/summary
题目1、公司扩招：
这道题依旧是一道签到题，但是我们这次设置了占比20%的大范围数据。
对于80%的小数据，只要直接按照公式计算整个数列即可，唯一要注意的是必须每次计算后立刻取模，且C++要使用long long或类似的大范围类型存储中间结果，不然可能会导致溢出。
而对于剩下20%的数据，因为数据规模达到了10^9999，所以很明显可以看出这是一道查找循环节的题目。
可以发现，其实这道题结果数列的每一个数字是多少，只和这个数字的前两个数字有关。如果数列不同位置的前两个数字是相同的，那么后一个数字一定是相同的。
而在对100003取模之后，前两个数字有大约10^12中不同的组合方式。这里可能会有同学直接放弃这个做法，但是其实只要写一个很短的程序稍微试验一下就会发现，对于题目中可能的100种k值，实际的循环节都远远没有10^12这么大。所以，只要先计算循环节长度，之后再进行一次高精度的取模运算，就可以根据循环节得出最终结果。
这里的高精度取模运算本质上是高精度除法，但是因为除数是非高精度数，所以实际上是对小学时竖式除法的编程模拟，即使对没有特殊学习过如何实现高精度除法的同学也并非那么困难。当然，因为考试时间有限，这20%的数据只属于加分项，即使没有得到这20分也是完全没有问题的。
题目2、快递机器人：
这道题是一道考察算法掌握和一些简单数学推理的题目。
最简单的做法是直接对所有的快递进行搜索，检查所有可能的情况，复杂度为O(n!)。
注意即使是这种做法中，因为机器人是不能向y轴负方向移动的，所以搜索的过程中也要注意排除非法的解。
进一步考虑，因为机器人不能向y轴负方向移动，所以可以只在y轴每一层的内部进行搜索，层与层之间的移动是已经固定了顺序的。但是因为y轴每一层收取快递所需要的时间花费是和来到这一层时的初始位置相关的，所以搜索的复杂度依然很高。
再进一步，当我们确定了每层的初始位置和结束位置时，实际上可以使用O(1)的时间复杂度计算出收取全部快递所需要的时间花费，因为一定要经过最左和最右两个快递的位置。因为每一层的搜索结束位置就是下一层的初始位置，而向y轴正方向移动的次数是固定的，所以这时就可以以层数和结束位置为状态，使用动态规划的方式优化搜索的速度了。
而实际上我们还可以发现，只要在每一层从最左侧或最右侧的快递位置向上走，就一定能够找到最优解，即我们每一层的开始/结束位置只和状态有关。具体的证明这里不展开，留给同学们作为思考题。这样，就可以将有效状态的数量大幅减少，从而可以用动态规划解决这道题的所有数据范围。
题目3、另一个快递机器人：
这道题是考察代码实现能力的题目，其中也包括了考察简单的算法能力。
通过阅读题目可以发现，这道题最终的结果计算包括两部分，即楼之间移动所需要花费的时间和楼内移动所需要花费的时间。且因为送快递的顺序是固定的，所以这两部分时间的计算没有任何重叠，可以分别计算并直接累加起来。
对于楼内移动时间的计算，实际上要计算的问题可以规约为：从1层到k层之间有多少个数位中包含4的数字？因为实际上最高的楼层号只有10^6，所以这里其实预处理一下所有楼层号就可以了。当然也可以使用容斥原理来计算，但是因为实现过于复杂所以这里不推荐。
对于楼间移动时间的计算，实际上就是一道最短路的问题，因为前面的题目也考察了很多最短路的知识，所以这里不再赘述。
最后，因为可能的情况比较多，所以实际实现中还需要注意代码的准确性。和题目2.3一样，更工程化的代码有助于实现的逻辑清晰，也会让测试更加简便。把代码全部写到一个主程序中很容易导致出错且很难调试。
海康威视工作强度 84人发布
