JLOI2016 毒瘤题解

这玩意就是我在上一篇里面记错的那个树形DP

我复制一下……

就一树形DP裸题。

设计状态 f[i][j] 表示在点 i 上,子树前 j 层未覆盖的最小答案。

然后 g[i][j] 表示子树全部覆盖完毕,又多往上覆盖了 j 层的答案。

然后转移就是了。注意最后更新要扫两遍。

为啥要倒着一遍啊?

不要脸的抄的学长的代码QAQ

把圆的左右端的点离散下来做扫描线。

用set维护。如果当前点的父亲是一个左半拉圆,那么当前层次要 +1

如果父亲是右半拉圆,就是和父亲是一样的。

注意要在正确的时机正确地删除元素。

还有注意比较的时候。

贪心+KMP

先枚举覆盖顺序,然后讨论一下:

当前的这一个子串放哪儿。

下一个和这一个相交不相交。

最大:第一个要尽量向前放。尽量不相交。相交最长。

最小:尽量相交,相交最短。不放这个位置去放下个位置就是个子问题,可以记搜。

组合数美滋滋。

首先DP。设 dp[i][j] 表示 前 i 门科目,有 j 个人被碾压的方案数。

然后 DP 的转移就是乘乘组合数。

\mathrm{dp[i][j]}= \sum_{k=j}^{n} \mathrm{dp[i-1][k]} \cdot C_k^{k-j} \cdot C_{n-k}^{rk-1-(k-j)}

最后每个 dp[i][k] 都要乘一个东西:成绩的合法分配方案。

那么就是乘这个:

d_i=\sum_{k=1}^{U_i}k^{n-rk} \cdot (U_i-k)^{rk-1}

(不超过)n次多项式,取点插值就行了。

容斥。别忘了正方形可以斜着放。

总方案是

\sum_{i=1}^{\min(n,m)}(i \times (n-i+1) \times (m-i+1)) \mod p

然后枚举两个点就可以算出 2, 3, 4 个点不可行的方案。

然后一个点不可行的方案很麻烦,

我们按照点把坐标系分三部分,然后有左面的宽 l ,右面的是 r ,高是 h

然后计算方案。

如果 h \leqslant \min (l,r) 那么比较好算。

如果不呢?减去 h-\min(l,r) 的部分!

公式见下,建议自己推导。

然后就基本上做完啦!

可以用 map 缩短代码。

到此为止就屠龙啦!

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据