CF1444D Rectangular Polyline(dp&构造)题解

发布于 2021-10-30  34 次阅读


题目大意

$T$ 组数据。

每组数据中给定长度依次为 $l_1,l_2,\dots,l_h$ 的 $h$ 条水平线段和长度依次为 $p_1,p2,\dots,p_v$ 的竖直线段。

要求求出一种方案使竖直线段和水平线段交替首尾相接,且不在除端点外的其它地方有交点。

若有解,输出 Yes 并输出一种方案,若无解,输出 No

$1 \le T \le 200$,$1 \le \sum h,\sum v,l_i,p_i \le 10^3$。

解题思路

首先当竖直线段和水平线段的条数不一样时,一定无解(题目中要求交替连接)。

然后我们发现我们要构造出一个首尾相接的封闭图形,可以视作一个点在平面上移动,最后回到原点的轨迹。那么水平方向上向右与向左移动的距离相等,竖直方向上向上与向下移动的距离也相等。

也就相当于,我们要对题目给出的两组线段都进行以下操作:选出一些线段,使得被选出的线段和剩下的线段长度相等。如果没法选出这样一些线段,那么也无解。

这玩意儿显然可以用简单背包 $dp$ 解决。$f_{i,j}$ 表示 $i$ 条线段,总长为 $j$ 的方案存不存在。

然后我们发现这个 $dp$ 的两维分别是线段数量(设为 $n$)和线段总长度(设为 $C$)。 发现题目中 $n \le 10^3$,$C \le 10^6$,我们直接进行背包,时间复杂度是 $O(n\times C)$ 的,无法通过。

但是我们发现我们 $f$ 数组都是 bool 类型,所以我们可以用 bitset 优化转移。

所以时间复杂度变成了 $O(\frac{n \times C}{w})$,这玩意儿大概是 $10^7$ 左右,可以通过。

然后我们就知道了一个状态可不可以被转移。但是怎么通过这个 $f$ 数组求出两部分分别是那些线段呢?

我们现在有一个目标值 $target$,表示我们需要取出一些数,让它们的和为 $target$。

那么我们从后往前扫过每个物品,如果在加入这个值为 $val$ 的前,已经可以到达 $target-val$ 的状态,那么加上这个物品之后就可以到达 $target$ 的状态,也即这件物品是到达 $target$ 状态的一部分。

大概就是一个从后往前,从结果状态倒着拆出物品的过程。

然后我们就把两堆线段分别拆成了总长度相等的两部分。

我们手动玩几个样例,发现这个路径可以分成三部分。

pic1.png

我们发现我们要尽量让路径不相交,那么我们一定是在 $OA$ 段中,水平方向先走长的后走短的,竖直方向先走短的后走长的,形成一个类似于凸包的东西(见图中铅笔线),或者说,下凸的形状。

同样,在 $BO$ 段中我们水平方向先走长的后走短的,竖直方向先走短的后走长的,形成一个上凸形状。

那 $AB$ 段呢?发现在这段上我们只能向左和向上走,且总长是固定的,所以说在这一段中我们是没法走出图中那个框的,也就不可能与其他线段相交。所以这一段其实怎么走都可以

那么这么构造一定是对的么?

$AB$ 段我们上面已经提到,是不可能与其他线段相交的,所以我们只需要考虑剩下的 $OA$ 段与 $OB$ 段相交的情况。

我们考虑 $OA$ 与 $OB$ 两条线段,显然只在端点处相交。$OA$ 段横向和竖向线段的段数相等,设为 $k$,再设线段长度的前缀和为 $sum_{x1} \sim sum_{xk}$,线段长度的前缀和为 $sum_{y1} \sim sum_{yk}$则线段 $OA$ 的斜率 $\frac{sum_{yk}}{sum_{xk}}$,而我们考虑图中凸包的第 $i$ 个顶点 $X$(第 $i$ 个顶点即 $i$ 次一横一竖后的位置),发现线段 $OX$ 的斜率为 $\frac {sum_{yi}}{sum_{xi}}$。而我们知道我们是从长到短选横向线段,从短到长选纵向线段,所以有 $sum_{xi} \ge \frac{i}{k}sum_{xk}$,$sum_{yi} \ge \frac{i}{k}sum_{yk}$,那么就有 $k_{OX}=\frac{sum_{yi}}{sum_{xi}} \le \frac{\frac{i}{k}sum_{yk}}{\frac{i}{k}sum_{xk}}=\frac{sum_{xk}}{sum_{yk}}=k_{OA}$,也即 $k_{OX} \le k_{OA}$。

或者如果你不想看这一段事实上并不难的数学推导,你也可以感性理解:斜率是纵比横的结果,而我们横向从长到短选,纵向从短到长选,保证了纵是最小前缀,横是最大前缀,所以斜率小于把所有线段都选上的纵比横。

所以我们发现任意一个点与 $O$ 连线的斜率都比 $OA$ 小(当然,除了 $O$ 和 $A$ 这两个点本身),也即 $OA$ 段都在 $OA$ 下方。

$OB$ 段同理,可以得到 $OB$ 段都在线段 $OB$ 上方。而 线段 $OA$ 和线段 $OB$ 除了顶点外不相交,所以 $OA$ 段和 $OB$ 段除了顶点外不相交。

证毕。

Code

感觉还是挺简洁的写法。

代码的实现方法是把横、竖分成两份,排序后把线段少一份的作为 $OA$ 段的横向线段,线段多一份的作为 $OB$ 段的横向线段。然后直接拼到一起模拟从零点开始移动的过程。

由于横竖线段总数相等,所以这么做一定可以构造出上面讲到的三段。

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}
const int N=1005,M=1000005;

int n,m,suma,sumb;
int a[N],b[N];
bool Nosol=false;
bitset <M> f[N];
vector <int> a1,a2,b1,b2,A,B;

void Dp(){
    for (int i=1;i<=n;++i) f[i].reset(); f[0][0]=true;
    for (int i=1;i<=n;++i) f[i]=f[i-1]|(f[i-1]<<a[i]);
    int tar=suma/2; a1.clear(),a2.clear();
    if ((suma%2) || (!f[n][tar])){ Nosol=true; return void(); }
    for (int i=n;i>=1;--i){
        if ((tar>=a[i]) && (f[i-1][tar-a[i]])){ a1.push_back(a[i]); tar-=a[i]; }
        else a2.push_back(-a[i]);
    }
    for (int i=1;i<=m;++i) f[i].reset(); f[0][0]=true;
    for (int i=1;i<=m;++i) f[i]=f[i-1]|(f[i-1]<<b[i]);
    tar=sumb/2; b1.clear(),b2.clear();
    if ((sumb%2) || (!f[m][tar])){ Nosol=true; return void(); }
    for (int i=m;i>=1;--i){
        if ((tar>=b[i]) && (f[i-1][tar-b[i]])){ b1.push_back(b[i]); tar-=b[i]; }
        else b2.push_back(-b[i]);
    }
}

int main(){
    //freopen("CF1444D.in","r",stdin);
    //freopen("CF1444D.out","w",stdout);
    int T=read();
    while (T--){
        n=read();
        suma=0,sumb=0;
        for (int i=1;i<=n;++i)
            a[i]=read(),suma+=a[i];
        m=read();
        for (int i=1;i<=m;++i)
            b[i]=read(),sumb+=b[i];
        if (n!=m){ printf("No\n"); continue; }
        Nosol=false;
        Dp(); if (Nosol){ printf("No\n"); continue; }
        if (a1.size()>a2.size()){ swap(a1,a2); for (auto& it : a1) it=-it; for (auto& it : a2) it=-it; }
        if (b1.size()<b2.size()){ swap(b1,b2); for (auto& it : b1) it=-it; for (auto& it : b2) it=-it; }
        sort(a1.begin(),a1.end(),greater<int>()); sort(b1.begin(),b1.end());    // +
        sort(a2.begin(),a2.end()); sort(b2.begin(),b2.end(),greater<int>());    // -
        A.clear(),B.clear();
        for (auto it : a1) A.push_back(it); for (auto it : a2) A.push_back(it);
        for (auto it : b1) B.push_back(it); for (auto it : b2) B.push_back(it);
        printf("Yes\n"); int x=0,y=0;
        for (int i=0;i<A.size();++i){
            x+=A[i]; printf("%d %d\n",x,y);
            y+=B[i]; printf("%d %d\n",x,y);
        }
    }
    return 0;
}

我们无法选择过去,但我们可以改变未来。