2008年信息学奥林匹克预赛试题及答案程序的完善

1.(求第k个最大的数)给定一个长度为100000的无序正整数序列，另一个数n (1

Var a:array[1..1000000]的整数；

n，m，ans:整数；

过程交换(var a，b:整数)；

var t:整数；

开始

如果(a & lt& gtb)然后开始

t:= a；a:= b；b:= t；

结束；

结束；

函数FindKth(left，right，n:integer):integer；

Var tmp，value，I，j:整数；

开始

如果left=right那么exit(left)；

tmp:=random(右-左)+左；

swap(a[tmp]，a[left])；

值:=____①_____

我:=左；j:=对；

而我& ltj do

开始

while(我& ltj)和(_ _ _ _ _ _ _ _②_ _ _ _ _ _ _ _)做dec(j)；

如果我& lt那就开始吧

a:= a[j]；inc(一)；

结束else break

while(我& ltj)和(_ _ _③_ _)do Inc(I)；

如果我& lt那就开始吧

a[j]:= a[I]；第十届会议；

结束else break

结束；

____④_____

如果我& ltn然后开始公司(I)；exit(FindKth(_ _ _ _ _ _ _⑤_ _ _ _ _)；结束；

如果我& gtn然后开始dec(j)；退出(_ _ _ _ _ _ _⑥_ _ _ _ _ _ _ _)；结束；

退出(一)；

结束；

var i:整数；

开始

随机化；

ans:=-1；

m:= 5；

对于i:=1到m do

读(a[I])；

读作(n)；

ans:=FindKth(1，m，n)；

writeln(a[ans])；

结束。

2.(矩阵中的数)有一个n*n(1≤n≤5000)的矩阵A，对于1 ≤ I < n，1≤j≤n，a[i，j]& lt；a[i+1，j] a[j，I]& lt；a[j，i+1].即矩阵中两个相邻的元素，右边的元素一定比左边的大。对于两个相邻的元素，下面的元素必须大于上面的元素。给定矩阵A中的一个数K，找出K所在的行和列(注意:输入的数据保证矩阵中的数是不同的)。

定义变量

n，k，answerx，answery:整数；

答:数组[1..5000,1..5000]的整数；

过程查找位置；

Var I，j:整数；

开始

I:= n；j:= n；

而j & gt0开始吧

如果a[n，j]& lt；k然后破；

第十届会议；

结束；

______①_________

而a[i，j]& lt；& gtk do

开始

while (___②_____)和(i & gt1)做dec(一)；

while (___③_____)和(j & lt= n)do Inc(j)；

结束；

_______④________

_______⑤________

结束；

var i，j:整数；

开始

读作(n)；

对于i:=1到n do

对于j:=1到n do

read(a[i，j])；

读(k)；

FindKPosition

writeln(answerx，' '，answery)；

结束。