【Henu ACM Round #13 F】Fibonacci-ish

在这里输入题意

【题解】

枚举序列的头两个数字是什么 O(N^2) 然后头两个数字确定之后。 f[3],f[4]..就确定了只需查看f[3],f[4]..是不是存在就好了。但是这样复杂度看起来是O(N^3)的了。

其实不然,a[n] = a[n-1]+a[n-2]这个递推的增长速度是接近2^n的增长速度的。
(所以到达10^9之后直接break就好了
所以实际上不会真的达到递推1000的规模
差不多只有O(N^2*100)的样子。
这是可以接受的了。

->但是有一种情况要特判,就是f[1] = f[2]=0的情况。这种情况直接统计1的个数即可。

程序中还加了一个优化。
因为前两项f1,f2确定之后f[i] = xf1+yf2
则我们提前算出来系数。
就能直接得到前两项是f1,f2的前提下fi的值了
根据这个可以做一下剪枝。

【代码】

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;

int a[N+10],n,b[N+10];
map<int,int> dic;
int x[N+10],y[N+10];

int main(){
	#ifdef LOCAL_DEFINE
	    freopen("rush_in.txt", "r", stdin);
	#endif
	ios::sync_with_stdio(0),cin.tie(0);
	x[1] = 1;y[1] = 0;
	x[2] = 0;y[2] = 1;
	x[3] = y[3]= 1;
    for (int i = 4;i <=N;i++){
        x[i] = x[i-2]+x[i-1];
        y[i] = y[i-2]+y[i-1];
    }


    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        dic[a[i]]++;
    }
    int ans = 2;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
            if (i!=j){
                if (a[i]==0 && a[j]==0){
                    int num = dic[0];
                    ans = max(ans,num);
                    continue;
                }
                dic[a[i]]--,dic[a[j]]--;
                int num = 2;
                b[1] = a[i],b[2] = a[j];
                if (ans>2 && ans<=40){
                    long long temp = 1LL*x[ans]*a[i]+1LL*y[ans]*a[j];
                    if (abs(temp)>1e9|| dic[temp]==0){
                        dic[a[i]]++,dic[a[j]]++;
                        continue;
                    }
                }
                for (int k = 3;k<=n;k++){
                    b[k] = b[k-2]+b[k-1];
                    if (abs(b[k])>1e9) break;
                    if (dic[b[k]]>0){
                        dic[b[k]]--;
                        num++;
                    }else break;
                }
                ans =max(ans,num);
                for (int k = 1;k <= num;k++) dic[b[k]]++;
            }
    cout << ans << endl;
	return 0;
}

【Henu ACM Round #13 F】Fibonacci-ish

相关推荐