洛谷P4436 游戏 [HNOI/AHOI2018]

时间：2022-06-22 19:32:30

正解:拓扑排序

解题报告:

传送门!

首先不难想到可以把麻油锁的一段先直接缩成一个点,然后预处理每个点能到达的最左和最右节点,然后就能O(1)地查询辣

所以难点在于预处理

可以想到,对于它给定的关于锁的信息,如果y<x,那要从x到x+1必然是只能从左往右走的,所以如果x到x+1有锁且y<x,那么x能延展到的最右端一定就是x+1能延展到的最右端(反过来显然是布星的昂,,,因为x+1要往左要有钥匙,但是钥匙又在左边,显然是布星的

所以对于y<x,就可以先拓展x+1的右边,然后再拓展x的左边,如果能到达y就直接把x的最右端=x+1的最右端

反之亦然

然后就可以连边,比如说现在发现应该先拓展x+1再拓展x,就连一条从x+1到x的边

然后现在就变成了一个图,要求顺序直接拓扑排序就好

这里拓展以下学个新知识,大概港下拓扑排序的定义

拓扑排序指的是一个对点的排列顺序,保证对序列中的任意一个点x,所有x的前驱都在其前面

然后拓扑排序的求法是在连边的时候再记录一个in[x]:x点有几个前驱

然后首先找到所有in=0的点,加入队列,然后就开始做

每次把队列的队首弹出,加入拓扑排序尾端,然后对这个点进行处理:对所有它的后继点的in---

很好理解趴,就相当于in[x]变成了记录x的前驱中还有几个麻油进序列

如果然后没进去一个in就--嘛,然后当in==0的时候说明它所有前驱已经进队了就都在它前面辣,所以它就也可以加入队列辣

然后可能说得麻油很清楚,,,因为它这个里面用到辣两个队列,,,就不好区分,,,凑合着理解趴×

然后考虑这个图拓扑排序之后得到的就是拓展顺序嘛,所以就拓扑排序然后按照那个顺序统计就好

然后就做完辣!

然后最后说一下就是,缩成一个点这个事儿,说起来挺简单,实现起来还是有点儿麻烦,,,可以理解成离散化,和离散化差不多(就是麻烦点儿QAQ

所以我还是想先解释一下cal(统计每个节点能到达的左右端点的函数)函数中的语句QwQ

while(dr[l[x]] || dr[r[x]]<n)//左右端点有一个麻油枚举到尽头就可以继续做QwQ
{
　　if(dr[l[x]] && rht[dr[l[x]-1]+1] && rht[dr[l[x]-1]+1]<=dr[r[x]]){l[x]=l[l[x]-1];continue;}

　　　　//这里,重点港下,,,好麻烦我天TT首先dr[l[x]]保证x还麻油拓展到边界,然后判断rht[dr[l[x]-1]+1]!=0,这里我说下,首先要知道x的单位是块(我把缩点形成的叫块!好表述些w)然后l,r,lft,rht的下标都是块,单位也是块(第几个块这样儿的w然后拿后面一个式子港,看后面w
　　if(dr[r[x]]<n && lft[dr[r[x]]]>=dr[l[x]-1]+1){r[x]=r[r[x]+1];continue;}

　　//判断限制它右边界继续拓展的锁的钥匙在不在能拓展的左边界的范围内,那就找x能拓展的左边界和钥匙位置比大小就好,然后理一下这几个变量,这里为了区分,将缩点后的称作块,缩点前的称作节点. r[x]:x能延展到的最右块,dr[r[x]]:x能延展到的最右节点,lft[dr[r[x]]]:最右节点的锁的位置,over
　

　return;//左右都不能拓展辣显然返回
}

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define rg register

#define gc getchar()

#define ll int

#define ls(x) (x<<1)

#define rs(x) (x<<1)|1

#define rp(i,x,y) for(rg ll i=x;i<=y;++i)

#define mb(i,x) for(rg ll i=head[x];i;i=edge[i].nxt)

const ll N=1e6+;

ll n,m,q,in[N],l[N],r[N],lft[N],rht[N];

vector<ll>to[N];

vector<ll>dr;

queue<ll>Q,wk;

il ll read()

{

    rg char ch=gc;rg ll x=;rg bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ad(ll x,ll y){++in[y];to[x].push_back(y);}

il ll fd(ll x){return lower_bound(dr.begin(),dr.end(),x)-dr.begin();}

il void pre()

{

    n=read();m=read();q=read();

    rp(i,,m){ll x=read(),y=read();y<=x?lft[x]=y:rht[x+]=y;dr.push_back(x);}

    ++m;dr.push_back();dr.push_back(n);sort(dr.begin(),dr.end());

    rp(i,,m){l[i]=r[i]=i;if(rht[dr[i-]+])ad(i-,i);if(lft[dr[i]])ad(i+,i);}

}

il void topsort()

{

    rp(i,,m)if(!in[i])Q.push(i);

    while(!Q.empty())

    {

        ll nw=Q.front(),sz=to[nw].size();Q.pop();wk.push(nw);

        rp(i,,sz-){if(!--in[to[nw][i]])Q.push(to[nw][i]);}

    }

}

il void cal(ll x)

{

    while(dr[l[x]] || dr[r[x]]<n)

    {

        if(dr[l[x]] && rht[dr[l[x]-]+] && rht[dr[l[x]-]+]<=dr[r[x]]){l[x]=l[l[x]-];continue;}

        if(dr[r[x]]<n && lft[dr[r[x]]]>=dr[l[x]-]+){r[x]=r[r[x]+];continue;}

        return;

    }

}

il void work(){while(!wk.empty()){cal(wk.front());wk.pop();}}

il void as(){while(q--){ll x=fd(read()),y=fd(read());if(l[x]<=y && y<=r[x])printf("YES\n");else printf("NO\n");}}

int main(){pre();topsort();work();as();return ;}

不开O2过不去,,,QAQ

相关文章