| 题目名称 | 1996. 迷之阶梯---加强版 |
|---|---|
| 输入输出 | Stairs.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 .CPP
于2015-06-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：16， 提交：25， 通过率：64% | ||||
 <蒟蒻>我要喝豆奶 |
100 | 0.003 s | 0.32 MiB | C++ |
|
<蒟蒻>我要喝豆奶 |
100 | 0.003 s | 0.32 MiB | C++ |
|
<蒟蒻>我要喝豆奶 |
100 | 0.011 s | 0.32 MiB | C++ |
 .CPP |
100 | 0.012 s | 0.30 MiB | C++ |
|
.CPP |
100 | 0.013 s | 0.30 MiB | C++ |
 Zayin |
100 | 0.018 s | 0.47 MiB | C++ |
 LOSER |
100 | 0.021 s | 0.40 MiB | C++ |
 0 |
100 | 0.026 s | 0.44 MiB | C++ |
 面对疾风吧 疾风 疾风吧 |
100 | 0.027 s | 0.31 MiB | C++ |
 stdafx.h |
100 | 0.030 s | 0.31 MiB | C++ |
| 关于 迷之阶梯---加强版 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
改一下题吧 你对拍拍点NB数据出来 @.cpp
0
2015-06-14 16:20
5楼
| ||||
|
加强体现在哪？？？？？？另外那个是2*k？？？？还是2^k??????
| ||||
|
回复 @溪哥 :
数据库错了，马上改数据，原版程序交上一分不给，全是o（nlong（n））才能过的 .CPP
2015-06-13 14:39
3楼
| ||||
|
把普通版的复制粘贴就过了
| ||||
|
快速幂公式（n的p次幂）
long long aux(int n,int p) { if(p==0) return 1; if(p==1) return n; if(p%2!=0) return (n*aux(n,(p-1)/2)*aux(n,(p-1)/2)); else return (aux(n,p/2)*aux(n,p/2)); } 比pow更快而且实用性更强； .CPP
2015-06-12 20:07
1楼
| ||||
forever
神利·代目【题目描述】
迷之阶梯---加强版
在经过地球防卫小队的数学家连续多日的工作之后，外星人发的密码终于得以破解。它告诉我们在地球某一处的古老遗迹中，存在有对抗这次灾难的秘密道具。防卫小队立刻派出了一个直升机小分队，迅速赶到了这处遗迹。要进入遗迹，需要通过一段迷之阶梯。登上阶梯必须要按照它要求的方法，否则就无法登上阶梯。它要求的方法有以下三个限制：
1．如果下一步阶梯的高度只比当前阶梯高1，则可以直接登上。
2．除了第一步阶梯外，都可以从当前阶梯退到前一步阶梯。
3．当你连续退下k步后，你可以一次跳上不超过当前阶梯高度+2k的阶梯。比如说你现在位于第j步阶梯，并且是从第j+k步阶梯退下来的，那么你可以跳到高度不超过当前阶梯高度+ 2k的任何一步阶梯。跳跃这一次只算一次移动。
开始时我们在第一步阶梯。由于时间紧迫，我们需要用最少的移动次数登上迷之阶梯。请你计算出最少的移动步数。
【输入格式】
第1行：一个整数N，表示阶梯步数。
第2行：N个整数，依次为每层阶梯的高度，保证递增。
【输出格式】
第1行：一个整数，如果能登上阶梯，输出最小步数，否则输出-1。
【样例输入】
5
1 2 3 4 5
【样例输出】
4
【提示】
数据范围
对于50%的数据：1≤N≤200。
对于100%的数据：1≤N≤20000。 每步阶梯高度不超过2^31-1。
卡时间啊，快速幂也不一定全过哦，想想位运算吧
在此提供快速幂函数
感谢ztc提供快速幂函数，非常感谢
long long aux(int n,int p)
{
if(p==0)
return 1;
if(p==1) return n;
if(p%2!=0) return (n*aux(n,(p-1)/2)*aux(n,(p-1)/2));
else return (aux(n,p/2)*aux(n,p/2));
}
【来源】
cogs