2024年3月7日发(作者：)

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

19.2 十九届提高组

一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）

1．一个32位整型变量占用（ A ）个字节。

A．4 B．8

C．32

D．128

D．11.125

2．二进制数11.01在十进制下是（ A ）。

A．3.25 B．4.125 C．6.25

3．下面的故事与（ B ）算法有着异曲同工之妙。

从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事…………………………’”

A．枚举 B．递归 C．贪心

D．分治

4．1948年，（ D ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

A．冯•诺伊曼(John von Neumann)

C．欧拉（Leonhard Euler）

【分析】 香农信息论鼻祖

5．已知一棵二叉树有2013个节点，则其中至多有（ A ）个节点有2个子节点。

A．1006 B．1007 C．1023 D．1024

【分析】（1）树根深度为0，深度为10的满二叉树节点总数2047；

（2）本题树深为10的完全二叉树，与满二叉树相比少了34个节点，

（3）深度为9的满二叉树节点总数量为1023；

（4）1023-（34/2）=1006

6．在一个有向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有5个顶点、8条边的连通图。若要使它不再是连通图，至少要删去其中的（ B ）条边。

A．2 B．3 C．4 D．5

【分析】要使图不联通，只要其中某一个节点不连通即可，所有顶点度最少是3，所以最少需要删除3条边

7．斐波那契数列的定义如下：F1=1，F2=1，Fn=Fn-1+Fn-2（n≥3）。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（ D ）。

function F(n:longint):longint;

begin

if n<=2 then

B．图灵（Alan Turing）

D．克劳德•香农（Claude Shannon）

F:=1

F:=F(n-1)+F(n-2);

1

else

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

end;

A．O(1) B．O(n) C．O(n2) D．O(Fn)

【分析】计算F1需要1次，计算F2需要一次，计算Fn需要计算F(n-1)的次数加上F（n-2）的次数，所以其实就是计算Fn次，于是答案选择D，至于这个Fn到底是多大，数学上可以计算，它等于O((（1+sqrt(5)）/2)^n).

8．二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么，二叉查找树的（ B ）是一个有序序列。

A．先序遍历 B．中序遍历 C．后序遍历 D．宽度优先遍历

9．将（2，6，10，17）分别存储到某个地址区间为0～10的哈希表中，如果哈希函数h(x)=（

D ），将不会产生冲突，其中a mod b表示a除以b的余数。

A．x mod 11

C．2x mod 11

D．B．x2 mod 11

xmod 11，其中x表示x下取整

【分析】A项6和17对11取余都是6发生冲突，B项10的平方和17的平方对11取余都是1发生冲突，C项6的两倍和17的两倍对11取余都是1发生冲突，D项分别为1，2，3，4，不冲突

10．IPv4协议使用32位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（ D ）位地址的IPv6协议所取代。

A．40 B．48 C．64 D．128

11．二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么12个顶点的二分图至多有（ C ）条边。

A．18

12．（ B ）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。

A．ASCII

【分析】

UNICODE与ASCII的区别 .

的特点

（1）ASCII 是用来表示英文字符的一种编码规范。每个ASCII字符占用1 个字节，因此，ASCII 编码可以表示的最大字符数是255（00H—FFH）。这对于英文而言，是没有问题的，一般只什么用到前128个(00H--7FH,最高位为0)。而最高位为1 的另128 个字符（80H—FFH）被称为“扩展ASCII”，一般用来存放英文的制表符、部分音标字符等等的一些其它符号。

（2）但是对于中文等比较复杂的语言，255个字符显然不够用。于是，各个国家纷纷制定了自己的文字编码规范，其中中文的文字编码规范叫做“GB2312—80”， 它是和ASCII 兼容的一种编码规范， 其实就是利用扩展ASCII没有真正标准化这一点，把一个中文字符 2

B．24 C．36 D．66

【分析】二分为6个和6个的顶点，此时边最多，有36条边。

B．Unicode C．GBK2312 D．BIG5

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

用两个扩展ASCII 字符来表示，以区分ASCII 码部分。

但是这个方法有问题，最大的问题就是中文的文字编码和扩展ASCII 码有重叠。而很多软件利用扩展ASCII 码的英文制表符来画表格，这样的软件用到中文系统中，这些表格就会被误认作中文字符，出现乱码。另外，由于各国和各地区都有自己的文字编码规则，它们互相冲突，这给各国和各地区交换信息带来了很大的麻烦。

E的产生

（1）要真正解决这个问题，不能从扩展ASCII 的角度入手，UNICODE作为一个全新的编码系统应运而生，它可以将中文、法文、德文……等等所有的文字统一起来考虑，为每一个文字都分配一个单独的编码。

3.什么是UNICODE

Unicode与ASCII一样也是一种字符编码方法，它占用两个字节（0000H—FFFFH）,容纳65536

个字符，这完全可以容纳全世界所有语言文字的编码。在Unicode 里，所有的字符都按一个字符来处理， 它们都有一个唯一的Unicode 码。

13．把64位非零浮点数强制转换成32位浮点数后，不可能（ D ）。

A．大于原数 B．小于原数 C．等于原数 D．与原数符号相反

【分析】64位非零浮点数强制转换成32位浮点数，两个数会有大小上的细微差别，但不会发生符号变化，因为有专门的符号位

14．对一个n个顶点、m条边的带权有向简单图用Dijkstr算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ B ）。

A．O(mn+n3) B．O(n2) C．O((m+n)log n) D．O((m+n2)log n)

【分析】Dijkstra算法（双重for 循环）计算单源最短路时间复杂度如果不借助堆或优先队列优化，是O（n^2）.

15．T(n)表示某个算法输入规模为n时的运算次数。如果T(1)为常数，且有递归式

T(n)=2*T(n / 2)+2n，那么T(n) = （ B ）。

A．Θ(n) B．Θ(n log n) C．Θ(n2) D．Θ(n2log n)

【分析】Θ的含义和“等于”类似，而大O的含义和“小于等于”类似

设 N×(1 / 2) ^X=1 ,X=log2N

T(n)=2*T(n / 2)+2n=2×(2×（T（n / 4）+2×(n / 2))+2n=22×T（n / 4）+(2n) ×2

=2X×T（1）+(2n) ×X =2 ^ log2N ×T（1）+(2N) ×log2N

=N +(2N) ×log2N= O(N ×log2N)

二、不定项选择题（共5题，每题1.5分，共计7.5分；每题有一个或多个正确选项，多选或 3

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

少选均不得分）

1．下列程序中，正确计算1，2，…，100这100个自然数之和sum（初始值为0）的是（ AC ）。

2．（ AD ）的平均时间复杂度为O(n log n)，其中n是待排序的元素个数。

A．快速排序 B．插入排序 C．冒泡排序 D．归并排序

【分析】只有快速排序和归并排序是n log n的，冒泡和插入都是n^2的时间复杂度。

3．以A0作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是（ CD ）。

A．A1 B．A2 C．A3 D．A4

4．（ AB ）属于NP类问题。

A．存在一个P类问题 B．任何一个P类问题

C．任何一个不属于P类的问题

D．任何一个在（输入规模的）指数时间内能够解决的问题

【分析】

1.

时间复杂度：

（1）时间复杂度：是指执行算法所需要的计算工作量。 时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

（2）多项式时间算法：如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。

4

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

2. P类、NP类问题

（1）P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。

（2）NP类问题：NP（Non-deterministic Polynomial）问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。

（3）所有的P类问题都是NP问题。 NP问题不是非P类问题

3. NPC问题（NP完全问题）：Cook 在1971年给出并证明了有一类问题具有下述性质：

（1）这类问题中任何一个问题至今未找到多项式时间算法；

（2）如果这类问题中存在一个问题有多项式时间算法，则这类问题都有多项式时间算法这类问题就是所谓的NP完全问题。

（3）NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。

5

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

5．CCF NOIP复赛考试结束后，因（ ABCD ）提出的申诉将不会被受理。

A．源程序文件名大小写错误

B．源程序保存在指定文件夹以外的位置

C．输出文件的文件名错误

D．只提交了可执行文件，未提交源程序

三、问题求解（共2题，每题5分，共计10分；每题全部答对得5分，没有部分分）

1． 某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1，s2，…，sn，均为0或1。该系统每次随机生成n个数a1，a2，…，an，均为0或1，请用户回答（s1a1+s2a2+…+snan）除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。然而，事与愿违。例如，当n=4时，有人窃听了以下5次问答：

就破解出了密码s1= 0 ，s2= 1 ，s3= 1 ，s4= 1 。

【分析】

（1）由第5组得到s1=0；

（2）由第1组、第5组得到s2=1；

（3）由第1组、第3组得到s3=1；

（3）由第2组、第3组得到s4=1；

2． 现有一只青蛙，初始时在n号荷叶上。当它某一时刻在k号荷叶上时，下一时刻将等概率地随机跳到1，2，…，k号荷尔蒙叶之一上，直至跳到1号荷叶为止。当n=2时，平均一共跳2次；当n=3时，平均一共跳2.5次。则当n=5时，平均一共跳 37/12 次。

【分析——递推】

（1）由n=2时，跳法2→2，2→1共2次，平均跳的次数f2=2次，说明在求平均时编号1不统计在内。

（2）由n=3时，跳法3→3，3→2，3→1，再从2号跳跳法2→2，2→1共5次，平均跳的次数f3=2.5次；f3=(3+f2)/2=2.5

6

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

（3）由n=4时，跳法分别是落在1号、2号、3号、4号；平均跳的次数

f4=（4+f2+f3）/3=（4+2+2.5）/3 = 8.5/3

（4）由n=5时，跳法分别是落在1号、2号、3号、4号、5号；平均跳的次数

f5=（5+f2+f3+f4）/4=（5+2+2.5+8.5/3）/4= 37/12

四、阅读程序写结果（共4题，每题8分，共计32分）

1．【字符串——判定输入的字符串是否是回文串】

var

n,i:integer;

str:string;

isPlalindrome:Boolean;

begin

readln(str);

n:=Length(str);

isPlalindrome:=true;

for i:=1 to (n idv 2) do

begin

if (str[i]<>str[n-i+1]) then

end;

if (isPlalindrome) then

writeln(‘Yes’)

else

writeln(‘No’);

isPlalindrome:=false;

end.

输入：abceecba

输出： Yes

【分析】 str[1]——str[8]、str[2]——str[7] 、 str[3]——str[6] 、str[4]——str[5]这4对字符相同则返回true

2．【数学——１到1000中是１０或１５的倍数的数的个数】

Var a,b,u,v,I,num:integer;

begin

readln(a,b,u,v);

num:=0;

for i:=a to b do

begin

if (I mod u=0)or(I mod v=0) then inc(num);

end;

7

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

writeln(num);

end.

输入：1 1000 10 15

输出： 133

【分析】此题计数1-1000范围内能够整除10或15的数有多少个，使用容斥原理或者集合求并很容易可以得到1000/10+1000/15-1000/30=133.

3．【动态规划——最长上升子序列的长度】

const SIZE=100;

var n,ans,I,j:integer;

height,num:array[1..SIZE] of integer;

begin

read(n);

for i:=1 to n do

begin

read(height[i]);

num[i]:=1;

for j:=1 to i-1 do

begin

if ((height[j]=num[i])) then

end;

ans:=0;

for i:=1 to n do

begin

end;

writeln(ans);

if (num[i]>ans) then ans:=ans+num[i];

num[i]:=num[j]+1;

end;

end.

输入：

8

3 2 5 11 12 7 4 10

输出： 4

【分析】

【1.状态描述】

（1）height[i]存放的数组

（2）num[i]：数组height[1]——height[i]中中包含height[i]上升序列长度

【2.状态转移】

8

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

1. 初始状态：num[i]:=1; num[1]:=1;

2. 状态转移：从下标1逐步递推到n，求解num[i]

num[i]=Max{ num[j], (1<= j<= i-1, height[j]

【3.算法分析】 例 height[4]=11 > height[3]=5，num[4]= num[3]+1=3

【4.算法设计】

1. 初始状态：num[i]:=1; num[1]:=1; 求解num[i]的最优解

2. 状态前驱： num[i]的前驱状态num[j]：num[1]—— num[i-1]

3. 状态转移：

（1）条件：if ((height[j]=num[i]))

（2）转移方程：num[i]:=num[j]+1;

4．【深度优先搜索——上下左右找棋盘数字为0的连续单元格数量】

const SIZE=100;

var

procedure colour(x,y:integer);

begin

begin

n,m,p,count,ans,x,y,I,j:integer;

a:array[1..SIZE,1..SIZE] of integer;

inc(count);

a[x][y]:=1;

if (x>1)and(a[x-1][y]=0) then colour(x-1,y); //上

if (y>1)and(a[x][y-1]=0) then

if (x

if (y

colour(x,y-1); //左

colour(x+1,y); //下

colour(x,y+1); //右

end;

fillchar(a,sizeof(a),0);

readln(n,m,p);

for i:=1 to p do

begin

end;

ans:=0;

9

read(x,y); a[x][y]:=1;

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

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的连续单元格数量

10

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

【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

（1）第一段start1、end1右移，应该在当前i、j之间：

start1:=i ; end1:=J-1

（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

begin

inc(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

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

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

begin

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