NOIP2008普及組復(fù)賽解題報(bào)告

1、NOIP2008普及組復(fù)賽解題報(bào)告一、ISBN號碼基礎(chǔ)字符串處理題，心細(xì)一點(diǎn)的基本都能得滿分。參考程序：program isbn;const inp='isbn.in' oup='isbn.out'var i,j,k,ans:longint; s:string; ch:char;procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end;procedure fclose; begin close(input); close(out

2、put); end;begin flink; readln(s);/ 輸入字符串 j:=0; i:=1; ans:=0; while j<9 do begin if si in '0'.'9' then/如果是數(shù)字,那么累加到ans中,共9個(gè)數(shù)字 begin inc(j); inc(ans,(ord(si)-ord('0')*j); end; inc(i); end; ans:=ans mod 11;計(jì)算識(shí)別碼 if ans=10 then ch:='X' else ch:=chr(ord('0')+ans)

3、;/把識(shí)別碼轉(zhuǎn)換成字符,方便輸出 if slength(s)=ch then write('Right') else write(copy(s,1,12)+ch);/輸出正確的識(shí)別碼 fclose;end.二、排座椅用的是賽前集訓(xùn)時(shí)提到的貪心，當(dāng)時(shí)說某些題目用貪心可以得部分分，但是本題貪心可以得滿分的。當(dāng)然本題的貪心需要預(yù)處理下，開2個(gè)一維數(shù)組，rowi錄如果在第i行加通道,可以分割多少對調(diào)皮學(xué)生,coli記錄如果在第j列加通道,可以分割多少對調(diào)皮學(xué)生,最后貪心法輸出分割學(xué)生最多的前K行和前L列。參考程序：program seat;const inp='seat.in&

4、#39; oup='seat.out'var flag,m,n,k,l,d,i,j,x,y,x1,y1:longint; tmp,col,row:array1.1000 of longint; s,s1:ansistring;procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end;procedure fclose; begin close(input); close(output); end;function min(a,b:longint)

5、:longint; begin if a<b then exit(a); exit(b); end;procedure qsort(m,n:Longint);/快排 var i,j,k,t:longint; begin i:=m; j:=n; k:=tmp(i+j) shr 1; repeat while tmpi>k do inc(i); while tmpj<k do dec(j); if i<=j then begin t:=tmpi; tmpi:=tmpj; tmpj:=t; inc(I); dec(J); end; until i>j; if m<

6、j then qsort(m,j); if I<n then qsort(i,n); end;begin flink; readln(m,n,k,L,d); fillchar(row,sizeof(row),0); fillchar(col,sizeof(col),0); for i:= 1 to d do /統(tǒng)計(jì)在每行、每列添加通道可以分割的學(xué)生數(shù) begin readln(x,y,x1,y1); if (x=x1) then inc(colmin(y,y1) else inc(rowmin(x,x1); end; j:=0; for i:= 1 to m do /把能沒個(gè)行通道分割的

7、學(xué)生數(shù)加入tmp數(shù)組,準(zhǔn)備排序 begin if rowi>0 then begin inc(j); tmpj:=rowi; end; end; qsort(1,j);/對tmp數(shù)組排序 flag:=tmpk;/flag為前K項(xiàng)的最小值 i:=1; j:=0; while (i<=n) and (j<k) do begin if rowi>=flag then /如果該行能分割的人數(shù)不少于flag,說明此處可以添加通道 begin write(i); inc(j); if j<>k then write(' '); end; inc(i);

8、end; writeln;/下面是求列通道,思想同上 j:=0; for i:= 1 to n do begin if coli>0 then begin inc(j); tmpj:=coli; end; end; qsort(1,j); flag:=tmpL; i:=1; j:=0; while (i<=m) and (j<L) do begin if coli>=flag then begin write(i); inc(j); if j<>L then write(' '); end; inc(i); end; fclose;end.三

9、、傳球游戲直接dp，似乎說遞推更確切點(diǎn)。f(i,k)表示經(jīng)過k次傳到編號為i的人手中的方案數(shù)。那么可以推出下面的方程：f(i,k)=f(i-1,k-1)+f(i+1,k-1) （i=1或n時(shí)，需單獨(dú)處理）邊界條件：f(1,0)=1;結(jié)果在f(1,m)中參考程序：program ball;const inp='ball.in' oup='ball.out'var i,j,k,n,m:longint; f:array0.30,0.30 of longint;procedure flink; begin assign(input,inp); reset(input);

10、 assign(output,oup); rewrite(output); end;procedure fclose; begin close(input); close(output); end;begin flink; readln(n,m); fillchar(f,sizeof(f),0); f1,0:=1; for k:=1 to m do/注意此處2個(gè)循環(huán)的次序 begin f1,k:=f2,k-1+fn,k-1; for i:= 2 to n-1 do fi,k:=fi-1,k-1+fi+1,k-1; fn,k:=fn-1,k-1+f1,k-1; end; write(f1,m);

11、 fclose;end.四、立體圖Pku原題，編號2330算不上難題，但是比較麻煩，細(xì)心點(diǎn)就ok了。先計(jì)算好畫布的大小，再寫一個(gè)根據(jù)左下角坐標(biāo)繪制一個(gè)單位立方體的子程序。然后遵循下面法則，不停繪制若干個(gè)立方體。（此處能體現(xiàn)出分割程序的偉大）因?yàn)橐煌５母采w，所以要遵循“視覺法則”：1.       先繪里層再繪外層2.       先繪底層再繪上層3.       先回左邊再繪右邊參考程序：program drawi

12、ng;const inp='drawing.in' oup='drawing.out'var m,n,i,j,k,x,y,h,tmp,maxx,maxy:longint; map:array1.1000,1.1000 of char;/畫布 a:array1.50,1.50 of integer;/記錄輸入的矩陣procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end;procedure fclose; begin close(

13、input); close(output); end;procedure print;/輸出畫布 var i,j:longint; begin for i:= 1 to maxx do begin for j:= 1 to maxy do write(mapi,j); if i<>maxx then writeln; end; end;procedure draw(x,y:longint);/在畫布(map數(shù)組)上繪制左下角坐標(biāo)為(x,y)的一個(gè)單位立方體 begin mapx,y:='+'mapx,y+1:='-' mapx,y+2:='-

14、'mapx,y+3:='-'mapx,y+4:='+' dec(x); mapx,y:='|'mapx,y+1:=' ' mapx,y+2:=' 'mapx,y+3:=' 'mapx,y+4:='|' mapx,y+5:='/' dec(x); mapx,y:='|'mapx,y+1:=' ' mapx,y+2:=' 'mapx,y+3:=' 'mapx,y+4:='|' mapx

15、,y+5:=' 'mapx,y+6:='+' dec(x); mapx,y:='+'mapx,y+1:='-' mapx,y+2:='-'mapx,y+3:='-'mapx,y+4:='+' mapx,y+5:=' 'mapx,y+6:='|' dec(x); inc(y); mapx,y:='/'mapx,y+1:=' ' mapx,y+2:=' 'mapx,y+3:=' 'mapx,y

16、+4:='/' mapx,y+5:='|' dec(x);inc(y); mapx,y:='+'mapx,y+1:='-' mapx,y+2:='-'mapx,y+3:='-'mapx,y+4:='+' end;begin flink; for i:= 1 to 1000 do for j:= 1 to 1000 do mapi,j:='.' /初始化畫布 readln(m,n); /計(jì)算畫布大小maxx * maxy maxy:=n*4+1+m*2; maxx:=0; for i:= 1 to m do begin tmp:=0; for j:= 1 to n do begin read(ai,j); if ai,j>tmp then tmp:=ai,j; end; tmp:=tmp