2014noip复赛模拟练习16(答案).doc

喜羊羊运动会训练时间题目描述这次运动会开幕式要进行团体操表演，于是喜羊羊召集大家紧锣密鼓地训练了起来，懒羊羊也在被召集之列。喜羊羊规定了每天的训练时间，只准早到，不许迟到，而且喜羊羊会做相关记录。这下懒羊羊可惨了，他虽然设定了闹钟，可是他动作慢，老迟到。现给出若干天的规定到场时间与懒羊羊的到场时间记录，判断每天懒羊羊有无及时赶到训练场，以及迟到或早到的时间。输入每两行时间为一组，每组中的第一行时间为规定的训练时间，第二行为懒羊羊到达训练场的时间。每行有两个整数H和M，H是以24小时记时法表示的小时数（0 = H = 24），M表示分钟数（0 = M = 59）。每组中的两个时间表示的是同一天的两个时间。若干组时间后以-1表示结束。输出若干行，如果这一天懒羊羊及时到达了训练场，则输出Yes及早到的分钟数；如果没有及时到达，则输出No及迟到的分钟数。样例输入14 3014 258 09 013 1012 507 257 25-1样例输出Yes 5No 60Yes 20Yes 0提示输入输出说明： 第一天 第二天 第三天 第四天规定训练时间 14：30 8：00 13：10 7：25到场时间 14：25 9：00 12：50 7：25有无及时到达 Yes No Yes Yes早到或迟到分钟数 5 60 20 0 程序段如下：var h1,n1,h2,n2,s1,s2:integer;beginread(h1);while h1-1 dobeginread(n1);s1:=h1*60+n1;/把时间从小时转化为分read(h2);read(n2);s2:=h2*60+n2;/把时间从小时转化为分if s2=90 A90成绩=75 B75成绩=60 C成绩=90 then inc(s);/如果分数达到90分那么加一分if a60 then begin write(Poor LanYangYang);/如果有一门功课在60分以下那么淘汰，并且退出exit;end;end;if s=4 then s:=5;/如果四门全优则得5分writeln(s);end.输入 90 96 99 95 输出 5 输入 65 66 78 62 输出 0输入 89 90 92 88 输出 2 输入 77 70 59 69 输出Poor LanYangYangNASA(美国航空航天局)因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋,因此在各方压力下终止了航天飞机的历史,但是此类事情会不会在以后发生，谁也无法保证,在遇到这类航天问题时,解决方法也许只能让航天员出仓维修,但是多次的维修会消耗航天员大量的能量,因此NASA便想设计一种食品方案,让体积和承重有限的条件下多装载一些高卡路里的食物. 航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次. 【输入格式】第一行两个数体积最大值(400)和质量最大值(400)第二行 一个数 食品总数N(50).第三行第3+N行每行三个数 体积(400) 质量(400) 所含卡路里(500) 【输出格式】一个数 所能达到的最大卡路里(int范围内)【样例输入】320 3504160 40 12080 110 240220 70 31040 400 220【样例输出】550 【分析】二维背包【源程序】Program v1334;Var f:array0.400,0.400of longword; n,maxv,maxw,v,w,p,i,j,k:longword;Beginreadln(maxv,maxw);readln(n);for i:=1 to n do begin readln(v,w,p); for j:=maxv downto v do for k:=maxw downto w do if fj,kfj-v,k-w+p then fj,k:=fj-v,k-w+p; end;writeln(fmaxv,maxw);End.输入 200 2105100 110 90120 200 18080 88 90102 105 103150 160 140 输出 193输入 320 3087200 180 190210 240 260178 188 198160 200 150320 330 300300 308 329350 340 345 输出 329输入 380 39010255 260 280200 230 240310 300 290298 288 278200 300 240198 180 176340 390 380321 308 314360 366 356288 278 290 输出 380题目描述:一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着CC发现瓶子实在太多了，于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。(不能丢弃有水的瓶子)显然在某些情况下CC无法达到目标，比如N=3,K=1。此时CC会重新买一些新的瓶子(新瓶子容量无限，开始时有1升水)，以到达目标。现在CC想知道，最少需要买多少新瓶子才能达到目标呢？输入文件(Water.in)：一行两个正整数， N,K(1=N=109，K=1000)。输出文件(Water.out)：一个非负整数，表示最少需要买多少新瓶子。输入样例1：3 1输出样例1：1输入样例2：13 2输出样例2：3输入样例3：1000000 5输出样例3：15808样例说明:无数据规模对于50%的数据，N0 do begin inc(t); at:=k mod 2; k:=k div 2; end; for i:=1 to t do if ai=1 then inc(ans); while ansm do begin for i:=1 to t do if ai=1 then break; while ai=1 do begin ai:=0; inc(i); dec(ans); end; ai:=1; inc(ans); if it then t:=i; end; for i:=1 to t do if ai=1 then inc(sum,dfs(i-1); writeln(sum-n);end. 输入 15 3 输出 8500 2 输出 204 输出 35000 3 输出 72给定一个十进制正整数n，它的递归变幻数定义如下：1如果n的位数多于1位（忽略前置的0），将n的各个位上的数相乘，乘积为m。称m为n的子变幻数，n称为m的父变幻数。求一个数的变幻数等于求其子变幻数。即求n的变幻数等于求m的变幻数。2如果n的位数只有一位，n的变幻数即为它本身。如求679的变幻数过程为：679 - 378(=6*7*9) - 168(=3*7*8) - 48(=1*6*8) - 32(=4*8) - 6(=2*3)，所以679的变幻数为6。 现在的问题是给定一个子变幻数k，问k的父变幻数最小是多少？ 如：k=18，则k的父变幻数可以是29，也可以是92。但最小为29。 数据输入：一个子变幻数k(位数小于1000)。 数据输出：k的最小父变幻数。当不存在父变幻数时请输出“There is no such number!”，输出结果不含引号。 样例输入：48样例输出： 68分析已知变换数求其子变换数是非常简单的，然而题目要求的是求它的逆过程。如果b为a的子变换数，那么定义b=son(a),假设a由k位组成，表示那么a可以表示成a1,a2,a3,ak b=son(a)=a1*a2*a3*.*ak 即b是由a的各个位相乘得到果把b分解，然后将各个因式相连，是不是也可以得到b的一个父变幻数？显然，从a到b的推导过程来说，是成立的。求最小的父变幻数贪心策略按照上述分解规则，通过一些贪心策略可以得到最小的父变幻数。从ab的变换过程中，因子只能是1位整数。从ba的过程中，b的因子只能取29, (有1的情况下，a一定不是b的最小父变幻数）b分解数字越少， a 越小。var a,b:array0.1000 of longint; ans:array0.10000 of longint; ch:char; n,i,j:longint;procedure divit(n:longint);var i,p,k,m:longint;begin b0:=0;p:=0; for i:=1 to a0 do begin p:=p*10+ai; inc(b0); bb0:=p div n; p:=p mod n; end; if p=0 then begin k:=1; while bk=0 do inc(k); m:=0; fillchar(a,sizeof(a),0); for i:=k to b0 do begin inc(m); am:=bi; end; a0:=b0-k+1; inc(ans0); ansans0:=n; end else dec(j);end;procedure init;begin assign(input,unreal.in); assign(output,unreal.out); reset(input); rewrite(output);end;procedure endit;begin close(input); close(output);end;begin init; a0:=0; while not eof do begin read(ch); if (ch=0) and (ch1) and (j10) do divit(j); if a01 then writeln(There is no such number!) else begin for i:=ans0 downto 1 do write(ansi); writeln; end; endit;end.对信息进行加密，可提高信息传输的安全性。正是由于它的重要用途，人们发明了各种各样的加密方式。其中一种方式是，对文中单词进行逆序处理。请你写一个程序，对已加密的文本进行解密。输入文件（encrypt.in）第1行，一个整数n，表示后面将有n行已加密的信息。第2行至第n+1行，每行一个不超过1000个字符的字符串，每个字符串中只有空格和小写字母组成。输出文件（encrypt.out）共n行，每行对应输出解密后的文本。输入输出样例：encrypt.inencrypt.out2eno owt eerht i ekil siht emag one two three i like this game数据范围：n= 50,000老师。时限2S。program encrypt;var n,i:longint; str:ansistring;procedure deal(now:ansistring);var l,k,i:longint;begin k:=pos( ,now); while k0 do begin for i:=k-1 downto 1 do write(nowi); write( ); delete(now,1,k); if now then begin while (now1= ) do begin delete(now,1,1); if now= then break; end; end; k:=pos( ,now);