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

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

3. 状态转移2：第二段数组全部交换结束，第一段尚有部分数组没有移动，只要调整第一段

的起始下标，第二段的起讫下标不需调整

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);

16

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

inc(i); end; 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

17

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

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

（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],

18

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

2. 查找第二个数cur2的位置j

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

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];

19

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

18. 十八届（2012）试题

18.1 十八届普及组

一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项） 1. 计算机如果缺少（ A ），将无法正常启动。

A.内存 B.鼠标 C.U盘 …… 此处隐藏：2073字，全部文档内容请下载后查看。喜欢就下载吧 ……