本文共 1113 字，大约阅读时间需要 3 分钟。

正题

题目大意

$n$个点，每个点可以走到$[a_i,n]$，每个点可以从$[b_i,n]$到达。

求$di{s}_{i,j}\ast (i+j)$的异或和

解题思路

首先我们可以知道肯定是先往后跳再往前走最优，因为如果先往前再往后最优的话显然可以直接往后跳。

所以我们先计算往前走的步数，枚举一个终点，然后一层一层扩展即可

之后考虑往后走，我们可以用并查集来，从步数少的枚举到步数大的，然后用并查集进行往后扩展，之后不断更新最短距离

$code$

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N=6100; int n,a[N],b[N],dis[N][N],fa[N],ans;bool v[N];vector
       
         q[N];int find(int x){
   return (fa[x]==x)?x:(fa[x]=find(fa[x]));}int main(){
   	scanf("%d",&n);	for(int i=2;i<=n;i++)		scanf("%d",&a[i]);	for(int i=2;i<=n;i++)		scanf("%d",&b[i]);	memset(dis,0x3f,sizeof(dis));	for(int i=1;i<=n;i++){
   		dis[i][i]=0;		int j=i-1,k=b[i],w=1;		while(j){
   			int z=k;			for(;j>=z;j--){
   				dis[j][i]=w;				k=min(k,b[j]);			}			w++;		}	}	a[1]=1;	for(int i=1;i<=n;i++){
   		for(int j=0;j<=n;j++){
   			q[j].clear();			fa[j]=j;v[j]=0;		}		for(int j=i;j<=n;j++)			q[dis[i][j]].push_back(j);		for(int j=0;j<=n;j++)			for(int k=0;k
        
         =a[q[j][k]];p=find(p)){ if(dis[i][q[j][k]]+1
        
       
      
     
    
   

转载地址：http://fdwaf.baihongyu.com/