首页 > 其他分享 >图论练习

图论练习

时间：2023-07-04 09:04:51浏览次数：43  
标签：图论 return int 练习 Tree long fa MAXN

图论练习

学长的题果然恐怖如斯

CF1458D Flip and Reverse

这个操作看着很奇怪

\(0\)先看成\(-1\)

那可操作的区间就是和为\(0\)

对每一个前缀和的值建点,把每种元素看作边

那可操作的区间就是一个环

然后你会发现一个操作就是相当于是反着走这个环

这里我们考虑连成无向边

考虑连边的过程,除了起点和终点,每个点的度数都是偶数

那对于\(x\rightarrow(x-1)\),和\(x\rightarrow(x+1)\),如果\(x\)不是起点终点

那一定会有\((x-1)\rightarrow x\),\((x+1)\rightarrow x\)

如果走\(x-1\)是我原本的路径

那\(x\rightarrow(x-1)\rightarrow x\rightarrow(x+1)\rightarrow x\)

反向就是\(x\rightarrow(x+1)\rightarrow x\rightarrow(x-1)\rightarrow x\)

由此对于原图任意一条欧拉路都是满足的

对此我们只需贪心跑欧拉路即可,具体就是看跑\(0\)是不是还回得到\(0\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int T;
int n;
string S;
int cnt_node;
map<int,int>V;
int Edge[MAXN][2];
int Cdg[MAXN][2];
int Tp=0;
void dfs(int x)
{
    if(Tp==n)
    {
        return;
    }
    if(Cdg[x][0]&&Cdg[Edge[x][0]][1])
    {
        Cdg[x][0]--;
        ++Tp;
        printf("0");
        dfs(Edge[x][0]);
    }
    else if(Cdg[x][1])
    {
        Cdg[x][1]--;
        ++Tp;
        printf("1");
        dfs(Edge[x][1]);
    }
    else if(Cdg[x][0])
    {
        Cdg[x][0]--;
        ++Tp;
        printf("0");
        dfs(Edge[x][0]);
    }
}
int main()
{
    freopen("date.in","r",stdin);
    freopen("date.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        V.clear();
        for(int i=1;i<=cnt_node;i++)
        {
            Edge[i][0]=0;
            Edge[i][1]=0;
            Cdg[i][0]=0;
            Cdg[i][1]=0;
        }
        cnt_node=0;
        cin>>S;
        V[0]=++cnt_node;
        int Now=0;
        n=S.size();
        for(int i=0;i<S.size();i++)
        {
            int Op=S[i]-'0';
            int Vp=(Op==1)?1:-1;
            if(!V[Now+Vp])
            {
                V[Now+Vp]=++cnt_node;
            }
            Edge[V[Now]][Op]=V[Now+Vp];
            Cdg[V[Now]][Op]++;
            Now+=Vp;
        }
        Tp=0;
        dfs(1);
        printf("\n");


    }

}

CF827F Dirty Arkady's Kitchen

一眼看上去很像魔改最短路

但由于无法停留,所以这里如果是把横跳放在点上是行不通的,事实上这里和最短路也没太大关系,因为需要维护的是到达该点的时间区间

由于要反复横跳,所以这里我们需要奇偶分类

可以发现每个点的时间戳是几段区间

这里考虑动态加边,也就是我们考虑对\(l\)排序

可以发现如果对于边排序的话,这里有个优美的性质

考虑\(e_i\)连\(u,v\),你会发现\(u\)的最早到达时间一定小于等于\(l\)

考虑归纳证明,可以发现每个节点的最早都是\(l+1\)的形式,这里奇偶分类,所以是一定满足的

这启示我们记录动态加边时的最晚到达时间,如果其大于等于\(l\)则当前边可行并更新,这里我们可以反复横跳来达到目的

否则这里我们可以把这条不满足的边先存起来附在\(u\)上,等我们更新了\(u\)的最晚到达时间,我们就可以再把它加进去,不过他的\(l\)必须更新,因为我们要利用这个\(l\)算最早到达时间

可以发现每条边最多算两次

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int n,m;
struct Edge{
    int u,v,l,r,op;
    bool operator<(const Edge x)const{
        return l>x.l;
    }
};
int x,y,l,r;
int f[MAXN][2];
vector<Edge>Att[MAXN][2];
int main()
{
    freopen("date.in","r",stdin);
    freopen("date.out","w",stdout);
    memset(f,-1,sizeof(f));
    priority_queue<Edge>q;
    while(q.size())
    {
        q.pop();
    }
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d %d",&x,&y,&l,&r);
        q.push((Edge){x,y,(l)&1?(l):(l+1),(r-1)&1?(r-1):(r-2),1});
        q.push((Edge){x,y,(l)&1?(l+1):(l),(r-1)&1?(r-2):(r-1),0});
        q.push((Edge){y,x,(l)&1?(l):(l+1),(r-1)&1?(r-1):(r-2),1});
        q.push((Edge){y,x,(l)&1?(l+1):(l),(r-1)&1?(r-2):(r-1),0});
    }
    f[1][0]=0;
    if(n==1)
    {
        printf("0");
        return 0;
    }
    while(q.size())
    {
        Edge temp=q.top();
        q.pop();
        if(temp.l>temp.r)
        {
            continue;
        }
        if(f[temp.u][temp.op]>=temp.l)
        {
            int Tx=temp.r+1;
            if(temp.v==n)
            {
                printf("%d",temp.l+1);
                return 0;
            }
            if(Tx>=f[temp.v][temp.op^1])
            {               
                f[temp.v][temp.op^1]=Tx;
                for(int i=0;i<Att[temp.v][temp.op^1].size();i++)
                {
                    Att[temp.v][temp.op^1][i].l=temp.l+1;
                    q.push(Att[temp.v][temp.op^1][i]);
                }
                Att[temp.v][temp.op^1].clear();
            }
        }
        else
        {
            Att[temp.u][temp.op].push_back(temp);
        }
    }
    printf("-1");
}

CF1307F Cow and Vacation

每个加油站的可达性是可以划分等价类的

但对于每个点可达的范围是不能划分的

这里我们考虑拆分路径为\(\dfrac{k}{2}\)(方便\(bfs\),其实可以随便拆),为了解决小数问题可以先拆点

然后这里可以维护每个加油站距离为\(\dfrac{k}{2}\)的点并将其划分为等价类

我们发现两个点的可达性关键在于这是否存在两个点走\(\dfrac{k}{2}\)后在相同等价类

然后这里我们还可以发现对于大部分\((x,y)\),实际上我们就是要尽量往上爬

可以发现走的这\(\dfrac{k}{2}\)一定是朝着对方走的,具体证明画画图就行了

然后用倍增维护即可,注意会往下走

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
int n,k,r;
int m;
int x,y;
int fa[MAXN];
int cnt_node;
vector<int>g[MAXN];
int find(int x)
{
    if(fa[x]==x)
    {
        return fa[x];
    }
    fa[x]=find(fa[x]);
    return fa[x];
}
void unionn(int i,int j)
{
    fa[find(i)]=find(j);
    return;
}
int Dis[MAXN];
int dep[MAXN];
int dp[MAXN][21];
void bfs(int root)
{
    queue<int>q;
    q.push(root);
    dep[root]=1;
    while(q.size())
    {
        int temp=q.front();
        q.pop();
        for(int i=0;i<g[temp].size();i++)
        {
            int v=g[temp][i];
            if(dep[v])
            {
                continue;
            }
            dep[v]=dep[temp]+1;
            q.push(v);
            dp[v][0]=temp;
            for(int j=1;j<=20;j++)
            {
                dp[v][j]=dp[dp[v][j-1]][j-1];
            }
        }
    }
}
int LCA(int a,int b)
{
    if(dep[a]<dep[b])
    {
        swap(a,b);
    }
    for(int i=20;i>=0;i--)
    {
        if(dep[dp[a][i]]>=dep[b])
        {
            a=dp[a][i];
        }
    }
    if(a==b)
    {
        return a;
    }
    for(int i=20;i>=0;i--)
    {
        if(dp[a][i]!=dp[b][i])
        {
            a=dp[a][i];
            b=dp[b][i];
        }
    }
    return dp[a][0];
}
int Leap(int x,int d)
{
    for(int i=20;i>=0;i--)
    {
        if((d>>i)&1)
        {
            x=dp[x][i];
        }
    }
    return x;
}
int main()
{
    freopen("date.in","r",stdin);
    freopen("date.out","w",stdout);
    scanf("%d %d %d",&n,&k,&r);
    cnt_node=n;
    for(int i=1;i<n;i++)
    {
        scanf("%d %d",&x,&y);
        ++cnt_node;
        g[x].push_back(cnt_node);
        g[cnt_node].push_back(x);
        g[y].push_back(cnt_node);
        g[cnt_node].push_back(y);
        
        
    }
    for(int i=1;i<=cnt_node;i++)
    {
        fa[i]=i;
    }
    queue<pair<int,int> >q;
    for(int i=1;i<=r;i++)
    {
        scanf("%d",&x);
        q.push(make_pair(x,0));
    }
    
    while(q.size())
    {
        pair<int,int> temp=q.front();
        q.pop();
        //cerr<<"fuck";
        //cerr<<temp.first<<' '<<temp.second<<endl;
        if(temp.second==k)
        {
            continue;
        }
        
        for(int i=0;i<g[temp.first].size();i++)
        {
            int v=g[temp.first][i];
            unionn(v,temp.first);
            if(Dis[v])
            {
                continue;
            }
            Dis[v]=temp.second+1;
            q.push(make_pair(v,Dis[v]));
        }
    }
    
    scanf("%d",&m);
    bfs(1);
    while(m--)
    {
        scanf("%d %d",&x,&y);
        int Lca=LCA(x,y);
        int dist=dep[x]+dep[y]-dep[Lca]*2;
        if(dist<=2*k)
        {
            printf("YES\n");
        }
        else
        {
            int K=k;
            int Dx=(dep[x]-dep[Lca]);
          //  printf("%d???\n",Dx);
            int Tx;
            if(Dx>=k)
            {
                Tx=Leap(x,k);
            }
            else{
            //    printf("???\n");
                k-=Dx;
                int Txp=(dep[y]-dep[Lca]-k);
                Tx=Leap(y,Txp);
            }
            k=K;
            int Dy=(dep[y]-dep[Lca]);
            int Ty;
            if(Dy>=k)
            {
                Ty=Leap(y,k);
            }
            else
            {
                k-=Dy;
                int Typ=(dep[x]-dep[Lca]-k);
                Ty=Leap(x,Typ);
            }
            k=K;
        //    printf("%d %d %d %d %d %d??\n",Tx,Ty,k,Lca,find(Tx),find(Ty));
            if(find(Tx)==find(Ty))
            {
                printf("YES\n");
            }
            else{
                printf("NO\n");
            }
        }
        

    }   
}

CF1556G Gates to Another World

第一步都没想到。。。

把原题抽象到线段树上

这里如果要往上跳就必须满足兄弟子树还有值?

好像有点问题

考虑原问题相当于是对于每个线段树的节点左右子树对应叶子连边

这里我们可以处理出每个区间可能保留的时间,数量级大概是\(m\)

然后我们可以直接保留这个区间,区间就代表所有叶子,然后按上述方法连边即可

最后倒着动态加边即可

这里的边数是\(mn\)的,因为每个叶子节点连的边的数量是它祖先的数量

#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
using namespace std;
const int MAXN=2e5+5;
int n;
int m;
long long L[MAXN];
long long R[MAXN];
int Idt[MAXN];
long long lsh[MAXN];
long long x,y;
int T;
char s[105];
vector<pair<long long,long long> >Query[MAXN];
int Tdt[MAXN];
struct Seg{
    int lc,rc;
    int T;
}Tree[MAXN*50];
int root;
int cnt_node;
void Update(int &p,long long l,long long r,long long ql,long long qr,int T)
{
    if(!p)
    {
        p=++cnt_node;
       // printf("%d %lld %lld-----\n",p,l,r);
    }
    if(l>=ql&&r<=qr)
    {
        Tree[p].T=T;
        return;
    }//15192848
    long long mid=(l+r)>>1ll;
    if(ql<=mid)
    {
        Update(ls,l,mid,ql,qr,T);
    }
    if(qr>mid)
    {
        Update(rs,mid+1,r,ql,qr,T);
    }
}
int Find(int p,long long x,long long l,long long r)
{
    if(l==r)
    {
        return p;
    }
    long long mid=(l+r)>>1ll;
   // printf("%lld gkdktdktpdp\n",mid);
    if(x<=mid)
    {
        if(ls)
        {
            return Find(ls,x,l,mid);
        }
        else{
            return p;
        }
    }
    else{
       // printf("%d>>>>rkskks\n",rs);
        if(rs)
        {
            return Find(rs,x,mid+1,r);
        }
        else{
            return p;
        }
    }
}
int Leaf(int x)
{
    if((!Tree[x].lc)&&(!Tree[x].rc))
    {
        return 1;
    }
    return 0; 
}
struct Edge{
    int u,v;
};
vector<Edge>G[MAXN];

void dfs(int l,int r)
{
    if(Leaf(l)&&Leaf(r))
    {
        int Tfp=min(Tree[l].T,Tree[r].T);
        G[Tfp].push_back((Edge){l,r});
        return;
    }
    else if((!Leaf(l))&&Leaf(r))
    {
        dfs(Tree[l].lc,r);
        dfs(Tree[l].rc,r);
    }
    else if((Leaf(l))&&(!Leaf(r)))
    {
        dfs(l,Tree[r].lc);
        dfs(l,Tree[r].rc);
    }
    else
    {
        dfs(Tree[l].lc,Tree[r].lc);
        dfs(Tree[l].rc,Tree[r].rc);
    }
    
}
int fa[MAXN*50];
int find(int x)
{
    if(fa[x]==x)
    {
        return fa[x];
    }
    fa[x]=find(fa[x]);
    return fa[x];
}
void unionn(int i,int j)
{
    fa[find(i)]=find(j);
    return;
}
int main()
{
  //  freopen("date.in","r",stdin);
  //  freopen("date.out","w",stdout);
    scanf("%d %d",&n,&m);
    int cnt_lsh=0;
    lsh[++cnt_lsh]=0;
    lsh[++cnt_lsh]=(1ll<<n);
    int cnt_w=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s);
        if(s[0]=='b')
        {
            scanf("%lld %lld",&x,&y);
            lsh[++cnt_lsh]=x;
            lsh[++cnt_lsh]=y+1;
            L[++cnt_w]=x;
            R[cnt_w]=y;
            Idt[cnt_w]=i;
            
        }
        else
        {
            scanf("%lld %lld",&x,&y);
            Query[i].push_back(make_pair(x,y));
        }
    }
    sort(lsh+1,lsh+1+cnt_lsh);
    cnt_lsh=unique(lsh+1,lsh+1+cnt_lsh)-lsh-1;
    for(int i=1;i<cnt_lsh;i++)
    {
        Tdt[i]=m+1;
    }
    for(int i=1;i<=cnt_w;i++)
    {
         int Tcf=lower_bound(lsh+1,lsh+1+cnt_lsh,L[i])-lsh;
         Tdt[Tcf]=Idt[i]-1;
    }
    for(int i=1;i<cnt_lsh;i++)
    {
        Update(root,0,(1ll<<n)-1,lsh[i],lsh[i+1]-1,Tdt[i]);
    }
    for(int i=1;i<=cnt_node;i++)
    {
        dfs(Tree[i].lc,Tree[i].rc);
        fa[i]=i;
    }
    vector<int>Ra;
    Ra.clear();
    for(int i=m+1;i>=1;i--)
    {
        for(int j=0;j<G[i].size();j++)
        {
            Edge tp=G[i][j];
         //   printf("%d %drueurueur\n",tp.u,tp.v);
            //printf("???\n");
            unionn(tp.u,tp.v);
        }
        for(int j=0;j<Query[i].size();j++)
        {
            pair<long long,long long>Toc=Query[i][j];
            if(find(Find(root,Toc.first,0,(1ll<<n)-1))==find(Find(root,Toc.second,0,(1ll<<n)-1)))
            {
                Ra.push_back(1);
            }
            else
            {
                Ra.push_back(0);
            }
        }
    }
    for(int i=Ra.size()-1;i>=0;i--)
    {
        printf("%d\n",Ra[i]);
    }
}

标签：图论,return,int,练习,Tree,long,fa,MAXN
From： https://www.cnblogs.com/kid-magic/p/17524321.html

相关文章

  • 面向对象综合案例练习
    面向对象综合案例练习练习1：文字版格斗游戏格斗游戏:每个游戏角色的名字血量都不同,在选定人物的时候(new对象的时候),这些信息就应该被确定下来建立两个类：角色类和测试类packagecom.itheima.MethodAllTest01;importjava.util.Random;publicclassRole{privateSt......
  • 浅谈图论
    多源最短路算法（Floyd）说到最短路，就不得不提到松弛。所谓松弛，就是当存在\(w_{u,v}>w_{u,k}+w_{k,v}\)时，令\(w_{u,v}=w_{u,k}+w_{k,v}\)一般来说，松弛操作后，我们会用松弛后的边不断松弛其他边，而这，就是大部分最短路算法的思路。思考一下，若用DP的思想考虑，那么我们易设出状态\(f_{i......
  • Linux三剑客grep、sed、awk(包括练习题)
    Linuxgrep、sed、awk（包含练习题）一、grepLinuxgrep(globalregularexpression)命令用于查找文件里符合条件的字符串或正则表达式。基本用法与常见的正则表达式grep[options]pattern[files]命令 参数 匹配模式 文件数据 -i：忽略大小写进行匹配。 -v：反向查找，只......
  • MySql经典练习题（一）
    数据库表结构和数据见我的上一篇博文1.查询"01"课程比"02"课程成绩高的学生的信息和课程分数selects.*,a.s_scorefromScorea,Scoreb,Studentswheres.s_id=a.s_idanda.s_id=b.s_idanda.c_id="01"andb.c_id="02"anda.s_score>b.s_score......
  • 图论：图的概念、存储和遍历 学习笔记
    图论图的概念从数据结构的角度看，图可以看作一个多对多的数据存储结构。而结合图论算法，图就可以成为很多问题的载体。图论是数据结构与算法结合的产物。OIWiki上给出的图相关概念比较全面，但是因为OI是民科各个地方的一些定义都不太一样，所以作大概了解即可。图的存储图的存......
  • 练习题
    1、N个分数求和博客链接https://blog.csdn.net/weixin_73142957/article/details/128798429publicclassDemo3_01{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intn=scanner.nextInt();intsu......
  • 图论2
    内容来自紫书、2019wannaflycamp、进阶指南、算法导论，可能根本看不完，可能这一切都没有意义。图论以前学算法的时候，很少关心算法正确性的证明，和传统的理科课程如高数课这一类课差得太远了。参加编程竞赛时每一份代码就像黑盒，没有方向感，看起来就像另外一种应试。图的存储略广......
  • 【十五】MySQL数据库之多表查询练习题
    【十五】MySQL数据库之多表查询练习题表结构和数据/*NavicatPremiumDataTransferSourceServer:localhostSourceServerType:MySQLSourceServerVersion:50624SourceHost:localhostSourceDatabase:sqlexamTargetServerT......
  • python内置函数：chr()、ord()使用方法及练习
    python内置函数：chr()、ord()使用方法及练习使用方法由于chr函数和ord函数经常是一起出现、一起使用的，所以我将它们放到同一篇文章。一、chrchr({需要转换的Unicode编码})，返回值是对应的字符例1：输入数字65-91，返回值是大写字母chr(65)Achr(90)Z......
  • 练习
    箭头函数：编写一个箭头函数，接受两个参数并返回它们的和。解构赋值：给定一个数组[1,2,3]，使用解构赋值将数组中的元素分别赋值给变量a、b和c。默认参数：编写一个函数，接受两个参数：name和age。如果name参数未提供，则将其默认设置为"Unknown"，如果age参数未提供，则将其默认设置......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99