6.3 练习

Topcoder 12505 CharacterBoard

我们考虑如果能够枚举长度,那么每个字符对应回原串的位置就是固定的了,这样我们就可以直接 2626 的剩下字符个数次方得到答案。

但是事实上字符串的长度可能到达 10910^9 ,这么考虑肯定是不行的。但是仔细想一想会发现,对于多数长度,你的 n×m100n \times m \le 100 个字符根本不会有冲突。而有冲突的长度,必然是某两个字符之间差距的约数。因此我们直接枚举每两个字符之间的差距,然后枚举这个差距的约数,然后单独计算这些长度即可。剩下的长度直接用等比数列求和。

Topcoder 12349 RockPaperScissors

实际上要做的就是条件概率的计算。由于卡牌之间不可区分,我们算出一共抽出了 aa 个石头,bb 个布,cc 个剪刀的情况下,下一张卡抽出第 ii 张卡的概率即可。

这个东西可以这样计算:先把第 ii 张卡丢掉再剩下的卡中算出现 (a,b,c)(a,b,c) 这种情况的概率,最后再把这张卡合并进去。这样做复杂度是 O(n5)O(n^5) 的。这里 dpdp 里面有组合数,所以需要把组合数写进转移里面,不然肯定会炸精度。

最后我们再做一个 dpdp ,设 dp[a][b][c]dp[a][b][c] 表示到现在抽出了 (a,b,c)(a,b,c) 这个状态,最优决策下期望得分是多少。转移就是枚举一下下一轮出什么以及下一轮来什么,选最优的转移即可。

复杂度 O(n5)O(n^5) ,空间 O(n4)O(n^4) ,需要略微卡空间。

##Topcoder 12339 FencingPenguins

其实这个颜色的限制很没用,可以转化成每条选择的边不能分开两个相同颜色的企鹅,那么可以转化成某些边可以选择,求出选择若干条边,使得每个多边形内部至少有一个企鹅的方案数。

这个问题我们可以区间 dpdp 解决。具体来说,我们设 g[l][r][0/1]g[l][r][0/1] 表示 lrl \sim r 没有封口,这段区间形成了一个多边形,并且这个多边形内部是否有企鹅。然后再设 f[l][r]f[l][r] 表示 lrl \sim r 的答案。这个题可以天然地断环成链,因为选择的是一条弦而不是弧,所以你做完后的 f[1][n]f[1][n] 一定可以涵盖所有弦的选择。

考虑转移,对于 gg 我们需要枚举最后一条边在哪里,然后这条边里面 l+1,k1l+1,k-1ff 来转移,剩下的继续用 gg 来转移。还需要讨论一下最后会不会获得企鹅。对于 ff 我们可以枚举第一个多边形的位置,这里就需要枚举第一个多边形的起点和终点 k,tk,t ,于是转移就是 g[k][t]×f[t+1][r]g[k][t] \times f[t + 1][r] 这个东西。复杂度 O(n4)O(n^4)

Topcoder 16616 UniqueMST

以前的题解

\