没有合适的资源?快使用搜索试试~ 我知道了~
首页NOIP复习资料:算法与习题集锦
NOIP复习资料:算法与习题集锦
5星 · 超过95%的资源 需积分: 9 9 下载量 183 浏览量
更新于2024-07-18
1
收藏 1.61MB PDF 举报
"NOIP复习资料,包含经典算法和习题,旨在帮助自学竞赛知识" 《NOIP复习资料》是一份由葫芦岛市一高中学生李思洋编写的备考指南,专注于全国信息学奥林匹克竞赛(NOIP)的复习。这份资料不仅整理了作者的学习笔记,还收集了一些经典的算法和习题,旨在帮助那些没有竞赛班和专业指导的自学群体。书中内容以C++为主,但也适用于熟悉C语言的读者。 前言部分强调了资料的修订历程和目的。作者在最初的整理基础上,经过多次修订,力求完善内容,以便分享给同校同学,共同提升竞赛水平。资料虽然详尽,但作者也提醒读者,其所涵盖的知识仅仅是信息学领域的基础,真正的学习之路还很长。 在编写资料时,作者设定了一些基本假设,期望读者已经具备一定的C++编程能力,能理解和应用代码,对算法和数据结构有初步认知,并掌握高中数学的相关知识,包括算法、数列、计数原理以及初等数论。此外,自学能力也被视为必备条件。 在代码约定方面,书中提到一些常见的常量,如N、M、MAX和INF,它们分别代表不同规模的数据或非常大的数值。作者提醒读者注意数组下标可能的不同起始值,以避免在阅读程序时产生误解。 对于新接触NOIP的读者,作者建议先阅读附录E以了解竞赛的基本情况。如果初赛知识欠缺,应首先补习这部分内容。若无C++基础,需要先学习入门教程,通常到“面向对象编程”章节前一页即可满足NOIP的需求。附录G则推荐了一些书籍和网站,供读者进一步深入学习和实践。 第一单元将涵盖竞赛中常用的操作和概念,可能是数据结构、算法基础等内容,这部分是解决NOIP竞赛问题的关键。通过这份复习资料,读者可以系统性地学习和准备信息学竞赛,提升解决问题的能力。
资源详情
资源推荐
第一单元 C++ 语言基础
11
max(a,b)
返回
a
和
b
中的最小值,
min(a,b)
返回
a
和
b
中的最大值。
其实我们可以自己写:
4.
交换变量的值 :
swap(a,b)
头文件:
<algorithm>
其实我们可以自己写:
inline void swap(int &a, int &b) { int t=a; a=b; b=t; }
5.
执行
DOS
DOS
DOS
DOS
命令或其他程序 :
system("
命令行
");
�
头文件:
<cstdlib>
�
暂停屏幕:
system("pause");
�
竞赛交卷或
OJ
提交代码之前必须删除
system
, 否则会被视为作弊 ( 如果是
tyvj
甚至都无法提交 ) 。
� 如果使用输入重定向,那么命令提示符不会接受任何键盘输入 —— 直接用文件内容代替键盘了。
6.
立刻退出程序 :
exit(0);
这种方法常用于深度优先搜索。执行后,程序立刻停止并返回
0
,所以在调用前应该输出计算结果。
头文件:
<cstdlib>
7.
计时 :
double a = (double)clock() / (double)CLOCKS_PER_SEC;
上面的
a
对应一个时刻。而将两个时刻相减,就是时间间隔。可用这种方法卡时。
头文件:
<ctime>
8.
断言 :
assert(
条件
)
� 条件为假时,程序立刻崩溃。
�
头文件:
<cassert>
�
如果定义了
NDEBUG
符号,那么它将不会起任何作用。
� 断言和错误处理不同:例如出现 “ 人数为负数 ” 的情况,如果责任在于用户,那么应该提示错误并重
新输入 , 而不是用断言 ; 如果发生在计算过程 , 应该用断言来使程序崩溃 , 以帮助改正代码中的错误 。
换句话说,错误处理防的是用户的错误,断言防的是代码的错误。
9.
快速排序 :
qsort(
首项的指针
,
待排序元素个数
,
每个元素所占字节
,
比较函数
)
�
头文件:
<cstdlib>
�
这是留给
C
党的快速排序,它比
STL
的排序算法啰嗦一些。
�
比较函数返回
int
类型,用于对两个元素的比较。原型如下:
int compare(const void *i, const void *j);
如果
*i
<
*j
,则应返回一个小于
0
的数;如果
*i==*j
则应返回
0
,否则返回一个大于
0
的数。
10. 随机数发生器 :
�
头文件:
<cstdlib>
� 产生随机数:
①
0~32767
的随机数:
rand()
② 粗略地控制范围:
rand()%
范围
注意,这种方法产生的随机数的分布是不均匀的。
③ 精确地控制范围:
(double)rand()/RAND_MAX*
范围
④ 控 制在
[a, b)
之间:
a + (int) ( (double)rand()/RAND_MAX*(b-a) )
� 初始化随机数种子:
①
srand(
数字
)
:初始化随机数种子。
② 注意 , 这条语句在程序开头使用 , 并且最多用一次 。 同一程序 、 同一平台 ,
srand
中的参数相等
,
用
rand()
产生的随机数序列相同。
③ 使随机数更加随机:引用
<ctime>
,然后这样初始化随机数种子,
srand(time(NULL))
。
不要在循环中使用这条语句(例如批量产生随机数据),因为
time
只精确到秒。
11. 数学函数 :
�
头文件:
<cmath>
� abs(x)
:求
x
的绝对值(该函数同时包含于
<cstdlib>
)。
� sin
、
cos
、
tan
、
asin
、
acos
、
atan
:三角函数,角的单位为弧度。
可用
atan(1)*4
表示
π
。
第一单元 C++ 语言基础
12
� sinh
、
cosh
、
tanh
、
asinh
、
acosh
、
atanh
:双曲函数
� sqrt
:求平方根
� ceil(x)
、
floor(x)
:分别返回大于等于
x
的最小整数、小于等于
x
的最大整数。注意,参数和返
回值都是浮点数类型。
� exp(x)
、
log(x)
、
log10
:分别求
e
x
、
ln
x
、
lg
x
( 顺便提一句,指数可以把加法问题转化为乘法问题,对数可以把乘法问题转化为加法问题。 )
� pow(a,b)
:计算
a
b
。由于精度问题,你仍然需要学会快速幂。
� fmod(a,b)
:计算
a
除以
b
的余数。当然,这是浮点数的版本。
( 2 ) 宏定义
宏定义是
C
语言的产物。在
C++
中,它真的
out
了。
1.
第一种用法 —— 配合条件编译 :
#define DEBUG
定义一个叫
DEBUG
的标识符。它应该与
#ifdef
或
#ifndef
配合使用。举例如下:
#define DEBUG
#ifdef DEBUG
void print(int v) { cout << v << endl;}
#else
void print(int) {}
#endif
如果符号
DEBUG
存在,那么编译器会编译上面的、能输出数值的
print
,否则编译器编译下面的、什么
事情都不做的
print
。
把上面的
#ifdef
换成
#ifndef
,那么编译的代码正好上面所说的相反。
2. 第二种用法 —— 表达式 :
#define N 5000
编译时,编译器会用类似于 “ 查找和替换 ” 的方法,把代码中的
N
换成
5000
。如果需要换成表达式,应
该用括号把它们包围。例如 :
#define a 1+2
#define b (1+2)
c=a*2; d=b*2;
编译时上面一行会变成 “
c=1+2*2; d=(1+2)*1;
” ,显然它们的值是不同的。
所以,用
enum
和
const
代替它是明智之举。
此外,要注意表达式末尾不能有分号 (除非你需要) 。
3. 第三种用法 —— 简易 “ 函数 ” :
#define FtoC (a) (((a)-32)/9*5)
这类似于一个函数 。 不过 , 由于编译器只是进行简单替换 , 所以为了安全 ,
a
、
b
应该用括号包围 , 整个表
达式也应该用括号包围。
这种 “ 函数 ” 用法和普通函数一样,且速度更快。然而,它很容易出现难以查出的错误。所以,请用内联
函数(
inline
)代替宏定义。
注意, 不要在 “ 参数 ” 中改变变量的值 !
4. 第四种用法 —— 简化一段代码 :
# define move(dx, dy) if (isfull(dir)) return; \
if (map(x+dx, y+dy)=='0') \
{ \
push(dir,x+dx,y+dy,head[dir], dep); \
check(dir); \
}
不要忘记每行后面的 “
\
” ,它相当于换行符。这次
move
简化了一大段代码。同样,内联函数也可以。
第一单元 C++ 语言基础
13
1 . 7 字符串操作 !
头文件 :
<cstring>
。
printf
和
scanf
在
<cstdio>
中 ,
cin
和
cout
在头文件
<iostream>
中且位 于
std
命名空间内。
下面假设待处理的字符串为
str
和
str2
,即:
char str[MAX], str2[MAX];
牢记, 字符串的最后一个字符一定是
'\0'
'\0'
'\0'
'\0'
。如果字符串内没有
'\0'
,进行以下操作 (输入除外) 时可能
会造成意外事故。
1.
输出字符串
str
str
str
str
:
� cout<<str;
� printf("%s",str); //
输出到文件:
fprintf(fout, "%s", str);
2.
输入字符串
str
str
str
str
:
� scanf("%s", str); //
输出到文件:
fscanf(fin, "%s", str);
� cin>>str;
以上两种方法在输入时会忽略空格 、 回车 、
TAB
等字符 , 并且在一个或多个非空格字符后面输入空格
时,会终止输入。
� fgets(str, MAX, fin);
每调用一次,就会读取一行的内容 (即不断读取,直到遇到回车停止) 。
3.
求字符串
str
str
str
str
的长度 :
strlen(str) //
这个长度不包括末尾的
'\0'
。
4.
把字符串
str2
str2
str2
str2
连接到字符串
str
str
str
str
的末尾 :
strcat(str, str2)
� str
的空间必须足够大,能够容纳连接之后的结果。
�
连接的结果直接保存到
str
里。函数返回值为
&str[0]
。
� strncat(str, str2, n)
是把
str2
的前
n
个字符连接到
str
的末尾。
5.
把字符串
str2
str2
str2
str2
复制到字符串
str
str
str
str
中:
strcpy(str, str2)
6.
比较
str
str
str
str
和
str2
str2
str2
str2
的大小:
strcmp(str, str2)
如果
str
>
str2
,返回
1
;如果
str==str2
,返回
0
;如果
str
<
str2
,返回
-1
。
7.
在
str
str
str
str
中寻找一个字符
c
c
c
c
:
strchr(str, c)
返回值是一个指针,表示
c
在
str
中的位置。用
strchr
的返回值减
str
,就是具体的索引位置。
8.
在
str
str
str
str
中寻找
str2
str2
str2
str2
:
strstr(str, str2)
�
返回值是一个指针 , 表示
str2
在
str
中的位置 。 用
strstr
的返回值减
str
, 就是具体的索引位置 。
�
此问题可以用
KMP
算法解决。
KMP
算法很复杂,在
NOIP
范围内用途不大。
9.
从
str
str
str
str
中获取数据 :
sscanf(str, "%d", &i);
格式化字符串 :
sprintf(str, "%d", i);
它们和
fscanf
、
fprintf
非常像,用法也类似。可以通过这两个函数进行数值与字符串之间的转换。
1 . 8 文件操作 !
正式竞赛时 , 数据都从扩展名为 “
in
” 的文件读入 , 并且需要你把结果输出到扩展名为 “
out
” 的文件中
;
在
OJ
(
Online Judge
,在线测评器)中则不需要文件操作。具体情况要仔细查看题目说明,以免发生悲剧 。
( 1 ) 输入 / 输出重定向
头文件:
< fstream >
或
< cstdio >
� 方法:只需在操作文件之前添加以下两行代码。
freopen("XXXXX.in","r",stdin);
freopen("XXXXX.out","w",stdout);
�
调用两次
freopen
后,
scanf
、
printf
、
cin
、
cout
的用法完全不变,只是操作对象由屏幕变成了指
定的文件。
�
使用输入重定向之后 , “ 命令提示符 ” 窗口将不再接受任何键盘输入 ( 调用
system
时也是如此 ) , 直到
第一单元 C++ 语言基础
14
程序退出。这时不能再用
system("pause")
暂停屏幕。
( 2 ) 文件流
头文件:
<fstream>
流的速度比较慢,在输入
/
输出大量数据的时候,要使用其他文件操作方法。
� 方法:定义两个全局变量。
ifstream fin("XXXXX.in");
ofstream fout("XXXXX.out");
� fin
、
fout
和
cin
、
cout
一样,也用 “
<<
” 、 “
>>
” 运算符输入
/
输出,如:
fin>>a; fout<<b;
当然,也可以通过
#define
把
fin
、
fout
变成
cin
、
cout
:
#define cin fin
#define cout fout
( 3 ) FILE 指针
头文件:
<cstdio>
或
<fstream>
� 方法:定义两个指针。
FILE *fin, *fout;
……
int main()
{
fin = fopen("XXXXX.in", "r");
fout = fopen("XXXXX.out", "w");
......
fclose(fin); fclose(fout); //
在某些情况下,忘记关闭文件会被认为是没有产生文件。
return 0;
}
�
进行输入
/
输出操作时,要注意 函数名的前面有
f
f
f
f
,即
fprintf
、
fscanf
、
fgets
,并且这些函数的第
一个参数不是格式字符串,而是
fin
或
fout
,如
fprintf( fout
fout
fout
fout , "%d", ans)
。
�
想改成从屏幕上输入
/
输出时,不用对代码动手术,只需把含
fopen
和
fclose
的代码注释掉,并改成 :
fin=stdin; fout=stdout;
1 . 9 简单的算法分析和优化
( 1 ) 复杂度
为了描述一个算法的优劣,我们引入算法时间复杂度和空间复杂度的概念。
时间复杂度 : 一个算法主要运算的次数 , 用大
O
表示 。 通常表示时间复杂度时 , 我们只保留数量级最大的
项,并忽略该项的系数。
例如某算法,赋值做了
3
n
3
+
n
2
+8
次,则认为它的时间复杂度为
O(
n
3
)
;另一算法的主要运算是比较,做
了
4
×
2
n
+2
n
4
+700
次,则认为它的时间复杂度为
O(2
n
)
。
当然,如果有多个字母对算法的运行时间产生很大影响,就把它们都写进表达式。如对
m
×
n
的数组遍历
的时间复杂度可以写作
O(
mn
)
。
空间复杂度 :一个算法主要占用的内存空间,也用大
O
表示。
在实际应用时,空间的占用是需要特别注意的问题。太大的数组经常是开不出来的,即使开出来了,遍历
的时间消耗也是惊人的。
第一单元 C++ 语言基础
15
( 2 ) 常用算法的时空复杂度
1s
运算次数约为
5,000,000
①
。 也就是说 , 如果把
n
代入复杂度的表达式 , 得数接近或大于
5,000,000
,
那么会有超时的危险。
常见的数量级大小 :
O(1)
<
O(log
n
)
<
O(
n
)
<
O(
n
log
n
)
<
O(
n
2
)
<
O(
n
3
)
<
O(2
n
)
<
O(
n
!)
数量级 能承受的大致规模 常见算法
O(1)
任意 直接输出结果
O(log
n
)
任意 二分查找、快速幂
O(
n
)
以百万计 (五六百万) 贪心算法、扫描和遍历
O(
n
log
n
)
以十万计 (三四十万) 带有分治思想的算法,如二分法
O(
n
2
)
以千计数 (两千) 枚举、动态规划
O(
n
3
)
不到两百 动态规划
O(2
n
)
24
搜索
O(
n
!)
10
产生全排列
O(
n
n
)
8
暴力法破解密码
O(1) 叫常数时间 ; O(
n
) 、 O(
n
2
) 、 O(
n
3
) 、 O(
n
4
) …… 叫做多项式时间 ; O(2
n
) 、 O(3
n
) …… 叫做指数时间 。
( 3 ) 简单的优化方法
1.
1.
1.
1. 时间的简单优化方法
时间上的优化在于少做运算、做耗时短的运算等。有几个规律需要注意:
� 整型运算耗时远低于实型运算耗时。
� 位运算速度极快。
� 逻辑运算比四则运算快。
� + 、 - 、 * 运算都比较快 ( - 、 * 比 + 慢一点点,可以忽略不计) 。
� / 运算比 + 、 - 、 * 慢得多 (甚至慢几十倍) 。
� 取余 % 和除法运算速度相当。
� 调用函数要比直接计算慢 (因为要入栈和出栈) 。
这些规律我们可以从宏观上把握。事实上,究竟做了几步运算、几次赋值、变量在内存还是缓存等多数由
编译器、系统决定。但是,少做运算 (尤其在循环体、递归体中) 一定能很大程度节省时间。
2.
2.
2.
2. 空间的简单优化方法
空间上的优化主要在于减小数组大小、降低数组维数等。常用的节省内存的方法有:
压缩储存 —— 见 180 页 “ A . 7 状态压缩 * ” 。
覆盖旧数据 —— 例如滚动数组 (见 62 页 “ ( 5 ) 使用滚动数组 ” ) 。
要注意的是,对空间的优化即使不改变复杂度,只是改变
n
的系数也是极有意义的。空间复杂度有时对时
间也有影响,要想方设法进行优化。
3.
3.
3.
3. 优化的原则
� 尽量不让程序做已做过的事。
� 不让程序做显然没有必要的事。
� 不要解决无用的子问题。
� 不要对结果进行无意义的引用。
①
不同资料给出的数值是不同的,不过这不要紧。在 NOIP 中,只要你的算法正确,就不会在运行时间上 “ 打擦边球 ” 。
剩余219页未读,继续阅读
「已注销」
- 粉丝: 4
- 资源: 14
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 新型矿用本安直流稳压电源设计:双重保护电路
- 煤矿掘进工作面安全因素研究:结构方程模型
- 利用同位素位移探测原子内部新型力
- 钻锚机钻臂动力学仿真分析与优化
- 钻孔成像技术在巷道松动圈检测与支护设计中的应用
- 极化与非极化ep碰撞中J/ψ的Sivers与cos2φ效应:理论分析与COMPASS验证
- 新疆矿区1200m深孔钻探关键技术与实践
- 建筑行业事故预防:综合动态事故致因理论的应用
- 北斗卫星监测系统在电网塔形实时监控中的应用
- 煤层气羽状水平井数值模拟:交替隐式算法的应用
- 开放字符串T对偶与双空间坐标变换
- 煤矿瓦斯抽采半径测定新方法——瓦斯储量法
- 大倾角大采高工作面设备稳定与安全控制关键技术
- 超标违规背景下的热波动影响分析
- 中国煤矿选煤设计进展与挑战:历史、现状与未来发展
- 反演技术与RBF神经网络在移动机器人控制中的应用
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功