洛谷5302 [GXOI/GZOI2019]特技飞行

Luogu

BZOJ

LOJ

分析

首先考虑怎么求出所有交点。

注意到 $a$ 与 $b$ 有交(假设 $y_{a,0}<y_{b,0}$ )当且仅当 $y_{a,1}>y_{b,1}$ 。

那么可以用 $\mathrm{set}$ 来维护 $y_{x,1}$ ,然后暴力求出所有交点。

因为交点个数 $\leq 500000$ ,所以可以过。


容易发现 $a,b$ 的贡献和 $c$ 的贡献是独立的。

先考虑怎么计算 $c$ 的贡献。显然只要求出有多少个交点被正方形覆盖了即可。

那么将坐标轴旋转 $45^\circ$ ,然后直接扫描线即可。可以用树状数组来维护。


最后考虑计算 $a,b$ 的贡献。

先考虑一种极端的情况。因为对向交换不改变相对顺序,所以全部对向交换一定是可行的。

考虑另一种极端情况即对向交换尽量少。显然对于每个环,最少要对向交换 $len-1$ 次。那么最少要对向交换 $n-\text{环数}$ 次。


于是这题就做完了。具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const double eps=1e-10;

struct node { double x,y1,y2; int op; } p[N*10];
bool operator <(node a,node b) { return a.x<b.x; }

int n,k,A,B,C,X0,X1;
int Y0[N],Y1[N];
int tot,sum,len,num;
int f[N],g[N];
double o[N*10];
ll ans1,ans2;
set<pair<int,int> > S;

inline bool cmp(int a,int b) { return Y1[a]<Y1[b]; }

//树状数组
int c[N*10];
inline int lowbit(int x) { return x&-x; }
inline void add(int x,int y) {
    for (;x<=len;x+=lowbit(x)) c[x]+=y;
}
inline int query(int x) {
    int res=0;
    for (;x;x-=lowbit(x)) res+=c[x];
    return res;
}

int main() {
    n=read(),A=read(),B=read(),C=read(),X0=read(),X1=read();
    for (re int i=1;i<=n;++i) Y0[i]=read();
    for (re int i=1;i<=n;++i) Y1[i]=read();
    //求交点
    for (re int i=n;i;--i) {
        for (set<pair<int,int> >::iterator it=S.begin();it!=S.end();++it) {
            pair<int,int> j=*it;
            if (j.first>Y1[i]) break;
            double k=1.0*(Y0[j.second]-Y0[i])/(Y0[j.second]-Y0[i]+Y1[i]-j.first);
            double x=X0+k*(X1-X0),y=Y0[i]+k*(Y1[i]-Y0[i]);
            p[++tot]=(node){x+y,x-y,0,0};
            o[++len]=x-y;
        }
        S.insert(make_pair(Y1[i],i));
    }
    sum=tot;
    //扫描线
    k=read();
    for (re int i=1;i<=k;++i) {
        int x_=read(),y_=read(),r=read();
        int x=x_+y_,y=x_-y_;
        p[++tot]=(node){x-r-eps,y-r-eps,y+r+eps,1};
        p[++tot]=(node){x+r+eps,y+r+eps,y-r-eps,-1};
        o[++len]=y-r-eps,o[++len]=y+r+eps;
    }
    sort(p+1,p+tot+1),sort(o+1,o+len+1),len=unique(o+1,o+len+1)-o-1;
    for (re int i=1;i<=tot;++i) {
        p[i].y1=lower_bound(o+1,o+len+1,p[i].y1)-o;
        p[i].y2=lower_bound(o+1,o+len+1,p[i].y2)-o;
    }
    for (re int i=1;i<=tot;++i) {
        if (!p[i].op) ans1+=(query(p[i].y1)>0);
        else add(p[i].y1,1),add(p[i].y2,-1);
    }
    //求环
    for (re int i=1;i<=n;++i) f[i]=i;
    sort(f+1,f+n+1,cmp);
    for (re int i=1;i<=n;++i) g[f[i]]=i;
    for (re int i=1;i<=n;++i)
        if (f[i]!=i) f[g[i]]=f[i],g[f[i]]=g[i],++num;
    //求答案
    ans1=ans1*C+1ll*sum*A,ans2=ans1+(sum-num)*(B-A);
    if (ans1>ans2) swap(ans1,ans2);
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 21 PM

发表评论