JZOJ – 5782 城市猎人

Time Limit : 1500ms
Memory Limit : 64MB

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

Case 1

8 3 3
2 5
3 6
4 8

Case 2

25 6 1
20 9

Case 3

9999 2222 2
1025 2405
3154 8949

Sample Output

Case 1

3
1
2

Case 2

4

Case 3

1980
2160

Data Constraint

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

解题思路

一条连接 $a$ 和 $b$ 的道路建成天数 $i$ 满足 $gcd(a,b)=m-i+1$

第一天会建成 $gcd(a,b) = m $ 的道路
第二天会建成 $gcd(a,b) = m – 1$ 的道路

那么对于 $gcd$ 和 $2 \times gcd$， $2 \times gcd$ 和 $3 \times gcd$ … $(n-1) \times gcd$ 和 $n \times gcd$，他们在同一天开始有一条相互连接的道路。

我们考虑从 $m$ 到 $1$ 枚举 $gcd$，他们建成时间是递增的。

再从 $1$ 往后枚举 $gcd$ 前的系数，用并查集将节点 $j \times gcd$ $(j-1) \times gcd$ 并入一个新建的虚拟节点，虚拟节点内存入当前道路的建成时间

最后对于询问跑树上LCA即可

注意，并入虚拟节点时一定要和并查集操作一样将两个节点的父亲并入一起，因为 $j \times gcd$ 可能有一个更小的因数，使得这个数已经加入了这棵并查集树。这也正是LCA能够求出最近时间的原因。因为他将建成更晚的节点和建成早的相互连通的节点在并查集树上连接在了一起。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 200000 + 10;

inline int read(){
    int x  = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9'){
        ch = getchar();
    }

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

int f[MAXN], val[MAXN];
int tree[MAXN][2], grand[MAXN][21], deep[MAXN], cnt;
int n, m, q;

inline int get(int x){
    int root = x;
    while(root != f[root]){
        root = f[root];
    }

    while(x != root){
        int tmp = f[x];
        f[x] = root;
        x = tmp;
    }

    return root;
}

inline void merge(int a, int b, int v){
    int f_a = get(a);
    int f_b = get(b);

    if(f_a == f_b)
        return;

    cnt++;

    int nowroot = n + cnt;

    f[f_a] = nowroot;
    f[f_b] = nowroot;
    f[nowroot] = nowroot;

    val[nowroot] = v;
    tree[nowroot][0] = f_a;
    tree[nowroot][1] = f_b;

}

inline void dfs(int x){
    for(register int i=1; i<=19; i++)
        grand[x][i] = grand[grand[x][i-1]][i-1];

    for(register int i=0; i<2; i++){
        int v = tree[x][i];

        if(v){
            deep[v] = deep[x]+1;
            grand[v][0] = x;

            dfs(v);
        }
    }
}

inline int LCA(int a, int b){
    if(deep[a] < deep[b])
        swap(a, b);

    for(register int i=19; i>=0; i--){
        if(deep[grand[a][i]] >= deep[b]){
            a = grand[a][i];
        }
    } 

    if(a == b)
        return a;

    for(register int i=19; i>=0; i--){
        if(grand[a][i] != grand[b][i]){
            a = grand[a][i];
            b = grand[b][i];
        }
    }

    if(a == b)
        return a;
    else
        return grand[a][0];
}
int main(){

    freopen("pictionary.in", "r", stdin);
    freopen("pictionary.out", "w", stdout);

    n = read();
    m = read();
    q = read();

    for(register int i=1; i<=n; i++)
        f[i] = i;

    for(register int gcd=m; gcd>=1; gcd--){
        int time = m - gcd + 1;

        for(register int k=2*gcd; k <= n; k+=gcd)
            merge(gcd, k, time);
    }

    deep[n+cnt] = 1;
    grand[n+cnt][0] = n+cnt;

    dfs(n+cnt);

    for(register int i=1; i<=q; i++){
        int a = read();
        int b = read();

        printf("%d\n", val[LCA(a, b)]);
    }   
    return 0;
}