2013NOIP初赛提高组试题解析

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

cur2:=a[j]; count2:=1; end else begin

while count1>0 do begin

if a[i]=cur1 then

(3) dec(count1) //（2分） else

(4) dec(count2) ; inc(i); end;

//（3分）

//（2分）

(5) cur1:=a[j] ; count1:=1; end; end;

if (ans_length

ans_length:=j-i+1; ans_start:=I; ans_end:=j; end;

end; // while j

for i:=ans_start to ans_end do write(a[i],’ ‘); end.

【分析——递推或动态规划】 【1.状态描述】

1．字符串：a:array[1..SIZE] of longint; 2. 子序列属性

（1）cur1,cur2：当前子序列中的两个不同整数

（2）count1,count2：表示子序列中的两个数cur1，cur2在子序列中出现的次数 （3）ans_length连续子序列最大长度

（4）i,j：当前子序列在数组中的起始、当前下标，

（5）ans_start,ans_end是最优解的起始下标 【2.状态转移】 1.初始状态：

（1）子序列起始位置是i=1；当前查找位置是j

（2）当前子序列中的两个不同整数cur1,cur2、出现次数count1,count2 2. 状态转移：设前查找位置是j

16

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

（1）如果a[j]与当前子序列中整数cur1,cur2其中一个相同，

则inc(count1)或inc(count2)

（2）如果a[j] 与整数cur1,cur2都不同，则产生一个新的两元序列 ①新序列的两个不同整数cur1,cur2要更改其中一个。

②新序列的起始位置是i需要调整 ③新序列的count1,count2要调整

3. 转移方程：比较a[j-1]与原来的cur1,cur2那个相等 （1）a[j-1]与原来的cur1相等，则

①count2调整为0，起始位置是i要移动，count1也要调整 while count2>0 do

begin

if a[i]=cur1 then dec(count1) else dec(count2); inc(i); end;

②新的cur2:=a[j]; count2:=1;

（1）a[j-1]与原来的cur2相等，则

①count1调整为0，起始位置是i要移动，count2也要调整 while count1>0 do

【3.算法分析】变量i、j表示第1、2个数的开始位置；cur1、cur2是两个不同的数 （1）初始时i=1，j=3，cur1=1，cur2=3，count1=2，count2=1 begin

if a[i]=cur1 then dec(count1) inc(i); end;

②新的cur1:=a[j] ; count1:=1;

else dec(count2) ;

（2）while j<14 j++；j=4时，a[j]=3与cur1、cur2都不同，因此a[j]=3将作为新的第二个数cur2，原来的cur1、cur2有一个成为cur1，关键是看a[j-1]与原来的cur1、cur2哪个相等。a[j-1]将作为新的cur1，原先的第一个数cur1也将调整。统计数量count1、count2跟着调整。 【4.算法设计】

1.初始状态：子序列的起始位置i=1; 第一个数cur1=a[1], 2. 查找第二个数cur2的位置j

while (j<=n)and(a[j]=a[i]) do inc(j);

17

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

3.循环结束说明a[j]与前面的数a[i]不同，即得到第二个数cur2，并计算count1、count2

cur1:=a[i];

cur2:=a[j];

count1:= j-1 ;

count2:=1;

4.继续向右移动j：如果a[j]与当前子序列中整数cur1,cur2其中一个相同，则inc(count1)

或inc(count2)

5.状态转移：a[j]是一个新的数，产生了一个新序列，含两个数a[j-1]、a[j]；要确定新序

列的起始位置i、原来的count1、count2只有一个有用，但要调整。

（1）a[j-1]与原来的cur1相等，count1有用，原来序列是起始位置i要右移，删除掉cur2 while count2>0 do

（2）a[j-1]与原来的cur2相等，count2有用，原来序列是起始位置i要右移，删除掉cur1

while count1>0 do begin

if a[i]=cur1 then dec(count1) else dec(count2) ; inc(i); end;

begin

if a[i]=cur1 then dec(count1) else dec(count2); inc(i); end;

cur2为新的数a[j]——cur2:=a[j];

cur1为新的数a[j]——cur1:=a[j];

18