noip备战模拟题(有解答).doc

1、吉祥数c/cpp)【问题描述】为了迎接圣诞，信息学兴趣小组的同学在辅导老师的带领下，举办了一个盛大的晚会，晚会的第一项内容是做游戏：猜数。老师给每位同学发一张卡片，每张卡片上都有一个编号(此编号为非负数，且小于255)，每个编号互不相同。老师制定了以下的游戏规则：第一轮，每位同学将自己卡片上编号的各位数字进行平方后再相加得到一组新数，编号在这组新数中出现的同学淘汰出局，第二轮，余下的同学再将编号的各位数字进行立方相加得到一组新数，编号在这组新数中出现的同学再淘汰出局，第三轮，余下的同学再将编号的各位数字进行4次方相加得到一组新数，编号在这组新数中出现的同学再淘汰出局，以此类推，经过n轮后，仍留

2、下来的同学，将获得圣诞特别礼物，卡片上的数即为2007年吉祥数。(假定班级人数不超过200人)【输入文件】（）第1行为1个正整数n(n8)，表示有n轮游戏,第二行是卡片上互不相同的编号。【输出文件】（） 为剩下来的各个吉祥数，按从小到大顺序输出，每两个数之间有一个空格。【输入样例】124 123 2 12 20 14 4 6 36 72【输出样例】2 6 12 24 72 123圣诞树c/cpp)【问题描述】圣诞特别礼物挂在一棵圣诞树上，这棵树有n层，每层有一件礼物，每件礼物都有一个价值，有的礼物还有一些连结线，与下层的礼物相连，领取礼物的规则如下：任选一件礼物，它的下面如果有连结线，则可以继

3、续取它连结的礼物，以此类推，直至取到没有连结线的礼物才结束，你如果是第一个去取，怎样取才能获得最大的价值呢请你编一程序解决这一问题。【输入文件】（）第一行只有一个数据n(n=100),表示有n层礼物，以下有n行数据，分别表示第1-n层礼物的状态，每行至少由一个数据构成，且第一个数据表示该礼物的价值，后面的数据表示它与哪些层的礼物相连，如果每行只有一个数据则说明这层礼物没有与下层礼物相连，每个数的大小均不超过10000。【输出文件】（）输出文件只有一个数，表示获得的取大价值。【输入样列】312 2 32030【输出样列】42传话c/cpp)【问题描述】兴趣小组的同学来自各个学校，为了增加友谊，晚

4、会上又进行了一个传话游戏，如果a认识b，那么a收到某个消息，就会把这个消息传给b，以及所有a认识的人。如果a认识b，b不一定认识a。所有人从1到n编号，给出所有“认识”关系，问如果i发布一条新消息，那么会不会经过若干次传话后，这个消息传回给了i，1=i=n。【输入文件】（）第一行是两个数n(n1000)和m(m10000)，两数之间有一个空格，表示人数和认识关系数。接下来的m行，每行两个数a和b，表示a认识b。1=a, b=n。认识关系可能会重复给出，但一行的两个数不会相同。【输出文件】（）一共有n行，每行一个字符T或F。第i行如果是T，表示i发出一条新消息会传回给i；如果是F，表示i发出一条

5、新消息不会传回给i。【输入样例】4 61 22 34 13 11 32 3【输出样例】TTTF暴力摩托c/cpp)【问题描述】晚会上大家在玩一款“暴力摩托”的游戏，它拥有非常逼真的画面和音响效果，如疾驰而过的汽车呼啸声，摩托车的引擎声和转弯时轮胎与地面摩擦而产生的声音。而且它在游戏中加入了对抗成份，比赛中你可以使用拳、脚去干扰对方，使其落后于你，是不是很卑鄙啊 游戏中千万不能手下留情，因为对手会主动攻击你。如果遇到开摩托车的警察，虽然也可以对他踢上一脚，但可得小心点呀，万一被他们捉住了，那就 GAME OVER 啦!当然了，车子总是要加油的咯，已知赛道长S公里（S10000整数，且为10的倍数

6、），赛车的油耗Q=1，即1公里路耗1个单位的油。Q不变，赛车的油箱为无穷大，同时在沿途的任何地方都可以加油。 约定，每次加油的数量为整数，且为10的倍数，赛车的速度与赛车加油后的总油量有关。其关系如下表列出：加油量车速（公里/小时）10100（10，20 90（20，30 80（30，40 75（40，+）70同时，汽车每加油一次需要耗费T分钟（T=100不论加油多少，开始时的加油不计时间）当S，T给出之后，选择一个最优的加油方案。使汽车以最少时间跑完全程。例如：当S=40，T=6（分钟），加油的方案有许多种，列出一些：1）起点加油40，用时40/75小时2）起点加油20，中途加20，用时20

7、/90+20/90+6/60（化为小时） 小时【输入文件】（）仅一行，为两个整数S、T。 【输出文件】（）输出一行，为最少用时（保留二位小数）【输入样例】40 6【输出样例】、 吉祥数c/cpp)问题描述为了迎接圣诞，信息学兴趣小组的同学在辅导老师的带领下，举办了一个盛大的晚会，晚会的第一项内容是做游戏：猜数。老师给每位同学发一张卡片，每张卡片上都有一个编号(此编号为非负数，且小于255)，每个编号互不相同。老师制定了以下的游戏规则：第一轮，每位同学将自己卡片上编号的各位数字进行平方后再相加得到一组新数，编号在这组新数中出现的同学淘汰出局，第二轮，余下的同学再将编号的各位数字进行立方相加得到一

8、组新数，编号在这组新数中出现的同学再淘汰出局，第三轮，余下的同学再将编号的各位数字进行4次方相加得到一组新数，编号在这组新数中出现的同学再淘汰出局，以此类推，经过n轮后，仍留下来的同学，将获得圣诞特别礼物，卡片上的数即为2007年吉祥数。(假定班级人数不超过200人)输入文件输入文件ghillie .in 有两行，第1行为1个正整数n(n8)，表示有n轮游戏,第二行是卡片上互不相同的编号。输出：剩下来的各个吉祥数，按从小到大顺序输出，每两个数之间有一个空格。输出文件 输出文件ghillie .out是1行，为剩下来的各个吉祥数，按从小到大顺序输出，每两个数之间有一个空格。输入样例124 123

9、 2 12 20 14 4 6 36 72输出样例2 6 12 24 72 123思路分析这是一道基础题，数据量不大，采用模拟法，将每一轮初始的编号数存在数组中，这个数组中所有数的值在一轮中不能更改，这组数产生的新数用数组来存放，然后将数组与数组进行比较，将数组中没有的数组中的数存入数组，下一轮开始时，先初始化数组，这时数组就取数组，程序中最好能自定义一个函数fj(n,k:integer),作用是将编号数n进行分解后，再将数字k次方，最后求和，函数值取这个和。另外输入数据时，由于第二行不知数据的个数，因此要用函数eoln来控制。参考程序如下：var a,b,c:array1.200 of lo

10、ngint; i,j,k,n,i1,i2,i3,t:integer; p:boolean; tem,s:longint; function fj(n,k:integer):longint; var x:array1.20 of integer; i,j,m:integer;s,s1,s2:longint; begin i:=0; fillchar(x,sizeof(x),0);s:=0; while n0 do begin i:=i+1; xi:=n mod 10; n:=n div 10 end; for j:=1 to i do begin s1:=1; for m:=1 to k do

11、s1:=s1*xj; s:=s+s1; end; fj:=s end; begin assign(input,); reset(input); assign(output,); rewrite(output); readln(n); j:=0; while not eof do begin j:=j+1; read(aj); end; for i:=2 to n+1 do begin i2:=0;i3:=0; fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); for k:=1 to j do begin s:=fj(ak,i); i2:=i2+

12、1; bi2:=s; end; for k:=1 to j do begin p:=true; for t:=1 to j do if ak=bt then p:=false; if p then begin i3:=i3+1; ci3:=ak; end; end; j:=i3; a:=c; end; for i:=1 to j-1 do for k:=i+1 to j do if aiak then begin tem:=ai; ai:=ak; ak:=tem end; for i:=1 to j-1 do write(ai, ); write(aj); close(input); clos

13、e(output); end.2、圣诞树（c/cpp）问题描述圣诞特别礼物挂在一棵圣诞树上，这棵树有n层，每层有一件礼物，每件礼物都有一个价值，有的礼物还有一些连结线，与下层的礼物相连，领取礼物的规则如下：任选一件礼物，它的下面如果有连结线，则可以继续取它连结的礼物，以此类推，直至取到没有连结线的礼物才结束，你如果是第一个去取，怎样取才能获得最大的价值呢请你编一程序解决这一问题。输入文件输入文件的第一行只有一个数据n(nmax) then max:=bj; bi:=max+ai; end; end; procedure print; var i:integer; max:longint; be

14、gin max:=0; for i:=1 to n do if bimax then max:=bi; writeln(max); close(input); close(output); end; begin init; work; print;end.3、传话（c/cpp）问题描述兴趣小组的同学来自各个学校，为了增加友谊，晚会上又进行了一个传话游戏，如果a认识b，那么a收到某个消息，就会把这个消息传给b，以及所有a认识的人。如果a认识b，b不一定认识a。所有人从1到n编号，给出所有“认识”关系，问如果i发布一条新消息，那么会不会经过若干次传话后，这个消息传回给了i，1=i=n。输入文件输入

15、文件中的第一行是两个数n(n1000)和m(m10000)，两数之间有一个空格，表示人数和认识关系数。接下来的m行，每行两个数a和b，表示a认识b。1=a, b=n。认识关系可能会重复给出，但一行的两个数不会相同。输出文件输出文件中一共有n行，每行一个字符T或F。第i行如果是T，表示i发出一条新消息会传回给i；如果是F，表示i发出一条新消息不会传回给i。输入样例4 61 22 34 13 11 32 3输出样例TTTF思路分析先把有向图建立起来：ai,j=1表示i能到j, 然后利用递归进行宽搜，搜索时注意从一点到另一点搜过一次就不能再搜，以免引起死循环。在搜索的过程中注意剪枝，否则有的点会超时

16、。参考程序如下：const maxn=1000;var n,m,i,j,x,y:longint; a:array1.maxn,1.maxn of boolean; v:array1.maxn of boolean;function dfs(x,root:longint):boolean;var j:longint; f:boolean;begin vx:=true; f:=false; for j:=1 to n do begin if ax,j and not vj then begin f:=f or dfs(j,root); if f then begin dfs:=true; exit

17、; end; end else if (j=root) and (ax,j) then begin dfs:=true; exit; end; end; dfs:=f;end;begin assign(input,); reset(input); assign(output,); rewrite(output); readln(n,m); fillchar(a,sizeof(a),false); for i:=1 to m do begin readln(x,y); ax,y:=true; end; for i:=1 to n do begin fillchar(v,sizeof(v),fal

18、se); if dfs(i,i) then writeln(T) else writeln(F); end; close(input); close(output);end.4、暴力摩托（c/cpp）问题描述晚会上大家在玩一款“暴力摩托”的游戏，它拥有非常逼真的画面和音响效果，如疾驰而过的汽车呼啸声，摩托车的引擎声和转弯时轮胎与地面摩擦而产生的声音。而且它在游戏中加入了对抗成份，比赛中你可以使用拳、脚去干扰对方，使其落后于你，是不是很卑鄙啊 游戏中千万不能手下留情，因为对手会主动攻击你。如果遇到开摩托车的警察，虽然也可以对他踢上一脚，但可得小心点呀，万一被他们捉住了，那就 GAME OVER

19、啦!当然了，车子总是要加油的咯，已知赛道长S公里（S10000整数，且为10的倍数），赛车的油耗Q=1，即1公里路耗1个单位的油。Q不变，赛车的油箱为无穷大，同时在沿途的任何地方都可以加油。 约定，每次加油的数量为整数，且为10的倍数，赛车的速度与赛车加油后的总油量有关。其关系如下表列出：加油量车速（公里/小时）10100（10，20 90（20，30 80（30，40 75（40，+）70同时，汽车每加油一次需要耗费T分钟（T=100不论加油多少，开始时的加油不计时间）当S，T给出之后，选择一个最优的加油方案。使汽车以最少时间跑完全程。例如：当S=40，T=6（分钟），加油的方案有许多种，列

20、出一些：1）起点加油40，用时40/75小时2）起点加油20，中途加20，用时20/90+20/90+6/60（化为小时） 小时 输入文件一行，为两个整数S、T。 输出文件输出一行，为最少用时（保留二位小数） 输入样例40 6 输出样例思路分析 当走到某一距离时，此时的最小用时，与后面的行程方案无关，也就是无后效性，符合动态规划的原则，将S以每10公里为一单位分成s div 10段，如s=40时，分法如下： 对应路段的最小用时用A数组存放。很显然A1=10/100，走到20公里处时的方案有：（1）从0公里处加20单位的油，所需最小用时为min=20/90；(2)先到10公里处，此时的最小用时为

21、A1，然后再加能到20公里的油，这段路的最小用时为：（20-10）/100，该方案的一共用时：A1+(20-10)/100。取两种方案的最小用时存入A2，同样可以求出A3、A4的最小用时，从而推出动态方程：Ai=mint(0到i), A1+t(1到i), A2+t(2到i), ,Ai-1+t(i-1 到 i), 其中t(0到i)表示只在0公里处加油后，以后不再加油，t(1到i) 表示在10公里处加油后，以后不再加油, 。参考程序如下：var s,t,i,j:longint; a:array1.1000 of real; m,min:real;begin assign(input,); assi

22、gn(output,); reset(input); rewrite(output); readln(s,t); for i:=1 to s div 10 do 在0处加油后不再加油，到 i的最小用时，用min 存放 begin case i of 1:min:=10/100; 2:min:=20/90; 3:min:=30/80; 4:min:=40/75; else min:=i*10/70; end; for j:=1 to i-1 do 分别求各种方案的最小用时数 begin case i-j of 1:m:=10/100; 2:m:=20/90; 3:m:=30/80; 4:m:=40/75; else m:=(i-j)*10/70; end; m:=m+t/60;从j到i的最小用时 if m+ajmin then min:=m+aj; end; ai:=min; end; writeln(as div 10:0:2); close(input); close(output);end.