E轮是Google的校招笔试轮次了。
A. Copy & Paste
求通过三种操作构造一个字符串S的最少操作次数
- 在生成串尾部添加一个字符
- 将生成串的一个子串拷贝到剪贴板
- 将剪贴板中的内容添加到生成串尾部
可以贪心么？考虑$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就可以了。
