首页 > 试题广场 >

附加题

[编程题]附加题
  • 热度指数:29522 时间限制: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

输出

4

说明

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

fscanf(STDIN, '%d', $n);
$line = fgets(STDIN);
$arr = explode(' ', trim($line));
$count = 0;
$i = 1;
$costMap = array();//记录首次到达i房间所用的步数
$mod = 1000000007;
//每次循环进入一个新房间
while (true)
{
    if ($i == $n + 1)
        break;
    
    //第1次到达i房间,把count记录下。并且由1<=pi<=i可知:前面房间全部偶数次访问才能抵达该房间
    $costMap[$i] = $count;
    
    //传送门,步数+1,后面就相当于已经处于传送到位的房间了
    $transport = 1;
    
    //为了抵达i+1房间,需要再次回到i房间,计算要花的步数,前面的房间可以看做全都没有访问过,所以两次首次相减即可
    $again = $costMap[$i] - $costMap[$arr[$i - 1]];//有可能为负,因为mod的原因。有可能为0,因为已经传送到位的本来就可能是同一个房间
    
    //+1进入下一房间
    $count = ($count + $transport + $again + 1) % $mod;
    $i++;
}
if ($count < 0)
    $count += $mod;
echo $count. PHP_EOL;

编辑于 2020-10-24 22:57:14 回复(0)
  • 仔细分析 1<=pi<=i 知道用动态规划做。
  • 记录第一次到达i为dp[i],此时前面的所有门肯定是已经到达偶数次了
    • 因为传送只会后退,前进的唯一方式是偶数次到达并+1,不能跳跃
    • 所以到达i门前面所有门都走过并且经过偶数次(反正法也可以证明)
  • dp[i]=dp[i-1]+第二次到达i-1 + 1
  • 第一次到达i-1门后再走一步会回到p[i-1],此时p[i-1]门到达奇数次,其他所有门到达偶数次
  • 这和第一次到达p[i-1]门的情况完全相同,所以从p[i-1]门回到i-1门,需要dp[i-1]-dp[p[i-1]]
  • 所以dp[i] = dp[i-1] + dp[i-1] - dp[p[i-1]] + 1 + 1
  • dp[i] = 2 * dp[i-1] - dp[p[i-1]] + 2
#include <iostream>
using namespace std;

long long p[1001], dp[1001], n;
const long long mod = 1e9 + 7;

int main (){
    cin >> n;
    for (int i = 1; i<= n; ++i) cin >> p[i];
    for (int i = 2; i<= n+1; ++i) 
        dp[i] = (2 * dp[i-1] - dp[p[i-1]] + 2) % mod;
    cout << (dp[n + 1] < 0 ? dp[n + 1] + mod : dp[n + 1]);
}
  • 感谢Abtt指正,已经修改过来
编辑于 2019-04-23 16:13:24 回复(17)
let n = parseInt(readline().trim());
let roomArr = readline().trim().split(" ");
let mod = 1000000007
let dp = new Array(n+2);
dp[1] = 0
for(let i = 2;i<=n+1;i++){
    dp[i]=2*dp[i-1]+2-dp[roomArr[i-2]]
    if(dp[i]<0){
        dp[i] += mod;
    }else if (dp[i] >= mod){
        dp[i] %= mod;
    }
}
console.log(dp[n+1])

发表于 2021-07-15 12:57:07 回复(0)
今日头条2018校园招聘后端开发工程师(第四批)编程题 - 题解
http://blog.csdn.net/flushhip/article/details/79458502
详细解答,没有之一(自吹一波)

源码:https://github.com/FlushHip/AlgorithmnCode
发表于 2018-03-06 17:43:33 回复(2)
皮皮浔已经解释该题可以用动态规划做,记录第一次到达i的步数为dp[i]。下面是我对状态转移方程的分段理解:dp[i] = (dp[i-1]) + (1) + (dp[i-1] - dp[p[i-1]]) + (1)。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        final int mod = 1000000007;
        int[] p = new int[n+1];
        int[] dp = new int[n+2];
        for (int i = 1; i <= n; ++i) {
            p[i] = sc.nextInt();
        }        
        for (int i = 2; i <= n+1; ++i) {
            dp[i] = (dp[i-1] << 1) - dp[p[i-1]] + 2;
            if (dp[i] < 0) dp[i] += mod;
            else if (dp[i] >= mod) dp[i] %= mod;
        }
        System.out.println(dp[n+1]);
    }
} 


编辑于 2020-03-14 13:30:38 回复(0)
思路:
(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)
//动态规划,dp[i]表示第一次到达i需要移动的次数
//dp[i] = dp[i - 1] + 第二次到达 i-1的次数 + 1
//第一次到i-1后,转移次数+1,然后到了p[i-1]
//第二次到达i-1的次数 = 1+p[i-1]到i-1的次数;
//因为第一次到达i-1以后,i-1之前的肯定都走过了偶数次
//所以p[i-1]到i-1的次数等于第一次由p[i-1]到i-1的次数
//转移方程:dp[i] = dp[i -1] + 1 + dp[i - 1] - dp[p[i-1]] + 1
//dp[i] = 2*dp[i - 1] - dp[p[i - 1]] + 2
#include<iostream>
#include<vector>

using namespace std;

const long long int mod = 1e9 + 7;
int main()
{
    int n;
    cin >> n;
    vector<int>p(n+1, 0);
    for(int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }
    
    vector<int>dp(n+2, 0);//记录第一次到达i为dp[i]
    dp[1] = 0;
    for(int i = 2; i<= n+1; i++)
    {
        dp[i] = (2*dp[i - 1] - dp[p[i - 1]] + 2) % mod;
    }
    cout << (dp[n + 1] < 0 ? dp[n + 1] + mod : dp[n + 1]);
    return 0;
}



发表于 2020-09-01 16:48:05 回复(0)
//直接求解可以通过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)
#include <bits/stdc++.h>
using namespace std;

const int M = 1e9+7;

int main(){
    int n;
    scanf("%d", &n);
    int a[n], dp[n+1];
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    for(int i=1;i<=n;i++)
        dp[i] = (2*dp[i-1]%M - dp[a[i-1]-1]+2) % M;
    printf("%d\n", dp[n]);
    return 0;
}

发表于 2020-12-02 00:41:13 回复(0)
真的绷不住了,被题目坑死了,1000000007难道等于 (10e9 + 7)吗???不知道是不是语言的问题,在js里面要用1e9 + 7表示,我说为什么死都做不出来服了
发表于 2024-03-09 20:24:46 回复(0)
我服了,提交给我生成了一个大循环,全部传送到最开始

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)
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)
测试用例的结果有问题,预期结果是每步取模还范围溢出的结果
发表于 2023-02-07 17:47:22 回复(0)
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
long long p[N], f[N];
int n,res;
int main() {
    cin >> n;
    // 只会往做走 往又走只有靠走了奇数次
    for(int i = 1; i <= n; ++ i) {
        cin>>p[i];
    }
    // 我们要求到n + 1需要走多少次
    // 可以求子问题 第二次走到n需要走多少次
    // 子问题 第二次走到n - 1需要走多少次
    // f[i] 如何 由 f[i - 1] 转移过来?
    // 我们假设f[i]记录的是到达i两次需要的次数
    // f[i - 1] + 1 次到达i第一次
    // 然后i走到p[i] p[i]再次走到i需要多少次
    // p[i] 走到 i - 1 
    // 综上f[i] 表示第二次进入i需要的行程数
    f[0] = 0;
    for(int i = 1; i <= n ; ++i) {
        // f[i] += f[i - 1] + 1; 
        int j = p[i];
        // f[i] += (f[i - 1] - f[j - 1] + 1);
        f[i] = (2*f[i - 1] - f[j - 1] + 2) %mod;
    }
    cout<<(f[n] + mod ) % mod<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2022-12-07 19:26:21 回复(0)
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)
n=int(input())
pi=list(map(int,input().split()))
dp=[0 for i in range(n+1)]
for i in range(1,n+1):
    #dp[i]第一次到i所需的移动次数,此处的i就是n+1
    dp[i]=(dp[i-1]+(dp[i-1]+1-dp[pi[i-1]-1])+1)%1000000007
print(dp[-1])

发表于 2022-06-24 10:19:31 回复(0)
# 设dp[i] = 两次到达第i房间。
# 则dp[i] = 第一次到达i + 第二次到达i
# 设dd[i] = 第二次到达i
# 有dp[i] = dp[i-1]+1 + dd(i)+1
# 因为第一次到达i 后,会跳到pi
# 又因为pi<=i 所以第二次到达i时,i-1也必须到达偶数次。
# 因此dd[i] = 跳到pi后 回到 i-1 点次数 +1
# 因为跳到pi 点时,pi进入奇数次
# 所以从pi 点到达i-1 点且i-1次数为偶数的次数,等价于从pi-1点到i-1点且i-1点为偶数次数-1,即dp[i-1]-dp[pi-1]-1
# 因此 dd[i] = dp[i-1] - dp[pi-1]
# 即 dp[i] = 2*dp[i-1]-dp[pi[i]-1] +2

n=int(input())
pi = list(map(int,input().split(' ')))
def solution(n,pi):
    dp = [0]*(1+n)
    pi.insert(0,0)
    mod = 1000000007
    for i in range(1,n+1):
        dp[i] = 2*dp[i-1]-dp[pi[i]-1] +2
#         print(dp[i],dp[i-1],dp[pi[i]-1])
    print(dp[n] % mod)
    
    

solution(n, pi)
    
    


发表于 2022-06-12 01:08:44 回复(0)
i房间的传送门可以把人传送到房间pi(1<=pi<=i),这句话很关键
发表于 2022-04-19 09:38:11 回复(0)
public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] p = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                p[i] = sc.nextInt();
            }
            sc.close();
            int mod = 1000000007;

            int[] f = new int[n + 2];
            f[1] = 0;
            for (int i = 2; i <= n + 1; i++) {
                //f[i - 1]表示第一次到达i - 1,接下来会去p[i - 1], 这会耗费一步;
                //到达p[i - 1]后,此时必然是第奇数次到达p[i - 1],故还会花费上一次从p[i - 1]到f[i - 1]的路才会回到i - 1,使得i - 1走过两次,才能去i;
                //由于第一次到达p[i - 1]需要耗费f[p[i - 1]], 第一次到达i - 1耗费f[i - 1];
                //那么从p[i - 1]到i - 1就需要耗费f[i - 1] - f[p[i - 1]]
                //第二次达到i - 1后,还需要走一步到达i

                //即,f[i] = (f[i - 1] + 1) + (f[i - 1] - f[p[i - 1]]) + 1;
                //第一部分:第一次到达f[i - 1], 并花费一步到p[i - 1];
                //第二部分: 第二次到达p[i - 1], 此时必定是奇数次,需要花费之前一样的步数到达i - 1
                //第三部分:第二次到达i - 1, 走一步到达i;
                f[i] = 2 * f[i - 1] % mod - f[p[i - 1]] + 2;
            }
            System.out.println(f[n + 1]);
        }
    }
发表于 2022-04-09 15:36:24 回复(0)
const ll mod = 1000000007;
ll dp[1010];//对于一个点从偶次状态到偶次状态的最小步数
int p[1010];
int n;

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        if(p[i] == i){
            ans = (ans + 1ll * 2) % mod;
            dp[i] = 1ll * 2;
        }
        else{
            ll now = 0;
            for(int j = p[i]; j < i; j++){
                now = (now + dp[j]) % mod;
            }
            (now = now + 2ll) % mod;
            dp[i] = now;
            ans = (ans + now) % mod;
        }
    }
    cout << ans << "\n";
}
这个题我们会发现,对于首次到一个点i,到达1 ~ i - 1的点都经过了偶数次,所以我们处理出每一个点从经历偶数次到经历偶数次的步数用dp[i]表示即可,这只是一个思维题,其实O(n)复杂度就能过。
发表于 2021-10-28 19:37:21 回复(0)