守望者的涵意

导读：　守望者的涵意(共3篇)守望者的逃离noip2007——解题报告守望者的逃离（NOIP2007）【题目描述】恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有...

欢迎来到中国招生考试网http://www.chinazhaokao.com/成考报名栏目，本文为大家带来《守望者的涵意》，希望能帮助到你。

守望者的逃离noip2007——解题报告
守望者的涵意 第一篇

守望者的逃离（NOIP2007）

【题目描述】

恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意：守望者跑步、闪烁或休息活动均以秒(s)为单位，且每次活动的持续时间为整数秒。距离的单位为米(m)。

【输入描述】

仅一行，包括空格隔开的三个非负整数M, S, T

【输出描述】

包含两行：

第1行为字符串“Yes”或“No”（区分大小写），即守望者是否能逃离荒岛。 第2行包含一个整数。第一行为“Yes”（区分大小写）时表示守望者逃离荒岛的最短时间；第一行为“No”（区分大小写）时表示守望者能走的最远距离。

【样例】

输入

39 200 4

输出

No

197

【限制】

30%的数据满足: 1 <= T<= 10， 1 <=S<= 100

50%的数据满足: 1 <= T <= 1000， 1 <= S <= 10000

100%的数据满足: 1 <= T <= 300000， 0 <= M<=1000 1 <=S <= 10^8

【解题报告】

啊！终于进入怨念的解题报告阶段了！

想必大家都玩过暴雪的经典《魔兽争霸3冰封王座》吧,暗夜精灵战役第三关主线任务守望者玛维必须在3分半钟内逃出该洞穴,而且必须存活下来. 一个字,就是跑,多多利用玛维的传送术,最好是有LV3,这样方便跑路,溜到开头的地方即可，网上的攻略估计也就写到这里了，笔者在这一关Ms也死了好几次，mana不够，换什么也白扯呀，总结起来，跑动+闪烁，控制法力，碰到兵，闪烁！快到门口时（快到时间）不要吝惜法力，闪呀！

但是呢，这道题就不一样了，你的每一次选择（跑步，闪烁，回法）都会浪费时间，正统的做法就是动规+贪心，先说一下动规的方法

【动态规划】

一、简单的动规

看到这道题就会想到模仿星际争霸的采矿（见CTSC2000）但是这道题最善良的地方在于时间是一秒为单位的（单秒，不是7秒，9秒，t1秒），这就给我们提供了划分阶段的标准——时间！此外，逃跑的速度还与另一个数据有关，那就是mana，耗费mana闪烁跑得很快，这招是救命用的！还有就是，当魔法足够时（而且距离足够）可以一直闪烁！所以用二维数组f[m,t]表示t秒m法的状态(距离)（这种状态的表示方法满足了无后效性和最优子结构）。

而对于f[m,t]状态，它与其前一秒的状态有关,前一秒的选择有三种：

1、 跑步

2、 闪烁

3、 回复mana

因此我们就可以写出状态转移方程了

f[i,j]=max

{f[i-10,j-1]+60, //闪烁

f[i ,j-1]+17, //跑步

f[i+4 ,j-1]} //回复，但此时不能跑步

但是这样写的方程有一个问题，那就是法力值不足的情况，如果mana<10转移方程的第一项（闪烁状态）就不能启用，我们也可以写出这种情况下的状态转移方程 F[I,j]=max{f[I,j-1]+17,f[i+4,j-1]}具体实现过程我就不赘述了（见参考程序）。 终止的情况，我们只要考虑t 而不必考虑mana，因为mana好像你手里的票子，活着的时候省着花，你都快死了（或者说已经死了），留着还有啥用？这个东西又不能带进棺材，只要考虑j=t时f[1..i,t]的最大值（你最多能跑多远）或者说只要考虑

f[0,t](这就是传说中死钱花光所有钱的跑法，这种人往往获得最潇洒！)

*此方法参考程序见“参考程序2”

二、动规的优化（见参考程序4）

按题目所说，最大魔法值为1000，最大时间为300000秒，那么需要300000000的数组，空间会溢出，所以使用两个一维数组来迭代，只需2000的数组，但是时间复杂度为O(t*m)，有可能会超时（唉！花个钱还这么麻烦）。

思考一下，可以发现，中间的过程无非就是闪烁加恢复魔法，有时再走几步，我们用ms数组记录，闪烁加恢复魔法可走的最大距离，再和走路比较，选出最优方案，存入ts数组，这样的话，时间复杂度只有O(t),比前面的算法好得多。而这种方法就是前面所说的贪心+动规

比较一下，单纯的动态规划最终得分80（两个超大数据点没有通过），而优化动态规划是满分，从这个角度，我们可以联想到贪心、递归、动规三者的关系，这里用一个Venn图来解释一下

【贪心算法】

这道题还有一种经典的算法就是贪心，如果说动态规划的方法是走一步看一步的话，那贪心就是上来一下子把能花的钱（

mana）都挥霍干净，看看自己跑出去没，没跑出去的话，看看自己离出口还有多远，很近的话——直接用跑的，要是远的话，那就恢复一下mana试试看

贪心策略：

1: 先闪烁，放干魔法。

2：如果剩下的距离>=120，就等5s，闪两次。

计算并比较跑步与闪烁的时间：

回复+闪烁：共耗时7S，前进了120米

跑步：7×17=119米

因此用去的时间tt=tt+7；行走的距离为ss：ss=ss+120;当tt=t-7时，ss<s时，m>=2时，应当放弃采用此策略。（因为此时，我们可以等的1秒或是2秒就可以闪了。）如果t-tt<7，放弃此策略。

3：如果 （s-ss>=34) and (m>=6) and (t-tt>=2)，那么就选择闪烁，等一秒，闪一秒。魔法减6。

4：如果 (s-ss>=51) and (m>=2 ) and (t-tt>=3) ，那么就选择闪烁，等两秒，闪一秒，魔法减2。

5：如果以上的到的结果的都不能跑出来，那么就选择跑路吧。最后判断能否跑出。 具体实现，见参考程序3【守望者的涵意】

【参考程序】

1、 简单动规（只是思路，给个大框，如果有能力的读者请越过） program Devil_Hunter;

var f:array[0..1000,0..1000] of integer;

M,S,T:integer;

i,j,k,maxf:integer;

function max(a1,a2,a3:integer):integer;

begin

max:=0;

if a1>=max then max:=a1;

if a2>=max then max:=a2;

if a3>=max then max:=a3;

end;

begin

assign(input,'data.in');

assign(output,'data.out');

reset(input);

rewrite(output);

readln(M,S,T);

f[m,0]:=s;

for i:=0 to M do

for j:=0 to T do

begin

if i>=10 then f[i,j]:=max

(f[i,j-1]+17,

f[i-10,j-1]+60,

f[i+4,j-1])

else f[i,j]:=max【守望者的涵意】

(f[i,j-1]+60,

f[i+4,j-1],

0);

end;

maxf:=0;

for k:=1 to M do if f[k,T]>=maxf then maxf:=f[k,T]; if maxf>=S then writeln('Yes') else writeln('No'); close(input);

close(output);

end.

2、 完整动规（此方法的缺憾就是数据太大的话，超时严重，预计得分60） program a3(input,output);

var

a,b:array[0..10000]of longint;

m,s,t,i,j:longint;

function max(a,b,c:longint):longint; {三个数找最大值} var

k:longint;

begin

if a>b then k:=a else k:=b;

if k max:=k;

end;

begin

assign(input,'escape.in');

assign(output,'escape.out');

reset(input);

rewrite(output);

readln(m,s,t);

for i:=0 to 10000 do {数组清0}

begin

a[i]:=0;

b[i]:=0;

end;

for i:=1 to t do

begin

for j:=0 to 9 do

begin

b[j]:=max(a[j]+17,a[j+4],0); {动态规划} if b[j]>=s then

begin

writeln('Yes'); {找到最小解，提前退出} writeln(i);

close(input);

close(output);

halt;

end;

end;

for j:=10 to m do

begin

b[j]:=max(a[j]+17,a[j+4],a[j-10]+60); {动态规划} if b[j]>=s then

begin

writeln('Yes'); {找到最小解，提前退出} writeln(i);

close(input);

close(output);

halt;

end;

end;

a:=b;

end;

writeln('No'); {无解}

writeln(a[m]);

close(input);

close(output);

end.

3、 贪心的方法（预计得分100）

program Devil_Hunter3;

var

m,s,t,ss,tt:longint;

begin

assign(input,'escape.in');reset(input);

assign(output,'escape.out');rewrite(output); read(m,s,t);

ss:=0;tt:=0;

while m>=10 do

begin【守望者的涵意】

dec(m,10);

inc(ss,60);

inc(tt);

if (ss>=s) and (t>=tt) then

begin

writeln('Yes');

write(tt);

close(output);halt;

end;

if tt>t then begin

dec(tt);

守望者的逃离 代码加注释和详解
守望者的涵意 第二篇

/*魔兽争霸........

这道题目我用的是贪心算法，分析如下：

记魅力值为moli,给定的时间为time，当前用时ti，

总路程dis，当前行驶di；

1.当魔力值够用（即moli>=10）时，不停地闪烁；

2.当6<=moli<10且"剩余时间">=2且"剩余距离">34时，恢复1s,闪烁1s,行驶60>17*2=34(步行)；

3.当2<=moli<6且"剩余时间">=3且“剩余距离”>51时，恢复2s，闪烁1s，行驶60>17*3=51(步行)；

4.当0<=moli<=1且"剩余时间">=7且“剩余距离”>119时，恢复5s，闪烁2s，行驶120>17*7=119(步行)；

5.否则，都用步行；

*/

#include<stdio.h>

int main()

{int moli,time,dis,ti,di,ji=0;

scanf("%d%d%d",&moli,&dis,&time);

di=0;ti=0;

while(moli>=10)

{moli=moli-10;

di=di+60;

ti++;

if(di>=dis&&time>=ti)

{printf("Yes\n%d\n",ti);ji=1;return 0;}

if(ti>time)

{ti--;

di=di-60;

moli=moli+10;

break;

}

} //以上为“1”的情况，疯狂闪烁！

while(dis-di>119)

{ti=ti+7;

di=di+120;

if(ti>=time)

{if(moli>=2)

{ti=ti-7;

di=di-120;

}

break;

}

}

if(di>=dis&&time>=ti)

{printf("Yes\n%d\n",ti);ji=1;return 0;} //以上为“4”的情况

while(dis-di>=34&&moli>=6&&time-ti>=2)

{ti=ti+2;

moli=moli-6;

di=di+60;

} //以上为“2”的情况

while(dis-di>=51&&moli>=2&&time-ti>=3)

{ti=ti+3;

moli=moli-2;

di=di+60;

}

的情况

if(di>=dis&&time>=ti)

{printf("Yes\n%d\n",ti);ji=1;return 0;}

do

{ti++;

di=di+17;

if(di>=dis&&time>=ti)

{printf("Yes\n%d\n",ti);ji=1;return 0;}

if(ti>time){ti--;di=di-17;ji=1;break;}

}while(0);

的情况

if(ji==0)printf("No\n%d\n",di); //没有解只能NO了

return 0;

} //以上为“3”//以上为“5”

高山上的守望者阅读答案
守望者的涵意 第三篇

高山上的守望者阅读答案

①巍峨的长白山上。大森林垂直绵延2000多米。1100米以下是针阔混交林。金秋时节，绚烂缤纷；1100米-1800米之间是针叶林。树木挺拔参天，气势磅礴；过了1800米，森林放慢了脚步。这里恶劣的自然条件，使大部分树木没有胆量穿越，即使是傲风斗雪的青松也望而却步。然而岳桦却以勇敢和坚毅不屈的精神，顽强地在这里扎下了根，成为在蓝天白雪之间悄悄结语、静静展开的高山上的守望者。

②岳桦在植物分类上属于桦木科，桦木属，为落叶森林植物。树皮呈灰黄白色，枝暗红色，幼枝暗绿色；冬芽呈矩圆形或卵球形。叶片薄，较硬，边缘呈不规则的锯齿状；花期为每年的5-6月。果期在8-9月。岳桦生长在寒湿地带的半阳坡山脊上，在我国分布于大小兴安岭、长白山等地。在俄罗斯东部、朝鲜、日本也有分布。

③岳桦生长地属于湿润性亚高山气候。冬季寒冷多风，夏季湿润多雨。降水量大而蒸发量小；年平均气温低，无霜期不足70天。生长季节短；风力强劲，每年有200多天的风力超过六级。这里土壤贫瘠，虽然土壤表层有机质含量较高，但10厘米以下土质疏松，腐殖质较少，角砾较多。

④在低海拔地区，尽管条件优越，但岳桦竞争不过云杉、冷杉等，只呈零星分布。随着海拔的升高，云桦越来越占据优势地位，并在海拔1700-2100米处形成东亚地区保护最为完整的岳桦林带，几乎为纯林。当海拔高于2100米，由于受风、雪等因素的影响，岳桦以斑块状分布于高山苔原带。

⑤岳桦一年之内只有两个多月的生长期，生长期内又常常遭遇8级以上大风。因此，岳桦生长得十分谨慎也十分缓慢。一棵看起来只有手腕粗的岳桦，往往已有十几岁甚至几十岁。岳桦的兄弟姐妹（红桦、硕桦、黑桦等）高大笔直。在人们面前一直是美丽而又充满灵性的精灵。而岳桦几乎不足3米高，不过数寸粗，枝条虬曲，枝干大幅度倾斜，显得矮小卑微，弯曲丑陋。但岳桦的木质却异常的细密坚硬，成龄的岳桦木坚如磬石，入水即沉，其超乎寻常的硬度常常令初识都瞠目结舌。

⑥处在高海拔地区的岳桦林作为独特的自然生态系统，具有涵养水源、调节气候以及维护物种多样性等方面的生态功能。它们在忍受恶劣生存环境带来的苦难的同时，用自己的根须牢牢地拢住了土壤，用自己的生命精心地护养着水源，用自己的身躯无私地庇护着动物。 ⑦这就是高山上的守望者——岳桦。它在艰难的磨难中体现自己的独特的魅力，以超凡脱俗的修练证明了身形硕小未必就是卑微。

（源自中科院沈阳生态研究所，有删改）

13.第一段在文中起什么作用？（2分）

14.第②-⑥段从五个方面介绍了岳桦，请将相关内容填写在下面空格处。（3分） 第②段：岳桦的属性及地理分布。第③段：

第④段：第⑤段：

15.第④段运用了多种说明方法，请写出两种并分析其作用。（4分）

16.本文的语言既准确严密又生动形象，任选一个方面结合第⑤段内容加以分析。（3分）

①照应题目，引出说明对象——岳桦。②生动形象，引起读者的阅读兴趣。③简要晚间新闻介绍岳桦的生长环境，强调其生命力的顽强。④引起下文。（答出任意两点，意思对即可。一点一分，共2分） 14、第③段：岳桦生长地的气候和土壤条件。第④段：岳桦在不同海拔地区的分布状态。第⑤段：岳桦的外观及木质特点。（意思对即可。一空一分，共3分） 15、①作比较。把岳桦与云杉、冷杉等进行比较，说明在低海拔地区岳桦生长不占优势。②列数字。用“1700-2100米”具体、准确地说明适合岳桦生长的海拔高度。③摹状貌。用“斑块状”形象地说明岳桦在高山苔原带的分布状态。（答出任意两种，言之成理即可。一种2分，其中说明方法1分，分析作用1分。共4分） 16、示例一：“一年之内只有两个多月的生长期”一句中的“只”表限制，强调岳桦生长期很短，体现了语言的准确严密。示例二：“成龄的岳桦木坚如磬石，入水即沉”一句中的“坚如磬石”“入水即沉”生动形象地说明岳桦木质异常细密坚硬。（任选一个方面，言之成理即可。举出例子，1分；分析2分，共3分）

以上就是中国招生考试网http://www.chinazhaokao.com/带给大家不一样的精彩成考报名。想要了解更多《守望者的涵意》的朋友可以持续关注中国招生考试网，我们将会为你奉上最全最新鲜的成考报名内容哦! 中国招生考试网，因你而精彩。

相关热词搜索：守望者加速器 异能守望者