下面讲的都比较简单，大家看完以后，有配套练习哦！

1 数组及其应用
这里还是只讲一些应用，基础知识自己看书或我提供的几个INTERNET资源。
1.下标的灵活运用
例如对称的情形，可以把下标设成：
a:array[-5..5] of integer;
只要a[i]:=a[-i];就进行了一次“对称”的赋值。

2.常量数组
善用可以减少不少程序量。
例如P1-9《公式变形》。我的参考程序只有三十多行，主要是因为灵活的应用了数组，
包括一个常量数组一个变量数组，减少了不少麻烦。

典型的常量数组有：

增量型：如在国际象棋棋盘上“马”的八个方向的活动可以用两的增量数组表示：
dx:array[1..8] of shortint=(1,2,2,1,-1,-2,-2,-1);
dy:array[1..8] of shortint=(-2,-1,1,2,2,1,-1,-2);
移动第d个方向只需要：
x:=x+dx[d];
y:=y+dy[d];

枚举型：例如平年一年第N个月的天数：
dcount:array[1..12] of shortint=(31,28,31,30,31,30,31,31,30,31,30,31);
便于修改。

3.避免下标越界
方法是{$R+}

4.数组的插入与删除
虽然数组应该避免频繁的插入与删除，但有时不可避免。方法如下：
插入：插入点以后每个元素往后移动一个位置，再插入：
for i:=len downto p do
a[i+1]:=a[i];
a[p]:=x;
inc(len);

删除：删除点以后的每个元素往前移动一个位置，如：
for i:=p to last do
a[i]:=a[i+1];
dec(len);

2 字符串处理

字符串处理因为其灵活性常使初学者头疼！我以前也怕它，不过很快就适应了。
一般常用的处理是：(以下的例子中s是一个字符串)
1.扫描字符

第i个字符是s[i]
例如s='Hello, world!'
则s[1]='H', s[6]=',', s[7]=' '; s[13]='!'
s的长度是length(s)

那么把字符串反转后输出的方法就是
for i:=length(s) downto 1 do
write(s[i]);

2.定位
就是查找子串
例如
s1='Hello, my friend!';
s2='my';

则pos(s2,s1)=8,即s2在s1的第8个字符处出现
但pos('him','history')=0,因为'him'在'history'中并不出现

3.分割,合并,删除
仅举几个例子。
1)copy
copy('Hello, my friend!',3,2)='ll'

2)delete
若s='Hello, my friend';
执行delete(s,4,4)
后s='Helmy friend'';

3)
s1='Hi,';
s2='Alan';
则s1+s2='Hi,Alan'

4.与数字互化
s='1234';
执行val(s,v,code)后v=1234; code=0; code=0说明成功的将字符串转化为了数字，否则code<>0

v=4567;
执行str(v,s)后s='4567';

5.字符的ASCII码
请自己看有关的书籍，一定要掌握！

注意：对于时间要求严格的题目，字符串操作的时间问题也不能忽视。

6.一个例子：
输入k个字符串（中间可能有多个空格），把他们反着连在一起输出。
如：
输入：abc d e f gh
输出:ghfedabc
分析：只要把空格删除，就可以得到这些字符串。
var
p:integer;
s,s2:string;
begin
readln(s);
s2:='';
repeat
while s[1]='' do delete(s,1,1); {删去开头的多余空格}
p:=pos(' ',s); {找第一个空格};
if p=0 then s2:=s+s2 {没有找到}
else begin
s2:=copy(s,1,p-1)+s2; {加入到s2的前面}
delete(s,1,p); {删去}
end;
until p=0; {没有空格了}
writeln(s2);
end.

3 整数的处理
主要是利用数学工具了。下面举几个例子。
1.求最大公约数gcd（greatest common divisor）
用欧几里德辗转相除法：
function gcd(a,b:longint):longint;
begin
if a mod b=0 then gcd:=b
else gcd:=gcd(b,a mod b);
end;

2.求最小公倍数
利用(a,b)*[a,b]=a*b 即可。
例如：
100和140的最大公约数为20,那么
最小公倍数=100*140 div 20=700

3.分离数字
很简单，涉及到数字的问题都可以借助于字符串。
例如反转各位数字：(13765->56731)
var
a:longint; {a=13765}
b:longint; {b will be 56731}
s1,s2:string;
i,code:integer;
begin
a:=13765;
str(a,s1);
s2:='';
for i:=length(s1) downto 1 do
s2:=s2+s1[i];
val(s2,b,code);
{now, b=56731!}
end.

4.素数的测试
一般是:
function isprime(k:longint):boolean;
var
i:longint;
begin
isprime:=false;
for i:=2 to trunc(sqrt(k)) do { ***}
if k mod i=0 then exit;
isprime:=true;
end;
对于大的素数（在longint范围内）可以采用先生成一个小的素数表，在 { *** } 改为测试
2到trunc(sqrt(k))内的所有素数。当然要保证素数表足够大。(到46341为止)
更快的测试方法将在后面介绍。

一定要注意是否运算结果可能溢出。

4 排序

以下均是：
a:array[1..n] of integer; 要求升序排列。

1.O(N^2)排序
冒泡排序
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]<a[j] then swap(a[i],a[j]);
算法时间复杂度为O(N^2).它的最佳，平均，最差情况是几乎一样的

选择排序：每次选最小的，然后把它去掉以后再选最小的...

2.O(nlogn)排序
归并排序：分成两堆，分别排序，再合并。
快速排序：选择一个支撑点，把比它小的放在左边，比他大的放在右边，分别排序。
在“分治法”部分，我会再提到快速排序和它的一些类似的问题的。

3.不基于比较的排序
如果数字都小于等于一个定值M，可以考虑数组排序：
令b[i]为i出现的次数，则：
fillchar(b,sizeof(b),0);
for i:=1 to n do
inc(b[a[i]]);
那么b中非零的数就组成了排好序的序列，也就是：
for i:=1 to m do
for j:=1 to b[i] do
writeln(i);

如果b[i]是一个链表，就成了桶排序。

5 高精度数的处理

注意：只要你会笔算，照搬到这里就可以了。
常用数据结构（这里我只讲一种）：数组,每个元素是一位数字。如：
123456789123456789
储存成：
a:array[1..len]=(0,0,0...0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9);
加法就是：
g:=0;
for i:=len downto 1 do
begin
s:=a[i]+b[i]+g;
c[i]:=s mod 10;
g:=s div 10;
end;
如果是N进制，把10换成N就可以了。

乘法（单精度与多精度）就是：
g:=0;
for i:=len downto 1 do
begin
s:=a[i]*b+g;
c[i]:=s mod 10;
g:=s div 10;
end;
注意：b不一定只是一位数。

高精度乘法（字符串形式）我推荐使用多项式乘法的方式。
const
maxn=100;
type
bign=string[maxn];

procedure mul(a,b:bign; var c:bign);
var
tmp:array[1..maxn*2] of integer;
i,j,g,p,k:integer;
begin
{删除多余的零}
while (length(a)>1)and(a[1]='0') do delete(a,1,1);
while (length(b)>1)and(b[1]='0') do delete(b,1,1);

{初始化积}
p:=length(a)+length(b);
for i:=1 to p do
tmp[i]:=0;

{乘法：每两位相乘}
for i:=1 to length(a) do
for j:=1 to length(b) do
begin
k:=p-i-j; {结果在第几位}
inc(tmp[p-k] ,v[a[i]]*v[b[j]] mod 10); {加到这一位上}
inc(tmp[p-k-1],v[a[i]]*v[b[j]] div 10);
end;

{整理结果}
g:=0;
c:='';
for i:=p downto 1 do
begin
c:=ch[(tmp[i]+g) mod 10]+c;
g:=(tmp[i]+g) div 10;
end;

{删除多余的零}
while (length(c)>1)and(c[1]='0') do delete(c,1,1);
end;

下面是一篇英文文章(PDF) Big numbers

6 进位制
大家应该比较熟吧。运算可以按高精度数处理，而进制转换嘛，也不难。
10进制换成N进制：
readln(p); {p<>0时}
i:=0;
while p>0 do
begin
inc(i);
a[i]:=p mod n;
p:=p div n;
end;
for j:=i downto 1 do
write(a[j]);

N进制转化成10进制：
p:=0;
for i:=1 to len do
p:=p*n+a[i];

这次复赛（其实是N年以前的ACM题目）考了负数进位制，其实还有复数进位制和fibinacci进制的!
他们都是基于定义的。利用类似的（广义）除法和取模运算，最后都能够得出正确的进制表示。
说到应用，主要是数学题，例如《tower of hanoi》，还有压缩存储。例如《拯救大兵瑞恩》和
《补丁vs错误》