sicily1029 Rabbit 中大OJ解题报告-程序员宅基地

技术标签： C++ sicily1029 Rabbit sicily ACM

由于中大的oj需要内网才能进去，就提供不了原始题目了，但是题目的意思就是说，开始有一对成年兔子，一对成年兔子每年能生一对幼兔，幼兔等m个月才成长为成年兔子，问d个月后总共有多少对兔子。

输入m d

2 3

3 5

1 100

输出 5

100

题目意思相信大家都能明白，那么解题思路又是怎么样的呢

我来大概说一下，先找到兔子增长队列的公式，然后开一个字符串数组，把前一个计算出的结果保存起来，用于递推后一个结果。

把2 3|3 5这两个输入用结构图的形式写出来，你会发现他们的增长队列有一个共同的公式，能根据前面的结果把后面的结果递推出来

公式如下

F(x)=F(x-1)+F(x-m);

其中m就是指多少个月幼兔成长为成年兔子

有了这条公式，就离成功解决这问题不远了。接着，很明显，这也是个大数加法的问题，因为兔子的增长实在是太快了，要算他们的总和就必须运用大数加法，将每一个月的兔子增长数目加起来，再加上最开始的那个兔子。

源码

#include<iostream>

using namespacestd;

//初始化

voidinitial(string &a,string &b){

       while(a.size()<b.size())a='0'+a;

       while(b.size()<a.size())b='0'+b;      

}

//删除第一个字符'0'

void del(string&a){

       if(a[0]=='0')

         a.erase(0,1);

}

//大数加法

stringbigItergeAdd(string a ,string b){

       initial(a,b);

       a='0'+a;

       b='0'+b;

       for(int i=a.size()-1;i>=0;i--){

              int num1=a[i]-'0';

              int num2=b[i]-'0';

              if(num1+num2>9){

                     a[i-1]=a[i-1]-'0'+1+'0';

                     a[i]=(num1+num2)-10+'0';

              }else{

                     a[i]=(num1+num2)+'0';

              }

       }

       del(a);

       return a;

}

typedef struct{

       string str;

}MyStr;

 

int main(){

       int m,d;

       while(scanf("%d%d",&m,&d)&&m!=0&&d!=0){

              MyStrmyStr[10024]={"0"};

              stringres="1",tmp="0",c="0";

              myStr[0].str="0";

              for(int i=1;i<=d;i++){

                     if(i<=m){

                            myStr[i].str="1";

                            res=bigItergeAdd(res,"1");

                            continue;

                     }

                     tmp=bigItergeAdd(myStr[i-1].str,myStr[i-m].str);

                     myStr[i].str=tmp;

                     res=bigItergeAdd(res,myStr[i].str);

              }

              cout<<res<<endl;

       }

       return 0;

}

本文链接：https://blog.csdn.net/wjb820728252/article/details/60583288

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

R语言在矢量地图上绘制分级设色散点图_r语言在地图上绘制不同颜色散点图-程序员宅基地

文章浏览阅读1.9k次。实现效果：R语言中ggplot2包提供绘制地图、散点图的方法，是实现在矢量地图上绘制分级设色散点图核心包绘制多边形geom_polygon（data,aes,fill, colour）绘制点 geom_point .....0、需要用到的包library(maptools) # 读取shp数据常用，可以将shp数据读取为SpatialPolygonsDataFrame 格式，为DataFrame（数据帧）子类，也称为空间多边形数据帧library(ggplot2) #绘图核..._r语言在地图上绘制不同颜色散点图

【matlab】求空间两个向量之间的夹角_matlab 向量夹角-程序员宅基地

文章浏览阅读3.1w次，点赞28次，收藏73次。原点O[0,0,0]OA=[1,1,0];OB=[1,0,0];sigma = acos(dot(OA,OB)/(norm(OA)norm(OB)));%弧度制sigma/pi180%换算成角度_matlab 向量夹角

论文阅读笔记——野外和非侵入性遗传方法评估棕熊种群规模_棕熊微卫星标记-程序员宅基地

文章浏览阅读497次。论文阅读笔记论文简介标题期刊情况论文内容摘要介绍论文简介标题英文：《An evaluation of field and non-invasive genetic methodsto estimate brown bear (Ursus arctos) population size》翻译：《野外和非侵入性遗传方法评估棕熊种群规模》期刊情况期刊：《Biological Conservation》期刊情况：2020年影响因子：4.711JCR分区 / 中科院分区：Q1 / 2区审_棕熊微卫星标记

如何将手机变成一个（Linux）服务器_手机改服务器-程序员宅基地

文章浏览阅读2.2w次，点赞16次，收藏103次。看到就是赚到_手机改服务器

java double转String，去掉科学计数法_数值类型转成字符串后,不要用科学计数法-程序员宅基地

文章浏览阅读1.8k次。在数值型double转String格式时，如果同时遇到数值较大的double和小数位较多的double处理方法：double a = 123456789.10001;double b = 1.987654321;System.out.println("a: " + a);System.out.println("b: " + b);java.text.NumberFormat NF = java.text.NumberFormat.getInstance();//设置数值的小数部分所允许的最大._数值类型转成字符串后,不要用科学计数法

Fiddler抓包—手机app抓包_fiddler 移动端 app抓包-程序员宅基地

文章浏览阅读1.3k次。Fiddler抓包工作原理正常情况下，手机app是直接向服务器请求数据的，如果通过Fiddler抓包那么需要通过Fiddler，再向服务器请求数据。当app数据传到Fiddler，那么可以将请求的数据进行修改。比如app请求"123456"，那么Fiddler可以将这一串数字改成"1"，再发给服务器。此时服务器接收到的数据就是"1"。服务器返回数据到app和请求数据是一样的道理。Fid..._fiddler 移动端 app抓包

随便推点

基于SegNet和UNet的遥感图像分割代码解读_unet遥感图像分割-程序员宅基地

文章浏览阅读5.6k次，点赞9次，收藏104次。基于SegNet和UNet的遥感图像分割代码解读目录基于SegNet和UNet的遥感图像分割代码解读前言概述代码框架代码细节分析划分数据集gen_dataset.pyUNet模型训练unet_train.py模型融合combind.pyUNet模型预测unet_predict.py分类结果集成ensemble.pySegNet模型训练segnet_train.py前言上了一学期的课，趁着寒假有时间，看了往年论文和部分比赛的代码，现在整理出来。整理的这部分内容以实际操作为主，主要讲解代码部分的分析。概_unet遥感图像分割

Vue组件开发——异步组件_vue2 defineasynccomponent-程序员宅基地

文章浏览阅读566次。一、引入我们在讲异步组件之前，我们再来回顾一下webpack打包时的分包操作。我们可以使用import()异步加载模块来实现分包操作。import函数的返回值是一个Promise，所以我们可以使用then进行下一步处理。如下图所示为打包后的文件目录，因为我们如果同步加载math.js文件，此时就不存在中间的文件，此时当浏览器请求资源时，就会很慢。二、vue中的异步组件通过上面的webpack配置我们明白了为什么要进行分包操作，此时我们想一个问题，如果一个网站的页面在用户第一次浏览器时就将全部页面_vue2 defineasynccomponent

解决ToolBox升级IDEA后导致之前配置的插件消失问题（附：IDEA2020版本前后配置文件地址）【修理篇】_toolbox 下载的ide没有copy之前的插件进来-程序员宅基地

文章浏览阅读2.5k次。【修理篇】ToolBox升级IDEA后之前配置的插件消失问题（附：IDEA2020版本前后配置文件地址）在IDEA的插件配置地址都是可配置的，通过修改idea.properties可指定插件和logs的地址等这个配置文件地址在IDEA2020.1版本后出现了一些变化。如下：2020.1版本之前:配置文件地址在IDEA安装目录的bin目录下。2020.1版本之后:在此版本之后有两种方法。1.从C盘\User\Administrator里开始找AppData\Roaming\JetBra_toolbox 下载的ide没有copy之前的插件进来