jzoj 5782 城市猎人

题目

题解

–本来是很难，但是总有优秀的大佬加神牛犇活在这个世界上
首先不用n^2枚举a和b，
某位大佬说：
a和b其实就是
1 * （m-i+1），2 * （m-i+1），3 * （m-i+1），4 * （m-i+1）。。。。
（哇，我咋不知道呢QAQ）
那么用并查集建一棵树就好了
树边就是连接他们的 i
然后好像有什么优化？——小树连大树（按秩合并）
最后跑对于每个询问的x和y，跑lca，找到连接他们的所有边的连通时间的最大值
就是答案啦啦啦

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=100005;int n,m,q;
int f[MAXN],s[MAXN];
int l[MAXN];
int d[MAXN];int Find(int x){if(x==f[x])return x;d[x]=d[f[x]]+1;return Find(f[x]);
}int lca(int x,int y){if(d[x]<d[y])swap(x,y);while(d[x]>d[y])x=f[x];if(x==y)return x;while(f[x]!=f[y]){x=f[x];y=f[y];}return f[x];
}int final(int x,int y,int d){int ans=0;while(x!=d){ans=max(ans,l[x]);x=f[x];}while(y!=d){ans=max(ans,l[y]);y=f[y];}return ans;
}int main(){freopen("pictionary.in","r",stdin);freopen("pictionary.out","w",stdout);cin>>n>>m>>q;for(int i=1;i<=n;i++){f[i]=i;s[i]=1;}for(int i=1;i<=m;i++){for(int j=2;j*(m-i+1)<=n;j++){int u=Find((j-1)*(m-i+1)),v=Find(j*(m-i+1));if(s[u]<=s[v]){f[u]=v;l[u]=i;s[v]=max(s[u]+1,s[v]);}else{f[v]=u;l[v]=i;s[u]=max(s[v]+1,s[u]);}}}for(int i=1;i<=q;i++){int x,y;scanf("%d%d",&x,&y);printf("%d\n",final(x,y,lca(x,y)));}return 0;
}