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

CJR_Rain · 2025-03-09 21:47:22 · 题解

思路：预处理 n 以内所有不重复的斐波那契数，然后进行 DFS 枚举所有取或不取的可能。

代码：

#include <bits/stdc++.h>

#define IS std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define OS std::cout.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define srnd srand((unsigned int)time(0))
#define rnd rand()
#define save(x) std::fixed << std::setprecision(x)
#define set_0(x) memset(x, 0, sizeof(x))
#define set_false(x) memset(x, false, sizeof(x))
#define set_true(x) memset(x, true, sizeof(x))
#define set_nega1(x) memset(x, -1, sizeof(x))
#define set_Iinf(x) memset(x, 0x7f, sizeof(x))
#define set_Finf(x) memset(x, 7e4, sizeof(x));
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define low_bit(x) (x & (-x))
#define __DEBUG__ puts("DEBUG")

using namespace std;

vector <long long> fib;

int dfs(int search, long long cnt) {

    if(cnt == 0) {

        return 1;
    }

    int res = 0;

    for(int i = search; i < fib.size(); ++i) {

        if(cnt - fib[i] < 0) {

            return res;
        }

        res += dfs(i + 1, cnt - fib[i]);//不降原则保证选数不重复
    }

    return res;
}

signed main() {

    IS;
    OS;

    long long n;
    cin >> n;

    fib.push_back(1);
    fib.push_back(2);

    while(fib.back() <= n) {

        fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    }

    fib.pop_back();

    cout << dfs(0, n);

    return 0;
}

然而 10^{12} 内不重复的斐波那契数有 58 个，上述代码又是 O(2^n) 级别的时间复杂度，绝对 TLE 。

所以我们需要剪枝

剪枝1：设数列 k 包含 n 以内所有不重复的斐波那契数，然后定义一个变量 sum=\sum{k}，在 DFS 搜到 k 中第 i 个数时，sum=sum-k_i，代表搜完这个数后 k 中还能搜的数之和。那么设 t 等于已经取的数之和，如果 n-t>sum，就可以直接剪枝掉了。

得出代码:

#include <bits/stdc++.h>

#define IS std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define OS std::cout.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define srnd srand((unsigned int)time(0))
#define rnd rand()
#define save(x) std::fixed << std::setprecision(x)
#define set_0(x) memset(x, 0, sizeof(x))
#define set_false(x) memset(x, false, sizeof(x))
#define set_true(x) memset(x, true, sizeof(x))
#define set_nega1(x) memset(x, -1, sizeof(x))
#define set_Iinf(x) memset(x, 0x7f, sizeof(x))
#define set_Finf(x) memset(x, 7e4, sizeof(x));
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define low_bit(x) (x & (-x))
#define __DEBUG__ puts("DEBUG")

using namespace std;

vector <long long> fib;//对应k
long long sum_fib = 0;//对应sum

int dfs(int search, long long sum) {//这里跟文中讲得不一样，参数sum = n - t

    if(sum <= 0 || sum_fib < sum || search >= fib.size()) {//剪枝1

        return sum == 0 ? 1 : 0;
    }

    sum_fib -= fib[search];
    int res = dfs(search + 1, sum - fib[search]) + dfs(search + 1, sum);
    sum_fib += fib[search];//利用回溯实现

    return res;
}

signed main() {

    IS;
    OS;

    long long n;
    cin >> n;

    fib.push_back(1);
    fib.push_back(2);

    while(fib.back() <= n) {

        fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    }

    fib.pop_back();

    sum_fib = accumulate(fib.begin(), fib.end(), 0ll);

    cout << dfs(0, n);

    return 0;
}

交上去一看，还是 TLE ，为什么？因为 k 是单调递增且增速极快的，我们又是从 k_1 开始一个一个搜，就使得在搜 k 中的前几个数时，sum 相对下降得太慢且 t 相对上升得太慢。这样一来，剪枝形同虚设。

我们可以发现，现在 TLE 的原因是 k 单调递增且增速极快，于是提出剪枝2：将 k 反转，使得 k 的性质变成单调递减且降速极快，并且由于没有改动 k 内元素，答案不变。

得出AC代码:

#include <bits/stdc++.h>

#define IS std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define OS std::cout.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define srnd srand((unsigned int)time(0))
#define rnd rand()
#define save(x) std::fixed << std::setprecision(x)
#define set_0(x) memset(x, 0, sizeof(x))
#define set_false(x) memset(x, false, sizeof(x))
#define set_true(x) memset(x, true, sizeof(x))
#define set_nega1(x) memset(x, -1, sizeof(x))
#define set_Iinf(x) memset(x, 0x7f, sizeof(x))
#define set_Finf(x) memset(x, 7e4, sizeof(x));
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define low_bit(x) (x & (-x))
#define __DEBUG__ puts("DEBUG")

using namespace std;

vector <long long> fib;//对应k
long long sum_fib = 0;//对应sum

int dfs(int search, long long sum) {//这里跟文中讲得不一样，参数sum = n - t

    if(sum <= 0 || sum_fib < sum || search >= fib.size()) {//剪枝1

        return sum == 0 ? 1 : 0;
    }

    sum_fib -= fib[search];
    int res = dfs(search + 1, sum - fib[search]) + dfs(search + 1, sum);
    sum_fib += fib[search];//利用回溯实现

    return res;
}

signed main() {

    IS;
    OS;

    long long n;
    cin >> n;

    fib.push_back(1);
    fib.push_back(2);

    while(fib.back() <= n) {

        fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    }

    fib.pop_back();

    sum_fib = accumulate(fib.begin(), fib.end(), 0ll);
    reverse(fib.begin(), fib.end());//剪枝2

    cout << dfs(0, n);

    return 0;
}