首页 > 试题广场 >

附加题

[编程题]附加题

热度指数：30173 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

存在n+1个房间，每个房间依次为房间1 2 3...i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略：
A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1；
B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；
现在路人甲想知道移动到房间n+1一共需要多少次移动；

输入描述:

第一行包括一个数字n(30%数据1<=n<=100，100%数据 1<=n<=1000)，表示房间的数量，接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。

输出描述:

输出一行数字，表示最终移动的次数，最终结果需要对1000000007 (10e9 + 7) 取模。

示例1

输入

2
1 2

输出

说明

开始从房间1 只访问一次所以只能跳到p1即 房间1， 之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，之后采用策略A跳到房间3，因此到达房间3需要 4 步操作。

算法知识视频讲解

Java

符石酒

我服了，提交给我生成了一个大循环，全部传送到最开始

import java.util.ArrayList;

import java.util.Random;

import java.util.Scanner;

public class Main {

public static class Room {

int roomId;

int vistIndex = 0;

int translateId;

public Room(int id, int translateId) {

this.roomId = id;

this.translateId = translateId;

}

int visitRoom() {

this.vistIndex += 1;

int result = 0;

if (this.vistIndex % 2 == 0) {

result = this.roomId + 1;

} else {

result = this.translateId;

}

return result;

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int totalNum = Integer.parseInt(in.nextLine());

ArrayList<Room> rooms = new ArrayList<Room>();

int i = 1;

while (in.hasNextInt()) {

int translateId = in.nextInt();

Room room = new Room(i, translateId);

rooms.add(room);

i += 1;

}

rooms.add(new Room(totalNum + 1, 0));

int key = 1;

int steps = 0;

if (totalNum >= 1) {

while (key <= totalNum) {

Room visitRoom = rooms.get(key - 1);

key = visitRoom.visitRoom();

steps += 1;

}

} else {

steps = 1;

}

System.out.println(steps);

}

发表于 2023-09-18 16:06:55 回复(0)

Java

neukfc

import java.util.Scanner;

import java.util.List;

import java.util.ArrayList;

public class Main {

static int[] visit;

static int[] p;

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int num = 0;

int i = 0;

if(in.hasNextInt()){

num = in.nextInt();

}

visit = new int[num];

p = new int[num];

while (i < num && in.hasNextInt()){

p[i] = in.nextInt() - 1;

i++;

}

visit[0] = 1;

System.out.println(jump(num));

}

public static long jump(int des){

long result = 0;

long mod = (long)(1e9 + 7);

if (des <= 0 || des > p.length){

return 0;

}

result =(2 * jump(des - 1) - jump(p[des - 1]) + 2) % mod;

return (result >= 0 ? result : result + mod);

}

发表于 2023-08-06 16:34:12 回复(0)

Java

牛客81885857号

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ps = new int[n + 1];
        int index = 1;
        while (index <= n) {
            ps[index ++] = sc.nextInt();
        }
        long[] dp = new long[n + 1];
        dp[0] = 0L;
        dp[1] = 2L;
        for (int i = 2; i <= n; i ++) {
            dp[i] = 2 * dp[i - 1] - dp[ps[i] - 1] + 2;
            dp[i] =  dp[i] < 0 ? dp[i] + 1000000007 : dp[i] % 1000000007;
        }
        System.out.println(dp[n]);
    }
}

发表于 2022-10-05 00:39:53 回复(0)

Java

offer收割机001

dp[i]表示第二次到达i的经历的次数

/**
             * dp[i-1] +1 第一次到达i，
             * +1 跳回nums[i]
             * 此时nums[i]奇数次，nums[i]之后到i-1都是偶数次

* 可以看成是从num[i]-1 走一步走过来的

             * -1 到达nums[i]-1 就相当于 nums[i]也是偶数从nums[i]到i-1都是偶数
             * +(dp[i-1]-dp[nums[i]-1]) 从nums[i]-1 到达i-1且i-1还是偶数次
             * +1 第二次到达 i即为所求
             * 总体上 dp[i] = dp[i-1]+1+1-1+(dp[i-1]-dp[nums[i]-1])+1;
             * 汇总
             * dp[i] = 2*dp[i-1]+2-dp[nums[i]-1];
             */

import java.util.*;
public class ChuanSongMen {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n+1];
        int[] dp = new int[n+1];
        dp[0] = 0;
        int mod = 1000000007;
        for(int i = 1;i<=n;i++){

            nums[i] = sc.nextInt();
            /**
             *  dp[i-1]+1 第一次到达i，
             *  +1 跳回nums[i]
             *  此时nums[i]奇数次，nums[i]之后到i-1都是偶数次
             *  此时和第一次到达nums[i]的情况完全相同
             *  -1 到达nums[i]-1 就相当于 nums[i]也是偶数 从nums[i]到i-1都是偶数
             *  +(dp[i-1]-dp[nums[i]-1]) 从nums[i]-1 到达i-1且i-1还是偶数次
             *  +1 爹第二次到达 i即为所求
             *  总体上 dp[i] = dp[i-1]+1+1-1+(dp[i-1]-dp[nums[i]-1])+1;
             *  汇总
             *  dp[i] = 2*dp[i-1]+2-dp[nums[i]-1];
             */
            dp[i] = (2*dp[i-1]-dp[nums[i]-1]+2)%mod;
        }
        dp[n] = dp[n]>0?dp[n]:dp[n]+mod;
        System.out.println(dp[n]);
    }
}

发表于 2020-08-12 09:02:04 回复(1)

Java

时光不暖少年梦

import java.util.*;
public class Main{
public static void main(String[] args){
    Scanner scan=new Scanner(System.in);
    int len=scan.nextInt();
    int[] arr=new int[len+1];
    long[] cnt=new long[len+1]; //保存的是当前位置调到下一个+1位置需要的次数
    Arrays.fill(cnt,0);
    cnt[1]=0;
    for(int i=0;i<len;i++){
        arr[i+1]=scan.nextInt();
    }
    Long res=0l; //保存所有的跳跃次数
    for(int i=1;i<=len;i++){
        long sum=0l;
        int pos=arr[i];
        while(pos<i){
            sum=(sum+cnt[pos])%1000000007;
            pos++;
      }
        cnt[i]=sum+2;
        res=(res+cnt[i])%1000000007;
    }
    System.out.println(res);
    }
}

编辑于 2019-07-20 00:32:11 回复(0)

Java

牛奶椰子糖

//直接求解可以通过60%
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        int roomNum=in.nextInt();
        int[] visitedNum=new int[roomNum];
        int[] transferDoor=new int[roomNum];
        for(int i=0;i<roomNum;i++)
        {
            transferDoor[i]=in.nextInt()-1;
        }
        int movingCount=0;//移动次数
        
        //从第一个房间开始 第一个房间已经过问过一次
        visitedNum[0]=0;
        int roomID=0;
        while(roomID!=roomNum)
        {
             visitedNum[roomID]+=1;
            movingCount++;
            if(visitedNum[roomID]%2==0)
            {
                roomID+=1;
            }
            else
            {
                roomID=transferDoor[roomID];
            }
        }
        System.out.println(movingCount%1000000007);
    }

发表于 2019-03-08 19:41:17 回复(5)

Java

HenryC

思路：

(1) 每个房间的移动次数记为d[j]，甲要移动到j，需要从j-1移动，即 d[j] = d[j-1] + 1,

(2) 此时d[j]第一次访问，甲跳转pi[j]，移动1次，此时pi[j]为奇数次访问，状态相当于d[pi[j]-1] +1,，甲需要从pi[j]开始移动，最后移动到 j-1, 且d[j-1]也应该再次变为偶数次访问，移动次数为d[j-1] - d[pi[j]-1] - 1, 移动到 j-1后，再加1，d[j-1] - d[pi[j]-1] + 1,为甲重新移动到j房间，(2)***移动了d[j-1] - d[pi[j]-1] +1次

(3) (1) + (2) = 2*d[j-1] - d[pi[j]-1] +2

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long mod = 1000000007;
int n = in.nextInt();
long d[] = new long [n+1];
int pi[] = new int[n+1];
for(int i = 1; i < n+1;i++){
pi[i] = in.nextInt();
}
if(n==1){
System.out.println(1);
return;
}
for(int j = 1; j < n+1; j++){
d[j] = (2 * d[j-1]%mod - d[pi[j]-1] + 2) % mod;
}
System.out.println(d[n]);
}
}

编辑于 2019-01-21 00:11:05 回复(0)