洛谷：P2437：蜜蜂路线

题目

P2437：蜜蜂路线

分析

本题难度不算太大。从图片上看，可以很容易得到递推规律：

\(dp[i]=dp[i-1]+dp[i-2]\)，基本上就是斐波那契数列。

但需要注意的是，题目给出的数字上限极高（\(M\lt N\le 1000\)），此时的斐波那契数会很大，超过了long long的范围，所以需要自行实现高精度类型。

// 大整数类，用于处理超出long long范围的数字
class BigInteger
{
   private:
    string digits;  // 用字符串存储大整数，低位在前，高位在后

   public:
    // 构造函数
    BigInteger(long long num = 0)
    {
        if (num == 0)
        {
            digits = "0";
        }
        else
        {
            while (num > 0)
            {
                digits.push_back(num % 10 + '0');
                num /= 10;
            }
        }
    }

    // 从字符串构造
    BigInteger(const string& s)
    {
        digits = s;
        reverse(digits.begin(), digits.end());
    }

    // 加法运算
    BigInteger operator+(const BigInteger& other) const
    {
        BigInteger result;
        result.digits = "";

        int carry = 0;
        int i = 0, j = 0;

        // 逐位相加
        while (i < digits.size() || j < other.digits.size() || carry)
        {
            int sum = carry;
            if (i < digits.size())
                sum += digits[i++] - '0';
            if (j < other.digits.size())
                sum += other.digits[j++] - '0';

            result.digits.push_back(sum % 10 + '0');
            carry = sum / 10;
        }

        return result;
    }

    // 输出运算符重载
    friend ostream& operator<<(ostream& out, const BigInteger& num)
    {
        string output = num.digits;
        reverse(output.begin(), output.end());
        return out << output;
    }
};

答案

思考

（无）