首页 > 题解 > bzoj 3622 已经没有什么好害怕的了

bzoj 3622 已经没有什么好害怕的了

Description

Input

Output

Sample Input

4 2

5 35 15 45

40 20 10 30

Sample Output

4

HINT

输入的2*n个数字保证全不相同。

还有输入应该是第二行是糖果,第三行是药片

题解

首先算一下应该有多少对$A_x > B_x$,发现$2x + k = n$,也就是$x = {n – k \over 2}$,那么$x + k = {n + k \over 2}$,那么$n + k \over 2$肯定要是个整数,所以可以先判下无解的情况。

现在的限制是很强的,要求恰好有k组,也就是说剩下的一定要是小于的情况。做这种容斥题就可以先考虑弱化它的限制,然后用容斥再满足它的限制。比如这种恰好k的就可以先dp出至少k的再容斥出来恰好的情况。

考虑一下至少k的怎么dp。$f[i][j]$表示A和B分别排序后,dp到了A组的第i个数字,A比B大的有j组。

这样的话因为两个数组都是有序的所以可以很方便地定位一段A比B大的前缀,设这段前缀一共有p个数,里面一开始已经选了j个,还剩下p-j个没有选,所以递推f[i+1]的时候就是:

$f[i][j] += f[i – 1][j]$(不限制第i个要大)
$f[i][j] += f[i – 1][j – 1] \times (p – j)$(限制第i个要大)

接下来就是容斥一下,设$g[i][j]$为有恰好j个小。我们发现对于一个$ f[i][j]$它的非确定A大于B的那些数对中,有$ (i−j)!$种排列。那么按照这种容斥

$$g[i][j]=f[i][j]\times (i−j)! − \sum_{k = j + 1}^n g[i][k] \times C^i_j$$

只要对于$i = n$的时候容斥一下就行了,g也不用求。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×