【2021noip模拟赛day3】D. 双面扑克

发布时间:2022-07-05 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了【2021noip模拟赛day3】D. 双面扑克脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

【题意】

k张扑克正反面各有一个数字范围1-n,q次询问l-r能否用扑克表示出来

【2021noip模拟赛day3】D. 双面扑克

 

 【分析】

没看到数据范围以前觉得是一个网络流的题

看了数据范围果断放弃

考虑把正反两个值之间连一个边,那么我们得到的图中,如果一个连通块为树,那么意味着这个树中最小-最大的区间不能被包含在l-r内

那么询问就变成了是否l-r没有包含任何一个不合法区间

我们将不合法区间按左端点降序排列,然后从右往左扫,计算出每个点最远向右扩展的位置nxt[i]

然后对于询问比较一下r和nxt[l]即可

 

【代码】

#include<bITs/stdc++.h>
using namespace std;
tyPEdef long long ll;
const int maxn=1e5+5;
int n,k;
int fa[maxn],minn[maxn],maxx[maxn],eg[maxn];
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
struct line
{
    int l,r;
}area[maxn];
bool cmp(line a,line b)
{
    return a.l<b.l;
}
int rlim[maxn];
int main()
{
    freopen("yy.in","r",stdin);
    freopen("yy.out","w",stdout);
    scanf("%d%d",&amp;n,&k);
    for(int i=1;i<=n;i++) fa[i]=minn[i]=maxx[i]=i;
    for(int i=1;i<=k;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int fx=find(x),fy=find(y);
        if(fx!=fy)
        {  
            minn[fx]=min(minn[fx],minn[fy]);
            maxx[fx]=max(maxx[fx],maxx[fy]);
            eg[fx]+=eg[fy]+1;
            fa[fy]=fx;
        }
        else eg[fx]++;
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int fi=find(i);
        if(i==fi && eg[i]<=maxx[i]-minn[i]) 
        {
            area[++cnt].r=maxx[i]; area[cnt].l=minn[i];
        }
    }
    sort(area+1,area+cnt+1,cmp);
    int rpos=n;
    for(int i=n;i>=1;i--)
    {
        while(cnt && area[cnt].l==i)
        {
            rpos=min(rpos,area[cnt].r-1);
            cnt--;
        }
        rlim[i]=rpos;
    }
    int q;
    scanf("%d",&q);
    int x,y;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        if(y>rlim[x]) PRintf("Non");
        else printf("Yesn");
    }
    return 0;
}

 

脚本宝典总结

以上是脚本宝典为你收集整理的【2021noip模拟赛day3】D. 双面扑克全部内容,希望文章能够帮你解决【2021noip模拟赛day3】D. 双面扑克所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。