笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 P3357 【最长k可重线段集问题】

posted on 2020-03-18 08:34:29 | under 题解 |

感觉这题压根没有正常的题解啊……

喷的原因可以去看我的上一篇题解:P3358Sol 戳我

由于这题需要用到 P3358 的前置芝士,所以大家如有需要可以去做完 P3358 这题再来。


给定平面 $\text{x-o-y}$上 $n$ 个开线段组成的集合 $\text{I}$,和一个正整数 $\rm k$ 从开线段集合 $\text{I}$ 中选取出开线段集合 $\text{S}\in \text{I}$, 使得在 x 轴上的任何一点 $\text{p}$ , $\text{S}$ 中与直线 $\text{x}=\text{p}$ 相交的开线段个数不超过 $\text{k}$ ,且 $\sum_{\text{z} \in \text{S}}|z|$ 达到最大。这样的集合 $\text{S}$ 称为开线段集合 $\text{I}$ 的最长 $\text{k}$ 可重线段集的长度。

对于任何开线段 $\text{z}$,设其端点坐标为 $( x_0 , y_0 )$ 和 $( x_1 , y_1 )$,则开线段 $\text{z}$ 的长度 $|\text{z}|$ 定义为: $|z| = \lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloor$。对于给定的开线段集合 $\text{I}$ 和正整数 $\text{k}$ ,计算开线段集合 $\text{I}$ 的最长 $\text{k}$ 可重线段集的长度。

$1\leq n\leq500,$ $1 \leq k \leq 13$.

发现和「区间集」那题没啥区别,只用关心 $x$ 轴,换一下长度的求法…好像有点不对?因为如果存在两条线段均垂直于 $x$ 轴,且两条线的左右端点分别都是 $x_i$ ,这样的话,建出图来这俩线段是串在一起不交的,但是本质上应该交。

于是自然想到,要换种表示方法在 $x$ 轴上表示一个线段。那么如果是在数轴上,比较简单的方式就是扩域。每个线段 $i$ 的左右端点 $(l_i,r_i)$ 变换成 $(2\times l_i,2\times r_i)$——听上去很不错,这样的话就相当于每个下标多了一个空间。那么对于一个左右端点相同的区间 $(x,x)$ ,就可以连边成 $(2\cdot x,2\cdot x + 1)$。这样的话,原本左右端点不用的区间也要改——由于那些相同的区间右端点加了 $1$,所以如果存在这样两个线段 $(p,p)$ 、 $(p,q)$ ,那么原本不交的两个区间,在扩域之后变成了相交的 $(2p,2p+1)$、$(2p,2q)$ 。

处理方式很简单,对于一个 $p\not=q$ 的区间 $(p,q)$,连边 $(2p+1,2q)$ 即可。思考这么做为啥是对的。对于原本存在的两个均不垂直 $x$ 轴的线段,他们如果相交,那么交的那一端,$r_1-l_2\geq 1$ ;如果不交,那么有 $l_2-r_1\geq 1$ 。扩域之后就变成了 $\geq 2$ 。所以如果只是左端点增加 $1$ ,根本不影响判定。

int len[N] ;
pint base[N] ;
int _n, _k, tot ;
map <int, int> Id, buc ;
map <int, int> :: iterator t ;

int calc(int a, int b, int c, int d){
    return (int)sqrt((ll)(a - c) * (a - c) + (ll)(b - d) * (b - d)) ;
}
int main(){
    int a, b, c, d ;
    cin >> _n >> _k ; cnt = -1 ;
    memset(head, -1, sizeof(head)) ;
    for (int i = 1 ; i <= _n ; ++ i){
        cin >> a >> b >> c >> d ;
        len[i] = calc(a, b, c, d) ;
        base[i].ft = a << 1 ;
        base[i].sc = c << 1 ;
        if (a == c)
            ++ base[i].sc ;
        else ++ base[i].ft ;
    }
    for (int i = 1 ; i <= _n ; ++ i){
        if (!Id.count(base[i].ft)) buc[base[i].ft] ++ ;
        if (!Id.count(base[i].sc)) buc[base[i].sc] ++ ;
    }
    add(0, 1, _k, 0) ; add(1, 0, 0, 0) ;
    for (t = buc.begin() ; t != buc.end() ; ++ t)
        Id[t -> ft] = ++ tot ; _s = 0 ; _t = tot + 1 ;
    for (int i = 1 ; i <= tot ; ++ i)
        add(i, i + 1, I, 0), add(i + 1, i, 0, 0) ;
    for (int i = 1 ; i <= _n ; ++ i){
        //cout << Id[base[i].ft] << " " << Id[base[i].sc] << endl ;
        add(Id[base[i].ft], Id[base[i].sc], 1, -len[i]) ;
        add(Id[base[i].sc], Id[base[i].ft], 0, len[i]) ;
    }
    n = _t + 1 ; ek() ;
    cout << -ans << endl ;
}