图森未来2020校招笔试题官方题解

首先可以使用最暴力的做法，即循环计算后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位开始反向进行几千次比较，就一定可以结束整个循环（如果这几千次比较都没有比出大小，那么一定是平局）。当然也可以根据数据的具体情况进一步缩小这个上界，不过对最终程序的结果不会有任何影响。

这道题是本套题目的签到题。

题目2、卡车牌照

这道题是一道纯考察代码实现能力的题目，希望考察的是工作中可能遇到的编写复杂逻辑的代码而不出错的能力。

当输入的最深层级为k时，输出的大小为2^k+1行，2^(k+1)+1列。

填充到数组中时可以每次都将四个角填充上“+”，边界填充上“-”和“|”符号。这样虽然会导致某些位置被重复填充多次相同的符号，但是对输出不会有任何影响。带来的好处则是实现更加简单，甚至可以实现函数模块化的完成某个层级中字符的填充。

模块化地实现这个程序而不是把所有代码堆砌到主程序中可以很好的避免代码中小的错误，以及可以更容易地编写测试代码调错。这是我们在工程中追求的“good smell”，我们也希望同学们可以从这道题目中体会到提升代码的工程质量对于复杂代码编写的重要性。

这道题依旧是一道签到题，但是我们这次设置了占比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一样，更工程化的代码有助于实现的逻辑清晰，也会让测试更加简便。把代码全部写到一个主程序中很容易导致出错且很难调试。