信息竞赛共享noip2013提高组pascal试题

第青少年信息学联赛初提高Pascal语言试竞赛时间：20131013选手注意 ） 枚 递 贪 分1948年 冯·诺伊曼（Johnvon 图灵（Alan 欧拉（Leonhard 克劳德·香农（Claude ）个节点有2个子节点 5个顶点、8条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。 斐波那契数列的定义如下：F1=1,F2=1,Fn=Fn–1+Fn–2(n≥3)。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（ funtionF(n:longint):longint;ifn<=2thenF:=1F:=F(n-1)+F(n- xmod x2mod 2xmod ⌊√⌋mod11，其中⌊√表示√使用 那么，12个顶点的二分图至多有（ GBK ） O(mn+ O((m+n)log O((m+n2)logT(n)表示某个算法输入规模为n时的运算次数。如果T(1)为常数，且有递归式T(n)2*T(n/2)+2n，那么T(n)= ） Θ(nlog Θ(n2log二、选择题（共5题，每题1.5分，共计7.5分；每题有一个或多个正确 fori:=1to100dosum:=sum+i;i:=whilei>100dosum:=sum+i;i:=sum:=sum+i;untili>i:=sum:=sum+i;untili<= 存在一个P任何一个P任何一个不属于PCCFNOIP复赛考试结束后，因 问答的过程被，也无助于——因为用户并没有直接发送。111001200110301100411100510000就出了s1 跳2次；当n=3时，平均一共跳2.5次。则当n=5时，平均一共跳 112345四、阅读程序写结果（共4题，每8分，共32分

n,i:integer;str:string;islindrome:n:=Length(str);islindrome:=true;fori:=1to(ndiv2)doif(str[i]<>str[n-i+1])thenislindrome:=false;if(islindrome)thenwri

a,b,u,v,i,num:readln(a,b,u,v);num:=0;fori:=atobdoif(imodu=0)or(imodv=0)then输入：1100010constSIZE=100;n,ans,i,j:height,num:array[1..SIZE]offori:=1tondonum[i]:=forj:=1toi-1doif((height[j]<height[i])and(num[j]>=num[i]))thennum[i]:=num[j]+1;ans:=fori:=1tondoif(num[i]>ans)thenans:=num[i];8325111274constSIZE=100;n,m,p,count,ans,x,y,i,j:integer;a:array[1..SIZE,1..SIZE]ofinteger;procedurecolour(x,y:integer);a[x][y]:=1;if(x>1)and(a[x-1][y]=0)thencolour(x-1,y);if(y>1)and(a[x][y-1]=0)thencolour(x,y-1);if(x<n)and(a[x+1][y]=0)thencolour(x+1,y);if(y<m)and(a[x][y+1]=0)thencolour(x,y+1);fillchar(a,sizeof(a),0);readln(n,m,p);fori:=1topdoread(x,y);a[x][y]:=1;ans:=fori:=1tondoforj:=1tomdoifa[i][j]=0thencount:=0;if(ans<count)thenans:=count;653456五、完善程序（第115分，第213分，共28分constintSIZE=100;inta[SIZE],n;p(1≤p≤n)apnpp个数（np个数）之间的相对位置。例如，51,2,3,4,5p=23,4,5,1,2。procedureswap1(p:longint);i,j:b:array[1..SIZE]oflongint;fori:=1topfori

//（2分:=p+1tonb[i-p]:=fori:=1tondoa[i]:=b[i];我们也可以用时间换空间，使用时间复杂度 O(n2)、空间复杂度为O(1)的算法procedureswap2(p:longint);i,j,temp:longint;fori:=p+1tondotemp:=forj:=idownto do //（2分a[j]:=a[j- :=temp; //（2分procedureswap3(p:longint);start1,end1,start2,end2,i,j,temp:longint;start1:=1;end1:=p;start2:=p+1;end2:=n;whiletruedoi:=j:=while(i<=end1)and(j<=end2)dotemp:=a[i];a[i]:=a[j]:=ifi<=end1thenstart1:=ielseif then //（3分start1:= //（3分end1:= //（3分start2:=（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。个子序列并列最长，输出任意一个即可。例如，序列“11232323311131”中，有两段满足条件的最长子序列，长度均为7，分别用下划线和上划线标出。programtwo;constSIZE=100;n,i,j,cur1,cur2,count1,count2,ans_length,ans_start,ans_end:longint;a:array[1..SIZE]offori:=1tondoi:=j:=while(j<=n)and(a[j]=a[i])docur1:=cur2:=count1:=count2:=1;

//（3分ans_length:=j-i+1;whilej<ndoifa[j]=cur1thenelseifa[j]=cur2thenelseifa[j-1]= then //（3分whilecount2>0doifa[i]=cur1thencur2:=a[j];count2:=1;elsewhilecount1>0doi