题解 | #附加题#
附加题
http://www.nowcoder.com/practice/58b04ed2865f4ff4921290f1bd4ee486
这种题目首先肯定是找模型 我先想到的肯定是如果 pi 都为 1 ,要怎么处理 然后发现这个简单了 如果到底n个房间的次数为 P(n); P(n + 1) = 2 * P(n) + 2 ;//因为回到1 肯定就是重走一遍 1 到 n 的路程 所以肯定是2倍了 然后有 额外走了 回 1 和到 n + 1 的路程 所以要 + 2 这个时候我们可以开始想 如果 不是会第一个位置 怎么减? 假定 到第 n 个位置 需要 P(n) 次 ,n 处的 指向房间 pi 为 x 不难推出 我们只是跳过了上面从 房间 1 到 房间 x 的过程,所以如下即可 P(n + 1) = 2* P(n) + 2 - P(x) 如此 把 n 个房间的 指向房间 给成数组形式即可 arr[n -1] 就是第n 间房的 指向数 Pi 即 xP(n+1) = 2 * P(n) + 2 - P(arr[n-1])将 n + 1 换成 n ,则 P(n) = 2 * P(n-1) + 2 - P(arr[n-2])
可得函数,function getNumAll(n,arr){又因为需要取模 1000000007if(n == 1){ return 0 }else if(n == 2){ return 2; }else{ return 2*getNumAll(n-1,arr) + 2 - getNumAll(parseInt(arr[n-2]),arr); }}
所以返回值 取模 即可
但是测试发现有误,猜测是数值过大,然后 返回值提前判断 是否需要取模,再测试,发现取值负数了,所以又加了一次 虽然成功了,但是一看速度。。。汗
Ps:提交代码如下
var n = parseInt(readline()); var arr = readline().split(" "); print(getNumAll(1*n+1,arr)%1000000007); function getNumAll(n,arr){ if(n == 1){ return 0 }else if(n == 2){ return 2; }else{ var result = 2*getNumAll(n-1,arr) + 2 - getNumAll(parseInt(arr[n-2]),arr); if(result > 1000000007){ result = result % 1000000007; } return result + 1000000007; } }