2020腾讯编程比赛热身赛题解

零、背景

前段时间有幸报名上了腾讯的2020编程比赛。

按照规则，前百名有文化衫。

本来我是很自信，自己进不了前百名，与文化衫无缘了的。

结果看到了最后一条规则：坚持参加所有场比赛的人也会有文化衫。

我依旧是很自信了，不过是文化衫我肯定能得到。

周六晚上做了一下热身赛的四道题，熟悉一下比赛环境。

结果看了第一题就不会了，后来一搜索，发现是ZOJ的题目。

当年参加ACM比赛的时候，ZOJ 就是大家的一场噩梦，题贼难了。

周日晚上凌晨的时候热身赛已经结束了，下面来分享下这四道题吧。

一、简单题

题意：给 n 个数字，每次选最大数字和最小数字，两个数字替换为差的绝对值。
问这样不断操作下去，是否可以使得所有数字相等，如果可以，是哪个数字？

歧义：首先题目有点歧义，最大数字与最小数字有多个时怎么处理？
这时候看英文原题的优势就到了，英文中 integer 是单数，所以是一个，哈哈。

思路：首先证明有答案。

证明如下：
第一步，最大值减去负数可以变成正数。
第二步，最大值减去0可以变成正数。
第三步，如果最值不相等，相减可以使得最大值减小。
第四步：既然最大值可以不断降低，那不能降低时所有值就相等了。

证明了存在答案，那接下来就是评估复杂度了。
第一步和第二步都可以在O(n)内完成。
而第三步则不好评估复杂度，我随机找了几个数据，模拟一下发现数字是按log级下降的。
所以复杂度应该是 O(n log(n))

二、简单数字游戏

题意：给 n 个数字，每次可以从中选择2个数字并相乘，进行 m 次。
求所有乘积之和最小。

思路：普通思想是排列组合体，数据量巨大。

通过分析发现一些组合明显比另一些更优。

我们随意假设四个数字a<=b<=c<=d，可以证明a*d + b*c是最小的。
所以结论是先排序，然后依次选择最大和最小的数字相乘即可。

当然，由于只需要进行m次操作，肯定只取前面的2m个数字啦。

三、九的数量

题意：给两个日期，问这个时间区间内的所有日期总共有多少个数字 9.

解释：一个日期是yyyy mm dd的数字形式，一位位看，求有多少个9。

思路：年数也不多，一年年的加就行了。

当然，之前给大家分享过一个方法。
求 [a,b] 的时候，可以通过 [0,b]与[0,a-1]相减的方式间接得到。

另外，有余有多次询问，对于完整的一年答案是固定的，可以把结果缓存起来。

四、神秘的乘法

题意：如上图，两个数字的叉积是每一位依次相乘，结果去掉前缀0后，按字符串的形式连起来。

解释：比如5678 * 2 的叉积是 10121416。

思路：最暴力的是递归枚举，但是不知道会不会超时。

画出99乘法表后，分析最高位，竟然可以发现一个规律。
如果两个数字相乘是两位数，那两位数的高位肯定小于这两个数字，反之亦然。

根据这个规律，我们就可以用来剪枝了，这样就不会超时了。

代码比较长，这里就不贴代码了。

五、最后

没想到热身赛的题都这么难，未来的比赛可以想象，能做出一道题就感谢苍天大地了。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code