某岛

… : "…アッカリ~ン . .. . " .. .
March 30, 2013

2013腾讯编程马拉松复赛第一场(3月29日)

A. 略。
B. idfs() 或者 bfs() 均可。
C. 组合 DP。
。。首先忽略同组之间的差异。。那么最后就是乘以一堆阶乘。。这里记作 pi 。。。
。。然后 f[i] 表示当前有 i 个粘着点时的方案数。。。
。。那么转移就是枚举上回的粘着点、本回分成多少组以及破坏了上回多少个粘着点。。。
。。复杂度 O(n^4)。。(450*50*50*50)。。。
D. 做法有很多。。个人比较倾向暴力矩形切割。。。
E. 裸 AC 自动机 DP。。。

代码。。
https://github.com/lychees/Exercise/tree/master/Online%20Contest/%E7%AC%AC%E4%BA%8C%E5%B1%8A%E8%85%BE%E8%AE%AF%E7%BC%96%E7%A8%8B%E9%A9%AC%E6%8B%89%E6%9D%BE/%E5%A4%8D%E8%B5%9B