NOIP2011普及组解题报告_精品.doc

NOIP2011普及组解题报告　 一、数字反转　　 没得满分只能说明一个问题，你的程序写的太少了。　　　 program reverse;　 var　 ??s:string;　 ??i,sta:longint;　　 begin　 ??assign(input,reverse.in);reset(input);　　　 ??assign(output,reverse.out);rewrite(output);　 ?　　 ??readln(i);　　　 ??str(i,s);　 ??sta:=1;　　　 ??if s[1]=-??then　 ????begin　　　 ??????write(-);　　 ??????sta:=2;　　 ????end;　　　 ??i:=length(s);　　　 ??while (s[i]=0) and (ista) do　 ????dec(i);　　　 ??while (i=sta) do　　 ????begin　　　 ??????write(s[i]);　 ??????dec(i);　　　 ????end;　　　 ?　　 ??close(input);close(output);　　 end.　　 ?　　 二、统计单词个数　　　 考你的基本功，和对程序的理解，尤其是细节上的优化。直接在文章中选出单词，与给定单词长度一致时才比较，函数传参数时也不要传字符串（会很慢的，具体慢多少没试）。　　 program stat;　　　 var　 ??s,p:ansistring;　　 ??i,j,first,num,len,c,k:longint;　　　 ?　 function cmp(x:longint):boolean;　　　 ??var　　　 ????i:longint;　　　 ??begin　　　 ????for i:= 1 to??c do　　 ???????if s[i] p[x+i-1] then exit(false);　　 ????exit(true);　 ??end;　 begin　 ??assign(input,stat.in);reset(input);　 ??assign(output,stat.out);rewrite(output);　　 ?　　 ??readln(s);readln(p);　　　 ??s:=upcase(s);p:=upcase(p);　 ??c:=length(s);??len:=length(p);　 ??i:=1;?????num:=0;??first:=-1;　 ??while (s[i]= )and (i=len) do inc(i);　 ??while (i=len) do　 ????begin　　　 ??????j:=i+1;　 ??????while (p[j] ) and (j=len) do　　 ????????inc(j);　 ??????if (j-i = c) and cmp(i) then　 ????????begin　　　 ??????????if first=-1 then first:=i;　　 ??????????inc(num);　 ????????end;　 ??????i:=j;??while (p[i]= ) and (i=len) do inc(i);　　 ????end;　 ??if first=-1 then　　　 ????writeln(-1)　　　 ??else writeln(num, ,first-1);　　　 ?　　　 ??close(input);close(output);　　 end.　　　 ?　　　 ?　 三、瑞士轮　　　 实践证明，如果单纯的排序r次，必然结果是超时。事实上只需一次真正意义上的排序以后，在以后的比赛中，按原顺序分成两组，获胜组和失败组，这两组依然是有序的，再把这两组归并成一组，就可以了。总时间复杂度O（N*R）。? 为了方便归并，下面的数组采用了滚动数组。　　　 program swiss_merger;　　 ?　　 ?　 var　 ??n,r,q,i,j,k,c,pwin,plose:longint;　　　 ??s,w,t:array[1..200050] of longint;　 ??id:array[0..1,1..200050] of longint;　　　 ?　　　 procedure qsort(n,m:longint);　 ??var　 ????i,j,k,t:longint;　 ?　 ??begin　　 ????i:=n;j:=m;??k:= id[0,(n+m)div 2];　 ????repeat　　　 ??????while (s[id[0,i]] s[