A. 奇怪的魔法：

思路：这里是并查集，但要求距离，所以要用带权并查集，定义两个数组，一个记录大小，一个记录与根的距离即可

题解：

#include <bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int fa[N],t,i,j,a[N],d[N],s[N];
char c;

int get(int x){
	if(fa[x]==x) return x;
	int root=get(fa[x]);
	d[x]+=d[fa[x]];
	return fa[x]=root;
}

void uni(int x,int y){
	x=get(x),y=get(y);
	fa[x]=y;
	d[x]=s[y];
	s[y]+=s[x];
}

int cnt;

int main(){
	cin>>t;
	for(int i=1;i<=t;i++){
		fa[i]=i;
		s[i]=1;
	}
	while(t--){
		cin>>c>>i>>j;
		if(c=='M'){
			if(get(i)==get(j)) continue;
			uni(i,j);
		}else if(c=='C'){
			if(get(i)==get(j)){
				cout<<abs(d[i]-d[j])-1<<endl;
			}else{
				cout<<-1<<endl;
			}
		}
	}
	return 0;
}

B. 不安分的魔法学院

思路：这是食物链，可以用并查集，也可以用扩展域，纯模版

题解：

#include <bits/stdc++.h>
using namespace std;

const long long N=150010;
long long n,k,fa[N],d[N],ans;

long long find(long long x){
	if(fa[x]==x) return x; 
	return fa[x]=find(fa[x]);
}

void merge(long long x,long long y){
	long long px=find(x),py=find(y);
	fa[px]=py;
}

int main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(long long i=1;i<=n*3;i++){
		fa[i]=i;
	}
	while(k--){
		long long t,x,y;
		cin>>t>>x>>y;
		if(x>n||y>n){
			ans++;
		}else if(t==2&&x==y){
			ans++;
		}else{
			long long x_self=x,x_eat=x+n,x_enemy=x+2*n;
			long long y_self=y,y_eat=y+n,y_enemy=y+2*n;
			if(t==1){
				if(find(x_eat)==find(y_self)||find(x_self)==find(y_eat)){
					ans++;
				}else{
					merge(x_self,y_self);
					merge(x_eat,y_eat);
					merge(x_enemy,y_enemy);
				}
			}else if(t==2){
				if(find(x_self)==find(y_self)||find(x_self)==find(y_eat)){
					ans++;
				}else{
					merge(x_self,y_enemy);
					merge(x_eat,y_self);
					merge(x_enemy,y_eat);
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

D. 典型楼梯问题

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

题解：

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5; 
const long long mod=1000000007;
long long n,m,a,v[N],cnt,f[N];

int main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(long long i=1;i<=m;i++){
		cin>>a;
		v[a]=1;
	}
	f[0]=1;
	if(!v[1]) f[1]=1;
	for(long long i=2;i<=n;i++){
		if(v[i]) continue;
		f[i]=(f[i-1]+f[i-2])%mod;
	}
	cout<<f[n]%mod;
	return 0;
}