Google Kickstart 2017 Round E题解

E轮是Google的校招笔试轮次了。

A. Copy & Paste

求通过三种操作构造一个字符串S的最少操作次数

  1. 在生成串尾部添加一个字符
  2. 将生成串的一个子串拷贝到剪贴板
  3. 将剪贴板中的内容添加到生成串尾部

可以贪心么?考虑$abcabcabab$,复制$ab$其实和复制$abc$再复制$ab$一样好(之前算错了),所以尽可能地多复制即可。即在位置$i$处时,尝试在$[0, i)$中找到最长的$[j, j+len)$等于$[i, i+len)$。
然而这个思路是错的,考虑下面的$’a’*11$字符串,最好的方法是等到3个再复制,比上面的按2的幂复制要少1次。
正确的解法是DP,表示字符串完成状态需要一维数组,如何表示剪贴板的状态呢?再加两维数组。$dp[i][ps][pl]$表示完成第$i$个字符时,剪贴板的内容为$[ps, ps + pl]$时至少需要多少操作。
Naive的方法是根据不使用剪贴板、使用当前剪贴板、更新剪贴板并使用三种情况进行讨论。由于更新剪贴板需要一个二重循环,所以在认为字符串判等是常数时间下,复杂度为$O(n^5)$。
为了降低复杂度,可以使用另开一个数组,或者使用$dp[i][0][0]$来表示所有$dp[i][ps][pl]$的最小值。因为我们肯定是使用最小值来更新的。这样复杂度就变成了$O(n^3)$了。
AC代码

B. Trapezoid Counting

梯形(trapezoid)是有且仅有一条平行边的凸(convex)四边形(quadrilateral),等腰(isosceles)梯形是两非平行边长相等的梯形。有一堆木条,要求从中选4个拼成一个等腰梯形,问有多少组方案。注意长度相等的两根木条仍然被认为是不同的木条。
很straightforward的题目了,首先梯形成立条件是短三边和大于最长边。然后讨论三种情况$2i+1j1k$、$2i+2j$(不可行由于是矩形)、$3i+j$。小数据挂了一发,因为$3i+j$没有判断梯形成立条件。
AC代码
后来看别人的题解发现其实$O(n^3)$是可以被卡掉的(Google还是比较仁慈的,毕竟不是ACM)。

C. Blackhole

用三个半径相等的球如何将三个点覆盖。the total set of points covered by at least one sphere must form a single connected area这句话是啥意思?
小数据由于只在一条线上,直接除以6就可以了。