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
xmod 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]
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] （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
发布评论