jzoj5399 【NOIP2017提高A组模拟10.7】Confess

题意

给定n+1(n<=6e3且n为偶数)个大小为n的集合，集合里的数都在[1,2n]内。
请求出任意一对交集大小大于n/2的集合。

分析

毛都没看出来，所以就打了50分的bitset.
我们考虑一下他交集大小的期望，也就是任意两对交集大小的平均数。
设有元素i的集合有ci个，任意一对ci都有1的贡献。
E=∑C(ci,2)C(n+1,2)

考虑ci如何取值能够最小化E。倘若Emin>=n/2则必定有解。
C(ci,2)可以近似的看为ci^2。又因为 ∑ci=n(n+1) ，也就是ci的和给定。
要使 ∑ci2 最小，应平均分ci.
因为 (a+k)2+(a−k)2=2a2+2k2>=2a2 ,
所以 ci=n+12 .代入算一下就可以得出 Emin=n2 .
因此必定有解，又因为最小期望跟所求一定，所以可以大胆猜测有很多解。事实上解的级别是O(n)的。我们估计一下，先不管其他规则，无解时 E<=n2−1 ，那么要想使得E>=n/2，则至少需要补 n/2−(n/2−1)1/n约等于n 个交满的解。因此解的级别可以估计成O(n)的。