热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

P2437蜜蜂路线题解

思路分析:1、以普通的第\(i\)个蜂房进行思考,将它的状态描述为:\(f[i]\),这是一个一维数组。它可以由哪些状态转移过来?由题意,可以从\(i-1\),\(i-2\)而来。


思路分析:

1、以普通的第\(i\)个蜂房进行思考,将它的状态描述为:\(f[i]\),这是一个一维数组。它可以由哪些状态转移过来?由题意,可以从\(i-1\),\(i-2\)而来。

根据加法原理有\(f[i]=f[i-1]+f[i-2]\),其中\(i>2\),而\(f[1]=f[2]=1\)。

这就是一个斐波那契数列啊!

2、看一下数据量,\(M<=N<=1000\),我们知道,\(1000\)极限值的斐波那契数列可不是一个小数字,\(int\)肯定暴掉,\(long\ long\)也是白费,\(usinged\ long \ long\)可以一试,根本还是高精度加法。


c++ 代码

#include
using namespace std;
//高精度+裴波那契数列
//本题目考点:
//1、递推
//2、递推关系式的推导:找出任意一个位置,思考它是怎么来的,再用加法原理。
vector add(vector &A, vector &B) {
if (A.size() vector C;
int t = 0;
for (int i = 0; i t += A[i];
if (i C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
int main() {
int m, n;
cin >> m >> n;
vector A, B, C;
A.push_back(1);
B.push_back(1);
for (int i = 3; i <= n - m + 1; i++) {
C = add(A, B);
//对加数需要重新赋值
//A<---B
A.assign(B.begin(), B.end());
//B<---C
B.assign(C.begin(), C.end());
}
//倒序输出结果
for (int i = B.size() - 1; i >= 0; i--)printf("%d", B[i]);
return 0;
}


推荐阅读
  • 给定行数 numRows,生成帕斯卡三角形的前 numRows 行。例如,当 numRows 为 5 时,返回的结果应为:[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]。 ... [详细]
  • 算法题解析:最短无序连续子数组
    本题探讨如何通过单调栈的方法,找到一个数组中最短的需要排序的连续子数组。通过正向和反向遍历,分别使用单调递增栈和单调递减栈来确定边界索引,从而定位出最小的无序子数组。 ... [详细]
  • 本题探讨了在大数据结构背景下,如何通过整体二分和CDQ分治等高级算法优化处理复杂的时间序列问题。题目设定包括节点数量、查询次数和权重限制,并详细分析了解决方案中的关键步骤。 ... [详细]
  • 2018-2019学年第六周《Java数据结构与算法》学习总结
    本文总结了2018-2019学年第六周在《Java数据结构与算法》课程中的学习内容,重点介绍了非线性数据结构——树的相关知识及其应用。 ... [详细]
  • 本题来自WC2014,题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系,要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]
  • PHP 实现多级树形结构:构建无限层级分类系统
    在众多管理系统中,如菜单、分类和部门等模块,通常需要处理层级结构。为了高效管理和展示这些层级数据,本文将介绍如何使用 PHP 实现多级树形结构,并提供代码示例以帮助开发者轻松实现无限分级。 ... [详细]
  • 深入解析Java虚拟机(JVM)架构与原理
    本文旨在为读者提供对Java虚拟机(JVM)的全面理解,涵盖其主要组成部分、工作原理及其在不同平台上的实现。通过详细探讨JVM的结构和内部机制,帮助开发者更好地掌握Java编程的核心技术。 ... [详细]
  • 本文深入探讨了POJ2762问题,旨在通过强连通分量缩点和单向连通性的判断方法,解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤,并附带完整的代码示例。 ... [详细]
  • 本文详细介绍了JavaScript中数组的两个重要高阶函数:map()和reduce()。map()用于将数组中的每个元素通过指定的函数进行处理并返回一个新的数组,而reduce()则用于对数组中的元素进行累积计算,最终返回一个单一值。 ... [详细]
  • 开发笔记:9.八大排序
    开发笔记:9.八大排序 ... [详细]
  • 本题探讨了在一个有向图中,如何根据特定规则将城市划分为若干个区域,使得每个区域内的城市之间能够相互到达,并且划分的区域数量最少。题目提供了时间限制和内存限制,要求在给定的城市和道路信息下,计算出最少需要划分的区域数量。 ... [详细]
  • 树链问题的优化解法:深度优先搜索与质因数分解
    本文介绍了一种通过深度优先搜索(DFS)和质因数分解来解决最长树链问题的方法。我们通过枚举树链上的最大公约数(GCD),将所有节点按其质因子分类,并计算每个类别的最长链,最终求得全局最长链。 ... [详细]
  • 主板IO用W83627THG,用VC如何取得CPU温度,系统温度,CPU风扇转速,VBat的电压. ... [详细]
  • 本文介绍如何利用栈数据结构在C++中判断字符串中的括号是否匹配。通过顺序栈和链栈两种方式实现,并详细解释了算法的核心思想和具体实现步骤。 ... [详细]
  • 本文详细介绍了8051系列微控制器的中断系统,特别是C51编译器中interrupt和using关键字的作用及其使用方法。通过深入分析这两个关键字的功能,帮助开发者更好地理解和优化中断程序的设计。 ... [详细]
author-avatar
Jean_香香
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有