欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CodeForces 29D Ant on the Tree

程序员文章站 2023-09-28 12:08:17
"洛谷题目页面传送门" & "CodeForces题目页面传送门" 题意见洛谷里的翻译。 这题有$\bm3$种解法,但只有一种是正解~~(这不是废话嘛)~~。 方法$\bm1$:最近公共祖先LCA(正解) 真的把它当作一棵树来做。使用父亲表示法,记录每个节点的父亲。可是输入中只能告诉你谁和谁连,并没 ......

洛谷题目页面传送门 & 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)\)题目被虐了,出题人好可怜