前言

小蓝书电子档 密码:xiaolanshu

$T1$

解：额外用一个 d 数组存储距离（详情请见小蓝书 $P_{218}$,没有的看电子档）

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=3e4+50;
int fa[N],d[N],sz[N];
int find(int x){
    if(x==fa[x]) return x;
    int root=find(fa[x]);
    d[x]+=d[fa[x]];
    return fa[x]=root;
}
void merge(int a,int b){
    int x=find(a),y=find(b);
    if(x==y) return;
    fa[x]=y;
    d[x]=sz[y];
    sz[y]+=sz[x];
}
int main(){
    for(int i=1;i<N;i++){
        fa[i]=i;
        sz[i]=1;
        d[i]=0;
    }
    int t;
    cin >> t;
    while(t--){
        char c;
        cin >> c;
        int i,j;
        cin >> i >> j;
        if(c=='M'){
            merge(i,j);
        }else{
            int x=find(i),y=find(j);
            if(x==y){
                cout << abs(d[i]-d[j])-1 << endl;
            }else{
                cout << -1 << endl;
            }
        }
    }
}

这么执着吗？好吧：

合并操作：

找到 i 和 j 的根节点（ ri 和 rj ）。

将 ri 的 fa 节点设为 rj 。

更新 ri 到 rj 的距离为 rj 的 sz（因为i的魔法师会接在 j 的末尾）。

更新 rj 的大小（增加 ri 的大小）。

查询操作：

检查 i 和 j 是否在同一集合（根节点相同）。 如果不在同一集合，返回 -1。 否则，计算i和j到根节点的距离，然后他们之间的距离为 abs(d[i]-d[j])-1。

$T2$

思路：看小蓝书的扩展域写法，结合前面的扩展域示例，是完全可以写出来的（作者就这么写出来了）

$T3$

解：广搜+小小的

$$DP$$

dist[i] 表示从 1~i 的最短距离。 dp[i] 表示从 1~i 的方案数。 对于每一层的城市，我们只处理那些未被访问过的城市，或者距离等于当前层数的城市。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,N=2e5+50;
int vis[N],dp[N],dist[N];
signed main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int> > vcr(n+1,vector<int> (0));
    int TT=m;
    while(TT--){
        int a,b;
        cin >> a >> b;
        vcr[a].push_back(b);
        vcr[b].push_back(a);
    }
    memset(dist,0x3f,sizeof dist); 
    dist[1]=0;
    dp[1]=1;
    queue<int> q;
    q.push(1);
    vis[1]=1;
    while(q.size()){
        int now=q.front();
        q.pop();
        for(auto it:vcr[now]){
            if(vis[it]==1){
                if(dist[it]==dist[now]+1){
                    dp[it]=(dp[it]+dp[now])%mod;
                }
            }else{
                dist[it]=dist[now]+1;
                dp[it]=(dp[it]+dp[now])%mod;
                vis[it]=1;
                q.push(it);
            }
        }
    }
    cout << dp[n]%mod;
}

$T4$

解：斐波那契数列变种，因为可以从 $i-1$ 和 $i-2$ 上来，如果楼梯坏了，则 f[i]=0 。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50,mod=1e9+7;
int vis[N],f[N];
signed main(){
    int n,m;
    cin >> n >> m;
    int TT=m;
    while(TT--){
        int x;
        cin >> x;
        vis[x]=1;
    }
    f[0]=1;
    f[1]=1;
    if(vis[1]==1) f[1]=0;
    for(int i=2;i<=n;i++){
        if(vis[i]==1) continue;
        f[i]=((f[i-1]%mod)+(f[i-2]%mod))%mod;
    }
    cout << f[n]%mod;
}
// 题目说了坏的踏板在1~N-1间，所以起点(0)和终点(N)的台阶是不会坏的