第一次信息学竞赛赛前辅导.docx
《第一次信息学竞赛赛前辅导.docx》由会员分享，可在线阅读，更多相关《第一次信息学竞赛赛前辅导.docx（28页珍藏版）》请在冰点文库上搜索。
第一次信息学竞赛赛前辅导
一、NOIP题型及算法类型：
1、数据统计类：
1）分类——统计算法
2）排序——选择、冒泡、快速、统计、归并、二叉树、堆
3）计算——高精度：
高+高，高+低，高-高，高-低，高*低，高*高，高div低，高mod低，
高精度div（mod）高精度，高精度比较大小。
4）进制转换——低精度p进制~高（低）精度q进制、高精度p进制转高精度q进制
2、字串处理类：
1）数据分离——子串查找、子串复制、数串互转、子串删除
2）字串编辑——用循环按字符处理，整串用函数处理。
3、模拟类：
1）直接模拟——读入一组数据处理一步、全部读入后再一次性处理。
2）分步模拟——将K步的工作分解成K个一步进行模拟。
4、数学类：
切忌直接模拟进行计算，一定要先进行数学推导，推的越多，程序越简单，速度越快。
1）找递推公式（关系）
2）找直接运算最终结果的公式
3）表达式计算
5、数据结构：
1）队列和栈的处理。
2）宽度优先搜索、深度优先搜索。
3）树型结构的建立、访问、维护。
4）最短路径。
5）拓扑排序。
6）最小生成树。
7）网络流问题。
6、动规：
1）线性（单一状态）
2）阵列（多状态）
3）多线程动规
4）二次动规。
二、时间分配问题：
1、完整四题：
20+30+60+70，本次参赛：
50+100+30（第一题30分钟,第二题100分钟,30分钟骗分）
2、每题时间分配：
1/3+1/3+1/3（1/3时间审题、1/3时间编写程序代码、1/3时间调试及测试）
三、审题方法：
1、根据题目确定基本类型
对于不熟悉的题型、过于繁琐、数据规模太大的题目，大胆猜测，小心验证，尽量转化、简化。
往往无法下手的题目，最终可以转化成最基本的算法解决。
（1）用稿纸尽可能多地模拟题目的数据，根据模拟过程中的数据变化结合已掌握的基本算法来找出规律。
（2）对找出的规律，用其它数据进行验证。
（如没有其它数据，则需要自己推导测试数据，推导技巧见下面）
2、确定了类型以后，精心挑选实现的算法，考虑方面：
数据规模大小、运行速度
数据规模问题：
（1）熟悉各种类型的变量所占空间大小和能存放的最大数值
整型：
Integer:
-32767~32767（-215~215）
Longint:
-2147483648~2147483647或-2.1*109~2.1*109、-231~231，
Int64:
-9223372036854775808～9223372036854775807
或-9.2*1018~9.2*1018、或-263~263，
Cardinal:
无符号的长整型，0~4294967295或0~232,4.29*109,
Qword:
无符号的int64型，0~184********709551615或0~1.8*1019,0~264
其中int64和Qword型为非顺序类型，不能用做For语句的控制变量
实型：
Real:
3.4*1038，7~8位有效数字
Double:
1.7*10308,15~16位有效数字
Extended：
1.1*104932，19~20位有效数字
（实型数据输出时，保留若干位小数的输出方法：
vara:
real;
m:
integer;
begin
m:
=round（a*100）;
write（mdiv100,mmod100）;
end.
字符串型：
String:
255个字符
Ansistring:
无限制，但速度超慢（一般只能满足O（n）的算法）
各种基类型的数组能开的最大上限
数组：
各种数值型：
一个99999999大小
字符串型：
999999大小
（2）运行速度问题：
（1）一般机器每秒能执行的指令换算成程序中的循环次数：
1亿~10亿
（2）熟悉各种基本算法的时间复杂度
如：
统计算法排序：
O（N）
选择、冒泡：
O（N2）
堆排、快速排序：
O（N*log2N）注：
对于N=a*10n，log2N<3.3*n
由于堆排时每次循环的操作较多，所以慢于快排。
归并：
O（N）
高精度：
高*高、高/高是O（N2），其余是O（N）
串处理：
注意串处理函数和过程只是使用方便，速度并不比自编的按位处理方法快。
迪杰斯特拉、拓扑排序：
O（N2）
3、仔细分析算法中各个细节的小算法，并规划程序结构（子程序）
一般结构：
init;
main;
Print;
其它子程序：
被重复2次或以上的程序段、只用一次但具有相对独立的功能
（尽可能把功能可以独立出来的程序段写成子程序，如：
复杂的逻辑判断、复杂的计算等）
四、程序编写：
先编写主程序，再自上而下地分层编写子程序，在编写过程中，应及时将今后还会使用到的程序段和写起来很麻烦的部分放到子程序中去。
五、调试程序：
打开变量查看器，自下而上地调试。
（一）先注释原主程序，重新建立临时主程序：
第一步：
单独执行init过程，确保init过程读入的数据完整无误。
第二步：
从最深层的子程序开始，逐个调试每个子程序
（1）用赋值语句给该子程序需要用到的各个参数和子程序需要用到的全局变量进行赋值。
（2）在主程序中直接调用该子程序，跟踪运行的结果并保证运行结果正确。
重复第二步，直到所有子程序调试通过。
（二）删除临时主程序，恢复原主程序。
分步运行主程序，检查每个子程序执行完毕后的各变量或数组里数据的正确性。
本步骤可能遇到的问题：
（1）变量：
超过存储范围、变量类型不匹配
（2）数组：
下标越界（尤其下标出现0）
（三）数据测试：
第一步：
样例数据的测试。
第二步：
自编数据测试
1、通过修改样例数据（速度快）
（1）不改变数据规模，改变个别数据以改变运行结果
（2）不改变运行结果，增加无用数据以扩大数据规模
（3）既改变数据规模，又改变运行结果
2、测试边缘数据
样例数据往往带有诱导性陷阱，而实际标准测试数据中除样例中的情况以外，还会有各种情况甚至刁钻的数据情况，对这些情况必须加以测试。
常见的有：
（1）样例中没有0而题目没明确否定
（2）样例中没有出现大量相同数据而题目没有说不行
（3）空串或各种关键字作为处理对象
总之，只要题目没有排除的情况，都是标准测试数据中可以出现的，都必须在这一步里加以严格测试。
3、测试极限数据
对题目所规定的最大数据规模进行测试，主要为了防止程序崩溃，一般不进行程序正确性检验。
（1）只有有限个读入数据：
直接输入大数据
（2）允许有重复数据的：
输入若干组后，利用复制/粘贴生成。
（3）不允许重复的，可利用小程序随机生成后写入到文件中。
六、常用错误代码含义：
（A）文件操作错误：
2：
文件末找到（常发生于.in文件未创建、或创建的文件夹不对）
102：
文件变量末赋值
103：
文件未打开
104：
文件未用读方式打开
105：
文件末用写方式打开
（B）运行时错误
200：
被零除
201：
范围检查错（跟踪检查数组下标）
202：
堆栈溢出错（常发生于递归层数过多）
（C）2、编译错误
下面列出在编译程序时可能出现的错误，在集成环境下，Pascal将自动加载源程序并定位于出错处。
1：
内存溢出
2：
缺标识符
3：
标识符未定义
4：
标识符重定义
5：
语法错误
6：
实型常量错
7：
整型常量错
8：
字符串常量跨行
9：
文件嵌套过多
10：
非正常文件结束
11：
行过长
12：
缺类型标识符
13：
打开文件过多
14：
无效文件名
15：
文件未找到
16：
磁盘满
17：
无效编译指示
18：
文件过多
19：
指针定义中未定义类型
20：
缺变量标识符
21：
类型错误
22：
结构过长
24：
文件分量不能为文件
25：
无效字符串长度
26：
类型不匹配
27：
无效子界基类型
28：
下界大于上界
29：
缺有序类型
30：
缺整型常数
31：
缺常数
32：
缺整型或实型常数
33：
缺指针类型标识符
34：
无效的函数结果类型
35：
缺标号标识符
36：
缺BEGIN
37：
缺END
38：
缺整型表达式
39：
缺有序表达式
40：
缺布尔表达式
41：
操作数类型与操作符不匹配
42：
表达式错
43：
非法赋值
44：
缺字段标识符
45：
目标文件过长
46：
未定义外部标识符
47：
无效*.OBJ文件记录
48：
代码段过长
49：
数据段过长
50：
缺DO
51：
无效PUBLIC定义
52：
无效EXTRN定义
53：
EXTRN定义过多
54：
缺0F
55：
缺INTERFACE
56：
无效重定位引用
57：
缺THEN
58：
缺T0或DOWNTO
59：
未定义的向前引用
60：
过程过多
61：
无效类型转换
62：
被零除D
63：
无效文件类型
64：
不能读写该类型的变量
65：
缺指针变量
66：
缺字符串变量
67：
缺字符串表达式
68：
单元循环引用
69：
单元名不匹配
70：
单元版本不匹配
71：
单元重名
72：
单元文件格式错误
73：
缺IMPLEMENTATl0N
74：
常数与CASE类型不相匹配
75：
缺记录变量
76：
常数越界
77：
缺文件变量
78：
缺指针变量
79：
缺整型或实型表达式
80：
标号不在当前块中
81：
标号已定义
82：
标号未定义
83：
无效参数
84：
缺UNIT
85：
缺“；”
86：
缺“：
”
87：
缺“，”
88：
缺“（”
89：
缺“）”
90：
缺“＝”
91：
缺“：
＝”
92：
缺“[”或“（．”
93：
缺“]”或“．）”
94：
缺“．”
96：
变量过多
97：
无效FOR控制变量
98：
缺整型变量
99：
此处不允许用文件
100：
字符串长度不匹配
101：
无效字顺序
102：
缺字符串常数
103：
缺整型或实型变量
104：
缺有序变量
105：
INLINE错
106：
缺字符表达式
107：
重定位项过多
112：
CASE常量越界
113：
语句错
114：
不能调用中断过程
116：
必须在8087方式下编译
117：
末找到目标地址
118：
此处不允许包含文件
120：
缺NIL
121：
无效限定符
122：
无效变量引用
123：
符号过多
124：
语句部分过长
126：
文件必须为变量参数
127：
条件符号过多
128：
条件指令错位
130：
初始条件定义错
13l：
过程和函数头与前面定义的不匹酉
132：
严重磁盘错误
133：
不能计算该表达式
134：
表达式错误结束
l35：
无效格式说明符
136：
无效间接引用
137：
此处不允许结构变量
138：
无SYSTEM单元不能计算
l39：
不能存取该符号
140：
无效浮点运算
141：
不能将覆盖编译至内存
142：
缺过程和函数变量
143：
无效过程或函数引用
144：
不能覆盖该单元
147：
缺对象类型
148：
不允许局部对象类型
149：
缺VIRTUAL
150：
缺方法标识符
151：
不允许虚拟构造方法
152：
缺构造方法标识符
153：
缺释放方法标识符
154：
FAIL只允许在构造方法内使用
155：
无效的操作符和操作数组合
156：
缺内存引用
l57：
不能加减可重定位符号
158：
无效寄存器组合
159：
未激活286／287指令
160：
无效符号引用
161：
代码生成错
162：
缺ASM
七、赛前记忆功能子程序：
1、基本数学类：
（1）两个变量交换数值：
procedureswap（a,b:
integer;varc,d:
integer）;
begin
c:
=b;d:
=a;
end;
（2）两组数据交换数值：
procedureswap（i,j:
integer;）;//传入两个数组的下标
vark,l:
integer;
begin
fork:
=1tondo
begin
l:
=a[i,k];a[i,k]:
=a[j,k];a[j,k]:
=l;
end;
end;
（3）求两数的最大值：
functionmax（a,b:
integer）:
integer;
begin
Ifa>bthenmax:
=aelsemax:
=b;
end;
（4）求一组数的最小值：
functionmin（a:
arr）ofinteger;
vari:
integer;
begin
min:
=maxint;
fori:
=1toa[0]do
ifmin>a[i]thenmin:
=a[i];
end;
（5）求两个数的最大公约数:
function gcd（a,b:
integer）:
integer;
begin
if b=0 then gcd:
=a
else gcd:
=gcd（b,a mod b）;
end ;
（6）判断一个数是否是素数
function prime （n:
integer）:
Boolean;
var i:
integer;
begin
for i:
=2 to trunc（sqrt（n）） do
if n mod i=0 then
begin
prime:
=false; exit;
end;
prime:
=true;
end;
（7）求出1~n范围内的所有素数（筛法求素数）
proceduregetprime（n:
longint;vara:
arr）;
vari,j,l:
longint;
t:
array[1..50000]ofboolean;
begin
fillchar（t,sizeof（t）,true）;
t[1]:
=false;i:
=2;
whileibegin
ifp[i]then
begin
j:
=i*2;
whilej=false;inc（j,i）;end;
end;
inc（i）;
end;
l:
=0;
fori:
=1tondo
ift[i]thenbegininc（l）;a[l]:
=i;end;
a[0]:
=l;
end;
（8）分解质因数
procedurezhiyinshu（m:
integer;vara:
arr）;
vari,p,k:
integer;
begin
p:
=0;i:
=2;
k:
=trunc（sqrt（m））;
while（m<>1）and（i<>k）do
begin
whilemmodi<>0doinc（i）;
whilemmodi=0do
begin
inc（p）;a[p]:
=i;m:
=mdivi;
end;
end;
ifm<>1then
begin
inc（p）;a[p]:
=m;
end;
a[0]:
=p;
end;
2、进位制转换：
（1）十进制转k进制:
/////////////////////////////////////////////////整数///////////////////////////////////////////////////////////////
proceduretrans_10_k（n,k:
longint;vara:
arr）;
vari:
longint;
begin
fillchar（a,sizeof（a）,0）;
whilen<>0do
begin
inc（a[0]）;a[a[0]]:
=nmodk;n:
=ndivk;
end;
Ifa[0]=0thena[0]:
=1;
end;
/////////////////////////////////////////////////小数///////////////////////////////////////////////////////////
proceduretrans_10_k（m:
real;l,k:
integer;vara:
arr）;//小数（l=16时相当于十进
//制的第5位）
begin
fillchar（a,sizeof（a）,0）;
while（m<>0）and（a[0]<=l）do
begin
m:
=m*k;inc（a[0]）;a[a[0]]:
=trunc（m）;m:
=m-a[a[0]];
end;
end;
（2）k进制转十进制:
//////////////////////////////////////////////////////整数////////////////////////////////////////////////////////
functiontrans_k_10（k:
integer;a:
arr）:
longint;
vari,j:
longint;
begin
j:
=1;trans_k_10:
=0;
fori:
=1toa[0]do
begin
trans_k_10:
=trans_k_10+a[i]*j;
j:
=j*k;
end;
end;
///////////////////////////////////////////////////小数////////////////////////////////////////////////////////
functiontrans_k_10（k:
integer;a:
arr）:
real;
varl:
real;
i:
integer;
begin
l:
=1;
fori:
=1toa[0]do
begin
l:
=l/k;trans_k_10:
=trans_k_10+a[i]*l;
end;
end;
（4）高精度数m进制转成高精度n进制:
procedurechu_m_n（a:
arr;m,n:
integer;varb:
arr;vary:
integer）;
vari:
integer;
begin
y:
=0;
fori:
=a[0]downto1do
begin
y:
=y*m+a[i];b[i]:
=ydivn;y:
=ymodn;
end;
b[0]:
=a[0];
whileb[b[0]]=0dodec（b[0]）;ifb[0]<1thenb[0]:
=1;
end;
////////////////////////////////////////////////////////////////////////////////////////////////////
proceduretrans_m_n（a:
arr;m,n:
integer;varb:
arr）;
vari,j,k:
integer;
begin
fillchar（b,sizeof（b）,0）;
whilenot（（a[0]=1）and（a[1]=0））do
begin
inc（b[0]）;chu_m_n（a,m,n,a,b[b[0]]）;
end;
end;
（5）2进制转换成2k进制（如：
8进制（k=3）、16进制（k=4））
proceduretrans_2_2k（a:
arr;k:
integer;varb:
arr）;
vari,j:
integer;
wq:
array[1..10]oflongint;
begin
wq[1]:
=1;fori:
=2tokdowq[i]:
=wq[i-1]*2;
fillchar（b,sizeof（b）,0）;
fori:
=1toa[0]divk+1do
forj:
=1tokdob[i]:
=b[i]+a[（i-1）*k+j]*wq[j];
b[0]:
=a[0]divk+1;
whileb[b[0]]=0dodec（b[0]）;ifb[0]<1thenb[0]:
=1;
end;
（6）2k进制转换成2进制：
proceduretrans_2k_2（a:
arr;k:
integer;varb:
arr）;
vari,j,l:
integer;
begin
fillchar（b,sizeof（b）,0）;l:
=0;
fori:
=1toa[0]do
forj:
=1tokdo
begin
b[（i-1）*k+j]:
=a[i]mod2;a[i]:
=a[i]div2;
end;
b[0]:
=a[0]*k;
whileb[b[0]]=0dodec（b[0]）;ifb[0]<1thenb[0]:
=1;
end;
3、高精度计算：
以下标程均为十进制，如改为10n进制可提高n倍速度。
（1）高精度数大小比较
functiona_dy_b（a,b:
arr）:
boolean;
vari:
integer;
begin
i:
=a[0];
ifa[0]<>b[0]thena_dy_b:
=a[0]>b[0]
elsebegin
while（a[i]=b[i]）and（i>0）dodec（i）;
a_dy_b:
=a[i]>b[i];
end;
end;
（2）高精度+低精度
procedureadd_h_l（a:
arr;b:
integer;varc:
arr）;
vari:
integer;
begin
a[1]:
=a[1]+b;
fori:
=1toa[0]do
begin
a[i+1]:
=a[i+1]+a[i]div10;
a[i]:
=a[i]mod10;
end;
c:
=a;
c[0]:
=max（c[0],19）;
whilec[c[0]]=0dodec（c[0]）
end;
（3）高精度+高精度
procedureadd_h_h（a,b:
arr;varc:
arr）;
vari,j:
integer;
begin
fillchar（c,sizeof（c）,0）;
ifa[0]>b[0]thenj:
=a[0]elsej:
=b[0];
fori:
=1tojdoc[i]:
=a[i]+b[i];
fori:
=1tojdo
begin
c[i+1]:
=c[i+1]+c[i]div10;
升级会员 