葫芦岛高中生李思洋编写的NOIP C++复习资料

NOIP

信息学奥赛

需积分: 9 39 浏览量更新于2024-07-09 收藏 5.66MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

《NOIP复习资料（C++）》是由葫芦岛市一高中学生李思洋编写的，专为准备参加NOIP（全国青少年信息学奥林匹克联赛）的学生设计。这本书旨在帮助OIer（算法竞赛爱好者）系统复习和巩固信息学基础知识，特别是C++编程技巧以及算法和数据结构。作者在2012年8月完成了初步版本，但由于时间紧迫和资源限制，存在不少错误和遗漏。该书的特点在于详实的笔记和经典算法集合，通过大量的代码示例来阐述理论知识。编者强调，尽管书中包含的内容相对全面，但它主要聚焦于NOIP复赛层面，因此对于初次接触NOIP或基础较弱的学生，可能需要先阅读附录E，了解比赛的基本概念和规则。为了有效学习，读者应具备一定的前提条件，例如： 1. 熟练掌握C++编程，或者至少能理解和应用C++到Pascal语言中的相应概念。 2. 具备阅读和理解代码的能力，能从代码中提取关键逻辑。 3. 对常见算法和数据结构有一定的了解，能理解相关概念。 4. 具备高中数学水平，包括算法、数列、计数原理和初步的数论知识。 5. 自主学习能力强，能独立解决问题和提升编程技能。此外，书中对代码中的变量约定也做了说明，如常数定义（N、M、MAX、INF）、数据规模的处理以及数组索引的边界问题。对于初赛知识的欠缺，作者建议在深入学习复赛内容之前先弥补基础，例如选择合适的C++教材，通常只需要阅读到“面向对象编程”章节的前一部分即可，因为NOIP比赛并不依赖高级特性，如图形用户界面。附录G提供了推荐的学习资源，包括书籍和在线平台，鼓励读者结合阅读和实践来提升自己的技能。第一单元则概述了竞赛中常见的操作和简单算法分析，为实际竞赛做准备。《NOIP复习资料（C++）》是一份实用的复习指南，旨在通过实战练习和理论讲解帮助学生提高信息学竞赛的竞争力，但同时也强调了自我学习和不断完善的必要性。

资源详情

资源推荐

第一单元 C++语言基础

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 命令或其他程序：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++语言基础

 sinh、cosh、tanh、asinh、acosh、atanh：双曲函数

 sqrt：求平方根

 ceil(x)、floor(x)：分别返回大于等于 x 的最小整数、小于等于 x 的最大整数。注意，参数和返

回值都是浮点数类型。

 exp(x)、log(x)、log10：分别求 e

、lnx、lgx

（顺便提一句，指数可以把加法问题转化为乘法问题，对数可以把乘法问题转化为加法问题。）

 pow(a,b)：计算 a

。由于精度问题，你仍然需要学会快速幂。

 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++语言基础

1.7 字符串操作!

头文件：<cstring>。printf 和 scanf 在<cstdio>中，cin 和 cout 在头文件<iostream>中且位于

std 命名空间内。

下面假设待处理的字符串为 str 和 str2，即：char str[MAX], str2[MAX];

牢记，字符串的最后一个字符一定是'\0'。如果字符串内没有'\0'，进行以下操作（输入除外）时可能

会造成意外事故。

1. 输出字符串 str：

 cout<<str;

 printf("%s",str); // 输出到文件：fprintf(fout, "%s", str);

2. 输入字符串 str：

 scanf("%s", str); // 输出到文件：fscanf(fin, "%s", str);

 cin>>str;

以上两种方法在输入时会忽略空格、回车、TAB 等字符，并且在一个或多个非空格字符后面输入空格

时，会终止输入。

 fgets(str, MAX, fin);

每调用一次，就会读取一行的内容（即不断读取，直到遇到回车停止）。

3. 求字符串 str 的长度：strlen(str) // 这个长度不包括末尾的'\0'。

4. 把字符串 str2 连接到字符串 str 的末尾：strcat(str, str2)

 str 的空间必须足够大，能够容纳连接之后的结果。

 连接的结果直接保存到 str 里。函数返回值为&str[0]。

 strncat(str, str2, n)是把 str2 的前 n 个字符连接到 str 的末尾。

5. 把字符串 str2 复制到字符串 str 中：strcpy(str, str2)

6. 比较 str 和 str2 的大小：strcmp(str, str2)

如果 str＞str2，返回 1；如果 str==str2，返回 0；如果 str＜str2，返回-1。

7. 在 str 中寻找一个字符 c：strchr(str, c)

返回值是一个指针，表示 c 在 str 中的位置。用 strchr 的返回值减 str，就是具体的索引位置。

8. 在 str 中寻找 str2：strstr(str, str2)

 返回值是一个指针，表示 str2 在 str 中的位置。用 strstr 的返回值减 str，就是具体的索引位置。

 此问题可以用 KMP 算法解决。KMP 算法很复杂，在 NOIP 范围内用途不大。

9. 从 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++语言基础

程序退出。这时不能再用 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，即 fprintf、fscanf、fgets，并且这些函数的第

一个参数不是格式字符串，而是 fin 或 fout，如 fprintf(fout, "%d", ans)。

 想改成从屏幕上输入/输出时，不用对代码动手术，只需把含 fopen 和 fclose 的代码注释掉，并改成：

fin=stdin; fout=stdout;

1.9 简单的算法分析和优化

(1) 复杂度

为了描述一个算法的优劣，我们引入算法时间复杂度和空间复杂度的概念。

时间复杂度：一个算法主要运算的次数，用大 O 表示。通常表示时间复杂度时，我们只保留数量级最大的

项，并忽略该项的系数。

例如某算法，赋值做了 3n

+8 次，则认为它的时间复杂度为 O(n

)；另一算法的主要运算是比较，做

了 4×2

+2n

+700 次，则认为它的时间复杂度为 O(2

)。

当然，如果有多个字母对算法的运行时间产生很大影响，就把它们都写进表达式。如对 m×n 的数组遍历

的时间复杂度可以写作 O(mn)。

空间复杂度：一个算法主要占用的内存空间，也用大 O 表示。

在实际应用时，空间的占用是需要特别注意的问题。太大的数组经常是开不出来的，即使开出来了，遍历

的时间消耗也是惊人的。

第一单元 C++语言基础

(2) 常用算法的时空复杂度

1s 运算次数约为 5,000,000

①

。也就是说，如果把 n 代入复杂度的表达式，得数接近或大于 5,000,000，

那么会有超时的危险。

常见的数量级大小：O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n

)＜O(n

)＜O(2

)＜O(n!)

数量级

能承受的大致规模

常见算法

O(1)

任意

直接输出结果

O(logn)

任意

二分查找、快速幂

O(n)

以百万计（五六百万）

贪心算法、扫描和遍历

O(nlogn)

以十万计（三四十万）

带有分治思想的算法，如二分法

O(n

)

以千计数（两千）

枚举、动态规划

O(n

)

不到两百

动态规划

O(2

)

搜索

O(n!)

产生全排列

O(n

)

暴力法破解密码

O(1)叫常数时间；O(n)、O(n

)、O(n

)……叫做多项式时间；O(2

)、O(3

)……叫做指数时间。

(3) 简单的优化方法

1. 时间的简单优化方法

时间上的优化在于少做运算、做耗时短的运算等。有几个规律需要注意：

 整型运算耗时远低于实型运算耗时。

 位运算速度极快。

 逻辑运算比四则运算快。

 +、-、*运算都比较快（-、*比+慢一点点，可以忽略不计）。

 /运算比+、-、*慢得多（甚至慢几十倍）。

 取余%和除法运算速度相当。

 调用函数要比直接计算慢（因为要入栈和出栈）。

这些规律我们可以从宏观上把握。事实上，究竟做了几步运算、几次赋值、变量在内存还是缓存等多数由

编译器、系统决定。但是，少做运算（尤其在循环体、递归体中）一定能很大程度节省时间。

2. 空间的简单优化方法

空间上的优化主要在于减小数组大小、降低数组维数等。常用的节省内存的方法有：

压缩储存——见 180 页“A.7 状态压缩*”。

覆盖旧数据——例如滚动数组（见 62 页“(5) 使用滚动数组”）。

要注意的是，对空间的优化即使不改变复杂度，只是改变 n 的系数也是极有意义的。空间复杂度有时对时

间也有影响，要想方设法进行优化。

3. 优化的原则

 尽量不让程序做已做过的事。

 不让程序做显然没有必要的事。

 不要解决无用的子问题。

 不要对结果进行无意义的引用。

①

不同资料给出的数值是不同的，不过这不要紧。在 NOIP 中，只要你的算法正确，就不会在运行时间上“打擦边球”。

剩余216页未读，继续阅读

hayzxjr

粉丝: 0
资源: 17

葫芦岛高中生李思洋编写的NOIP C++复习资料

⑦、NOIP刷题-2020.06.10.rar

CSP-J CSP-S NOIP 刷题（2020.02.01）.pdf

noip历年真题题解.pdf

2020年noip普及组c++初赛

noip历年真题 pdf

noip2009 c++试题

2020noip初赛普及组c++

全国信息学奥赛noip初赛复习

noip普及组初赛复习

noip竞赛学习材料清单

c++ noip 复赛 魔法阵

noip版codeblocks下载教程

NOIP2001-J2

NOIP普及组知识汇总

noip 竞赛知识点

noip 树基础知识

如何卸载dev c++

noip 1995年试题

高精度做P1009 [NOIP1998 普及组] 阶乘之和c++

Noip2015普及组题解:扫雷游戏(C++)\\\\

最新资源

c++ noip 复赛魔法阵