noip历届程序填空题汇编.docVIP

历届程序填空题汇编 2009年普： 1．（最大连续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为4，-5，3，2，4时，输出9和3；数列为1 2 3 -5 0 7 8时，输出16和7。 var a: array[1..100] of integer; n, i, ans, len, tmp, beg: integer; begin read(n); for i := 1 to n do read(a[i]); tmp := 0; ans := 0; len := 0; beg := ① ; for i := 1 to n do begin if tmp + a[i] ans then begin ans := tmp + a[i]; len := i - beg; end else if ( ② ) and (i - beg len) then len := i - beg; if tmp + a[i] ③ then begin beg := ④ ; tmp := 0; end else ⑤ ; end; writeln(ans, , len); end. 2. (国王放置) 在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的攻击的区域是:(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。读入三个数n,m,k，输出答案。题目利用回溯法求解。棋盘行标号为0~n-1，列标号为0~m-1。 var n, m, k, ans: integer; hash: array[0..4, 0..4] of integer; procedure work(x, y, tot: integer); var i, j: integer; begin if tot = k then begin inc(ans); exit; end; repeat while hash[x, y] 0 do begin inc(y); if y = m then begin inc(x); y := ① ; end; if x = n then exit; end; for i := x - 1 to x + 1 do if (i = 0) and (i n) then for j := y - 1 to y + 1 do if (j = 0) and (j m) then ② ; ③ ; for i := x - 1 to x + 1 do if (i = 0) and (i n) then for j := y - 1 to y + 1 do if (j = 0) and (j m) then ④ ; inc(y); if y = m then begin inc(x); y := 0; end; if x = n then exit; until false; end; begin read(n, m, k); ans := 0; fillchar(hash, sizeof(hash), 0); ⑤ ; writeln(ans); End. 2008年普： 1．（字符串替换）给定一个字符串S（S仅包含大小写字母），下面的程序将S中的每个字母用规定的字母替换，并输出S经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串S，第二个字符串S’由26个字母组成，它是a~z的任一排列，大小写不定，S’规定了每个字母对应的替换字母：S’中的第一个字母是字母A和a的替换字母，即 S中的A用该字母的大写替换，S中的a用该字母的小写替换；S’中的第二个字母是字母B 和b的替换字母，即S中的B用该字母的大写替换，S中的b用该字母的小写替换；… …以