首页 > 其他 > 详细

【题解】Luogu P4436 [HNOI/AHOI2018]游戏

时间:2019-02-18 21:49:23      阅读:179      评论:0      收藏:0      [点我收藏+]

原题传送门

\(n^2\)过百万在HNOI/AHOI2018中真的成功了qwqwq

先将没门分格的地方连起来,枚举每一个块,看向左向右最多能走多远,最坏复杂度\(O(n^2)\),但出题人竟然没卡(建议JSOI的出题人好好学学)

#include <bits/stdc++.h>
#define N 1000005
#define getchar nc
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    register int x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
int n,m,q; 
int a[N],is[N],vis[N],l[N],r[N];
inline void dfs(register int x)
{
    if(vis[x])
        return;
    int L=x,R=x,ok;
    do{
        ok=0;
        if(L<=a[L-1]&&a[L-1]<=R)
        {
            ok=1;
            dfs(L-1);
            L=l[L-1];
        }
        if(L<=a[R]&&a[R]<=R)
        {
            ok=1;
            dfs(R+1);
            R=r[R+1];
        }
    }while(ok);
    l[x]=L,r[x]=R;
    vis[x]=1;
}
int main()
{
    n=read(),m=read(),q=read();
    for(register int i=1;i<=m;++i)
    {
        int x=read(),y=read();
        a[x]=y;
    }
    is[1]=1;
    for(register int i=1;i<=n;++i)
    {
        is[i+1]=is[i];
        if(a[i])
            ++is[i+1];
    }
    ++m;
    for(register int i=1;i<=n;++i)
        if(a[i])
            a[is[i]]=is[a[i]];
    for(register int i=1;i<=m;++i)
        dfs(i);
    while(q--)
    {
        int x=is[read()],y=is[read()];
        if(l[x]<=y&&y<=r[x])
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

【题解】Luogu P4436 [HNOI/AHOI2018]游戏

原文:https://www.cnblogs.com/yzhang-rp-inf/p/10398062.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!