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

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

a :array[1..100] of integer; readln(n);

for i:=1 to n do for i:=1 to n-1 do if a[i]>a[i+1] then begin

temp := a[i]; a[i] := a[i+1]; a[i+1] := temp; end;

for i:=n downto 2 do

if a[i]

temp := a[i]; a[i] := a[i-1]; a[i-1] := temp; end; sum := 0;

for i:=2 to n-1 do inc(sum,a[i]); writeln(sum div (n-2));

read(a[i]);

begin

end. 输入： 8

40 70 50 70 20 40 10 30 输出：___250 / 6 = 41____

【分析】两次循环比较交换后数组状态如下，去掉首位最小最大值

2．【1——120之内的120的因子，120与i的最大公约数是i本身】 var n,i,ans:integer;

function gcd(a,b :integer) : integer; //求a、b的最大公约数 begin begin

if a mod b=0 then gcd :=b;

else gcd := gcd(b,a mod b);

end;

readln(n); ans := 0;

36

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

for i:=1 to n do

if gcd(n,i)=i then ans := ans + 1; writeln(ans);

end. 输入：120

输出：____16_____

【分析】120=1*2*2*2*3*5，共有下列数与120的最大公约数是他们本身。 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120

3．【数转化为2n +……+21 + 20】 var data : array[1..20] of integer;

n,i,h,ans

: integer;

procedure merge; begin

data[h-1] := data[h-1] + data[h]; dec(h); inc(ans);

end; begin

readln(n);

h := 1; data[h] := 1; for i:=2 to n do begin inc(h); data[h] := 1;

while (h>1) and (data[h]=data[h-1]) do merge; // end;

writeln(ans);

ans := 0;

end.

（1）输入：8 输出：__7____ （4分） （2）输入：2012 输出：__2004______ （4分） 【1.状态描述】

1.数组data, n设置data中某元素是1的次数 2. ans数组data元素合并次数

【2.算法设计】递推，确定数组data的下标h:设置data[h]:=1 1. 初始状态：第1次设置：h := 1; ans := 0; 2. 状态转移：第i次设置数组data值 （1）h加1：inc(h);

37

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

（2）并设置data[h]:=1

（3）从h开始向左检查data中有没有相同元素，有进行合并 3. 状态转移：数组data值进行合并 （1）h减1：dec(h);

（2）统计合并次数ans： inc(ans)

【3.模拟执行】转换状态表，本题是统计合并的次数，合并的过程过程执行一次便统计一次。合并的条件是data[h]=data[h-1]

(1)由上可知，数组有效元素为n，当n可以表示为2^x时，转换次数为:

38

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

2^0+2^1+2^2+2^3+...+2^ (x-1),例1变到8转换7次，1变到16转换15次

（2）当i从1变到1024时，转换次数为2^0+2^1+2^2+2^3+...+2^ 9=1023； 当i从1变到

2048时，转换次数为2^0+2^1+2^2+2^3+...+2^ 9+2^10=2047

（3）2012=1024 + 512 + 256 + 128 + 64 + 16 + 8 + 4；t(x)表示从数组初始状态1变到x

状态的转换次数；

（4）当n=2012时，当i从1变到2012时，转换次数：

t(1024)+t(512)+t(256)+t(128)+t(64)+t(16)+t(8)+t(4) =1023+511+255+127+63+15+7+3=2004

4．【先序遍历、中序遍历的序列构造出二叉树】

Var left, right, father :array[1..20] of integer;

//中序遍列生成的树，遍列结果放入s3中 procedure check(x:integer); begin

if left[x]>0 then check(left[x)); s3 := s3 + sl[x];

if right[x]>0 then check(right[x]); end;

//求出节点对应值的和——ABCDEF基本值分别对应123456，求出的是各个节点基本值乘以该

节点深度的和

procedure calc(x,dep :integer); begin

ans:= ans + dep*(ord(sl[x])-ord('A')+1); if left[x] > 0 then calc(left[x],dep+l); if right[x]> 0 then calc(right[x),dep+l); end;

//以第s1[x]字符为根，s1[th]作为它的子树，先左后右 procedure dfs(x,th :integer); begin

if th = n+1 then //s1中所有的字符串已经加入到树中，要判断这棵树是否正确 begin sl, s2, s3

:string;

n,ana :integer;

s3 :='';

check(1); //中序遍列生成的树，遍列结果放入s3中

39

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

if s2=s3 then //判断构建的二叉树正确，正确则进入计算输出 begin

//如果s1[x]左右子树都为空，s1[th]作为s1[x]的左子树，x的左为ch, ch的父为x if (left[x]=0) and (right[x]=0) then begin

left[x] := th; father[th] := x;

dfs(th, th+1); //深度搜索以ch为根，s1[ch+1]为其子树 father[th] := 0; //回溯 left[x] := 0;

end;

//如果s1[x]只有右子树为空，s1[th]作为s1[x]的右子树，x的右为ch, ch的父为x

if right[x] = 0 then begin

ans := 0;

calc(1,1); writeln(ans);

end;

exit; //构建的二叉树不对，退出回溯 end;

right[x] := th; father[th] := X; dfs(th, th+1);

father[th] := 0; //回溯

right[x] := 0;

end;

//如果s1[x]已经有左右子树，s1[th]作为其兄弟处理 if (father[x] > 0) then dfs(father[x],th); end; begin

readln(s1); readln(s2); n := length(s1);

fillchar(left,sizeof(left),0); fillchar(right,sizeof(right),0); fillcahr(father,sizeof(father),0); dfs(1,2);

end. 输入： ABCDEF

40