历届奥赛试题解析-初赛讲解(6)

省淳中信息学奥赛辅导 奥赛试题解析

【3.算法设计】

1. 初始状态——底部最优解solve= a[x,y]三角形元素值 2. 状态转移——求点(x,y)达到底部的最优解solve(x,y) 2.1遍列各种前驱状态向下或右斜

solve(x,y)= MAX{ solve (x+1,y)、 solve (x+1,y+1) }+ a[x,y] 3. 目标状态：顶点到底部最优解solve(1,1)

4. 【字符处理+循环中途退出break】 var n,ans,i,j: integer;

S: string;

Function get(i: integer) : char; //获取循环字符串中第i个字符 begin

if i<= n then get:= s[i] else get:=s[i-n]; end; begin

readln(s); n:= length (s); ans:= 1; for i:= 2 to n do begin

for j:=0 to n-1 do

if get(i+j) < get(ans+j) then begin

ans:=i; break; end

else if get(i+j)> get(ans+j) then break;

end;

for j:=0 to n-1 do write(get(ans+j)); writeln; end.

输入：CBBADADA 输出：__ ACBBADAD __ 【分析】:

1. i=2,j=0,ans=1 get(i+j)= get(2)= B, get(ans+j)= get(1)= C → ans=2 2. i=3, j=0,ans=2 get(i+j)= get(3)= B, get(ans+j)= get(2)= B

26

省淳中信息学奥赛辅导 奥赛试题解析

j=1,ans=2 get(i+j)= get(4)= A, get(ans+j)= get(3)= B → ans=3

3. i=4, j=0,ans=3 get(i+j)= get(4)= A, get(ans+j)= get(3)= B → ans=4 4. i=5, j=0,ans=4 get(i+j)= get(5)= D get(ans+j)= get(4)=A → break 5. i=6, j=0,ans=4 get(i+j)= get(6)= A, get(ans+j)= get(4)=A

j=1,ans=4 get(i+j)= get(7)=D, get(ans+j)= get(5)=D

j=2,ans=4 get(i+j)= get(8)=A, get(ans+j)= get(6)=A

j=3,ans=4 get(i+j)= get(1)=C, get(ans+j)= get(7)=D → ans=6

6. i=7, j=0,ans=6 get(i+j)= get(7)= D, get(ans+j)= get(6)=A → break 7. i=8, j=0,ans=6 get(i+j)= get(8)= A, get(ans+j)= get(6)=A

j=1,ans=6 get(i+j)= get(1)=C, get(ans+j)= get(7)=D → ans=8

输出：get(8)、get(9) 、get(10) 、get(11) 、get(12) 、get(13) 、get(14) 、get(15)即 S[8]、S[1] 、S[2] 、S[3] 、S[4] 、S[5] 、S[6] 、S[7]

四、完善程序（前2空每空2分，后8空每空3分，共计28分）

1.（坐标统计）输入n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点

（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。 Const SIZE= 100;

Var X,y,f:array[1..SIZE] of integer;

N,i,j,max_f,ans: integer; Begin

readln(n);

For i:=1 to n do Readln (x[i],y[i]]); Max_f :=0; For i:=1 to n do Begin

f[i]:= ① 0 ； // f[i]点i控制点的数量 For j:= 1 to n do Begin

if(x[j]< x[i]) and ( ②y[j]

If ④（i>1）and (f[i]>=f[i-1]) then Begin

max_f:= f[i]; ⑤ ans:= i ; End; End;

27

省淳中信息学奥赛辅导 奥赛试题解析

For i:= 1 to n do Writeln(f[i]); Writeln(ans); End.

【分析】宽度搜索 【1.状态描述】

（1）x[i],y[i]：点i的坐标 （2）f[i]：点i的能控制点的数量

【2.状态转移】求f[i]。搜索棋盘中所有点j——For j:= 1 to n do 1.转移规则： if(x[j]< x[i]) and ( y[j]

2. （排列数）输入两个正整数n，m（1

大输出所有这样的排列。例如： 输入：3 2 输出：1 2 1 3

2 1 2 3 3 1 3 2

const SIZE=25;

var used: array[1.. SIZE] of boolean; //数i是否已经被取到 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

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:= ① false ; for i:=m downto 1 do

28

省淳中信息学奥赛辅导 奥赛试题解析

begin

② used[data[i]]:=false; for j:= data[i]+1 to n do if used[j]= false then begin

used[j]:= true; data[i]:= ③ j ;

flag:= true; //更换1个data[i]成功，跳出循环输出 Break; end;

if flag then //更换data[i+1]——data[m] begin

for k:=i+1 to m do for j:=1 to ④ n do if used[j]= false then begin

data[k]:= j; used[j]:= true; Break; end;

⑤ break; end; end; end; end. 【分析】: 【1.状态描述】

（1）data[1..M ]:取得的m个数

（2）used[i]=true表示数i已经再当前组合中，不能再选择 【2.状态转移】

1. 初始状态：将1—M个数放入数组data[1]—data[M]中，得到第1个组合 2. 状态转移：从i =M——1逐步更改data[i]—data[M]中的数 （1）将原来data[i]中的数不选用used[used[i]]:=FALSE

（2）将原来data[i]中的数更改为data[i]+1，

（3）在data[1]—data[N]中凡是没有被选中的数逐步选择来更换data[i+1]—data[m]中

数

【3.算法分析】以n=5,m=3为例，

29

省淳中信息学奥赛辅导 奥赛试题解析

【4.算法设计】

1. 初始状态：将1—M个数放入数组data[1]—data[M]中，得到第1个组合 2. 状态变化规则： data[i]，data[i]= data[i]+1；

3. 状态转移——检查data[M]……data[1]数，尝试将data[i]逐渐加大 （0）数据输出data[1]—data[M]

for i:=m downto 1 do begin

1. 尝试data[i]中的数更改，

（1）data[i]原来数不选——used[data[i]]:=false; （2）将data[i]中新数据的范围： data[i]+1——N for j:= data[i]+1 to n do begin

如果j存且在当前状态未选，则得到新组合，做如下处理 ①得到新组合标记：flag:= true;

②j已被选中，作标记：used[j]:= true; ③新组合中data[i]为新的数j：data[i]:= j ; ④跳出当前循环，对data[i+1]…data[m]进行处理

End;

2.如果data[i]改成了新的数j，则data[i+1]…data[m] …… 此处隐藏：2134字，全部文档内容请下载后查看。喜欢就下载吧 ……