AGC015E – Mr.Aoki Incubator

题意:

给出很多条河流,类似y=v_i\ast x+ x_ i 的格式,然后,所有河流只有y轴右边有。。。每次你可以污染一条河,然后一条被污染的河会污染和他相交的所有河(所有河都流向x正半轴,然后污染不会污染往回走),询问让所有线都被污染的方案数。。。

分析:

非常牛逼的dp题,然后agc的E根本不会做,只能磨磨代码维持生活。
我们先把所有线按照x_i排序,然后我们考虑,当一条河被污染的时候,被传染的范围是什么。。。
然后我们发现,x_jx_i大的区域,以最高的满足v_j \lt v_i的线为界。。。在下方则以最下方的满足v_j>v_i的线为界。。。
于是乎,我们把问题转换成的,给你一个1到n的序列和n的区间,询问有多少种覆盖方案。。。
接下来我们就可以dp了。。。
我们设dp[i]表示用了前i种区间的方法,然后维护前缀和。。。

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,LL>
#define db double
#define fi first
#define se second
const LL N=5e5+10;
const LL inf=0x3f3f3f3f;
const LL mod=1e9+7;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n;
struct Node{double k,b;}node[N];
bool cmp(Node a,Node b){return a.b<b.b;}
double maxn[N],minn[N];
int find_L(int l,int r,double k,int ret)
{
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(maxn[mid]>k) ret=mid,r=mid-1;
        else l=mid+1;
    }
    return ret;
}
int find_R(int l,int r,double k,int ret)
{
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(minn[mid]<k) ret=mid,l=mid+1;
        else r=mid-1;
    }
    return ret;
}
int L[N],R[N],ri=0;
vector<int> vec[N];
LL sum[N],dp[N];
void solve()
{
    sum[0]=dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i]=(sum[i-1]-(ri?sum[ri-1]:0)+mod)%mod;
        sum[i]=(sum[i-1]+dp[i])%mod;
        for(int j=0;j<vec[i].size();j++)
            ri=max(ri,vec[i][j]);
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++) scanf("%lf %lf",&node[i].b,&node[i].k);
    sort(node+1,node+n+1,cmp);
    minn[n]=node[n].k;maxn[1]=node[1].k;
    for(int i=2;i<=n;i++) maxn[i]=max(maxn[i-1],node[i].k);
    for(int i=n-1;i>=1;i--) minn[i]=min(minn[i+1],node[i].k);
    for(int i=1;i<=n;i++) L[i]=find_L(1,i,node[i].k,i);
    for(int i=1;i<=n;i++) R[i]=find_R(i,n,node[i].k,i);
    // for(int i=1;i<=n;i++) cout<<maxn[i]<<" ";puts("");
    // for(int i=1;i<=n;i++) cout<<minn[i]<<" ";puts("");
    // for(int i=1;i<=n;i++)
        // printf("%lf %lf %d %d\n",node[i].k,node[i].b,L[i],R[i]);
    for(int i=1;i<=n;i++) vec[R[i]].push_back(L[i]);
    solve();
    printf("%lld\n",((sum[n]-(ri?sum[ri-1]:0))%mod+mod)%mod);
    return 0;
}

关于“AGC015E – Mr.Aoki Incubator”我的1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注