hihoCoder太阁最新面经算法竞赛3题解

2
0

Problem A

简单的动态规划。

我们可以先算出一共有多少个 合法 的二进制数。 用f[n][x]表示n位二进制数,最后1位是x(x取值0或1),合法的二进制数的数目。 于是有:

f[n][0] = f[n - 1][0] + f[n - 1][1]  
f[n][1] = f[n - 1][0];

Problem B

DFS求出区域R中包含的所有单位正方形。R的周长显然是由若干单位正方形的边组成的。具体来说如果一条边两侧的正方形一个是R区域内>的,一个是R区域外的,那么这条边就属于R周长的一部分。

Problem C

动态规划。

设S[1..n]是一个长度为n的字符串,best(S)是S的最短压缩,那么best(S)可能为三种形式中最短的一种:

  • 原串形式:best(S) = S。例如CCD最短压缩就是CCD本身。
  • 拼接形式: best(S[1..n]) = best(S[1..i]) + best(S[i+1..n])。例如AAAAAAAAAABABABCCD的最短压缩9(A)3(AB)CCD,可以视为由best(AAAAAAAAAABABAB) = 9(A)3(AB) 和 best(CCD) = CCD 拼接而成。
  • 嵌套形式: best(S[1..n]) = k(best(S[1..n/k])),其中k>1且是n的约数,S是由k个S[1..n/k]循环拼接而成。 例如HIHOHIHOCODERHIHOHIHOCODER有循环节HIHOHIHOCODER,所以best(HIHOHIHOCODERHIHOHIHOCODER) = 2(best(HIHOHIHOCODER))。

1 answer(s)

1

谢谢分享,一直在等第三题的题解!

write answer 切换为英文 切换为中文


转发分享