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))。