CodeForces 29D Ant on the Tree

2019-08-16 07:59:21来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

CodeForces 29D Ant on the Tree

洛谷题目页面传送门 & CodeForces题目页面传送门

题意见洛谷里的翻译。

这题有\(\bm3\)种解法,但只有一种是正解(这不是废话嘛)


方法\(\bm1\):最近公共祖先LCA(正解)

真的把它当作一棵树来做。使用父亲表示法,记录每个节点的父亲。可是输入中只能告诉你谁和谁连,并没有说谁是谁的父亲,这该怎么办呢?其实很简单,只需要通过根是\(1\)这个信息,先把\(1\)的父亲设成自己,把所有\(1\)的邻居\(i\)的父亲都设成\(1\),然后再对\(i\)进行如下操作:把所有\(i\)的“还没有父亲”的邻居\(j\)的父亲都设成\(i\),然后对\(j\)进行如下操作:把所有\(j\)的“还没有父亲”的邻居\(k\)的父亲都设成\(j\),然后对\(k\)进行如下操作……这样就做出来一棵树。我们还需要一个二维bool数组,在\(\operatorname{O}\left(n^2\right)\)时间内预处理出对于任意一对节点与叶子节点(也就是说第一维是任意节点,第二维是叶子节点)\((x,y)\)\(x\)是不是\(y\)的祖先。设叶子节点集合为\(l\),然后从\(1\)走到\(l_1\)、从\(l_1\)走到\(l_2\)、……、从\(l_{n-1}\)走到\(l_n\)、从\(l_n\)走到\(1\)。对于每一次走,从起点一直向上走,一直走到是终点的祖先为止(相当于走到原起点和终点的最近公共祖先(LCA)),再向下走到终点,把经过的点都压入答案序列。最后如果答案序列的大小不是\(2n-1\)就输出\(-1\),否则输出答案就可以了。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
vector<int> nei[301]/*邻接表*/,ans/*答案序列*/;
int f[301];//父亲
bool ance[301][301];//[1]是否是[2]的祖先
void mktre(int x){//对x进行如下操作:
    for(int i=0;i<nei[x].size();i++)//将所有x的
        if(!f[nei[x][i]])/*“孤儿”邻居*/f[nei[x][i]]=x/*收养*/,mktre(nei[x][i])/*并对它进行如下操作……*/;
}
void go(int st,int ed){//从st走到ed
    while(!ance[st][ed])st=f[st],ans.push_back(st);//往上走到是ed的祖先为止
    vector<int> rev;
    while(st!=ed)rev.push_back(ed),ed=f[ed];//本应向下走,但用的是父亲表示法,只能向上走
    for(int i=rev.size()-1;i>=0;i--)ans.push_back(rev[i]);//倒过来压入答案序列
}
int main(){
    int n/*节点数*/,i;scanf("%d",&n);
    for(i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        nei[x].push_back(y);nei[y].push_back(x);
    }
    f[1]=1;/*1的父亲是自己*/mktre(1);//先对1进行操作
    int x=1,y;ance[1][1]=true;
    ans.push_back(1);//因为1没有机会压入答案序列,只好特殊招待
    while(~scanf("%d",&y)){
        int z=y;while(z!=1)ance[z][y]=true,z=f[z];ance[1][y]=true;//预处理ance
        go(x,y);x=y;//从l[i]走到l[i+1]
    }
    go(x,1);
    if(ans.size()>(n<<1)-1)return !printf("-1");//大小不是2n-1
    for(i=0;i<ans.size();i++)printf("%d ",ans[i]);//输出答案
    return 0;
}

这种方法的时间复杂度是\(\mathrm{O}\left(n^2\right)\)。因为做树的时间是边数,\(\mathrm{O}(n)\);走一次的时间是\(\mathrm{O}(n)\),走\(n\)\(\mathrm{O}\left(n^2\right)\)。对于\(300\)的水数据,简直再容易不过了!


方法\(\bm2\):暴搜

不把这张图当作树来看,而当作图。走的时候,从起点毫无方向感地搜遍全图直到搜到终点为止。走的函数里要再加一个参数,表示走过来的节点,避免再回去,造成死循环。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
vector<int> nei[301]/*邻接表*/,ans/*答案序列*/;
bool dfs(int st/*起点*/,int ed/*终点*/,int prv/*走过来的,避免死循环*/){//暴搜
    if(st==ed)return true;//到达了,带回这个喜讯
    for(int i=0;i<nei[st].size();i++)//枚举邻居
        if(nei[st][i]!=prv&&dfs(nei[st][i],ed,st)){//如果不是走过来的,那看看能不能搜到终点
            ans.push_back(nei[st][i]);//此时已经搜到了,压入答案序列
            return true;//搜到了,返回
        }
    return false;//没搜到
}
int main(){
    int i,n/*节点数*/;scanf("%d",&n);
    for(i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        nei[x].push_back(y);nei[y].push_back(x);
    }
    int x=1,y;
    while(~scanf("%d",&y))dfs(y,x,0),x=y;//从l[i]开始暴搜l[i+1],因为dfs中是回溯时压入答案序列的,是反的,所以起点和终点也要反过来,反反得正
    dfs(1,x,0);
    ans.push_back(1);//因为1没有机会压入答案序列,只好特殊招待
    if(ans.size()>(n<<1)-1)return !printf("-1");
    for(i=0;i<ans.size();i++)printf("%d ",ans[i]);
    return 0;
}

暴搜中枚举邻居,每个邻居都可能将整个图遍历一遍,\(\mathrm{O}\left(n^2\right)\),最多有\(n\)次暴搜,所以整个时间复杂度是$
\mathrm{O}\left(n^3\right)$。这时间复杂度是在欺负出题人的数据范围吗?


方法\(\bm3\):Floyd指路

聪明的读者也许一定没想到,这题还可以用Floyd吧!先用Floyd算出任意两点的最短路(邻居距离为\(1\)),然后在走的时候,就有方向、不盲目、不彷徨、自信了,很显然,走能够缩短与终点的距离的邻居呗!在这里,Floyd起到了指路的作用。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f//设成INT_MAX相加时会爆int
int dis[301][301]/*最短距离*/,n/*节点数*/;
vector<int> ans;//答案序列
void go(int st,int ed){//从st走到ed
    if(st==ed)return;//到达,返回
    for(int i=1;/*一定有能走的点,所以不需要终止条件*/;i++)//枚举每个点
        if(dis[st][i]==1/*是邻居*/&&dis[i][ed]<dis[st][ed]/*能缩短距离*/){//走
            ans.push_back(i);//压入答案序列
            go(i,ed);//走一步
            return;//能走的点只有一个,找到了就算成功了,不再找了
        }
}
int main(){
    int i,j;scanf("%d",&n);
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)dis[i][j]=i==j?0:inf;//初始化dis
    for(i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        dis[x][y]=dis[y][x]=1;//邻居的距离为1
    }
    //Floyd
    for(int k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)
        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
//  for(i=1;i<=n;i++){for(j=1;j<=n;j++)printf("dis[%d][%d]=%d\t",i,j,dis[i][j]);puts("");}
    int x=1,y;
    ans.push_back(1);//因为1没有机会压入答案序列,只好特殊招待
    while(~scanf("%d",&y))go(x,y),x=y;//从l[i]走到l[i+1]
    go(x,1);
    if(ans.size()>(n<<1)-1)return !printf("-1");
    for(i=0;i<ans.size();i++)printf("%d ",ans[i]);
    return 0;
}

虽然有方向了,但也要为此付出代价——奇慢无比的Floyd。所以时间复杂度还是\(\mathrm{O}\left(n^3\right)\)题目被虐了,出题人好可怜


原文链接:https://www.cnblogs.com/ycx-akioi/p/CodeForces-29D.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:斜率优化dp学习笔记 洛谷P3915[HNOI2008]玩具装箱toy

下一篇:冒泡排序