省淳中信息学奥赛辅导 奥赛试题解析
【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分） 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)：
11
省淳中信息学奥赛辅导 奥赛试题解析
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; 【分析】
【1.算法分析】前P个数逐渐往后移动
12
省淳中信息学奥赛辅导 奥赛试题解析
【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分）
begin
end2:=n;
a[i]:=a[j]; inc(i);
//（3分）
end1:= (6) J-1(或start2-1） ; //（3分） start2:=j;
13
省淳中信息学奥赛辅导 奥赛试题解析
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 3. 状态转移2：第二段数组全部交换结束，第一段尚有部分数组没有移动，只要调整第一段 的起始下标，第二段的起讫下标不需调整 14 省淳中信息学奥赛辅导 奥赛试题解析 4.结束条件：两段的前交换数组的下标i,j均大于两段结束下标。 2．（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多个子 序列并列最长，输出任意一个即可。例如，序列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中，有两段满足条件的最长子序列，长度均为7，分别用下划线和上划线标出。 program two; const SIZE=100; var n,I,j,cur1,cur2,count1,count2, ans_length,ans_start,ans_end:longint; //cur1,cur2分别表示当前子序列中的两个不同整数 //count1,count2分别表示cur1，cur2在当前子序列中出现的次数 //ans_length连续子序列最大长度，ans_start,ans_end记录子序列的是开始结束下标 a:array[1..SIZE] of longint; begin readln(n); for i:=1 to n do read(a[i]); i:=1; j:=1; //i，j分别表示当前子序列的首尾，并保证其中至多有两个不同整数 while (j<=n)and(a[j]=a[i]) do inc(j); cur1:=a[i]; cur2:=a[j]; count1:= (1) j-1 ; //（3分） count2:=1; ans_length:=j-i+1; while j if a[j]=cur1 then inc(count1) else if a[j]=cur2 then inc(count2) else begin //a[j]与cur1,cur2不同，一个新的两元序列且a[j]=cur2，a[j-1]=cur1 if a[j-1]= (2) cur1 then begin while count2>0 do begin if a[i]=cur1 then dec(count1) //（3分） else dec(count2); inc(i); end; 15
2013NOIP初赛提高组试题解析
