AtCoder Kenkoooo Recommendation
Fido_Puppy
·
·
个人记录
1 月 5 日
[ABC226H] Random Kth Max
先考虑怎么求 E(\min(X_i))。
转化成 \min \ge x 的概率之和。
E(\min(X_i))=\int_0^{100} \mathrm{d}x \prod_{k=1}^n \dfrac{\max(0, r_k - \max(x, l_k))}{r_k-l_k}
将值域分成 \Theta(n) 段，每段对一个 \Theta(n) 次多项式积分，就可以在 \Theta(n^2) 的复杂度内算出答案。
然后考虑求 E(\mathrm{kthmax}(X_i))。
套上 min-max 容斥：
E(\mathrm{kthmax}(X_i)) = \sum_{S \subseteq \{1,\ldots,n\}} {(-1)}^{|T|-K} \binom{|T|-1}{K-1}E(\min_{k \in S}X_k)
由于积分的线性性，可以先算出所有多项式的和再积分。
将值域分成 \Theta(n) 段，这样每个 X_i 如果被选上，对最终要积的多项式的贡献是乘上一个一次多项式。
设 f_{i,j} 表示前 i 个变量，选了 j 个，要积的多项式之和。
枚举值域段 \Theta(n)，动态规划状态数 \Theta(n^2)，决策数 \Theta(1)，转移 \Theta(n)，总复杂度 \Theta(n^4)。
[AGC025D] Choosing Points
不会构造，看了题解。
一个比较牛的性质是只考虑距离不为 \sqrt {D_1} 的性质，将不能同时选的点之间连边，连完后是一张二分图。
证明：
当 D 是奇数时，设 x^2+y^2=D，则 x, y 一奇一偶，考虑从一个点出发，假设能经过奇数条边回到自身，则横纵坐标变化量之和为 0，但是横纵坐标变化量之和为奇数，假设不成立。
当 D 是偶数时，分两种情况讨论：
-
D \equiv 2 \pmod 4
-
D \equiv 0 \pmod 4
然后考虑既有不为 \sqrt{D_1} 又有不为 \sqrt{D_2} 的限制怎么做，根据 \sqrt{D_1} 的限制连一张二分图，根据 \sqrt{D_2} 的限制也连一张二分图，然后根据在第一张图中是黑色或白色，在第二张图中是黑色或白色，能够将原图染成一张四分图，取其中颜色数最多的点即可。