by PKU

A

D[J]

E[J]

G[G]

给定圆锥表面积,求一个最大的圆锥体积

三分

K

求一个n边形,划分为三角形和四边形的划分方式

递推

回忆卡特兰数的递推公式

$C(n) = \sum_{i=2}^{n-1} C(i)C(n-i+1)$

这个即划分为三角形的方案

对于一条边(1-n),其必属于一个三角形或四边形,
对于三角形我们枚举另一个顶点,对于四边形我们枚举另一条边

$f(n) = \sum_{i=2}^{n-1} f(i)f(n-i+1) + \sum_{i=2}^{n-2} \sum_{j=i+1}^{n-1} f(i)f(n-j+1)f(j-i+1)$

令$g(n) = \sum_{i=2}^{n-1} f(i)f(n-i+1)$

$f(n) = g(n) + \sum_{i=2}^{n-2} f(i)g(n-i+1)$

即枚举第一个点,将剩下的分为两部分

M[G]

两个01矩阵,判断其中一个能否通过另一个删除一些行/列得到

暴力枚举删除那些列,然后贪心check每一行