题解：CF2195F Parabola Independence

Amoribus · 2026-03-07 18:25:12 · 题解

要是两两连边，求图的最大独立集，是不可行的。这是个 NP-hard 问题。

注意到偏序关系是解决这个问题的重要手段。

当两个二次函数没有交点时，必有 f_i>f_j 或 f_i<f_j 恒成立。

设 f_i=a_ix^2+b_ix+c_i，f_j=a_jx^2+b_jx+c_j。

要使 f_i-f_j=a_dx^2+b_dx+c_d>0（a_d=a_i-a_j,b_d=b_i-b_j,c_d=c_i-c_j） 恒成立，

只要 a_d=b_d=0,c_d>0 或 a_d>0,\Delta=b_d^2-4a_dc_d<0。可以 O(1) check。

为了简便思考，当 f_i>f_j 恒成立时我们连一条 i\to j 的边。不难发现，合法的独立集一定是图上的一条路径。

然后记 F(i) 为到达节点 i 的最长路，G(i) 表示从节点 i 出发的最长路。F(i) 直接拓扑排序 + dp，G(i) 建反图然后拓扑排序 + dp 均可求出。

然后对于节点 i，答案为 F(i)+G(i)-1。