思想：对每个元素按从低位到高位对每一位进行一次排序
8.高精度计算
A.
B.
C.
D.
9.树的遍历顺序转换
A. 已知前序中序求后序
procedure Solve(pre,mid:string);
var i:integer;
begin
if (pre='') or (mid='') then exit;
i:=pos(pre[1],mid);
solve(copy(pre,2,i),copy(mid,1,i-1));
solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i));
post:=post+pre[1]; {加上根，递归结束后post即为后序遍历}
end;
B.已知中序后序求前序
procedure Solve(mid,post:string);
var i:integer;
begin
if (mid='') or (post='') then exit;
i:=pos(post[length(post)],mid);
pre:=pre+post[length(post)]; {加上根，递归结束后pre即为前序遍历}
solve(copy(mid,1,I-1),copy(post,1,I-1));
solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i));
end;
C.已知前序后序求中序
function ok(s1,s2:string):boolean;
var i,l:integer; p:boolean;
begin
ok:=true;
l:=length(s1);
for i:=1 to l do begin
p:=false;
for j:=1 to l do
if s1=s2[j] then p:=true;
if not p then begin ok:=false;exit;end;
end;
end;
procedure solve(pre,post:string);
var i:integer;
begin
if (pre='') or (post='') then exit;
i:=0;
repeat
inc(i);
until ok(copy(pre,2,i),copy(post,1,i));
solve(copy(pre,2,i),copy(post,1,i));
midstr:=midstr+pre[1];
solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1));
end;
10.求图的弱连通子图(DFS)
procedure dfs ( now,color: integer);
begin
for i:=1 to n do
if a[now,i] and c=0 then begin
c:=color;
dfs(I,color);
end;
end;
11.拓扑排序
寻找一数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO.
12.进制转换
A.整数任意正整数进制间的互化
NOIP1996数制转换
设字符串A$的结构为: A$='mp'
其中m为数字串(长度< =20),而n,p均为1或2位的数字串(其中所表达的内容在2-10之间)
程序要求:从键盘上读入A$后(不用正确性检查),将A$中的数字串m(n进制)以p进制的形式输出.
例如:A$='48< 10 >8'
其意义为:将10进制数48,转换为8进制数输出.
输出结果:48< 10 >=60< 8 >
B.实数任意正整数进制间的互化
C.负数进制：
NOIP2000
设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负 进制下的数：-R∈{-2，-3，-4,....-20}
13.全排列与组合的生成
排列的生成：（1..n）
procedure solve(dep:integer);
var
i:integer;
begin
if dep=n+1 then begin writeln(s);exit; end;
for i:=1 to n do
if not used then begin
s:=s+chr(i+ord('0'));used:=true;
solve(dep+1);
s:=copy(s,1,length(s)-1); used:=false;
end;
end;
组合的生成(1..n中选取k个数的所有方案)
procedure solve(dep,pre:integer);
var
i:integer;
begin
if dep=k+1 then begin writeln(s);exit; end;
for i:=1 to n do
if (not used) and (i >pre) then begin
s:=s+chr(i+ord('0'));used:=true;
solve(dep+1,i);
s:=copy(s,1,length(s)-1); used:=false;
end;
end;
14 递推关系
计算字串序号模型
USACO1.2.5 StringSobits
长度为N (N< =31)的01串中1的个数小于等于L的串组成的集合中找出按大小排序后的第I个01串。
数字划分模型
*NOIP2001数的划分
将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。
d[0,0]:=1;
for p:=1 to n do
for i:=p to n do
for j:=k downto 1 do inc(d[i,j],d[i-p,j-1]);
writeln(d[n,k]);
*变形1：考虑顺序
d[ i, j] : = d [ i-k, j-1] (k=1..i)
*变形2：若分解出来的每个数均有一个上限m
d[ i, j] : = d [ i-k, j-1] (k=1..m)
15.算符优先法求解表达式求值问题
const maxn=50;
var
s1:array[1..maxn] of integer; {s1为数字栈}
s2:array[1..maxn] of char; {s2为算符栈}
t1,t2:integer; {栈顶指针}
procedure calcu;
var
x1,x2,x:integer;
p:char;
begin
p:=s2[t2]; dec(t2);
x2:=s1[t1]; dec(t1);
x1:=s1[t1]; dec(t1);
case p of
'+':x:=x1+x2;
'-':x:=x1-x2;
'*':x:=x1*x2;
'/':x:=x1 div 2;
end;
inc(t1);s1[t1]:=x;
end;
procedure work;
var c:char;v:integer;
begin
t1:=0;t2:=0;
read(c);
while c< >';' do
case c of
'+','-': begin
while (t2 >0) and (s2[t2]< >'(') do calcu;
inc(t2);s2[t2]:=c;
read(c);
end ;
'*','/':begin
if (t2 >0) and ((s2[t2]='*') or (s2[t2]='/')) then calcu;
inc(t2);s2[t2]:=c;
read(c);
end;
'(':begin inc(t2); s2[t2]:=c; read(c); end;
')':begin
while s2[t2]< >'(' do calcu;
dec(t2); read(c);
end;
'0'..'9':begin
v:=0;
repeat
v:=10*v+ord(c)-ord('0');
read(c);
until (c< '0') or (c >'9');
inc(t1); s1[t1]:=v;
end;
end;
while t2 >0 do calcu;
writeln(s1[t1]);
end;
16.查找算法
折半查找
function binsearch(k:keytype):integer;
var low,hig,mid:integer;
begin
low:=1;hig:=n;
mid:=(low+hig) div 2;
while (a[mid].key< >k) and (low< =hig) do begin
if a[mid].key >k then hig:=mid-1
else low:=mid+1;
mid:=(low+hig) div 2;
end;
if low >hig then mid:=0;
binsearch:=mid;
end;
树形查找
二叉排序树：每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值。
查找
function treesrh(k:keytype):pointer;
var q:pointer;
begin
q:=root;
while (q< >nil) and (q^.key< >k) do
if k< q^.key then q:=q^.left
else q:=q^.right;
treesrh:=q;
end;
17．KMP算法
18．贪心
*会议问题
（1） n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。
解：按每项活动的结束时间进行排序，排在前面的优先满足。
（2）会议室空闲时间最少。
（3）每个客户有一个愿付的租金，求最大利润。
（4）共R间会议室，第i个客户需使用i间会议室，费用相同，求最大利润。
附录1 常用技巧
1.带权中位数
我国蒙古大草原上有N（N是不大于100的自然数）个牧民定居点P1（X1，Y1）、P2（X2，Y2）、 …Pn（Xn，Yn），相应地有关权重为Wi，现在要求你在大草原上找一点P（Xp，Yp），使P点到任 一点Pi的距离Di与Wi之积之和为最小。
即求 D=W1*D1+W2*D2+…+Wi*Di+…+Wn*Dn 有最小值
结论：对x与y两个方向分别求解带权中位数，转化为一维。
设最佳点p为点k，则点k满足：
令W为点k到其余各点的带权距离之和，则
sigema( i=1 to k-1) Wi*Di < = W/2
sigema( i=k+1 to n) Wi*Di < = W/2
同时满足上述两式的点k即为带权中位数。
2．求一序列中连续子序列的最大和
begin
maxsum:=-maxlongint;
sum:=0;
for i:=1 to n do begin
inc(sum,data);
if sum >maxsum then maxsum:=sum;
if sum< 0 then sum:=0;
end;
writeln(maxsum);
end;
3．
附录2 数据结构相关操作
1．链表的定位函数loc(I:integer):pointer; {寻找链表中的第I个结点的指针}
procedure loc(L:linklist; I:integer):pointer;
var p:pointer;
j:integer;
begin
p:=L.head; j:=0;
if (I >=1) and (I< =L.len) then
while j< I do begin p:=p^.next; inc(j); end;
loc:=p;
end;
2．单链表的插入操作
procedure insert(L:linklist; I:integer; x:datatype);
var p,q:pointer;
begin
p:=loc(L,I);
new(q);
q^.data:=x;
q^.next:=p^.next;
p^.next:=q;
inc(L.len);
end;
3．单链表的删除操作
procedure delete(L:linklist; I:integer);
var p,q:pointer;
begin
p:=loc(L,I-1);
q:=p^.next;
p^.next:=q^.next;
dispose(q);
dec(L.len);
end;
4．双链表的插入操作（插入新结点q）
p:=loc(L,I);
new(q);
q^.data:=x;
q^.pre:=p;
q^.next:=p^.next;
p^.next:=q;
q^.next^.pre:=q;
5．双链表的删除操作
p:=loc(L,I); {p为要删除的结点}
p^.pre^.next:=p^.next;
p^.next^.pre:=p^.pre;
dispose(p);
[转帖]初赛的内容增加
在初赛的内容个增加以下内容：
数据结构 1. 指针类型2. 多维数组3. 单链表及循环链表4. 二叉树5. 文件操作（从文本文件中读入数据，并输出到文本文件中）
程序设计 1. 算法的实现能力2. 程序调试基本能力3. 设计测试数据的基本能力4. 程序的时间复杂度和空间复杂度的估计
算法处理 1. 离散数学知识的应用（如排列组合、简单图论、数理逻辑）2. 分治思想3. 模拟法4. 贪心法5. 简单搜索算法（深度优先 广度优先）搜索中的剪枝6. 动态规划的思想及基本算法
（一） 初赛内容与要求：
计 基算 本机 常的 识 1. 计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）2. 信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）3. 信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令、程序，和存储程序原理、程序的三种基本控制结构）4. 信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）5. 信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）6. 人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文件及交互操作））7. 信息技术的新发展、新特点、新应用等。
计 基算 本机 操的 作 1. WINDOWS和LINUX的基本操作知识2. 互联网的基本使用常识（网上的浏览、搜索和查询等）3. 常用的工具软件使用（文字编辑、电子邮件收发等）
程序设计的基本知识 数据结构 1. 程序语言中基本数据类型（字符、整数、长整数、浮点）2. 浮点运算中的精度和数值比较3. 一维数组（串）与线性表4. 记录类型（PASCAL）/结构类型（C）
程序设计 1. 结构化程序设计的基本概念2. 阅读理解程序的基本能力3. 具有将简单问题抽象成适合计算机解决的模型的基本能力4. 具有针对模型设计简单算法的基本能力5. 程序流程描述（自然语言/伪码/NS图/其他）6. 程序设计语言（PASCAL/C/C++，2003仍允许BASIC）
基本算法处 理 1. 初等算法（计数、统计、数学运算等）2. 排序算法（冒泡法、插入排序、合并排序、快速排序）3. 查找（顺序查找、二分法）4. 回溯算法
（二）复赛内容与要求：
在初赛的内容个增加以下内容：
数据结构 1. 指针类型2. 多维数组3. 单链表及循环链表4. 二叉树5. 文件操作（从文本文件中读入数据，并输出到文本文件中）
程序设计 1. 算法的实现能力2. 程序调试基本能力3. 设计测试数据的基本能力4. 程序的时间复杂度和空间复杂度的估计
算法处理 1. 离散数学知识的应用（如排列组合、简单图论、数理逻辑）2. 分治思想3. 模拟法4. 贪心法5. 简单捊
最新评论