C++ 暴力解法：斐波那契数列维护序列

题目描述

您需要写一种数据结构来维护一个数列，其中需要提供以下操作：

1. 在数列后方插入 'F_1···F_x'（斐波那契数列：'1,1,2,3,5,8···'）
2. 在数列前方插入 'F_1···F_x'
3. 在数列后方删去 'x' 个数
4. 查询数列区间 '[x,y]' 的最大值
5. 查询数列区间 '[x,y]' 的和

数列一开始为空，删除操作与查询操作保证数列内有足够的数

输入格式

第一行为 'n'，表示操作的个数，下面 'n' 行每行，对于操作 '1,2,3' 有两个数 'op' 和 'x'，对于操作 '4,5' 有三个数 'op,x' 和 'y'，'op' 表示操作的序号（'1 ≤ opt ≤ 6'）

输出格式

对于操作 '4,5' 每行输出一个数，表示查询结果

样例 #1

样例输入 #1

6
1 5
3 2
4 1 2
1 3
2 2
5 3 5

样例输出 #1

2
4

提示

以下是每个操作后数列的内容：

• '1,1,2,3,5'
• '1,1,2'
• '1,1,2'（查询 '[1,2]' 的最大值结果为 '2'）
• '1,1,2,1,1,2'
• '1,1,1,1,2,1,1,2'
• '1,1,1,1,2,1,1,2'（查询 '[3,5]' 的和结果为 '4'）

代码实现

下面是一种使用暴力方法实现的C++代码：

#include <iostream>
#include <vector>
using namespace std;

// 计算斐波那契数列的第n个数
int fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

int main() {
    int n;
    cin >> n;

    vector<int> sequence; // 存储数列的向量

    for (int i = 0; i < n; i++) {
        int op;
        cin >> op;
        
        if (op == 1) {
            int x;
            cin >> x;
            for (int j = 0; j < x; j++) {
                sequence.push_back(fibonacci(j+1));
            }
        }
        else if (op == 2) {
            int x;
            cin >> x;
            for (int j = x-1; j >= 0; j--) {
                sequence.insert(sequence.begin(), fibonacci(j+1));
            }
        }
        else if (op == 3) {
            int x;
            cin >> x;
            for (int j = 0; j < x; j++) {
                sequence.pop_back();
            }
        }
        else if (op == 4) {
            int x, y;
            cin >> x >> y;
            int max_val = sequence[x-1];
            for (int j = x; j < y; j++) {
                if (sequence[j] > max_val) {
                    max_val = sequence[j];
                }
            }
            cout << max_val << endl;
        }
        else if (op == 5) {
            int x, y;
            cin >> x >> y;
            int sum = 0;
            for (int j = x-1; j < y; j++) {
                sum += sequence[j];
            }
            cout << sum << endl;
        }
    }

    return 0;
}

希望对你有帮助！