20zr提高组十连测day7

http://www.zhengruioi.com/contest/734/problem/1633

毒瘤啊

拿到144的好成绩,惊人的排进了前20??

AKEEAK了

我的做法 : 直接枚举最小生成树即可,那个 $b>100a$ 直接最短路,最短路树就是最小生成树!!!!

下场 : 38分跑路

服了

std:

首先有一个考场上观察出来的性质:把所有a的边都加进去连成几个连通块,那么我们每个连通块内部一定只能走a的边得到最短路

然后拓展一下 : 一个最短路是合法的,当且仅当他在一个连通块内是这样走的外,在连通块外的路径不能多次经过一个连通块

相当于我们不能绕过a连通块又回来,即a->b->a虽然最短路最短但是不行!

所以就可以状压所有连通块经过性,ljh的做法,orzljh

于是,你又会发现,如果一个连通块大小小于等于3,一定不会出现这样的路径

因为无论如何都是 $a+a<b+b$ 这样子,也就是说绕路一定更劣

这样我们只需要状压大于等于4的

复杂度 $O(2^{n/4}*m*polylog)$ n/4是18左右很好过??

鬼畜贪心题...

考虑每个限制,找到其连通块内深度最小的那个点!设为限制点

然后做完了....检查所有的这样的点深度最大的点是否合法就好了....

因为如果有点在他的子树内,他不是深度最大的

如果有点在他的子树外,这个点是某一限制的最大的点,所以一定会是再向上接近其他限制都不能了....

就....没了QAQ

$a_i$ 都一样, $f_i$ 表示用i个人的分组方案

然后直接枚举多少人和i分成一组就好了...

$f_i=\sum_{j=1}^{a_i}\binom{i-1}{j-1}f_{i-j}$

$f_{i,j}$ 表示考虑了前i个人,剩下j个人

将人按照 $a_i$ 从大到小排序即可

f_{i,j}=f_{i-1,j-1}+\sum_{l=1}^{a_1}\binom{j+l-1}{l-1}f_{i-1,j+l-1}

相当于枚举有多少人分进新的一组里面!

因为之前的人一定满足大于等于 $a_i$ 所以可以直接做....

这个式子每层拍个FFT就 $O(n^2log)$ 了...

std:

这个状态还能再优化!!!

$f_{i,j}$ 表示已经分好所有队伍人数大于等于i的,然后剩下j个人

f_{i,j}=\sum_{l=0}^{\frac i n}f_{i-1,j+i*l+b_i}*\frac{(j+i*l)!}{(i!)^l*j!*l!}

枚举有多少组

后面这个东西就是考虑所有人随意排列

然后 $i!^l$ 就是所有组内部人排序无意义

$l!$ 就是所有组排序无意义

$j!$ 就是剩下的那些人排序无意义

注意 $b_i$ ,是因为我们下一步一定不能再用他们了,所以这一次一定要用光了

GG!

夏晓光(loveJY)的博客