NOIP1996 提高組題目、題解、程序
文章目錄
這是我整理的信息學資料的一部分，包含1996-2008年信息學聯賽的題目、題解和程序。希望能夠對大家有一定的幫助。所寫的程序使用 Free Pascal 編譯。這些程序都是我一年或兩年前所寫，所以分析和代碼難免會出現不優美或有問題，如果你發現這樣的問題，請及時和我聯繫。如果你需要其它年份的資料，本站提供這些資料的目錄。
比賽安排(20分)
設有2^n(n<=6)個球隊進行單循環比賽,計劃在2^n-1天內完成,每個隊每天進行一場比賽.設計一個比賽的安排,
使在2^n-1天內每個隊都與不同的對手比賽.例如n=2時的比賽安排為:
隊 1 2 3 4
比賽 1-2 3-4 第一天
1-3 2-4 第二天
1-4 2-3 第三天
簡析：設定一個標誌數組，標記某兩個對是否比賽過。由於是單循環，兩者互相比賽，那麼數組[A,B]和數組[B,A]都需要設置為True。然後循環判斷每天每個隊應該和誰比賽即可。
program noip1996_1_bisaianpai;
type integer=longint;
var i,j,k,l,n,m:integer;
a:array[1..64,1..64]of boolean;
b:array[1..64]of integer;
function ok(i,j:integer):boolean;
var t:integer;
begin
for t:=1 to m do
if (b[t]=i)or(b[t]=j) then exit(false);
exit(true);
end;
begin
readln(k);
for i:=1 to 2**k do
a[i,i]:=true;
for i:=1 to 2**k-1 do
begin
n:=0;
fillchar(b,sizeof(b),false);
m:=0;
for j:=1 to 2**k do
begin
for l:=1 to 2**k do
if (a[j,l]=false) and (ok(j,l)=true) then
begin a[j,l]:=true; a[l,j]:=true; m:=m+2; b[m-1]:=j; b[m]:=l; write(j:2,'-',l:2,' ');
break;
end;
if (n=2**(k-1)) then begin write('ok'); break; end;
end;
writeln;
end;
for i:=1 to 2**k do
for j:=1 to 2**k do
if a[i,j]<>true then write('err at:',j:2,'-',l:2,' ');
end.
數制轉換(20分)
設字符串A$的結構為: A$=‘mp’
其中m為數字串(長度<=20),而n,p均為1或2位的數字串(其中所表達的內容在2-10之間)
程序要求:從鍵盤上讀入A$後(不用正確性檢查),將A$中的數字串m(n進制)以p進制的形式輸出.
例如:A$=‘48<10>8’
其意義為:將10進制數48,轉換為8進制數輸出.
輸出結果:48<10>=60<8>
簡析：這是一個數值轉換算法的直接應用。直接貼出程序。
program jinzhizhuanhuan;
type integer=longint;
var s,s1:string[255];
j1,j2:integer;
i,j,k:integer;
function getadd(s1,s2:string[255]):string[255];
var l1,l2,l,i,shu1,shu2,shu3,shu4,p:integer;
ret:string[255];
begin
l1:=length(s1); l2:=length(s2); if l1>l2 then l:=l1 else l:=l2;
ret:='';
shu4:=0; shu3:=0; shu2:=0; shu1:=0;
for i:=1 to l do
begin
shu1:=ord(s1[l1-i+1])-48;
shu2:=ord(s2[l2-i+1])-48;
if (s1[l1-i+1]=' ')or(l1-i+1<1) then shu1:=0;
if (s2[l2-i+1]=' ')or(l2-i+1<1) then shu2:=0;
shu3:=shu1+shu2+shu4;
shu4:=shu3 div 10;
shu3:=shu3 mod 10;
ret:=chr(shu3+48)+ret;
end;
if shu4<>0 then ret:=chr(shu4+48)+ret;
exit(ret);
end;
function cheng(s1,s2:string[255]):string;
var l1,l2,l,i,j,shu1,shu2,shu3,shu4,k:integer;
ret,b:string[255];
begin
l1:=length(s1); l2:=length(s2);
ret:='0';
for i:=l1 downto 1 do
for j:=l2 downto 1 do
begin
shu1:=ord(s1[i])-48;
shu2:=ord(s2[j])-48;
shu3:=shu1*shu2;
str(shu3,b);
if b<>'0' then
for k:=1 to l1-i+l2-j do
b:=b+'0';
ret:=getadd(ret,b);
end;
exit(ret);
end;
function chengfang(s1:string[255];l:integer):string[255];
var ret:string[255];
i:integer;
begin
ret:='1';
for i:=1 to l do
ret:=cheng(ret,s1);
exit(ret);
end;
function getdiv(s:string;j:integer;var modint:integer):string;
var yushu,l,i,t,shu,ff:integer;
ret:string[255];
begin
if s='0' then exit('0');
ret:=' ';
yushu:=0;
l:=length(s);
t:=0;
for i:=1 to l do
begin
shu:=(yushu*10+(ord(s[i])-48));
ff:=shu div j;
ret[i]:=chr(ff+48);
if (t=0)and(ord(ret[i])<>48) then t:=i;
yushu:=shu mod j;
end;
modint:=yushu;
if t=0 then exit('0');
exit(copy(ret,t,l-t+1));
end;
function to10jinzhi(nin:string[255];j:integer):string;
var l,i:integer;
ret,b,b1,f:string[255];
begin
l:=length(nin);
ret:='0';
str(j,b1);
for i:=1 to l do
begin
str(ord(nin[i])-48,b);
f:=cheng(b,chengfang(b1,l-i));
ret:=getadd(ret,f);
end;
exit(ret);
end;
function zhuanhuan(nin:string[255];j:integer):string;
var ret,b,now,now1:string[255];
f:integer;
begin
ret:='';
now:=nin;
now1:=getdiv(now,j,f);
while now<>now1 do
begin
now:=now1;
str(f,b);
ret:=b+ret;
now1:=getdiv(now,j,f);
end;
if now<>'0' then
ret:=now+ret;
exit(ret);
end;
begin
writeln('Input a string:',' e.g.99136<7>4');readln(s);
i:=pos('<',s);
j:=pos('>',s);
if (i=0) or (j=0) then begin writeln('Wrong number!'); exit; end;
s1:=copy(s,i+1,j-i-1);
val(s1,j1);
val(copy(s,j+1,length(s)),j2);
writeln(zhuanhuan(to10jinzhi(copy(s,1,i-1),j1),j2));
end.
字符串編輯(30分)
從鍵盤輸入一個字符串(長度<=40個字符),並以字符’.‘結束.
例如:‘This is a book.’,現對該字符串進行編輯,編輯功能有:
D:刪除一個字符,命令的方式為:
D a 其中a為被刪除的字符
例如:D s 表示刪除字符’s’,若字符串中有多個’s’,則刪除第一次出現的,如上例中刪除的結果為:
‘Thi is a book.’
I:插入一個字符,命令的格式為:
I a1 a2 其中a1表示插入到指定字符前面,a2表示將要插入的字符
例如: I s d 表示在指定字符’s’的前面插入字符’d’,若原串中有多個’s’,則插入在最後一個字符的前面,
如上例中,原串:‘This is a book.’
插入後:‘This ids a book.’
R:替換一個字符,命令格式為:
R a1 a2 其中a1為被替換的字符,a2為替換的字符,若在原串中有多個a1,則應全部替換
例如:原串:‘This is a book.’
輸入命令: R o e
替換後:’ This is a beek.’
在編輯過程中,若出現被指定的字符不存在時,則給出提示信息
簡析：這是一道模擬題，主要考察字符串函數的使用。
program noip1996_3;
var s:string;
c1,c2,c3,c4,c5:char;
i,j:integer;
begin
write('Input a string:'); readln(s);
while true do
begin
write('Delete, Insert, Or Replace?'); read(c1,c2,c3);
case c1 of
'D': begin
i:=pos(c3,s);
if i=0 then writeln('No char!')
else
begin
delete(s,i,1);
writeln('New string:',s);
end;
end;
'I': begin
read(c4,c5);
i:=pos(c3,s);
if i=0 then writeln('Nochar')
else
begin
insert(c5,s,i);
writeln('New string:',s);
end;
end;
'R': begin
read(c4,c5);
i:=pos(c3,s);
while i<>0 do
begin
s[i]:=c5;
i:=pos(c3,s);
end;
writeln('New string:',s);
end;
end;
end;
end.
© 轉載需附帶本文連結，依 CC BY-NC-SA 4.0 釋出。