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

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

ans:=0;

for i:=1 to n do

for j:=1 to m do

if a[i][j]=0 then begin

count:=0;

colour(i,j);

if (ans

end;

writeln(ans);

end. 输入： 6 5 9 1 4 2 3 2 4 3 2 4 1 4 3 4 5 5 4 6 4 输出： 7 【分析】

【1.状态描述】

（1）棋盘状态：a[x][y]:=1或0

（2）count,ans：数字为0的连续单元格数量，count当前解,ans当前最优解 【2.状态转移】

1. 初始状态：查找棋盘每个值为0的单元格 a[i][j]=0 2. 状态转移：如果a[i][j]=0则

（1）：状态修改 inc(count); a[i][j]:=1;

（2）：按上下左右4个方向深度搜索下一单元格 【3.算法分析】分上下左右找数字为0的连续单元格数量

11

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

【4.算法设计】

1. 初始状态：查找棋盘每个值为0的单元格 ，并以它为起点查找数字为0的连续单元格数

量count,初始count:=0 2. 父状态a[x][y]=0

procedure colour(x,y:integer);

begin

1. 计算新状态：inc(count); 2. 父状态访问过标志：a[x][y]:=1;

3. 试探各种子状态可能——按上下左右4个方向深度搜索下一单元格 4. 下一单元格值为0，则深度搜索colour(x-1,y)…… end;

五、完善程序（第1题15分，第2题13分，共计28分）

12

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

1．（序列重排）全局数组变量a定义如下：

const int SIZE=100; int a[SIZE],n;

它记录着一个长度为n的序列a[1]，a[2]，…，a[n]。现在需要一个函数，以整数p(1≤p≤n)为参数，实现如下功能：将序列a的前p个数与后n-p个数对调，且不改变这p个数（或n-p个数）之间的相对位置。例如，长度为5的序列1，2，3，4，5，当p=2时重排结果为3，4，5，1，2。有一种朴素的算法可以实现这一需求，其时间复杂度为O(n)、空间复杂度为O(n)：

procedure swap1(p:longint); var

I,j:longint;

b:array[1..SIZE] of longint;

for i:=1 to p do b[（1） n-p+i ]:=a[i]; for i:=p+1 to n do b[i-p]:=a[i]; for i:=1 to n do a[i]:=b[i];

//（2分）

begin

end; 【分析】 【算法设计】

1. 第一种方法是通过开一个b数组，然后先将a数组中1到p的数复制到b数组中后p个位置：n-p+1到n。

2. 将a数组p+1到n区间的数复制到b数组前段1——n-p。

3. 最后再将b数组元素复制回a数组中；显然第一空是n-p+i。以p=3为例

我们也可以用时间换空间，使用时间复杂度为O(n2)、空间复杂度为O(1)的算法： procedure swap2(p:longint); var begin

for i:=p+1 to n do begin

temp:=a[i];

for j:=I downto (2) i+1-p do a[j]:=a[j-1]; //（2分）

(3) a[i-p] :=temp; //（2分） end;

I,j,temp:longint;

end;

13

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

【分析】

【1.算法分析】前P个数逐渐往后移动

【2.算法设计】

1.初始状态：将第p+1位置空出——temp:=a[i];，将前p个数后移 2.空出位置i从p+1一直到n，移动的数就是i左边的p个数

3.将空出位置i原来的数temp放到i的前面空出的位置i-p——a[i-p]:=temp;

事实上，还有一种更好的算法，时间复杂度为O(n)、空间复杂度为O(1); procedure swap3(p:longint); var

start1,end1,start2,end2,I,j,temp:longint; start1:=1; end1:=p; start2:=p+1; while true do begin i:=star1; j:=start2;

while (i<=end1)and(j<=end2) do begin

temp:=a[i]; a[j]:=temp; inc(j); end;

if i<=end1 then start1:=i else if (4) j<=end2 then

begin

start1:= (5) i ; //（3分）

14

begin

end2:=n;

a[i]:=a[j]; inc(i);

//（3分）

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

end1:= (6) J-1(或start2-1） ; //（3分） start2:=j; end

else end;

break;

end; 【分析】 【1.算法分析】

1. 将数组分成两段start1——end1；start2——end2进行交换， i,j是两段数中当前交换数组的下标

2. 状态转移1：第一段数组全部交换结束，第二段尚有部分数组没有移动，即 if (i>end1) and( j

（2）第二段start2右移、end2不变—— start2:=j;

3. 状态转移2：第二段数组全部交换结束，第一段尚有部分数组没有移动，即 if (i<=end1) and( j>end2) then

（1）第一段的起始位置 需要调整i，结束位置不变——start1:=i （2）第二段调整的数改变，但位置不变即start2、end2不调整

【2.算法设计】

1.初始状态：设置要调整两段的起讫下标；两段数组进行交换 start1:=1; end1:=p; start2:=p+1; end2:=n;

2. 状态转移1：第一段数组全部交换结束，第二段尚有部分数组没有移动， if (i>end1) and( j

15