快手[编程题]魔法深渊

版权声明:本文为博主-姜兴琪原创文章,未经博主允许不得转载。

前几个月放映的头号玩家简直火得不能再火了,作为一个探索终极AI的研究人员,月神自然去看了此神剧。

由于太过兴奋,晚上月神做了一个奇怪的梦,月神梦见自己掉入了一个被施放了魔法的深渊,月神想要爬上此深渊。

已知深渊有N层台阶构成(1 <= N <= 1000),并且每次月神仅可往上爬2的整数次幂个台阶(1、2、4、....),请你编程告诉月神,月神有多少种方法爬出深渊

输入描述:

输入共有M行,(1<=M<=1000)

第一行输入一个数M表示有多少组测试数据,

接着有M行,每一行都输入一个N表示深渊的台阶数

输出描述:

输出可能的爬出深渊的方式

示例1

输入

4
1
2
3
4

输出

1
2
3
6

解题思路:

第6个台阶可以从2,4,5一次性到达,把dp[2],dp[3],dp[4],dp[5]求和即可

第1000个台阶可以从488(1000-512),744(1000-256)...999一次性到达,把dp[488]+...+dp[999]求和即可

备注:

为了防止溢出,可将输出对10^9 + 3取模
import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] sc = new int[n];
        for(int i=0;i<n;i++){
            sc[i]=in.nextInt();
        }
        int[] dp=new int[1001];
        for(int i=1;i<1001;i++){
            dp[i]=0;
        }
        dp[0]=1;
        int[] byteArray={1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
        for(int i=0;i<1000;i++){
            for(int j=0;j<10 && i>= byteArray[j];j++){
                dp[i]+=dp[i-byteArray[j]];
                dp[i]%=(1000000000 + 3);
            }
        }
        for(int i=0;i<n;i++){
            System.out.println(dp[sc[i]]);
        }
        in.close();
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PHP实战技术

PHP找工作指南!如有雷同,算我抄你!

本文章是小编经过58、前程无忧、智联招聘、51、拉勾网等招聘网站总结PHP开发工作所需技能的部分总结,如有不对或不全之处,还请多多提意见!

24780
来自专栏知晓程序

举报!这里有人,在光天化日之下聚众撸猫

但并不是每个人都有机会成为「猫奴」。这时候,你需要 「吸猫君」 ,来帮你开启「云吸猫」的生活。

9420
来自专栏练小习的专栏

网站508规范(译)

出处:蓝色理想和玩·艺|中国同步发布 Guide to the Section 508 Standards for Electronic and Informa...

19650
来自专栏小狼的世界

推荐给开发和设计人员的iPad应用

葫芦瓢送了一部iPad,把玩几天后,不管是从iTunes商店的推荐,还是各种应用推荐软件的列表中,没有找到特别好的应用。还是利用搜索引擎,找到了一些对开发人员...

19620
来自专栏FreeBuf

【FB TV】一周「BUF大事件」:弹幕网站Acfun遭遇黑客攻击

本周BUF大事件还是为大家带来了新鲜有趣的安全新闻,本周弹幕社区网站Acfun遭遇黑客攻击,剧情峰回路转;航路纵横被爆泄露用户隐私信息,官方紧急调整;英特尔披露...

10800
来自专栏机器学习和数学

[编程经验] 链家23个全国主要城市的现房数据分析

今天起来看到一个公众号发的推文,分析了链家上面成都的房价数据,自己好奇也玩了一把,收集了全国23个主要城市的在售房产数据,并作了对比,拿出来跟大家分享。涉及的城...

29830
来自专栏游戏杂谈

游戏繁体化那些让人蛋疼的事儿

项目首先从国内开始做,然后跟台湾那边谈了合作,要发行台湾版本。这过程中遇到一些问题,特别的坑,特此记录一下

15120
来自专栏LanceToBigData

TCP/IP(二)物理层详解

前言   在前面说了一下,计算机网络的大概内容,没有去深刻的去了解它,这篇文章给大家分享一下物理层!   我们知道ISO模型是七层,TCP/IP模型是五层,而t...

31450
来自专栏牛客网

19届前端实习生面经

17500
来自专栏程序员互动联盟

【程序员故事】搞笑篇

1、我真想开个程序员餐厅了,我当老板娘,进门时先写代码再进,一楼餐厅分C包间、java包间、linux/unix包间。搞开源软件的就坐大厅里,搞Ruby的上二楼...

28230

扫码关注云+社区

领取腾讯云代金券