end;
writeln(num);
end.
输入：1 1000 10 15 输出：
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] < height[i]) and (num[j] >= num[i])) then
num[i] := num[j]+1;
end;
end;
ans := 0;
for i := 1 to n do begin
if (num[i] > ans) then
ans := num[i];
end;
writeln(ans);
end.
输入：
8
3 2 5 11 12 7 4 10 输出：
CCF NOIP2013 初赛提高组 Pascal 语言试题
第 6 页，共 12 页
4. const SIZE = 100;
var
n, m, p, count, ans, x, y, i, j : integer; a : array[1..SIZE, 1..SIZE] of integer;
procedure colour(x, y : integer); begin 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
colour(x, y-1);
if (x < n) and (a[x+1][y] = 0) then
colour(x+1, y);
if (y < m) and (a[x][y+1] = 0) then
colour(x, y+1);
end;
begin
fillchar(a, sizeof(a), 0); readln(n, m, p); for i := 1 to p do begin
read(x, y);
a[x][y] := 1;
end;
ans := 0;
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 < count) then
ans := count;
CCF NOIP2013 初赛提高组 Pascal 语言试题
第 7 页，共 12 页
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 输出：
五、完善程序（第 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)：
procedure swap1(p : longint);
var
i, j : longint;
b : array[1..SIZE] of longint;
begin
for i := 1 to p do
b[ (1) ] := a[i];
//（2 分）
for i := p + 1 to n do b[i - p] := a[i];
CCF NOIP2013 初赛提高组 Pascal 语言试题
第 8 页，共 12 页
for i := 1 to n do
a[i] := b[i];
end;
我们也可以用时间换空间，使用时间复杂度为 O(n)、空间复杂度为 O(1)的算法：
2
procedure swap2(p : longint);
var
i, j, temp : longint;
begin
for i := p + 1 to n do begin
temp := a[i];
for j := i downto (4) do a[j] := a[j - 1]; (5) := temp;
end;
end;
事实上，还有一种更好的算法，时间复杂度为 O(n)、空间复杂度为 O(1)：procedure swap3(p : longint);
var
start1, end1, start2, end2, i, j, temp : longint; begin
start1 := 1; end1 := p; start2 := p + 1; end2 := n; while true do begin
i := start1;
j := start2;
while (i <= end1) and (j <= end2) do begin
temp := a[i];
a[i] := a[j];
CCF NOIP2013 初赛提高组 Pascal 语言试题
第 9 页，共 12 页
//（2 分）//（2 分）
a[j] := temp; inc(i); inc(j);
end;
if i <= end1 then
start1 := i else if begin
start1 := (5) ; //（3 分） end1 := (6) ; //（3 分） start2 := j; end else
break;
(4) then
//（3 分）
end;
end;
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 在当前子序列中出现的次数
a : array[1..SIZE] of longint;
begin
readln(n);
for i := 1 to n do
read(a[i]); i := 1;
CCF NOIP2013 初赛提高组 Pascal 语言试题
第 10 页，共 12 页
NOIP2013初赛提高组Pascal试题及答案
