[并差集][二分] Jzoj P5782 城市猎人

[并差集][二分] Jzoj P5782 城市猎人

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

 

 

题解

• 发现在第i天，1*(m-i+1)、2*(m-i+1)...(n/(m-i+1))*(m-i+1)会相连
• 所以，边数为Σn/i，所以就只有nlogn条边，显然可以存的下
• 可以用并差集的按秩排序，把size小的并到size大的，可以减小一些树的高度
• 然后要记录这条边链接的时间
• 对于查询两个点最早连接时间
• 可以二分出一个时间，然后在并差集上寻找在二分出时间内的两个点的属于哪个并差集里
• 如果在同一个并差集里，说明还可以时间还可以前，否则时间要往后推

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 using namespace std;
 7 const int inf=1000000;
 8 int n,m,q,fa[100010],size[100010],day[100010],x,y,u,v,l,r,ans;
 9 int getfather(int x,int y)
10 {
11     while (fa[x]!=x&&day[x]<=y) x=fa[x];
12     return x;
13 }
14 void bcj()
15 {
16     for (int i=m;i>=1;i--)
17         for (int j=2;j<=n/i;j++)
18         {
19             int u=getfather(i,m),v=getfather(i*j,m);
20             if (u!=v)
21             {
22                 if (size[u]>size[v]) swap(u,v);
23                 day[u]=m-i+1;
24                 size[v]+=size[u];
25                 fa[u]=v;
26                 if ((++l)>=n-1) return;
27             }
28         }
29 }
30 int main()
31 {
32 //    freopen("pictionary.in","r",stdin);
33 //    freopen("pictionary.out","w",stdout);
34     scanf("%d%d%d",&n,&m,&q);
35     for (int i=1;i<=n;i++) fa[i]=i,day[i]=inf,size[i]=1;
36     bcj();
37     for (int i=q;i>=1;i--)
38     {
39         scanf("%d%d",&u,&v);
40         l=0; r=m;
41         while (l<=r)
42         {
43             int mid=(l+r)/2;
44             x=getfather(u,mid),y=getfather(v,mid);
45             if (x==y) ans=mid,r=mid-1; else l=mid+1;
46         }
47         printf("%dn",ans);
48     }
49     return 0;
50 }

 

转载于:.html