题解：B4219 [常州市程序设计小能手 2023] 数学作业

· · 题解

B4219 [常州市程序设计小能手 2023] 数学作业 题解

题目传送门

思路

先输入 n，将小于等于 n 的所有斐波那契数提前初始化好，存在数组中。也可以提前用打表处理好。然后用 DFS 对于每一个斐波那契数进行选或不选的搜索即可。

void dfs(int i,int sum){
    if(sum+a[i]==n){
        ans++;
        break;
    }
    dfs(i+1,sum);
    dfs(i+1,sum+a[i]);
}

但是，观察一下数据范围：数据范围是 n\le10^{12}，而小于等于 10^{12} 的斐波那契数共有大约 58 个，但是我们的算法复杂度为 O(2^n)，显然直接就 TLE 了。

于是我们就得想一个优化方法。

优化

使用前缀和优化

我们可以创建前缀和数组 h 使 h_i 表示数列 f 从 f_0 到 f_{i-1}的和，若当前选择的斐波那契数和 s 加上后面所有斐波那契数的和还是小于 n，则直接退出搜索。

    if(i>=m){
            continue;
        }//我这里是模拟递归

代码

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

typedef long long ll;

struct node{
    int i;
    ll s;
};
int main(){
    ll n;
    cin>>n;
    vector<ll> fib;
    if(n>=1){
        fib.push_back(1);
    }
    if(n>=2){
        fib.push_back(2);
        ll a=1,b=2;
        while(1){
            ll c=a+b;
            if(c>n) break;
            fib.push_back(c);//计算数列
            a=b;
            b=c;
        }
    }
    reverse(fib.begin(),fib.end());//反转数列

    int m=fib.size();

    if(m==0){//特判
        if(n==0) cout<<1;
        else cout<<0;
        return 0;
    }
    vector<ll> prefix(m+1,0);//前缀和数组
    for(int i=m-1;i>=0;i--){
        prefix[i]=fib[i]+prefix[i+1];//计算前缀和
    }

    stack<node> st;

    st.push({0,n});//初始化栈

    ll ans=0;

    while(!st.empty()){
        node temp=st.top();
        st.pop();
        int i=temp.i;
        ll s=temp.s;

        if(s==0){//如果s=0，答案+1
            ans++;
            continue;
        }
        if(i>=m){//如果i>=m，跳过
            continue;
        }

        if(fib[i]>s){//如果当前数大于s，将当前数入栈
            st.push({i+1,s});
        }
        else{
            if((i+1<m)?prefix[i+1]<s:0<s){//如果当前数小于s，将当前数入栈，将当前数的下一个数入栈
                st.push({i+1,s-fib[i]});
            }
            else{//如果当前数小于s，将当前数入栈，将当前数的下一个数入栈
                st.push({i+1,s});
                st.push({i+2,s-fib[i]});
            }
        }
    }
    cout<<ans;
    return 0;
}