首页 > 试题广场 >

魔法深渊

[编程题]魔法深渊
  • 热度指数:12416 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
前几个月放映的头号玩家简直火得不能再火了,作为一个探索终极AI的研究人员,月神自然去看了此神剧。
由于太过兴奋,晚上月神做了一个奇怪的梦,月神梦见自己掉入了一个被施放了魔法的深渊,月神想要爬上此深渊。

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

数据范围: ,输入的数据组数满足

输入描述:
输入共有M行

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

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


输出描述:
输出可能的爬出深渊的方式
示例1

输入

4
1
2
3
4

输出

1
2
3
6

备注:
为了防止溢出,可将输出对10^9 + 3取模
/*
动态规划。类似于跳台阶。
用递归会超时。
取模防止溢出。
*/
import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        int[] dp = new int[1001];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= 1000; i++) {
            int tmp = 1;
            while (tmp <= i) {
                dp[i] += dp[i - tmp];
                tmp *= 2;
                dp[i] %= 1000000000 + 3;
            }
        }
        while (T-- > 0) {
            int n = in.nextInt();
            System.out.println(dp[n]);
        }
    }
}

发表于 2019-06-28 11:07:14 回复(1)
"""
台阶问题考虑动态规划
每次仅可往上爬2的整数次幂个台阶(1、2、4、....)
当前台阶方法数 = 所有一次可到达当前台阶方法数的和
dp[n] = dp[n-1]+dp[n-2]+dp[n-4]+... ( n-t>=0,dp[0]=1 )
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    m = int(input().strip())
    mod = 1000000003
    dp = [0] * 1001
    dp[0] = 1
    for i in range(1, 1001):
        t = 1
        while t <= i:
            dp[i] += dp[i - t]
            dp[i] %= mod
            t = t * 2
    for _ in range(m):
        n = int(input().strip())
        print(dp[n])

发表于 2019-07-05 13:24:48 回复(7)
动态规划!
f(0) = 1;  f(1) = 1;  f(2) = 2;  f(3) = 3; f(4) = 6……
这里与跳台阶每次只能选择跳一格或者两格的题目很类似。
从后往前考虑,台阶为n时,第一次可以跳2的指数个台阶,总共有1,2,4,8……k(k小于n)种跳法,剩下的n - k个台阶为台阶为n-k的跳法,可以得到下式:
f(n) = f(n-1) + f(n - 2) + f(n - 4) +... + f(n - k)
递归时将过程值保存,因为当计算f(5) = f(4) + f(3) + f(1)时,f(3)又要计算一遍,时间复杂度会爆表。
#include <iostream>
#include <algorithm>
using namespace std;

long Result[10001] = {0}; //存放各个n对应的结果


long NumOption(int n)
{
	long res = 0;
	if (n == 0) Result[0] = 1;
	if (n == 1) Result[1] = 1;
	if (n == 2) Result[2] = 2;
	int step = 0;
	if (Result[n] != 0) return Result[n]; // 若结果里已经有值,直接取出不用递归
	while (true)
	{
		if (n - pow(2, step) < 0) break; // 循环结束
		res += NumOption(n - pow(2, step));
		step++;
	}
	Result[n] = res % (1000000003);
	return Result[n];
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int in;
		cin>>in;
		long res = NumOption(in);
		cout << res << endl;
	}
	return 0;
}

编辑于 2020-04-01 10:09:49 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m,n[1001],res[1001];
    cin>>m;
    for(int i=0;i<m;i++)
        cin>>n[i];
    vector<int> p = {1,2,4,8,16,32,64,128,256,512};
    vector<long long> dp(1001,0);
    dp[0] = 1;
    for (int i = 1; i < dp.size();i++)
    {
        for (int j = 0; j < p.size();j++)
        {
            if (i >= p[j])
            {
                dp[i] = dp[i] + dp[i - p[j]];
                dp[i] %= 1000000003LL;
            }
        }
    }
    for(int i=0;i<m;i++)
        cout<<dp[n[i]]<<endl;
    return 0;
}

发表于 2019-06-30 14:53:04 回复(1)
	
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+3;
int main(){
int M, N;
int a[1001] = {1, 1};
for(int i=2; i<=1000; i++){
int p = 1;
while(p<=i){
a[i] = (a[i]+a[i-p])%MOD;
p <<= 1;
}
}
cin>>M;
while(M--){
cin>>N;
cout<<a[N]<<endl;
}
return 0;
}
编辑于 2019-07-06 20:19:35 回复(3)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    long long dp[1001]={0};
    dp[1]=dp[0]=1;
    for(int i=2;i<=1000;i++){
        for(int j=1;j<=i;j<<=1)
            dp[i]+=dp[i-j];
        dp[i]%=1000000000 + 3;
    }
    cin>>n;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        cout<<dp[t]<<endl;
    }
    return 0;
}

发表于 2019-10-19 10:28:57 回复(0)
#include<iostream>
#include<vector>
usingnamespacestd;
intmain()
{
    intM;
    cin>>M;
    vector<int>***(10001,0);
    ***[0]=1;
    intsub[]={1,2,4,8,16,32,64,128,256,512};
    for(inti=0;i<1001;i++)
    {
        for(intj=0;j<10&&i>=sub[j];j++)
        {
            ***[i]+=***[i-sub[j]];
            ***[i]%=1000000003;
        }
    }
    intN=0;
    for(inti=0;i<M;i++)
    {
        cin>>N;
        cout<<***[N]<<endl;
    }
    return0;
}
发表于 2019-08-09 12:39:14 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int M=sc.nextInt();
        int[] nums=new int[M];
        int max=0;
        for(int i=0;i<M;i++){
            int num=sc.nextInt();
            nums[i]=num;
            max=Math.max(max,num);
        }
        int[] dp=new int[max+1];
        dp[0]=1;
        for(int i=1;i<=max;i++){
            for(int j=0;i-(int)Math.pow(2,j)>=0;j++){
                dp[i]+=dp[i-(int)Math.pow(2,j)];
                //经验,可以在每次都取MOD,效果等同于最后取MOD,
                        //好处是能够防止溢出
                dp[i]%=1000000003;
            }
        }
        for(int i=0;i<M;i++){
            System.out.println(dp[nums[i]]);
        }
    }
}

发表于 2019-08-05 11:53:43 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Solution4_魔法深渊 {

    final static int MOD = 1000000003;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(bf.readLine());
        int[] ans = new int[m];
        //保存最大那个数字 求得dp[max],直接在根据输入打印dp中对应的值
        int max = 0;
        for (int i = 0; i < m; i++) {
            int a = Integer.parseInt(bf.readLine());
            if (max<a) max = a;
            ans[i] = a;
        }
        int[] dp = jump(max);
        for (int i = 0; i < m; i++) {
            System.out.println(dp[ans[i]]);
        }

    }

    private static int[] jump(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j *= 2) {
                dp[i] += dp[i - j];
                dp[i] = dp[i] % MOD;
            }
        }
        return dp;
    }
}
发表于 2019-08-03 16:50:25 回复(0)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin>>n;
    long long a[1001]={0};
    int b[10]={1,2,4,8,16,32,64,128,256,512};
    
    a[0]=1;
    a[1]=1;

    for(int k=2;k<=1000;k++){
            int l=0;
            while(b[l]<=k){
                a[k]=(a[k]+a[k-b[l]])%(1000000003);
                l++;
            }
    }
    int m;
    for(int i=0;i<n;i++){
        cin>>m;
        cout<<a[m]<<endl;
    }
    
}
发表于 2019-07-23 21:15:31 回复(1)

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

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

编辑于 2018-11-11 00:41:31 回复(0)
发表于 2018-11-07 15:48:18 回复(0)
#coding=utf-8
def stair(m):#动态规划
    import math #导入对数哈函数
    re=[]#实现记忆
    for n in range(m+1):#从0~m进行计算
        if n==0:#边界条件
            re.append(1)
        elif n==1:
            re.append(1)
        else:
            d,s=int(math.log(n,2)),0#找到最接近的2**i,如n=5时,d=2
            for i in range(d+1):
                s+=re[n-2**i]#re[n]=re[n-2**i]+re[n-2**(i-1)]+.....+re[n-2**0]
            re.append(s)
    return re[-1]
while 1:
    try:
        n=int(input())
        for i in range(n):
            print(stair(int(input()))%1000000003)#防止溢而取模
    except:
        break

发表于 2020-08-17 12:14:36 回复(0)
#include<iostream>
(720)#include<vector>

using namespace std;

int main(void){
    int n;
    cin>>n;
    int stepNum;
    vector<int> dp(10001, 0);
    dp[1] = 1;
    dp[0] = 1;
    for (int i = 2; i <= 1000; i++){
        int Ex = 1;
        while (Ex <= i){
            dp[i] = (dp[i] + dp[i - Ex]) % (1000000000 + 3);
            Ex *= 2;
        }
    }
    for (int i = 0; i < n; i++){
        cin>>stepNum;
        cout<<dp[stepNum]<<endl;
    }
    return 0;
}

发表于 2020-05-02 17:58:59 回复(0)
对斐波那契数列进行推广即可
n=int(input())
def find(n):
    dp=[1]
    for i in range(1,n+1):
        s=0
        for j in range(n):
            if 2**j<=i:
                s+=dp[i-2**j]
            else:break
        dp.append(s)
    return dp[-1]
for i in range(n):
    print(find(int(input()))%(10**9 + 3))


发表于 2020-04-24 10:14:16 回复(0)
import math
M = int(input())
mi = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
mod = 1000000003
for i in range(M):
    n = int(input())
    dp = [0]*(n+1)
    dp[0] = 1
    dp[1] = 1
    for ni in range(2, n+1):
        end = int(math.log(ni, 2))
        for j in range(0, end+1):
            dp[ni] += dp[ni-mi[j]]
        dp[ni] %= mod
    print(dp[n])

发表于 2020-04-22 21:21:19 回复(0)
G^J头像 G^J
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        for(int i=0;i<m;i++) {
            int n = in.nextInt();
            System.out.println(ans(n));
        }
    }
    
    private static long ans(int n) {
        if(n == 1) {
            return 1;
        }
        long[] dp = new long[n+1];
        dp[1] = 1;
        dp[0] = 0;
        for(int i=2;i<=n;i++) {
            long sum = ((i&(i-1))==0) ? 1 : 0;
            for(int j=i-1;j>=1;j--) {
                if(((i-j)&(i-j-1))==0) {
                    sum+=dp[j];
                    sum%=1000000003;
                }
            }
            dp[i] = sum;
        }
        return dp[n];
    }
}
发表于 2020-03-11 01:09:32 回复(0)
完全背包问题,不过一定要注意溢出(真的是防不胜防)😥
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int M = Integer.parseInt(sc.nextLine());
        for(int i = 0;i<M;i++){
            int N = Integer.parseInt(sc.nextLine());
            long[] dp = new long[N+1];
            dp[0] = 1;
            for(int j = 1;j<=N;j++){
                for(int step : generateSteps(N)){
                    if(j >= step){
                        dp[j] = dp[j]+dp[j-step];
                        dp[j] %= 1000000003;
                    }
                }
            }
            long res = dp[N] % 1000000003;
            System.out.println(res);
         }
    }
    
    private static List<Integer> generateSteps(int N){
        List<Integer> steps = new ArrayList<>();
        int step = 1;
        while(N > 0){
            steps.add(step);
            N -= step;
            step *= 2;
        }
        return steps;
    }
}


发表于 2020-02-27 21:42:10 回复(0)
没有AC的注意一下取模,我就卡在这里了
发表于 2020-02-24 19:24:08 回复(0)
#include<iostream>
using namespace std;

int dps(int i, int dp[]){
    if(dp[i]!=0) return dp[i];

    /*//法三,不知为何错误
    for(int j=i/2*2;j>=1;j/=2){
        dp[i] += dps(i-j, dp);
        dp[i] %= 1000000003;
    }*/
    
    //法二
    for(int j=1;j<=i;j*=2){
        dp[i] += dps(i-j, dp);
        dp[i] %= 1000000003;
    }
    return dp[i];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m,n;
    int dp[1001] = {0};
    dp[0]=1;dp[1]=1;
    /*//法一
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=i;j*=2){
            dp[i] += dp[i-j];
            dp[i] %= 1000000003;    //防止溢出
        }
    }*/
    cin>>m;
    while(m--){
        cin>>n;        
        //cout<<dp[n]<<endl; //法一
        cout<<dps(n, dp)<<endl;
    }
    return 0;
}
递归是自上而下,还是自下而上快?
发表于 2020-01-29 00:25:02 回复(0)