Fibonacci-ish

发表于 更新于 分类于 ，

    给出长度为n的数组$a_1, a_2, \cdots, a_n$，重排数组后。

    求最大的k使得$a_i = a_{i-1}+a_{i-2}, 2<i\le k$

    n<=1000

Fibonacci-ish

Created by LXC on Sun May 14 16:39:09 2023

https://codeforces.com/problemset/problem/633/D

ranting: 2000

tag: brute force, dp, hashing, implementation, math

题意

给出长度为n的数组$a_1, a_2, \cdots, a_n$，重排数组后。
求最大的k使得$a_i = a_{i-1}+a_{i-2}, 2<i\le k$

n<=1000

题解

我们只需要确定前两项就行了，剩下的可以通过递推式在数组中查找是否存在。而这个类似斐波那契数列，当前两项均非0时，是指数增长的。所以数列的长度是对数数量级的O(logn)。

枚举前两项时间复杂度$O(n^2)$，查找后续$O(logn)$项可用平衡树$O(logn)$。
所以总时间复杂度$O((nlogn)^2)$

代码

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

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll& i : a)
        cin >> i;
    map<ll, int> mp;
    for (ll i : a)
        mp[i]++;
    int ans = 2;
    if (mp.count(0))
        ans = max(ans, mp[0]);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j || a[i] == 0 && a[j] == 0)
                continue;
            int cnt = 2;
            map<ll, int> c;
            ll p = a[i], q = a[j];
            c[p]++;
            c[q]++;
            while (mp.count(p + q) && ++c[p + q] <= mp[p + q]) {
                int t = p + q;
                p = q;
                q = t;
                cnt++;
            }
            ans = max(ans, cnt);
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}