LuoguP3938 - [mNOIP Day1] 斐波那契

2017/11/03

题面

懒得复制了

解法

注意到树的深度是 的。

dfs 在线求 LCA 即可。(大雾)

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int SIZ = 1e6 + 2007;

int N, M;
LL fibo[SIZ];
LL psum[SIZ];

LL getfa(LL x) {
    int dep = lower_bound(psum, psum + N + 2, x) - psum;
    return x - psum[dep - 1];
}

vector<LL> getpath(LL x) {
    vector<LL> ret;
    ret.push_back(x);

    while(x != 1) {
        x = getfa(x);
        ret.push_back(x);
    }

    return ret;
}

LL query(LL a, LL b) {
    vector<LL> pa = getpath(a);
    vector<LL> pb = getpath(b);
    sort(pa.begin(), pa.end());
    sort(pb.begin(), pb.end());
    vector<LL> insc;
    set_intersection(pa.begin(), pa.end(), pb.begin(), pb.end(),
            back_inserter(insc));

    return insc.empty() ? -1 : insc[insc.size() - 1];
}

int main() {
    fibo[0] = 1;
    fibo[1] = fibo[2] = 1;
    for(N=3;N<SIZ;N++) {
        fibo[N] = fibo[N-1] + fibo[N-2];
        if(fibo[N] > 2e12) break;
    }

    psum[1] = fibo[0];
    for(int i=2;i<=N+1;i++) {
        psum[i] = psum[i-1] + fibo[i-1];
    }

    scanf("%d", &M);
    LL u, v;
    while(M--) {
        scanf("%lld %lld", &u, &v);
        printf("%lld\n", query(u, v));
    } 
}