题解：P11315 [RMI 2021] 速通 / Speedrun

· · 题解

题目传送门

题目分析

题目要求在有 N 个节点的树上给每一个节点上存一个 01 串，使能在有失误的情况下通过节点上的信息于任意一个节点开始遍历整棵树。

思路

首先观察数据的大小和限制，最坏情况下每个节点只能存大小为 20 的 01 串，且最多失误 2000 次。题中最多存在 1000 个节点，平均下来每一个节点走向下一个节点时可以有 2 次失误。然后还可以观察到 \lceil\log_21000\rceil=10。也就是在每一个 01 串里可以存 2 个节点的编号。

接下来思考 01 串里应该存什么节点的编号。首先当前节点的父亲节点可以存进去，这样不论初始在哪一节点上，都可以不断地到达当前节点的父亲节点从而到达根节点。

对于树的遍历存在众所周知的两种遍历方法：\texttt{DFS} 和 \texttt{BFS}。这道题的走法显然只符合 \texttt{DFS}。那么就可以想到使用 \texttt{DFS} 序来尝试解决该题。

方法

在第一次运行里，根据边建好图后跑一个 \texttt{DFS} 序并存每个节点的父亲节点，然后对于每一个节点的 01 串将其父亲节点编号以及 \texttt{dfn} 为当前节点的下一个的节点编号存进去。

在第二次运行里，我们先不断地走到当前节点的父亲，到达根节点，然后不断尝试走到 \texttt{dfn} 为当前节点的下一个的节点。如果可以走通，那么继续往下走；如果走不通，那么就回到其父亲节点继续尝试走。实际上就是模拟 \texttt{DFS} 遍历树的过程。

这样子走失误次数最多就是总节点数减去一定不会走失误的两个节点即根节点与 \texttt{dfn} 为最后一个的节点，次数最坏就为 998 次，远小于限制的 2000 次。

代码

#include<bits/stdc++.h>
#define bit bitset<10>
using namespace std;
const int N=1e3+5;

void setHintLen(int);void setHint(int,int, bool);int getLength();bool getHint(int);bool goTo(int);

int dfn[N],idx,f[N],rdfn[N];
vector<int> a[N];
void dfs(int now,int fa){
    f[now]=fa;
    dfn[now]=++idx;
    rdfn[idx]=now;
    for(const int& i:a[now]){
        if(i==fa) continue;
        dfs(i,now);
    }
}//dfs序
void assignHints(int subtask, int n, int A[], int B[]){
    setHintLen(20);
    for(int i=1;i<n;i++){
        a[A[i]].push_back(B[i]);
        a[B[i]].push_back(A[i]);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        bit z=f[i];
        for(int j=1;j<=10;j++)
            setHint(i,j,z[j-1]);//存父亲
        if(dfn[i]<n){
            bit nz=rdfn[dfn[i]+1];
            for(int j=1;j<=10;j++)
                setHint(i,j+10,nz[j-1]);//存dfn为下一个的节点
        }
    }
}
void speedrun(int subtask, int n, int start){
    bit sz;
    for(int i=1;i<=10;i++)
        sz[i-1]=getHint(i);
    int fa=sz.to_ulong();
    while(fa>0){
        goTo(fa);
        bit nz;
        for(int i=1;i<=10;i++)
            nz[i-1]=getHint(i);
        fa=nz.to_ulong();
    }//走到根节点
    for(int i=1;i<=10;i++)
        sz[i-1]=getHint(i+10);
    int nxt=sz.to_ulong();
    while(nxt>0){
        bool flag=goTo(nxt);
        if(flag){
            bit nz;
            for(int i=1;i<=10;i++)
                nz[i-1]=getHint(i+10);
            nxt=nz.to_ulong();
        }//走到了继续走
        else{
            bit nz;
            for(int i=1;i<=10;i++)
                nz[i-1]=getHint(i);
            goTo(nz.to_ulong());
        }//走不到就回到其父亲节点
    }
}