1、有两个字串A$,B$及一组字串变换的规那么至多6个规那么:A1$-B1$A2$-B2$规那么的含义为：在A中的子串A1$可以变换为B1$、A2$可以变换为B2$。例如：A$abcdB$xyz变换规那么为：abc-xuud-yy-yz那么此时，A$可以经过一系列的变换变为B$，其变换的过程为：abcd-xud-xy-xyz共进行了三次变换，使得A$变换为B$。输入:键盘输人文件名。文件格式如下：A$B$A1$B1$A2$B2$|-变换规那么./所有字符串长度的上限为20。输出:格式如下：假设在10步包含10步以内能将A$变换为B$，那么输出最少的变换步数；否那么输出“NOANSWER!”b.in
2、:abcdwyzabcxuudyyyz屏幕显示：题三自由落体存盘名:NOIPG3在高为H的天花板上有n个小球，体积不计，位置分别为0，1，2，、n-1。在地面上有一个小车长为L，高为K，距原点距离为S1。小球下落距离计算公式为d1/2*g*（t2），其中g=10，t为下落时间。地面上的小车以速度V前进。如下图：小车与所有小球同时开始运动，当小球距小车的距离=0.00001时，即认为小球被小车接受小球落到地面后不能被接受。请你计算出小车能接受到多少个小球。键盘输人：H，S1，V，L，K，nl=H，S1，V，L，K，n=100000屏幕输出：小车能接受到的小球个数。5.09.05.02.51.85
3、1题四矩形覆盖存盘名NOIPG4在平面上有n个点n=50，每个点用一对整数坐标表示。当n4时，4个点的坐标分另为：p11，1，p22，2，p33，6，P40，7，见图一。这些点可以用k个矩形1=k=4全部覆盖，矩形的边平行于坐标轴。当k=2时，可用如图二的两个矩形sl，s2覆盖，s1，s2面积和为4。问题是当n个点坐标和k给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开边线与顶点也都不能重合。文件格式为nkxly1x2y2.xnyn0=xi,yi=500）一个整数，即满足条件的最小的矩形面
4、积之和。d.in:42112236072002年全国青少年信息学计算机奥林匹克分区联赛复赛提高组试题解题报告可以在任一堆上取假设干张纸牌，然后移动。分析：如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！拿例题来说，平均张数为10,原张数9，8，17，6，变为-1，-2，7，-4，其中没有为0的数，我们从左边出发：要使第1堆的牌数-1变为0，只须将-1张牌移到它的右边第2堆-2中；结果是-1变为0，-2变为-3，各堆牌张数变为0，-3，7，-4；同理：要使第2堆变为0，只需将-3移到它的右边第3堆中去，各堆牌张数变为0，0，4，-4；要
5、使第3堆变为0，只需将第3堆中的4移到它的右边第4堆中去，结果为0，0，0，0，完成任务。每移动1次牌，步数加1。也许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，步数是一样的。如果张数中本来就有为0的，怎么办呢？如0，-1，-5，6，还是从左算起从右算起也完全一样，第1堆是0，无需移牌，余下与上相同；再比如-1，-2，3，10，-4，-6，从左算起，第1次移动的结果为0，-3，3，10，-4，-6；第2次移动的结果为0，0，0，10，-4，-6，现在第3堆已经变为0了，可节省1步，余下继续。程序清单programNOIPG1
6、;constmaxn=100;vari,j,n,step:integer;ave:longint;a:array1.maxnofinteger;f:text;filename:string;beginwrite（Inputfilename:）;readln（filename）;assign（f,filename）;reset（f）;readln（f,n）;=0;step:fori:=1tondobeginread（f,ai）;inc（ave,ai）;end;=avedivi;=1tondoai:=ai-ave;i:=1;j:=n;whileai=0doinc（i）;过滤左边的0whileaj=
7、0dodec（j）;过滤右边的0while（ij）dobegininc（ai+1,ai）;将第i堆牌移到第i+1堆中去ai:第i堆牌移走后变为0inc（step）;移牌步数计数inc（i）;对下一堆牌进行循环操作过滤移牌过程中产生的0writeln（step）;end.点评：基此题较易此题有3点比较关键：一是善于将每堆牌数减去平均数，简化了问题；二是要过滤掉0不是所有的0，如-2，3，0，-1中的0是不能过滤的；三是负数张牌也可以移动，这是辩证法关键中的关键。在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$。abcdxyz此题是典型的广度优先搜索的例子，但如果只采用正向搜索，某些情
8、况下计算量过大，速度过慢，故采取双向搜索且判重并适当剪枝，效果较好。$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-,Y-$M8192,0,655360programNOIPG2;constmaxn=2300;typenode=record定义节点数据类型str:string115;dep:byte;str表示字串，其长度不会超过115长度超过115的字串不可能通过变换成为目标字串，因为题目限定变换10次之内，且串长不超过20，即起始串最多可经过5次变换时增长，中间串的最大长度为20+5*19=115，否那么经过余下的步数不可能变为长度不超
9、过20的目标串，dep表示深度ctype=array1.maxnofnode;bin=0.1;varmaxk:c:array0.1ofctype;x0:array0.6,0.1ofstring20;open,closed:array0.1ofinteger;procedureInit;读取数据，初始化varf:temp:i,j:=0to1doforj:=1tomaxndonew（ci,j）;whilenoteof（f）and（i=6）dobeginreadln（f,temp）;x0i,0:=copy（temp,1,pos（,temp）-1）;x0i,1:=copy（temp,pos（,temp
10、）+1,length（temp）;=i-1;close（f）;procedurecalc;vari,j,k:st:bin;d:procedurebool（st:bin）;判断是否到达目标状态或双向搜索相遇vari:ifx00,1-st=cst,closedst.strthenbegin如果到达目标状态，那么输出结果，退出writeln（cst,closedst.dep）;halt;=1toclosed1-stdoifcst,closedst.str=c1-st,i.strthenbegin如果双向搜索相遇即得到同一节点，那么输出结果2个方向搜索的步数之和，退出writeln（cst,close
11、dst.dep+c1-st,i.dep）;procedurecheckup（st:判断节点是否与前面重复=1toclosedst-1doifcst,i.str=cst,closedst.strthenbegindec（closedst）;exit;如果节点重复，那么删除本节点bool（st）;如果节点不重复，再判断是否到达目标状态procedureexpand（st:扩展产生新节点vari,j,k,lx,ld:inc（openst）;=cst,openst.str;队首节点出队k:=cst,openst.dep;ld:=length（d）;=1tomaxkdobegin从队首节点父节点出发产生
12、新节点子节点lx:=length（x0i,st）;=1tolddobeginif（copy（d,j,lx）=x0i,st）and（length（copy（d,1,j-1）+x0i,1-st+copy（d,j+lx,ld）=maxnthenexit;如果队列已满，只好退出inc（closedst）;新节点入队cst,closedst.str:=copy（d,1,j-1）+x0i,1-st+copy（d,j+lx,ld）;cst,closedst.dep:=k+1;子节点深度=父节点深度+1checkup（st）;检查新节点是否重复Beginforst:=0to1dobegin正向（st=0）逆向
13、（st=1）搜索节点队列初始化openst:closedst:=x00,st;repeat选择节点数较少且队列未空、未满、深度未达到10的方向先扩展if（open0=closed0）or（closed0=maxn）or（c0,closed0.dep10）thenexpand（0）;if（open1=closed1）or（closed1=maxn）or（c1,closed1.dep10）thenexpand（1）;如果一方搜索终止，继续另一方的搜索，直到两个方向都终止ifnot（open0=closed0）or（closed0=maxn）or（c0,closed0.depifnot（open1=
14、closed1）or（closed1（c1,closed1.depuntil（open0=closed0）or（c0,closed0.dep10）or（closed0=maxn）and（closed1=maxn）or（open1=closed1）or（c1,closed1.dep10）;终止条件：任一方队空无解或搜索深度超过1010步内无解或双方均溢出可能有解也可能无解，应尽量避免，要尽量把节点数组开大一点，采用双向搜索，采取剪枝措施等End;BEGINinit;calc;writeln（NOANSWER!）END.基此题较难考察队列、双向广度优先搜索算法及字符串的运算，基本上可以考察出参赛者
15、的数据结构和算法水平。显然，小车太慢即VVmax时，一个球也接不到。即在VVmax时输出为0。下面分别求Vmin和Vmax。当第n-1个小球落地的瞬间，小车在小球的右端离小球尚有e=0.00001的距离，小车的这个极小速度就是Vmin。小车从天花板落到地面的时间t1=,这段时间内小车走了S1-n-1-e,所以Vmin=。当第1个小球落到距小车的上表面为e的瞬间，小车在小球的左端离小球距离为e，小车的这个极大速度就是Vmax。小球从天花板落到离小车上表面为e的距离的时间为t2=,小车移动的距离为S1+L+e,所以Vmax=那么，当VminV=Vmax时，就可接到球了。显然，时间段t2,t1是小车
16、接球的时间，在t2时刻，小车的位置为：左表面离原点距离为S1-V*t2,右表面离原点距离为S1-V*t2+L；在t1时刻，小车的位置为：左表面离原点距离为S1-V*t1,右表面离原点距离为S1-V*t1+L；故小车的接球范围（在小车运动范围外扩展e）为S1-V*t1-e，S1-V*t2+L+e,球的个数就等于接球范围内所包含的0n-1之间的整数的个数.programNOIPG3;constg=10重力加速度;e=1E-5;小车接受小球的极限距离varH,s1,v,l,k,t1,t2,Vmin,Vmax:real;n2,n1,num,n:readln（h,s1,v,l,k,n）;num:=-1;
17、t1:=sqrt（2*h/g）;小球落地时间ifh=k+ethent2:=0elset2:=sqrt（2*（h-k-e）/g）;小球落到小车上的最短时间ifs1-v*t2+L+en-1thenn2:=n-1;n2取trunc（s1-v*t2+L+e）与n-1的较小值ifs1-v*t1-en-1elseif（s1-v*t1-e）=trunc（s1-v*t1-e）=trunc（s1-v*t1-e）小车接受的球的最小编号为n1elsen1:=trunc（s1-v*t1-e）+1;ifnum=-1thennum:=n2-n1+1;小车接受的球的个数为numwriteln（num）;送分题此题“物理味”
18、有余而“信息味”不足，连循环语句都用不上！难见的“送分题”，可物理较差的人也得不到多少分哦！分析1、此题的难度较大。如果你这样认为：即在假定已用i个矩形面积和满足最小覆盖所有点的基础上，穷举所有2个矩形合并成1个矩形条件是：在所有合并方案中使合并后面积最小，从而使矩形个数减少为i-1那就错了，可是却可以通过前4组测试数据！正确的做法是对不同的K值分别进行计算，好在K值较小，否那么.讨论：k=1，只要求出n个点坐标的最大、最小值，就可求得矩形的位置与面积；k=2，有2个矩形，它们只有2种分布形式：左右式flag=0，上下式flag=1对于左右式，显然要先将所有点按横坐标升序排列，可将点1点i-1
19、放入矩形1中，将点i点n放入矩形2中，求两矩形的面积之和；如果面积和比上一个值小，记下；让i从2循环到n,就可完成左右式的全部搜索；对于上下式，先将所有点按纵坐标升序排列，依此类推。k=3，有3个矩形，它们有6种分布形式：要用两重循环进行搜索：设i,j为循环变量，将点1i-1放入矩形1中，点ij-1放入矩形2中，点jn放入矩形3中；点必须在放入前排好序均为升序：对于flag=0,所有点按横坐标排序；对于flag=1,所有点按纵坐标排序；对于flag=2,所有点先按横坐标排序，然后点in按纵坐标排序；对于flag=3,所有点先按横坐标排序，然后点1j-1按纵坐标排序；对于flag=4,所有点先按纵坐标排序，然后点1j-1按横坐标排序；对于flag=5,所有点先按纵坐标排序，然后点in按横坐标排序；至于k=4,4个矩形有22种分布形式，实在太复杂！幸好测试数据中没有K=4的情形（似乎有意放了一马？）。据说此题全国没有一人全对！只要求K=1，2，3$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+$M65520,0,6
