发布时间 : 星期一 文章2012十八届noip提高组题目及答案 - 图文更新完毕开始阅读
begin ans := 0; calc(1,1); writeln(ans); end; exit; end; if (left[x]=0) and (right[x]=0) then begin
left[x) := th; father[th] := x; dfs(th, th+1); father[th] := 0; left[x] := 0; end; if right[x] = 0 then begin
right[x] := th; father[th] := X; dfs(th, th+1); father[th] := 0; right[x] := 0; end; if (father[x] > 0) then dfs(father[x],th); end;
begin readln(s1); readln(s2); n := length(s1); fillchar(left,sizeof(left),0); fillchar(right,sizeof(right),0); fillcahr(father,sizeof(father),0); dfs(1,2); end. 输入： ABCDEF BCAEDF
输出：____________
五、完善程序（第1题第2空3分，其余每空2.5分，共计28分） 1．（排列数）输入两个正整数n,m(1?n?20,1?m?n) ，在1?输入：3 2 输出：1 2
1 3 2 1 2 3 3 1
3 2
const SIZE=20; var used :array [1..SIZE] of boolean; data :array [1..SIZE] of integer; n,m,i,j,k :integer; flag :boolean; begin readln(n,m); fillchar(used,sizeof(used)，false); for i:=1 to m do begin
n 中任取m个数，按字典序从小到大输出所有这样的排列。例如
data[i] := i;
used[i] := true; end; flag := true; while flag do begin for i:=1 to m-1 do write(data[i],' '); writeln(data[m]); flag := ① ; for i := m downto 1 do begin ② ; for j := data[i]+1 to n do if used[j] = false then begin used[j] := true; data[i] := ③ ; flag := true; break; end; if flag then begin for k:= i+l to m do for j:= 1 to ④ do if used[j]=false then begin data[k] := j; used[j] := true; break; end; ⑤ ; end; end; end; end.
2．(新壳栈)小Z设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前c个元素是它的壳，支持翻转操作。其中，c>2是一个固定的正整数，表示壳的厚度。小Z还希望，每次操作，无论是压入、弹出还是翻转，都仅用与c无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗?
程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足c个，应当输出相应的错误信息。
指令 1[空格]e 2 3 0 涵义 在栈顶压入元素e 弹出（并输出）栈顶元素 翻转栈顶的前c个元素 退出 表1：指令的涵义
输入 3 1 1 1 2 1 3 1 4 3 1 5 3 2 2 2 输出 3 2 5 栈中的元素 （左为栈底，右为栈顶） 1 1 2 1 2 3 1 2 3 4 1 4 3 2 1 4 3 2 5 1 4 5 2 3 1 4 5 2 1 4 5 1 4 说明 输入正整数c 压入元素1 压入元素2 压入元素3 压入元素4 翻转栈顶的前c个元素 压入元素5 翻转栈顶的前c个元素 弹出栈顶元素3 弹出栈顶元素 2 弹出栈顶元素 5 3 2 2 2 0 错误信息 4 1 错误信息 1 4 1 空 空 空 由于栈中元素不足c个，无法翻转，故操作失败，输出错误信息 弹出栈顶元素4 弹出栈顶元素1 由于栈中元素不足c个，无法翻转，故操作失败，输出错误信息 退出 表2：输入输出样例
const
NSIZE = 100000;
CSIZE = 1000; var n,c,r,tail,head :longint; s : array[1..NSIZE] of longint; //数组s模拟一个栈，n为栈的元素个数 q :array[1..CSIZE] of longint; //数组q模拟一个循环队列，tail为队尾的下标，head为队头的下标 direction,empty :boolean;
function previous(k :longint) :longint; begin if direction then previous := ((k+c-2) mod c) + 1; else previous := (k mod c) + 1; end;
function next(k :longint) :longint; begin if direction then ① else next := ((k+c-2) mod c)+1; end;
procedure push; var element :longint; begin read(element); if next(head) = tail then begin inc(n); ② ; tail := next(tail); end; if empty then empty := false else head := next(head); ③ := element; end;
procedure pop; begin if empty then begin writeln('Error: the stack is empty!'); exit; end: writeln( ④ ); if tail = head then empty := true else begin
head := previous(head); if n > 0 then begin
tail := previous(tail); ⑤ := s[n]; dec(n); end; end; end;
procedure reverse; var
temp :longint; begin if ⑥ = tail then begin
direction := not direction; temp := head; head := tail; tail := temp; end else
writeln('Error:less than',c,' elements in the stack!'); end;
begin readln(c); n := 0; tail := 1; head := 1; empty := true; direction := true; repeat read(r); case r of 1 : push; 2 : pop; 3 : reverse; end; until r = 0; end.