[数论][LCA][并查集]JZOJ 5782 城市猎人

[数论][LCA][并查集]JZOJ 5782 城市猎人

Description

有n个城市，标号为1到n，修建道路花费m天，第i天时，若gcd(a,b)=m-i+1，则标号为a的城市和标号为b的城市会建好一条直接相连的道路，有多次询问，每次询问某两座城市最早什么时候能连通。
 

Input

第一行输入三个正整数n,m,q，其中q表示询问个数。
接下来q行，每行两个正整数x，y，表示询问城市x和城市y最早什么时候连通。
 

Output

输出q行，每行一个正整数，表示最早连通的天数
 

Sample Input

Input 1
8 3 3
2 5
3 6
4 8
Input 2
25 6 1
20 9
Input 3
9999 2222 2
1025 2405
3154 8949

Sample Output

Output 1
3
1
2
Output 2
4
Output 3
1980
2160

Data Constraint

对于40%的数据，n≤ 1000，q<=100000
对于100%的数据，1 ≤ n,q≤ 100000,1<=m<=q

分析

显然对于gcd(a,b)=k，a与b都是k的倍数且a/k+1=b/k

那么我们就知道，第i天会有这样一个数列变得连通：m-i+1,2*(m-i+1),3*(m-i+1),...

那么问题就变成了求问两个连通块之间最早的连通时间

我们想到了并查集，但是不能路径压缩，这样会破坏数据详细性

只能按秩合并咯

然后对于每个点给一个ti表示i这个点与父亲相连通的最早时间

那么我们预处理好并查集，求x,y到它们LCA（不包括LCA，注意！）的max{ti 即可

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1+1e5;
int n,m,q;
int f[N],r[N],t[N],d[N];int Get(int x) {if (x==f[x]) return x;int root=Get(f[x]);d[x]=d[f[x]]+1;return root;
}int Ask(int x,int y) {int ans=0;if (d[x]<d[y]) swap(x,y);while (d[x]>d[y]) ans=max(ans,t[x]),x=f[x];while (x!=y) {ans=max(ans,max(t[x],t[y]));x=f[x];y=f[y];}return ans;
}int main() {freopen("pictionary.in","r",stdin);freopen("pictionary.out","w",stdout);scanf("%d%d%d",&n,&m,&q);for (int i=1;i<=n;i++) f[i]=i,r[i]=1;for (int i=1;i<=m;i++) {for (int j=2;j<=n/(m-i+1);j++) {int u=Get((m-i+1)*(j-1)),v=Get((m-i+1)*j);if (u==v) continue;if (r[u]<=r[v]) {f[u]=v;t[u]=i;r[v]=max(r[u]+1,r[v]);}else {f[v]=u;t[v]=i;r[u]=max(r[v]+1,r[u]);}}}for (int i=1;i<=n;i++) Get(i);for (int i=0;i<q;i++) {int a,b;scanf("%d%d",&a,&b);Get(a);Get(b);printf("%dn",Ask(a,b));}fclose(stdin);fclose(stdout);
}

View Code

 

转载于:.html