2023年7月30日发(作者：)
资料收集于网络，如有侵权 请联系网站删除
NOIP 主 编
完成日期
只供学习与交流
C++版）
葫芦岛市一高中 李思洋
2012年8月27日
复习资料
（资料收集于网络，如有侵权 请联系网站删除
前 言
有一天，我整理了NOIP的笔记，并收集了一些经典算法。不过我感觉到笔记比较凌乱，并且有很多需要修改和补充的内容，于是我又搜集一些资料，包括一些经典习题，在几个月的时间内编写出了《NOIP复习资料》。
由于急于在假期之前打印出来并分发给同校同学（我们学校既没有竞赛班，又没有懂竞赛的老师。我们大家都是自学党），《NOIP复习资料》有很多的错误，还有一些想收录而未收录的内容。
在“减负”的背景下，暑期放了四十多天的假。于是我又有机会认真地修订《NOIP复习资料》。
我编写资料的目的有两个：总结我学过（包括没学会）的算法、数据结构等知识；与同学共享NOIP知识，同时使我和大家的RP++。
大家要清醒地认识到，《NOIP复习资料》页数多，是因为程序代码占了很大篇幅。这里的内容只是信息学的皮毛。对于我们来说，未来学习的路还很漫长。
基本假设
作为自学党，大家应该具有以下知识和能力：
① 能够熟练地运用C++语言编写程序（或熟练地把C++语言“翻译”成Pascal语言）；
② 能够阅读代码，理解代码含义，并尝试运用；
③ 对各种算法和数据结构有一定了解，熟悉相关的概念；
④ 学习了高中数学的算法、数列、计数原理，对初等数论有一些了解；
⑤ 有较强的自学能力。
代码约定
N、M、MAX、INF是事先定义好的常数（不会在代码中再次定义，除非代码是完整的程序）。N、M、MAX针对数据规模而言，比实际最大数据规模大；INF针对取值而言，是一个非常大，但又与int的最大值有一定差距的数，如100000000。
对于不同程序，数组下标的下限也是不同的，有的程序是0，有的程序是1。阅读程序时要注意。
阅读顺序和方法
没听说过NOIP，或对NOIP不甚了解的同学，应该先阅读附录E，以加强对竞赛的了解。
如果不能顺利通过初赛，你就应该先补习初赛知识。这本《NOIP复习资料》总结的是复赛知识。
如果没有学过C++语言，应该先选择一本C++语言教材。一般情况下，看到“面向对象编程”一章的前一页就足够了（NOIP不用“面向对象编程”，更不用摆弄窗口对话框）。
附录G介绍了一些书籍和网站。你应该选择一本书，认真地学习。再选择一个网站，作为练习的题库。
第一单元对竞赛中常用的操作和简单的算法分析进行了总结，算作对C++语言的巩固。同时，阅读这一单元之后，你应该选择一个合适的C++代码编辑器。
第二到第六单元介绍了竞赛常用的算法。阅读每一章时，应该先阅读“小结”——名曰“小结”，实际上是“导读”。
这五个单元除了经典习题，还有某些思想和算法的具体实现方法。这些信息可能在明处，也可能在暗处，阅读时要注意挖掘和体会。如果有时间，应该在不看解析和代码的前提下独立完成这些题。
只供学习与交流 资料收集于网络，如有侵权 请联系网站删除
第七单元是第六单元的一个部分，由于它的内容来自《背包九讲》，所以单独放在一个单元。
从第八单元开始，到第十三单元，基本上就没有习题了。换句话说，该“背课文”了。
第八单元介绍了常用的排序算法。你可以有选择地学习，但一定要掌握“STL算法”和“快速排序”。
第九单元介绍了基本数据结构，你一定要掌握第九单元前五小节的内容（本单元也有应该优先阅读的“小结”）。有余力的话，第六小节的并查集也应该掌握。
第十单元介绍了与查找、检索有关的数据结构和算法。你也可以有选择地学习。
第十一单元与数学有关。数学对于信息学来说具有举足轻重的地位。标有“！”的应该背下来，至于其他内容，如果出题，你应该能把它解决。
第十二单元仍与数学有关。
第十三单元是图论。学习时要先阅读“小结”，把概念弄清楚。之后要掌握图的实现方法。接下来要掌握一些经典图论算法：Kruskal算法、Dijkstra算法、SPFA、Floyd算法、拓扑排序。
附录F总结了2004年以来NOIP考察的知识点，可以作为选择性学习的参考。
在学习算法和数据结构的同时，应该阅读和学习附录A。
如果你还有余力，你应该学习第十四单元。第十四单元的内容不是必须要掌握的，但是一旦学会，可以发挥C++语言的优势，降低编程复杂度。
临近竞赛时，应该阅读附录B和附录C，以增加经验，减少失误。
面临的问题
1. 这是复赛复习资料——需要有人能用心总结、整理初赛的知识，就像这份资料一样。
2. 潜在的问题还是相当多的，只是时间不够长，问题尚未暴露。
3. 部分代码缺少解说，或解说混乱。
4. 个人语文水平较差，《资料》也是如此。
5. 没有对应的Pascal语言版本。
如果有人能为P党写一个Pascal版的STL，他的RP一定会爆增！
ATX整理《资料》，并以自由文档形式发布。
6. 希望有人能用 LE
最后，欢迎大家以交流、分享和提高为目的修改、复制、分发本《资料》，同时欢迎大家将《资料》翻译成Pascal语言版供更多OIer阅读！
谢谢大家的支持！
葫芦岛市一高中 李思洋
2012年8月27日
只供学习与交流 资料收集于网络，如有侵权 请联系网站删除
目 录
标题上的符号：
1. !：表示读者应该熟练掌握这些内容，并且在竞赛时能很快地写出来。换句话说就是应该背下来。
2. *：表示内容在NOIP中很少涉及，或者不完全适合NOIP的难度。
3. #：表示代码存在未更正的错误，或算法本身存在缺陷。
前
言 ........................... 1
目
录 ........................... I
.............. 1
第一单元
C++语言基础
................ 55
第五单元 分治算法
5.1 一元三次方程求解 .............. 55
5.2 快速幂 ...................... 55
1.1 程序结构 ...................... 1
1.2 数据类型 ...................... 4
1.3 运算符 ........................ 7
1.4 函数 .......................... 9
1.5 输入和输出! ................... 10
1.6 其他常用操作! ................. 11
1.7 字符串操作! ................... 13
1.8 文件操作! .................... 14
1.9 简单的算法分析和优化 ........... 15
1.10 代码编辑器 ................... 17
第二单元 基础算法. ............... 18
2.1 经典枚举问题 .................. 18
2.2 火柴棒等式 .................... 19
2.3 梵塔问题 ..................... 20
2.4 斐波那契数列 .................. 20
2.5 常见的递推关系! ............... 21
2.6 选择客栈 ..................... 23
2.7 2k进制数 ..................... 25
2.8 Healthy Holsteins ........... 25
2.9 小结 ......................... 27
第三单元 搜索 ................... 29
3.1 N皇后问题 .................... 29
3.2 走迷宫 ....................... 31
3.3 8数码问题 .................... 33
3.4 埃及分数 ..................... 36
3.5 Mayan游戏 ................... 38
3.6 预处理和优化 .................. 42
3.7 代码模板 ..................... 44
3.8 搜索题的一些调试技巧 ........... 46
3.9 小结 ......................... 46
第四单元 贪心算法. ............... 49
4.1 装载问题 ..................... 49
4.2 区间问题 ..................... 49
4.3 删数问题 ..................... 50
4.4 工序问题 ..................... 50
4.5 种树问题 ..................... 50
4.6 马的哈密尔顿链 ................ 51
4.7 三值的排序 .................... 52
4.8 田忌赛马 ..................... 53
4.9 小结 ......................... 54
只供学习与交流
5.3 排序 ........................ 55
5.4 最长非降子序列 ................ 57
5.5 循环赛日程表问题 .............. 57
5.6 棋盘覆盖..................... 58
5.7 删除多余括号 ................. 59
5.8 聪明的质监员 ................. 61
5.9 模板 ........................ 62
5.10 小结 ....................... 63
第六单元 动态规划 ................ 64
6.1 导例：数字三角形 .............. 64
6.2 区间问题：石子合并 ............ 67
6.3 坐标问题..................... 69
6.4 背包问题..................... 71
6.5 编号问题..................... 72
6.6 递归结构问题 ................. 73
6.7 DAG上的最短路径 .............. 75
6.8 树形动态规划* ................ 76
6.9 状态压缩类问题：过河 ........... 79
6.10 Bitonic旅行 ............... 80
6.11 小结 ....................... 81
第七单元 背包专题 ................ 83
7.1 部分背包问题 ................. 83
7.2 0/1背包问题! ................ 83
7.3 完全背包问题 ................. 84
7.4 多重背包问题 ................. 84
7.5 二维费用的背包问题 ............ 85
7.6 分组的背包问题 ................ 86
7.7 有依赖的背包问题 .............. 86
7.8 泛化物品..................... 86
7.9 混合背包问题 ................. 87
7.10 特殊要求.................... 87
7.11 背包问题的搜索解法 ........... 89
7.12 子集和问题 .................. 89
第八单元 排序算法 ................ 91
8.1 常用排序算法 ................. 91
8.2 简单排序算法 ................. 93
8.3 线性时间排序 ................. 94
8.4 使用二叉树的排序算法* .......... 95
8.5 小结 ........................ 96
第九单元 基本数据结构 ............ 97 资料收集于网络，如有侵权 请联系网站删除
9.1 线性表（顺序结构） ............. 97
9.2 线性表（链式结构） ............. 97
9.3 栈 .......................... 99
9.4 队列 ........................ 100
9.5 二叉树 ...................... 101
9.6 并查集! ..................... 105
9.7 小结 ........................ 108
第十单元 查找与检索 ............. 111
10.1 顺序查找 ................... 111
10.2 二分查找! .................. 111
10.3 查找第k小元素! ............. 112
10.4 二叉排序树 .................. 113
10.5 堆和优先队列* ............... 115
10.6 哈夫曼（Huffman）树 ......... 117
10.7 哈希（Hash）表 .............. 119
第十一单元 数学基础 ............. 124
11.1 组合数学 ................... 124
11.2 组合数的计算! ............... 125
11.3 排列和组合的产生（无重集元素）! 125
11.4 排列和组合的产生（有重集元素） . 128
11.5 秦九韶算法 .................. 130
11.6 进制转换（正整数） ........... 131
11.7 高精度算法（压位存储）! ....... 131
11.8 快速幂! .................... 136
11.9 表达式求值 .................. 137
11.10 解线性方程组* .............. 141
第十二单元 数论算法 ............. 144
12.1 同余的性质! ................. 144
12.2 最大公约数、最小公倍数! ....... 144
12.3 解不定方程ax＋by＝c!* ....... 144
12.4 同余问题* .................. 145
12.5 素数和素数表 ................ 145
12.6 分解质因数 .................. 146
第十三单元 图与图论算法. ......... 149
13.1 图的实现 ................... 149
13.2 图的遍历 ................... 151
13.3 连通性问题 .................. 152
13.4 欧拉回路 [邻接矩阵] ......... 156
13.5 最小生成树（MST） ........... 157
13.6 单源最短路问题（SSSP问题） ... 159
13.7 每两点间最短路问题（APSP问题）!162
13.8 拓扑排序 ................... 163
13.9 关键路径 ................... 165
13.10 二分图初步 ................. 168
13.11 小结 ...................... 171
第十四单元 STL简介 ............. 175
14.1 STL概述 ................... 175
14.2 常用容器 ................... 175
14.3 容器适配器 .................. 181
14.4 常用算法 ................... 182
14.5 迭代器 ..................... 186
只供学习与交流
14.6 示例：合并果子 .............. 187
附录A 思想和技巧 ............... 189
A.1 时间/空间权衡 ............... 189
A.2 试验、猜想及归纳 ............. 189
A.3 模型化 ..................... 189
A.4 随机化* .................... 190
A.5 动态化静态 .................. 190
A.6 前序和! .................... 191
A.7 状态压缩*................... 192
A.8 抽样测试法* ................. 194
A.9 离散化* .................... 195
A.10 Flood Fill* .............. 196
附录B 调试 .................... 198
B.1 常见错误类型 ................ 198
B.2 调试过程.................... 198
B.3 调试功能.................... 198
B.4 符号DEBUG的应用 ............ 199
B.5 代码审查表 .................. 200
B.6 故障检查表 .................. 201
B.7 命令行和批处理* .............. 201
附录C 竞赛经验和教训 ............ 205
C.1 赛前两星期 .................. 205
C.2 赛前30分钟 ................. 205
C.3 解题表 ..................... 206
C.4 测试数据.................... 209
C.5 交卷前5分钟 ................ 209
C.6 避免偶然错误 ................ 210
C.7 骗分 ....................... 211
附录D 学习建议 ................. 212
D.1 学习方法.................... 212
D.2 学习能力.................... 212
D.3 关于清北学堂 ................ 212
附录E 竞赛简介 ................. 214
E.1 从NOIP到IOI ............... 214
E.2 NOIP简介 .................. 214
E.3 常用语 ..................... 217
E.4 第一次参加复赛…… ........... 218
附录F
NOIP复赛知识点分布 ....... 220
附录G 资料推荐 ................. 222
G.1 书籍 ....................... 222
G.2 网站 ....................... 222
参考文献 ....................... 223
计算机专业是朝阳还是夕阳？ ........ 224
杜子德在CCF NOI2012开幕式上的讲话 226
多数奥赛金牌得主为何难成大器 ...... 228
资料收集于网络，如有侵权 请联系网站删除
第一单元 C++语言基础
1.1 程序结构
(1) 程序框架
注释：注释有两种，一种是“//”，另一种是“/* … */”。“//”必须单独放置一行，或代码所在行的后面；而“/*”、“*/”成对存在，可以插入到代码的任意位置。
引用头文件：在代码开头写“#include <头文件名>”。如果想引用自己的头文件，需要把尖括号（表示只从系统目录搜索头文件）换成双引号（表示先从cpp所在文件夹搜索，然后再到系统文件夹搜索）。
命名空间：很多C++的东西都要引用std命名空间，所以代码中会有“using namespace std;”。
main()：所有程序都要从main()开始。
在所有的算法竞赛中，main()的返回值必须是0，否则视为程序异常结束，得分为0分。
语句和语句块：
1. 语句：一般情况下，一条语句要用一个分号“;”结束。为了美观和可读性，可以把一条语句扩展成几行，也可以把多个语句写到同一行上。
2. 语句块：用“{”和“}”包围的代码是语句块。无论里面有多少代码，在原则上，语句块所在的整体都视为一条语句。
(2) 选择结构
1. if语句：if表示判断。如果条件为真，就执行接在if后的语句（语句块），否则执行else后的语句（语句块）。如果没有else，就直接跳过。if有以下几种格式：
if (条件)
语句或语句块
// 如果条件成立，就执行if后面的语句或语句块。
if (条件) // 如果条件成立，就执行if后面的A，否则执行B。
语句或语句块A
else
语句或语句块B
if (条件1) // 实际上，这是if语句内的if语句，即if的嵌套。所以else和if中间要有空格。
语句或语句块A
else if (条件2)
语句或语句块B
……
else
语句或语句块N
2. switch语句：switch表示选择。它根据条件的不同取值来执行不同的语句。格式如下：
switch (表达式)
{
case 值1:
代码段A
只供学习与交流 资料收集于网络，如有侵权 请联系网站删除
break;
case 值2:
代码段B
break;
……
default:
代码段N
break;
};
如果表达式的值是值1，就执行代码段A；如果表达式的值是值2，就执行代码段B……否则执行代码段N。
注意：
default一部分可以省略。
如果不使用break，那么紧随其后的case部分代码也会被执行，直到遇到break或switch语句结束为止！
switch结尾要有一个分号。
3. if、switch都可以嵌套使用。
【问题描述】输入一个日期，判断它所在年份是否为闰年，并输出所在月份的天数。闰年的判断方法：四年一闰，百年不闰，四百年又闰。
int year,month,day;
bool b=false;
cin>>year>>month>>day;
// 判断是否为闰年
if (n%400==0)
b=true;
else if (n%100!=0 && n%4==0)
b=true;
if (b)
cout< else cout< // 判断所在月份的天数 switch (month) { case 1: case 3: case 5: case 7: case 8: case 10: case 12: cout<<"这个月有31天。"< break; case 4: case 6: case 9: case 11: cout<<"这个月有30天。"< break; case 2: cout<<"这个月有"<<(b ? 29 : 28)<<"天。"< break; }; 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 (3) 循环结构 1. while语句：如果条件成立，就继续循环，直到条件不成立为止。格式如下： while (条件) 循环体（语句或语句块） 2. do…while语句：如果条件成立，就继续循环，直到条件不成立为止。它与while的最大区别在于，do…while循环中的语句会被执行至少一次，而while中的语句可能一次都没有被执行。格式如下： do { 循环体 } while (条件); // 注意分号 4. for语句：for分四部分，有初始条件、继续循环的条件、状态转移的条件和循环体。格式如下： for (初始条件; 继续循环的条件; 状态转移的条件) 循环体 转换成while循环，即： 初始条件 while (继续循环的条件) { 循环体 状态转移 } for后三个条件不是必需的，可以省略不写，但分号必须保留。 5. 在循环语句内部使用break，可以跳出循环；使用continue，可以忽略它后面的代码，马上进入下一轮循环。 注意，这两个语句只对它所在的一层循环有效。 6. 写for循环时，一定要注意： 不要把计数器的字母打错，尤其是在复制/粘贴一段代码的时候。 根据算法要明确不等号是“<”、“>”，还是“<=”、“>=”。 逆序循环时，不要把自减“--”写成自增“++”！ 【问题描述】输入n，输出n!（n!＝1×2×3×4×……×n）。结果保证小于long long的范围。当输入值为负数时结束程序。 int n; long long r=1; cin>>n; while (n>-1) { r=1; for (int i=1; i<=n; i++) r*=i; cout< cin>>n; } 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 (4) goto语句 goto语句用于无条件跳转。要想跳转，首先要定义标签（在代码开头的一段标识符，后面紧跟冒号），然后才能goto那个标签。 很多教程不提倡使用无条件跳转，因为它破坏了程序结构，还容易给代码阅读者带来麻烦。不过，这不代表goto没有使用价值。goto的一个用途是跳出多层循环： for (int i=0; i<9; i++) for (int j=0; j<9; j++) for (int k=0; k<9; k++) { if (满足某种条件) goto __exited; …… } __exited: (5) C与C++的区别 C++语言是以C语言为基础开发出来的，C语言的大多数内容被保留了下来。在信息学竞赛领域，很多情况下C和C++可以互相转化，甚至不用对代码进行任何修改。 下面是信息学竞赛领域中C和C++的重要区别： C++支持用流输入输出，而C只能用scanf和printf——再见了，%d！ C++非常支持面向对象编程，而C已经“out”了。 《资料》中的“高精度算法”就只能用C++完成，因为在struct内定义了成员函数。 C++可以用更强大的string类处理字符串，而不必担心发生某些低级错误。 C++有强大的STL，而C没有（有一个小小的qsort和bsearch算是补偿了）。 STL是很多人从C转到C++的重要原因。 C的头文件名仍然可以用在C++中，不过可能会收到警报——应该去掉“.h”，前面再加一个“c”。 如 C程序运行速度稍优于C++。不过也没快多少。 总之，C能做的一切事情，C++也能做；C++能做的一切事情，C不一定能做。 1.2 数据类型 (1) 基本数据类型 名称 int unsigned int① char unsigned char short② ①②占用空间 别名 4 signed, signed int, long, long int 4 1 1 2 数据范围 –2,147,483,648～2,147,483,647 unsigned, unsigned 0～4,294,967,295 long,unsigned long int char unsigned char short int, –128～127 0～255 –32,768～32,767 一般都使用有符号整数，除非范围不够大，或者你确定你的减法运算不会出现“小数减大数”。 一般来说，使用int、long long更保险一些，除非内存不够用。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 signed short int unsigned short long long① 2 8 unsigned short int signed long long long double 0～65,535 –9,223,372,036,854,775,808～ 9,223,372,036,854,775,807② 0～18,446,744,073,709,551,615 true或false –128～127 –128～127 0～255 3.4E +/- 38 (7位有效数字) 1.7E +/- 308 (15位有效数字) unsigned long long 8 bool char signed char unsigned char float double 1 1 1 1 4 8 (2) 变量与常量 1. 定义变量：“变量类型 标识符”，如“int i;”定义了一个名字为i的整型变量。 注意，此时i并未初始化，所以i的值是不确定的。 2. 定义常量：“const 变量类型 标识符=初始值”，如：const int N=90; 3. 合法的标识符： 标识符不能和关键字（在IDE中会变色的词语）相同。 标识符只能包括字母、数字和下划线“_”，并且开头只能是字母或下划线。 标识符必须先定义后使用。 在同一作用域内，标识符不能重复定义（即使在不同作用域内也不应重复，否则容易产生歧义）。 C++区分大小写。所以A和a是两个不同的标识符。 (3) 数组 1. 定义一个一维数组：int a[10]; 这个数组一共10个元素，下标分别为0～9。访问某个元素时，直接用a加方括号，如a[5]。 2. 定义一个二维数组：int b[5][3]; 这个数组一共5×3＝15个元素，分别是b[0][0]、b[0][1]、b[0][2]、b[1][0]……b[4][2]。 访问某个元素时要用两个方括号，如b[2][1]。 多维数组的定义和使用方法与此类似。 3. 数组名和元素的寻址：以上面的a、b为例 数组名是一个指针，指向整个数组第一个元素所在的地址。如a就是&a[0]、b就是&b[0][0]。 多维数组的本质是数组的数组，所以b[0]实际上是b[0][0]、b[0][1]……的数组名，b[0]就是&b[0][0]。 在内存中，数组中每个元素都是紧挨着的，所以可以直接进行指针的运算。如a+3就是&a[3]，**(b+1)就是b[1][0]，*(*(b+3)+2)就是b[3][2]。 在竞赛中要尽可能回避这些功能。 4. 字符串： 字符串实际上是char的数组。 字符串最后一位必须是'0'，否则会在进行输出、使用字符串函数时发生意外。 ①② 不要使用“__int64”！它是Visual C++特有的关键字。 假如a是long long类型，把超过231的值赋给它时要使用字面值LL（ULL）：a=2345LL。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 数组，包括字符串，不可以整体地赋值和比较。如果需要，应使用memcpy和memcmp（字符串是strcpy和strcmp）。 5. C++中数组的下标只能从0开始（当然可以闲置不用），并且int a[10]中a的最后一个元素是a[9]，不是a[10]！ 6. C++不检查数组下标是否越界！如果下标越界，程序很有可能会崩溃！ (4) 指针 1. 取地址运算符和取值运算符： 取地址运算符“&”：返回变量所在的地址。一般用于变量。（而数组名本身就是指针，无需“&”） 取值运算符“*”：返回地址对应的值，或用于改变指针所指内存空间的值。只能用于指针。 2. 指针的意义：保存另一个变量的内存地址。 3. 定义指针：int *p; 定义多个指针时，每个字母的前面都要有“*”。 注意，如果p没有被初始化，它就会指向一个未知的内存空间，而错误地操作内存会导致程序崩溃！ 4. 指针使用实例： int a = 0, b = 1; int c[] = {1,2,3,4,5,6,7,8,9,10}; int *p; // 定义一个指针 p=&a; // 让p指向a (*p)=3; // 相当于a=3 (*p)=b; // 相当于a=b，此时a等于1 // p=b; // 非法操作，左边是int *，右边是int，类型不匹配。 p=&b; // 让p指向b，从此p和a没关系了 p=c+6; // 让p指向c[6]，p和b又没关系了 cout<<*p; // 输出p指向的变量的值，即c[6] p++; // 现在p指向了c[7]; p=NULL; // 表示p没有指向任何变量 cout<<*p; // 由于NULL（0）是一段无意义的地址，所以程序极有可能崩溃。 为了不在竞赛中把自己搞晕，请回避指针，对其敬而远之。 (5) 引用 通俗地讲，引用是某个变量的别名。下面定义了一个叫p的引用，它实际上是f[0][2]。无论是改变p的值，还是改变f[0][2]的值，结果都是一样的。 int &p = f[0][2]; 使用引用的好处是，在函数的形参中定义引用类型，可以直接修改变量的值，而不用考虑“&”和“*”运算符。像上面一行代码一样，如果频繁调用f[0][2]，也可以用引用节省篇幅，提高代码可读性。 引用与指针不同。引用被创建的同时也必须被初始化，并且必须与合法的存储单元关联。一旦引用被初始化，就不能改变引用的关系。而指针可以不立刻初始化，也可以改变所指向的内存空间。 (6) 结构体 结构体用struct定义。例如下面代码定义了一个叫pack的结构体，它有两个成员，一个叫value，另一个叫weight。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 struct pack { int value, weight; }; 变量可以定义成上面的pack类型：pack p; // 不必写成struct pack p; 访问pack的成员时，用“.”运算符（指针变量用“->”）：、(&p)->value C++中结构体可以像类一样建立自己的构造函数、成员函数，也可以重载运算符。 对于pack这个结构体，它的内部不允许再有pack类型的成员，但是可以有pack类型的指针。 1.3 运算符 (1) 运算符的优先级 运算符 :: .（对象成员） ->（指针） []（数组下标） ()（函数调用） ++ -- (typecast)（强制类型转换） sizeof ~ ! +（一元） -（一元） *（取值运算符） &（取地址运算符） new delete .* ->* * / %（取余数） + - <<（左移） >>（右移） < <= > >= ==（判断相等） !=（判断不等） &（按位与） ^（异或） |（按位或） &&（条件与） ||（条件或） :（条件运算符） = *= /= %= += -= &= ^= >>= <<= , 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从右向左 从右向左 从左向右 结合方式 无 从左向右 从右向左 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 (2) 常用运算符的作用 1. 算术运算符：+、-、*、/、%分别表示加、减、乘、除、取余。 两个整数做除法时，如果除不开，程序将把小数部分直接截断（不是四舍五入）。即：整数/整数＝整数，浮点数/浮点数＝浮点数。 学习过其他语言的同学要注意，C++中没有乘方运算符，“^”也不是乘方运算符。 2. 比较运算符： >、>=、<、<=、==（相等）、!=（不等）用来判断不等关系，返回值是true或false。 小心，千万不要把“==”写成“=”！ 永远不要对浮点数使用==和!=运算符！正确的做法是： const double eps = 0.000001; // 自己控制精度 …… if (d>=2-eps && d<=2+eps) …… // 相当于if (d==2) 不应该判断一个变量的值是否等于true。安全的做法是判断它是否不等于false。 3. 位运算： &、|、^分别表示按位与、按位或、按位异或，即两个操作数上每一个二进制位都要进行运算。 ~表示按位求反。 <<、>>表示二进制位的移动。当某一位数字移动到二进制位的外面之后，它就直接“消失”了。 a< 4. 逻辑运算符： &&、||、^分别表示与、或、异或。!表示非。 ?:是条件运算，它是C++唯一一个三目运算符。它的格式如下：A ? B : C。 如果A不为false，那么返回B，否则返回C。 可以将这个运算符理解为一个简化版的if。 ||、&&、?:是短路运算符①。不要在这三种运算符内调用函数或赋值，以免发生难以查出的错误！ 5. 比较运算符、位移运算符、逻辑运算符、条件运算符的优先级较低，所以使用时要多加括号，以防出错。 6. 自增（++）、自减（--）运算符： 增量分别是1和-1。 这两种运算符只能用于数值类型的变量，不能用于非数值类型变量、常量、表达式和函数调用上。 前缀++、--和后缀++、--的作用效果不同： int i=0, j=8, k=5; j = j + (++i); // i先自增，变成1，然后再和j相加。执行之后i=1，j=9。 k = k + (i++); // i先和k相加，使k=6。然后i再自增。执行之后i=2，k=6。 前缀运算符返回引用类型，后缀运算符返回数值类型。 为了避免错误，不要让++、--和其他能够改变变量的操作在同一行出现！ 7. 赋值运算符： 在C++中赋值是一种运算符。所以你会看到i=j=0、d[x=y]、return c=i+j之类的代码。 +=、-=、*=、……可以简化书写。例如a*=2+3相当于a=a*(2+3)。 (3) 真值表 p true (1) ①q true (1) p && q (p & q) p || q (p | q) true (1) true (1) p ^ q false (0) !p (~p) false (0) 例如计算“a && b”，如果a为false，那么实际上结果就是false——不管b是什么，程序都不再计算了。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 true (1) false (0) false (0) false (0) true (1) false (0) false (0) false (0) false (0) true (1) true (1) false (0) true (1) true (1) false (0) false (0) true (1) true (1) (4) 类型强制转换 用一对小括号把数据类型包上，则它右侧的变量或常量的值（变量本身不变）就变成了对应的类型。如： int i=2; float c=6.4/(float)i; // 把i的值变成float类型。 两个操作数进行四则运算，如果想保留小数位，那么两个操作数应该都是浮点数。上面的代码就是这样。 1.4 函数 (1) 定义和使用函数 1. 定义和调用函数：下面定义了一个函数，返回值是double类型的，其中有两个参数i、j，分别是int和float类型的。 double foo(int j, float j) { …… } 如果函数不需要返回任何值，可定义为void类型。 函数的定义必须在函数调用的前面。只有在前面添加了函数定义，才能把具体实现放到调用的后面： double foo(int, float); // 放到调用之前 2. 返回值：return 值; 函数是void类型的，那么return后面除了分号，什么都不跟。 调用之后，函数立刻结束。 不可以直接对函数名赋值（学过Pascal或Basic语言的同学要特别注意）。 3. 如果你的函数需要返回指针或引用，你必须注意：不要引用函数内部的变量！因为函数一结束，函数内部的变量就烟消云散，不复存在了。正确做法是引用静态变量（static）或全局变量。 4. 内联函数（inline）：当一个函数内部只有寥寥几句时，如“华氏度变摄氏度”，可以考虑将其定义成内联函数，通知编译器省略函数入栈等操作，直接展开函数内容，以加快运行速度。 inline int FtoC(int f) { return (f-32)/9*5; } (2) 传递实参 1. 按值传递：例如int foo(int n)，在调用foo时，程序会把参数复制一份给n。这样，对n的任何修改都不会反映到调用foo的参数上面。 对于按值传递数组，一定要慎重。因为复制数组的元素要浪费很多时间。 2. 传递指针：例如int foo(int *n)。对n的修改会反映到调用foo的参数上面。 修改n的值时要注意，必须用取值运算符，否则改变的是n指向的内存空间①。 此外，这种方法可以用于传递数组——调用时只需把数组名作为参数。这时不需要取值运算符。 3. 传递引用：例如int foo(int &n)。 优点是既可以直接修改调用foo的参数，又不会带来指针的麻烦（无需取值运算符）。缺点是不能传入常 ① 使用const可防止n指向的内存空间发生改变：int foo(const int *n)。这时再写n=5之类的语句会被报错。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 数或表达式。 1.5 输入和输出! (1) 使用标准输入/输出 头文件： 变量约定：FILE *fin, *fout;——fin、fout分别代表输入文件和输出文件。把它们换成stdin和stdout，就是从屏幕输入和从屏幕输出。“1.5 字符串操作”也使用了同样的变量。 1. 输出字符串或变量的值：printf("格式字符串", ……); 或fprintf(fout, "格式字符串", ……); 格式字符：“%”后连接一个字母。 字符 d u o x, X 含义 整数① 无符号整数 八进制整数 十六进制整数（小写、大写） 字符 e, E f c s 含义 用科学记数法表示的浮点数 浮点数 字符 字符串（字符数组） 常见的修饰符： %5d：5位数，右对齐。不足5位用空格补齐，超过5位按实际位数输出。 %-5d：5位数，左对齐。不足5位用空格补齐，超过5位按实际位数输出。 %05d：5位数，右对齐。不足5位用'0'补齐，超过5位按实际位数输出。 %+d：无论是正数还是负数，都要把符号输出。 %.2f：保留2位小数。如果小数部分超过2位就四舍五入，否则用0补全。 1. 输入到变量 读取不含空白的内容：scanf("格式字符串", &……); 或fscanf(fin, "格式字符串", &……); ① 格式字符和printf基本一致。 ② 不要忘记“&”！printf传的是值，scanf传的是地址！ ③ scanf和fscanf的返回值是：成功输入的变量个数。fscanf返回EOF，表示文件结束。 ④ scanf和fscanf忽略TAB、空格、回车。遇到这些字符它们就停止读取。 读取单个字符：fgetc(fin); 首先要判断它是否为EOF（文件结束）。如果不是，就可以用强制类型转换变成char。 读取到行末时，要注意对换行符的处理。 Windows、Linux、Mac的回车字符是不同的。Linux是'n'，Mac是'r'，Windows下是两个字符——'r'和'n'。 (2) 使用流输入/输出 1. 2. 3. 4. ①头文件： 输入到变量：cin>>n; 输出到屏幕上：cout< 可以连续输入、输出，如cin>>n>>m; cout< 换行：cout< 格式化输出： 在Windows下调试时，用“%I64d”输出long long类型的值。交卷时，由于用Linux测试，要改成“%lld”。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 头文件： 右对齐，长度为n，不足的部分用空格补齐： (n); (' '); cout< // 如果想用“0”补齐，就可以把空格换成“0” 前两行代码，每次输出之前都要调用。 输出成其他进位制数： 8： cout< 16： cout< 其他进位制需要自己转换。 5. 注意，数据规模很大时，流的输入输出速度会变得很慢，甚至数据还没读完就已经超时了。 在进行输入输出之前加入这样一条语句：ios::sync_with_stdio(false); 调用之后，用cin、cout输入输出的速度就和scanf、printf的速度一样了。 1.6 其他常用操作! 本资料常用的头文件： C++的流、容器、算法等都需要引用std命名空间。所以需要在#include后面、你的代码前面加上一句： using namespace std; (1) 库函数 1. 数组的整体操作： 头文件： 将a[]初始化：memset(a, 0, sizeof(a)); 第二个参数应该传入0、-1或0x7F。传入0或-1时，a[]中每个元素的值都是0或-1；如果传入0x7F时，那么a[]中每个元素的值都是0x7F7F7F7F（不是0x7F！），可认为是“无穷大”。 将a[]整体复制到b[]中：memcpy(b, a, sizeof(a)); 判断a[]和b[]是否等价：memcmp(a, b, sizeof(a)); // 返回0表示等价 2. 字符操作： 头文件： tolower(c)、toupper(c)：将c转化为小写或大写。 isdight(c)、isalpha(c)、isupper(c)、islower(c)、isgraph(c)、isalnum(c)：分别判断c是否为十进制数字、英文字母、大写英文字母、小写英文字母、非空格、字母或数字。 3. 最大值/最小值： 头文件： max(a,b)返回a和b中的最小值，min(a,b)返回a和b中的最大值。 其实我们可以自己写： 4. 交换变量的值：swap(a,b) 头文件： 其实我们可以自己写：inline void swap(int &a, int &b) { int t=a; a=b; b=t; } 5. 执行DOS命令或其他程序：system("命令行"); 头文件： 暂停屏幕：system("pause"); 竞赛交卷或OJ提交代码之前必须删除system，否则会被视为作弊（如果是tyvj甚至都无法提交）。 如果使用输入重定向，那么命令提示符不会接受任何键盘输入——直接用文件内容代替键盘了。 6. 立刻退出程序：exit(0); 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 这种方法常用于深度优先搜索。执行后，程序立刻停止并返回0，所以在调用前应该输出计算结果。 头文件： 7. 计时：double a = (double)clock() / (double)CLOCKS_PER_SEC; 上面的a对应一个时刻。而将两个时刻相减，就是时间间隔。可用这种方法卡时。 头文件： 8. 断言：assert(条件) 条件为假时，程序立刻崩溃。 头文件： 如果定义了NDEBUG符号，那么它将不会起任何作用。 断言和错误处理不同：例如出现“人数为负数”的情况，如果责任在于用户，那么应该提示错误并重新输入，而不是用断言；如果发生在计算过程，应该用断言来使程序崩溃，以帮助改正代码中的错误。 换句话说，错误处理防的是用户的错误，断言防的是代码的错误。 9. 快速排序：qsort(首项的指针, 待排序元素个数, 每个元素所占字节, 比较函数) 头文件： 这是留给C党的快速排序，它比STL的排序算法啰嗦一些。 比较函数返回int类型，用于对两个元素的比较。原型如下： int compare(const void *i, const void *j); 如果*i＜*j，则应返回一个小于0的数；如果*i==*j则应返回0，否则返回一个大于0的数。 10. 随机数发生器： 头文件： 产生随机数： ① 0~32767的随机数：rand() ② 粗略地控制范围：rand()%范围 注意，这种方法产生的随机数的分布是不均匀的。 ③ 精确地控制范围：(double)rand()/RAND_MAX*范围 ④ 控制在[a, b)之间：a + (int) ((double)rand()/RAND_MAX*(b-a)) 初始化随机数种子： ① srand(数字)：初始化随机数种子。 ② 注意，这条语句在程序开头使用，并且最多用一次。同一程序、同一平台，srand中的参数相等，用rand()产生的随机数序列相同。 ③ 使随机数更加随机：引用 不要在循环中使用这条语句（例如批量产生随机数据），因为time只精确到秒。 11. 数学函数： 头文件： abs(x)：求x的绝对值（该函数同时包含于 sin、cos、tan、asin、acos、atan：三角函数，角的单位为弧度。 可用atan(1)*4表示π。 sinh、cosh、tanh、asinh、acosh、atanh：双曲函数 sqrt：求平方根 ceil(x)、floor(x)：分别返回大于等于x的最小整数、小于等于x的最大整数。注意，参数和返回值都是浮点数类型。 exp(x)、log(x)、log10：分别求ex、lnx、lgx （顺便提一句，指数可以把加法问题转化为乘法问题，对数可以把乘法问题转化为加法问题。） pow(a,b)：计算ab。由于精度问题，你仍然需要学会快速幂。 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简化了一大段代码。同样，内联函数也可以。 1.7 字符串操作! 头文件： 下面假设待处理的字符串为str和str2，即：char str[MAX], str2[MAX]; 牢记，字符串的最后一个字符一定是'0'。如果字符串内没有'0'，进行以下操作（输入除外）时可能只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 会造成意外事故。 1. 输出字符串str： cout< printf("%s",str); 2. 输入字符串str： scanf("%s", str); cin>>str; // 输出到文件：fprintf(fout, "%s", str); // 输出到文件：fscanf(fin, "%s", 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) 输入/输出重定向 头文件： 方法：只需在操作文件之前添加以下两行代码。 freopen("","r",stdin); freopen("","w",stdout); 调用两次freopen后，scanf、printf、cin、cout的用法完全不变，只是操作对象由屏幕变成了指定的文件。 使用输入重定向之后，“命令提示符”窗口将不再接受任何键盘输入（调用system时也是如此），直到程序退出。这时不能再用system("pause")暂停屏幕。 (2) 文件流 头文件： 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 流的速度比较慢，在输入/输出大量数据的时候，要使用其他文件操作方法。 方法：定义两个全局变量。 ifstream fin(""); ofstream fout(""); fin、fout和cin、cout一样，也用“<<”、“>>”运算符输入/输出，如：fin>>a; fout< 当然，也可以通过#define把fin、fout变成cin、cout： #define cin fin #define cout fout (3) FILE指针 头文件： 方法：定义两个指针。 FILE *fin, *fout; …… int main() { fin = fopen("", "r"); fout = fopen("", "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表示。通常表示时间复杂度时，我们只保留数量级最大的项，并忽略该项的系数。 例如某算法，赋值做了3n3+n2+8次，则认为它的时间复杂度为O(n3)；另一算法的主要运算是比较，做了4×2n+2n4+700次，则认为它的时间复杂度为O(2n)。 当然，如果有多个字母对算法的运行时间产生很大影响，就把它们都写进表达式。如对m×n的数组遍历的时间复杂度可以写作O(mn)。 空间复杂度：一个算法主要占用的内存空间，也用大O表示。 在实际应用时，空间的占用是需要特别注意的问题。太大的数组经常是开不出来的，即使开出来了，遍历的时间消耗也是惊人的。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 (2) 常用算法的时空复杂度 1s运算次数约为5,000,000①。也就是说，如果把n代入复杂度的表达式，得数接近或大于5,000,000，那么会有超时的危险。 常见的数量级大小：O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n2)＜O(n3)＜O(2n)＜O(n!) 数量级 O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2n) O(n!) O(nn) 能承受的大致规模 任意 任意 以百万计（五六百万） 以十万计（三四十万） 以千计数（两千） 不到两百 24 10 8 常见算法 直接输出结果 二分查找、快速幂 贪心算法、扫描和遍历 带有分治思想的算法，如二分法 枚举、动态规划 动态规划 搜索 产生全排列 暴力法破解密码 O(1)叫常数时间；O(n)、O(n2)、O(n3)、O(n4)……叫做多项式时间；O(2n)、O(3n)……叫做指数时间。 (3) 简单的优化方法 1. 时间的简单优化方法 时间上的优化在于少做运算、做耗时短的运算等。有几个规律需要注意： 整型运算耗时远低于实型运算耗时。 位运算速度极快。 逻辑运算比四则运算快。 +、-、*运算都比较快（-、*比+慢一点点，可以忽略不计）。 /运算比+、-、*慢得多（甚至慢几十倍）。 取余%和除法运算速度相当。 调用函数要比直接计算慢（因为要入栈和出栈）。 这些规律我们可以从宏观上把握。事实上，究竟做了几步运算、几次赋值、变量在内存还是缓存等多数由编译器、系统决定。但是，少做运算（尤其在循环体、递归体中）一定能很大程度节省时间。 2. 空间的简单优化方法 空间上的优化主要在于减小数组大小、降低数组维数等。常用的节省内存的方法有： 压缩储存——见192页“A.7 状态压缩*”。 覆盖旧数据——例如滚动数组（见66页“(5) 使用滚动数组”）。 要注意的是，对空间的优化即使不改变复杂度，只是改变n的系数也是极有意义的。空间复杂度有时对时间也有影响，要想方设法进行优化。 ① 不同资料给出的数值是不同的，不过这不要紧。在NOIP中，只要你的算法正确，就不会在运行时间上“打擦边球”。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 3. 优化的原则 尽量不让程序做已做过的事。 不让程序做显然没有必要的事。 不要解决无用的子问题。 不要对结果进行无意义的引用。 1.10 代码编辑器 为了学习信息学，你需要一台带有C++编译器的计算机。 为了方便编程，你还需要IDE（集成开发环境）或具有编程特性的代码编辑器，否则你需要自己从命令行编译程序。 常见的IDE和编辑器如下： 名称 DEV-C++ Code::Blocks 适用操作系统 Windows 代码编辑功能 一般 编译器 调试功能 单文件编译 自备 × × × × × × × × 自备 差 好 好 一般 好 gdb** 好 gdb gdb 好 √ √（调试除外） × √ √ g++*** × g++ g++ × × Linux、Windows 好 好 Anjuta C/C++ IDE Linux GUIDE Windows、Linux 一般 Emacs（Linux自带） Linux、Windows 好 Vim（Linux自带） Linux、Windows 好 Eclipse**** 记事本＋命令提示符 gedit＋终端 Visual C++ Qt Creator Windows、Linux 好 Windows × Linux 差 Windows 好 Windows、Linux 好 自备* 好 * 不是GCC，而是微软自己的编译器。 ** gdb调试功能的好坏取决于你使用的熟练程度。 *** 会用就能编译。 **** 需要安装CDT插件才能编写C++的程序。 Windows不预备C++编译器，你需要自己下载并安装，下载地址。Linux自备GCC，无需再安装编译器。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 第二单元 基础算法 2.1 经典枚举问题 (1) 韩信点兵 【问题描述】正整数x除以3余1，除以5余2，除以7余3。问符合条件的最小x。 // 当x比较大时，更合适的做法是解同余式组，具体做法见145页。 int x; for (x=1; ;x++) if (x%3==1 && x%5==2 && x%7==3) break; cout< (2) 百鸡问题 【问题描述】1只公鸡5文钱，1只母鸡3文钱，3只小鸡1文钱。如果正好花100文钱，可以买几只公鸡、几只母鸡、几只小鸡？ for (int x=0; x<=20; x++) for (int y=0; y<=33; y++) { // 公鸡 // 母鸡 int z=3*(100-5*x-3*y); // 小鸡 if (z>=0) cout< } (3) 求水仙花数 【问题描述】请输出所有的水仙花数。水仙花数是一个三位数，每一位数字的立方相加，得到的总和是它本身，如143＝13＋43＋33。 for (int i=1; i<=9; i++) for (int j=0; j<=9; j++) for (int k=0; k<=9; k++) { int p=i*100+j*10+k, q=i*i*i + j*j*j + k*k*k; if (p==q) cout< } (4) 砝码称重 【问题描述】给你若干个1g、2g、5g、10g、20g、50g的砝码，数量分别为a[1]、a[2]……a[6]，问用这些砝码可以称量出多少种重量（重量大于0，小于等于1000）。 int count=0, weight[1001], a[7]; memset(weight, 0, sizeof(weight)); 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 for (int x1=0; x1<=a[1]; x1++) for (int x2=0; x2<=a[2]; x2++) for (int x3=0; x3<=a[3]; x3++) for (int x4=0; x4<=a[4]; x4++) for (int x5=0; x5<=a[5]; x5++) for (int x6=0; x6<=a[6]; x6++) { int w=1*x1+2*x2+5*x3+10*x4+20*x5+50*x6; weight[w]++; } for (int i=1; i<=1000; i++) if (weight[i]>0) count++; cout< 上面的代码看起来似乎很“笨拙”，但实际上它已经能顺利地解决问题了。 2.2 火柴棒等式① 【问题简述】给你n（n≤24）根火柴棍，你可以拼出多少个形如“A＋B＝C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0），数字的形状和电子表上的一样。 注意： 1. 加号与等号各自需要两根火柴棍。 2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A，B，C≥0）。 3. n根火柴棍必须全部用上。 【分析】 直接枚举A和B（事实证明只到3位数）。为了加快速度，事先把222以内各个数所用的火柴数算出来。 #include using namespace std; int matches[223], n; void getmatches(); // 把火柴棍事先算好 int count=0; int main() { getmatches(); cin>>n; for (int i=0;i<=111;i++) for (int j=0;j<=111;j++) { int k=i+j; if(matches[i]+matches[j]+matches[k]+4==n) ① 题目来源：NOIP2008第二题 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 count++; } cout< return 0; } void getmatches() { matches[0]=6; matches[1]=2; matches[2]=5; …… matches[222]=15; } // 事先编一个程序来产生这一部分代码。 2.3 梵塔问题 【问题描述】已知有三根针分别用1、2、3表示。在一号针中从小到大放n个盘子，现要求把所有的盘子从1针全部移到3针。移动规则是：使用2针作为过渡针，每次只移动一块盘子，且每根针上不能出现大盘压小盘，找出移动次数最小的方案。 【分析】 这是一个经典的递归问题。 递归的思路：如果想把n个盘子放到3针上，就应该先把n-1个盘子放到2针上。然后把1针最底部的盘子移动到3针，再把2针上的n-1个盘子移动到3针上。 void move(int n, int a, int b, int c) // a是盘子来源，b是暂存区、c是目标 { if (n==1) cout< else { move(n-1,a,c,b); cout< // 只有一根针时直接移动 // 先把n-1个盘子移动到#2上 // 把n-1个盘子移动到#3上 move(n-1,b,a,c); } } 调用：move(n,1,2,3); 时间复杂度：O(2n)。n层梵塔至少要移动2n－1步。 2.4 斐波那契数列 斐波那契数列为1，1，2，3，5，8，…… 1（n≤2）很明显，斐波那契数的递推公式是f(n)＝ f(n－2)＋f(n－1)（n＞2）(1) 递归 int f(int n) { 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 } if (n<=2) return 1; else return f(n-2)+f(n-1); (2) 记忆化搜索 当n很大时，递归的运行速度会明显变慢。根本原因在于递归算法进行了大量的重复运算。所以可以开一个数组，记录每个被计算过的函数值。每次调用f时，如果函数值被计算过，就直接调用计算好的结果。 int F[MAX] = {0}; // 初始化为0表明没有计算过 int f(int n) { if (F[n]!=0) return F[n]; if (n<=2) return F[n]=1; else // 直接调用记录的值 } return F[n]=f(n-2)+f(n-1); // 计算，同时记录计算结果 (3) for循环 尽管记忆化快了很多，但仍然不是最好的。本问题递推顺序明显，用一个for循环就可以解决问题了。 int t1, t2, r; // int f[MAX] = {0, 1, 1}; t1=t2=r=1; for (int i=3; i<=n; i++) { r=t1+t2; // f[i]=f[i-2]+f[i-1]; t1=t2, t2=r; } // cout< // 使用f后这一行代码就没有意义了。 // cout< 2.5 常见的递推关系! 1. 前序和：设Si表示数列中首项①到第i项的和。 Si的递推公式：Si＝Si-1＋ai 第i项到第j项中所有元素的和：S＝Sj－Si-1 2. 等差数列 递推公式：设首项为a0，公差为d，则an＝an-1＋d 通项公式②：an＝a0＋nd 11前n项和：Sn＝2(a0＋an)(n＋1)＝(n＋1)a0＋2dn(n＋1) 3. 等比数列 递推公式：设首项为a0，公比为q，则an＝qan-1 通项公式：an＝a0qn ①② 在本节若无特殊说明，n都是从0开始的，当然“n条直线”、“n个物品”是例外。 这里的通项公式、求和公式和高中数学的略有不同，原因是首项的下标不同。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 a0(1－qn+1)前n项和：Sn＝ 1－q1n＝0或n＝1递推公式：fn＝ n≥2fn-1＋fn-24. 斐波那契（Fibonacci）数列 前n项和：Sn＝fn+2－1 51+5通项公式（不能用于编程！）：fn＝52n+1n+11-5 －2实例： ① 楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，计算共有多少种不同的走法。 ② 有一对雌雄兔，每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子？ ③ 有n*2的一个长方形方格，用一个1*2的骨牌铺满方格。求铺法总数。 5. 第二类Stirling数 s(n,k)表示含n个元素的集合划分为k个集合的情况数。 递推公式：s(n,k)＝s(n－1,k－1)＋k·s(n－1,k)，1≤k＜n 6. 错位排列 示例：在书架上放有编号为1，2，…，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。求满足以上条件的放法共有多少种？ 错位排列数列为0，1，2，9，44，265，… n＝10第一种递推公式：dn＝1 n＝2 (n－1)(dn－2＋dn－1)n≥3第二种递推公式：dn＝0ndn－1 ＋(－1)n-2n＝1 n≥2111111通项公式：dn＝n!0!－1!＋2!－3!＋4!－…＋(－1)n n!7. 分平面的最大区域数 n条直线分平面的最大区域数的序列为：2，4，7，11，… 递推公式：fn＝fn－1＋n 通项公式：fn＝n(n＋1)/2＋1 n条折线分平面的最大区域数的序列为：2，7，16，29，… 递推公式：fn＝fn－1＋4n－3 通项公式：fn＝(n－1)(2n－1)＋2n n条封闭曲线（如一般位置上的圆）分平面的最大区域数的序列为：2，4，8，14，… 递推公式：fn＝fn－1＋2(n－1) 通项公式：fn＝n2－n＋2 8. 组合数 n(n－1)(n－2)……(n－m＋1)Amnm通项公式：Cn＝＝＝m!m!n! m!(n－m)!m-1m n0第一种递推公式：Cmn＝Cn-1＋Cn-1 （边界条件Cn＝Cn＝1） n－m＋1m-1第二种递推公式：Cm Cn （边界条件C0n＝n＝1，必须先乘后除） mnn-m优化：m＞2时，可利用Cmn＝Cn 来减少计算次数。 9. 卡塔兰（Catalan）数列 序列：1，2，5，14，42，132，429，1430，4862，16796… 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 n C2n通项公式：hn＝ n+11n＝1第一种递推公式（基于公式意义）：hn＝ n≥2h1hn－1＋h2hn－2＋...＋hn－1h1 1n＝1第二种递推公式（基于组合数性质）：hn＝2(2n－1)h －n＋1n1n≥2实例： ① 有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？ ② 一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ ③ 在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数？ ④ n个结点可构造多少个不同的二叉树？ ⑤ 一个栈（无穷大）的进栈序列为1，2，3，…n，有多少个不同的出栈序列？ ⑥ 将一个凸多边形区域分成三角形区域的方法数？ ⑦ 一个乘法算式P＝a1a2a3…an，在保证表达式合法的前提下（某个数不会被括号括两次，如“((a))”是错误的），有多少种添加括号的方法？ 2.6 选择客栈① 【问题描述】 丽江河边有n家（2≤n≤200,000）很有特色的客栈，客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰（总共k种，用整数0~k-1表示，且0＜k≤50），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。 两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p（0≤p，最低消费≤100）。 他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。 【分析】 首先考虑30%（n≤100）的数据。很明显，本题需要用枚举法解决。 枚举法的思路很明显：枚举区间[i, j]（i≠j，且i、j色调相同），再判断区间内是否有最低消费不超过p的咖啡店。时间复杂度为O(n3)。 现在开始优化算法。可以看到，判断区间内咖啡店的时间为O(n)，有减少的余地。令c[i]表示[1, i]之间最低消费不超过p的咖啡店个数②，那么可以看出，如果c[j]－c[i]＞0，说明i、j之间有符合要求的咖啡店。这样判断区间的时间就降到了O(1)。 有这一步做基础，为了使思路清晰，就可以把不同颜色的客栈分开了。 在处理j时，我们要统计1～j－1与j的解的个数。处理j＋1时又要处理1～j－1，造成了重复计算。 ①② 题目来源：NOIP2011 day1第二题 事实上不是咖啡店个数。如果i、j并列出现“√×”的情况，那么c[j]－c[i]也应该大于0。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 设sum[j]为[1, j]到[i, j]中解的个数。如果j＋1无法消费，那么由于j的存在，有sum[j+1]＝sum[j]；如果j＋1可以消费，那么j＋1可以和1到j中任何一个客栈组合，那么sum[j+1]＝j。 最后将每种颜色的所有sum相加，就可以在O(n)的时间内得出答案了。 #include #include using namespace std; int n,k,p; int c[51][200001], top[51]; long long total=0; int main() { memset(top,-1,sizeof(top)); memset(c,0,sizeof(c)); ios::sync_with_stdio(false); cin>>n>>k>>p; int cnt=0; bool P=false; for (int i=0; i { int x,y; cin>>x>>y; int t=++top[x]; if (y<=p || P) cnt++; c[x][t]=cnt; P = y<=p; } for (int color=0; color { int prev=c[color][0]; long long sum=0; for (int i=0; i<=top[color]; i++) { if (c[color][i]-prev>0) sum=i; total+=sum; prev=c[color][i]; } } cout< 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 return 0; } 2.7 2k进制数① 【问题描述】 设r是个2k进制数（1≤k≤9），并满足以下条件： (1) r至少是个2位的2k进制数。 (2) 作为2k进制数，除最后一位外，r的每一位严格小于它右边相邻的一位。 (3) 将r转换为2进制数q后，则q的总位数不超过w（k＜w≤30000）。 输入k和W，请满足上述条件的不同r的数量。 【分析】 本题不可能直接枚举——答案不超过200位，说明用到了高精度算法！ 先不考虑w。对于一个m位数来讲，m个数字的顺序是确定的。所以只需直接从n（n＝2k－1）个数中取nm个数，组成m位数。所以符合条件的m位数有Cm个。 现在考虑w存在的情况。这里有一个明显的事实：2k进制数，除首位外，每一位转化为二进制后都是k个二进制位。现在最大的问题就是2k进制数的首位。 二进制不超过w位的数，在2k进制下就是a＝[w/k]＋1位（w能被k整除时，认为首位有0个数字）。此时首位剩下b＝w%k个二进制位，即最大可以取2b－1。接下来只需针对2k进制下位数不足a和恰好为a两种情况分别进行枚举。 C所以，符合条件的2进制数个数为f(k,w)＝C＋Cnini=2ka-1i=22b-1i=1inw≥kn a k＜w＜knn-i其中n＝2k－1，a＝[w/k]＋1，b＝w mod k。 通过排列组合，我们间接地枚举了所有符合条件的解。 2.8 Healthy Holsteins② 【问题描述】 农民约翰以他有世界上最健康的奶牛为骄傲。他知道每种饲料的各种维生素的含量，以及一头牛每天需要最少的维生素的量。请你帮助约翰喂养这些奶牛，使得它们能够保持健康，并且消耗的饲料种类最少。 【输入格式】 第一行：一个数V（1≤V≤25），表示维生素的种类数。 第二行：V个整数，表示一头牛一天需要的维生素量。一个整数对应一种维生素。 第三行：一个数G（1≤G≤15），表示饲料的种类数。 第四行：G个整数，表示每种饲料的各种维生素的含量。 【输出格式】 输出共一行。第一个数是需要的最少的饲料种类数。从第二个数开始，输出所需的饲料种类序号。请输出字典序最小的解。 【分析】 ①② 题目来源：NOIP2006第四题 题目来源：USACO Training Gateway 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 本题最多只有15种饲料。如果尝试所有取法，也只有215＝32768种状态，因此完全可以枚举所有方案。 考虑一种饲料，它要么用来喂牛，要么扔到一边去。用来喂牛可以用“1”表示，放到一边用“0”表示。于是，G种饲料的状态可以转化成一个G位的二进制数。这样，枚举0到2G－1的数，就枚举了所有状态。 当然这只是一种思路。如果不能熟练使用位运算，这种做法的编程复杂度会比DFS高很多。 【代码】 #include using namespace std; int v, req[26]; int g, vitamin[16][26]; int Min=100, minstat=0; // Min表示需要最少饲料数，minstat表示目前的最优状态 int count(int stat) // 统计stat中“1”的个数 { int r=0; while (stat) { r+=stat & 1; stat>>=1; } return r; } int main() { cin>>v; for (int i=1; i<=v; i++) cin>>req[i]; cin>>g; for (int i=1; i<=g; i++) for (int j=1; j<=v; j++) cin>>vitamin[i][j]; for (int stat=0; stat < (1< { int r[26] = {0}; // 尝试所有组合 for (int i=1; i<=g; i++) // 计算组合中每种维生素的量 if (stat & (1<<(i-1))) for (int j=1; j<=v; j++) r[j]+=vitamin[i][j]; bool no=false; for (int i=1; i<=v; i++) if (r[i] if (no) continue; int c=count(stat); if (c 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 } } cout< for (int i=1; i<=g; i++) if (minstat & (1<<(i-1))) cout< return 0; 2.9 小结 本单元总结了三种基本算法：枚举、递归和递推。 1. 枚举 所谓枚举，就是将所有的可能一一遍历出来，在遍历中逐个检查答案的正确性，从而确定最终结果。因此，枚举法适合解决“是否有解”和“有多少个解”的问题。搜索的本质就是枚举。 应用枚举法搜索答案之前，要确定枚举的对象和状态的表示方式。 常见的枚举方法有三种：第一种是使用for循环，第二种是利用排列组合，第三种是顺序化（比如把状态与二进制数对应）。 由于枚举法产生了大量的无用解，所以规模稍大的时候要进行优化。优化时要从两方面入手，一是减少状态量，二是降低单个状态的考察代价。优化过程要从以下几个方面考虑：枚举对象的选取、枚举方法的确定、采用局部枚举或引进其他算法。 （在这里附上次短路的求法：先求出最短路，枚举最短路上的每一条边，对于每一条边都删除然后重新求最短路。几个新的“最短路”的最小值就是次短路。） 2. 递归 递归，即自己调用自己。递归法将较复杂的大问题分解成较简单的小问题，然后一层一层地得出最终答案。 递归是实现许多重要算法的基础。深度优先搜索、记忆化搜索、分治算法和输出动态规划的中间过程等都需要用递归实现。 有一些数据结构也是递归定义的，如二叉树。使用此类数据结构时，也要递归地思考问题。 写递归要从两方面入手：分解问题的方式、边界条件。 注意，没有边界条件会引发无限递归，从而导致程序崩溃！ 3. 递推 递推指利用数列中前面一项或几项，通过递推公式来求出当前项的解。 递推与递归不同。一般情况下，递推用循环语句完成，而递归必须定义函数。递推也可以转化为递归，即记忆化搜索，这常用于递推顺序不明显的情况。 解决递推问题要从以下几方面入手：状态表示、递推关系、边界条件。 按照计算顺序，递推可以分为顺退和逆推。对于某些问题，递推顺序甚至直接影响编码的复杂度。 动态规划必须使用递推或记忆化搜索来解决。动态规划的状态转移方程一定是递推式。但动态规划与纯粹的递推不同，前者有明显的阶段，而后者的数学性更强。 我们已经在数学课上学习了数列的通项公式和递推公式。高中数学喜欢通项公式，而信息学更喜欢递推公式。下次遇到类似问题，就去寻找递推式吧。 4. 递归和递推的比较 递归 递推 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 1. 问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的。 2. 需要利用分治思想解决的问题。 3. 回溯、深度优先搜索 4. 输出动态规划的中间过程。 结构清晰、可读性强 目的性强 适合解决的问题 1. 能够用递推式计算的数学题。 2. 动态规划（必须使用递推或记忆化搜索） 特点 速度较快、比较灵活 思路不易想到 迭代（使用for循环等） 编码方式 在函数中调用自己 问题的性质不同，改写的方法也不同。 ① 有的问题可以根据程序本身的特点，使用替代方法 栈来模拟递归调用。 ② 有的问题可以改写成递推或迭代算法。 在拓扑关系不明显时，可以采用记忆化搜索。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 第三单元 搜索 3.1 N皇后问题 【问题描述】在国际象棋中，皇后可以攻击与她在同一条水平线、垂直线和对角线的棋子。现在有一张N×N的国际象棋棋盘，在上面放置N个皇后。有多少种使皇后不能互相攻击的方案？（N≤13） (1) 深度优先搜索（DFS） 逐列（行）搜索。每测试一个位置，就检查它是否与其他皇后冲突，如果冲突，回溯①。 每放置一个皇后，就要记录——所在列、“/”对角线和“”对角线都不能放皇后了。 #include #include using namespace std; bool column[20],cross1[50],cross2[50]; int pos[20]; int n, sum=0; void dfs(int row) { if (row==n) { sum++; return; } for (int i=0;i if (!(column[i] || cross1[row-i+n] || cross2[row+i])) // 判断是否可以放置皇后 { // 对皇后已经控制的列和对角线做标记 column[i]=cross1[row-i+n]=cross2[row+i]=true; pos[row]=i; dfs(row+1); // 解除标记，这样才能在新位置上放置皇后。 column[i]=cross1[row-i+n]=cross2[row+i]=false; } } int main() { cin>>n; memset(column,0,sizeof(column)); ① 一般情况下，深度优先搜索要使用回溯法。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 } memset(cross1,0,sizeof(cross1)); memset(cross2,0,sizeof(cross2)); dfs(0); cout< return 0; (2) 状态压缩* 把状态放在一个4字节的int整型变量中，并且使用位运算——这样，速度会比朴素算法的快很多。 #include using namespace std; // sum用来记录皇后放置成功的不同布局数；upperlim用来标记所有列都已经放置好了皇后。 int n, sum = 0, upperlim = 1; // 搜索算法，从最右边的列开始。 void test(long row, long ld, long rd) { if (row != upperlim) { /* row，ld，rd进行“或”运算，求得所有可以放置皇后的列,对应位为0， 然后再取反后“与”上全1的数，来求得当前所有可以放置皇后的位置，对应列改为1。 也就是求取当前哪些列可以放置皇后。 */ long pos = upperlim & ~(row | ld | rd); while (pos) // 0 -- 皇后没有地方可放，回溯。 { /* 拷贝pos最右边为1的bit，其余bit置0。 也就是取得可以放皇后的最右边的列。 */ long p = pos & -pos; /* 将pos最右边为1的bit清零。 也就是为获取下一次的最右可用列使用做准备， 程序将来会回溯到这个位置继续试探。 */ pos -= p; /* row + p，将当前列置1，表示记录这次皇后放置的列。 (ld + p) << 1，标记当前皇后左边相邻的列不允许下一个皇后放置。 (ld + p) >> 1，标记当前皇后右边相邻的列不允许下一个皇后放置。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 */ /* 此处的移位操作实际上是记录对角线上的限制，只是因为问题都化归 到一行网格上来解决，所以表示为列的限制就可以了。显然，随着移位 在每次选择列之前进行，原来N×N网格中某个已放置的皇后针对其对角线 上产生的限制都被记录下来了。 */ test(row + p, (ld + p) << 1, (rd + p) >> 1); } } else sum++; } int main() { cin>>n; } // row的所有位都为1，即找到了一个成功的布局，回溯。 // N个皇后只需N位存储，N列中某列有皇后则对应bit置1。 upperlim = (upperlim << n) - 1; test(0, 0, 0); cout< return 0; 3.2 走迷宫 【问题描述】从文件中读入一个m行n列的迷宫，其中0代表可以通过，1代表不可通过（墙）。请给出一条从(1,1)出发到(m,n)的路径。如果不能到达，输出“Failed”。例如： 10 8 1101010101 (1) 预处理 为了防止在搜索时发生下标越界，我们需要做一个小处理：在迷宫的外圈圈上一层围墙，即 1 1 1 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 1 1 1 1 1 1 1 以下是一些定义： char map[110][110]; bool visited[110][110]; point prev[110][110]; struct point {int r,c;}; int n,m; // 先行后列。 // 记录路径的方法：从A结点扩展到B结点时，将prev[B]设为A。 void flag(int r, int c) // 追踪结点，在经过的路径上画箭头。 { point &t=prev[r][c]; if (!(r==1&&c==1)) flag(t.r,t.c); if (t.r==r && t.c else if (t.r==r && t.c>c) map[r][c]='^'; else if (t.r>r && t.c==c) map[r][c]='<'; else if (t.r } (2) 深度优先搜索（DFS） 搜索方法叫做“一条道走到黑”。 #define isok(a,b) (Map[a][b]!='1')&&(visited[a][b]==false) #define expand(a,b) {prev[a][b]=p;DFS(a,b);} void DFS(int r,int c) { if (r==m&&c==n) { flag(m,n); for (int i=0;i<=m+1;i++) cout< exit(0); // 该语句会使程序立即退出。 } visited[r][c]=true; point p; p.r=r; p.c=c; if (isok(r-1,c)) expand(r-1,c) if (isok(r,c-1)) expand(r,c-1) if (isok(r+1,c)) expand(r+1,c) if (isok(r,c+1)) expand(r,c+1) 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 } (3) 广度优先搜索（BFS） 搜索过程像墨水的扩散。 queue #define isok(a,b) (map[a][b]!='1')&&(visited[a][b]==false) #define expand(a,b) {prev[a][b]=p;t.r=a;t.c=b;(t);} void BFS() { point t,p; p.r=p.c=1; (p); while (!()) { p=(); (); int &r=p.r, &c=p.c; visited[r][c]=true; if (r==m&&c==n) { flag(m,n); for (int i=0;i<=m+1;i++) cout< return; } if (isok(r-1,c)) expand(r-1,c) if (isok(r,c-1)) expand(r,c-1) if (isok(r+1,c)) expand(r+1,c) if (isok(r,c+1)) expand(r,c+1) } cout<<"No Way."< } // 判断能否扩展 // 扩展结点 正常形态的迷宫由于道路“狭窄”，能扩展的结点很少，所以DFS、BFS、双向搜索和启发式搜索都能承受。但是，如果换成畸形迷宫（比如100×100的“0”），DFS和BFS将无法忍受。 3.3 8数码问题 【问题描述】用最少的步数实现（空格用0表示）： 2 8 3 1 2 3 1 6 4 → 4 5 6 7 5 7 8 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 (1) BFS① typedef int state[9]; const int N=1000000; state st[N],goal; int dist[N],parent[N]; const int dx[]={-1,1,0,0}, dy[]={0,0,-1,1}; void print(int p) { if (parent[p]!=-1) print(parent[p]); } // 输出st[p] state &s=st[p]; cout< cout< cout< cout< int BFS() { // 返回目标状态在st[]中的下标 init_lookup_table(); // 初始化查找表（判重用） int front=1, rear=2; parent[front]=-1; while (front { state &s=st[front]; if (memcmp(goal, s, sizeof(s))==0) return front; int z; for (z=0; z<9; z++) if (s[z]==0) break; // 找“零” int x=z/3, y=z%3; // “0”的行列编号 for (int d=0; d<4; d++) { int newx=x+dx[d]; int newy=y+dy[d]; int newz=newx*3+newy; if (newx>=0 && newx<3 && newy>=0 && newy<3) { state &t=st[rear]; memcpy(&t, &s, sizeof(s)); t[newz]=s[z]; t[z]=s[newz]; dist[rear]=dist[front]+1; parent[rear]=front; if (try_to_insert(rear)) rear++; // 扩展结点 ① 以下代码直接摘自刘汝佳的《算法竞赛入门经典》。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 } } } front++; } return 0; (2) 顺序化* 下面的代码把0～8的全排列和0～362879（9!－1）的整数一一对应起来。 bool visited[362880]; int fact[9]; void init_lookup_table() { fact[0]=1; for (int i=1;i<9;i++) fact[i]=fact[i-1]*i; } bool try_to_insert(int s) { } int code=0; // 把st[s]映射到整数code state &p = st[s]; for (int i=0; i<9; i++) { int cnt=0; for (int j=i+1; j<9; j++) if (p[j] code+=fact[8-i]*cnt; } if (visited[code]) return false; else return visited[code]=true; (3) 使用哈希表判重 上面的编码法时间效率很高，但是毕竟不是通用的方法。如果结点数非常大，编码也是无法承受的。 const int MAXSIZE = 1000003; int head[MAXSIZE], next[MAXSIZE]; void init_lookup_table() {memset(head,0,sizeof(head));} int h(state &s) { // 散列函数：把每个格子里数连接成一个九位数，并将它除以MAXSIZE的余数作为哈希函数值。 int v=0; for (int i=0; i<9; i++) v=v*10+s[i]; return v%MAXSIZE; } bool try_to_insert(int s) 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 { } int h=hash(st[s]); int u=head[h]; while (u) { if (memcmp(st[u],st[s],sizeof(st[s]))==0) return false; u=next[u]; } next[s]=head[h]; head[h]=s; return true; 3.4 埃及分数 【问题描述】在古埃及，人们使用单位分数的和（形如1/a，其中a是自然数）表示一切有理数。 如：2/3＝1/2＋1/6，但不允许2/3＝1/3＋1/3，因为加数中有相同的。 对于一个分数a/b，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好；其次，加数个数相同的，最小的分数越大越好。如： 19/45＝1/3＋1/12＋1/180 19/45＝1/3＋1/15＋1/45 19/45＝1/3＋1/18＋1/30 19/45＝1/4＋1/6＋1/180 19/45＝1/5＋1/6＋1/18 最好的是最后一种，因为1/18比1/180，1/45，1/30，1/180都大。 给出a，b（0＜a＜b＜1000），编程计算最好的表达方式（输入a，b，按从小到大顺序输出所有分母）。 【分析】 1. 迭代加深搜索：本题由于搜索层数不明，用深搜极易陷入死胡同，用广搜空间又吃不消，这时迭代加深搜索就成了考虑的对象。 1a1112. 有序化：枚举的对象为分母，＝＋＋＋…＋，输出又要求有序，所以，不妨设a1＜a2＜…＜an。 ba1a2a3an3. 定界法：设限定的搜索层数为depth ，当前搜到第k层，当前正要枚举分母ak ，还需枚举总和为x/y的分数。answer[d]表示当前最优解中的第d个分母，如果还没有得到解则表示正无穷。则必然有： max{y/x，ak-1}+1≤ak≤min{(D-C+1)*y/x，Maxlongint①/x，answer[depth]-1} 枚举的初值容易得出，但终值的确定则要用到我们一开始对分母有序性的假设了。值得注意的是，直接限界避免了搜索过程中屡次使用可行性剪枝，在一定程度上可以提高了程序的运行速度。 #include #include #include using namespace std; const int MAXDEPTH=10, maxlongint=2147483647; int depth; ① maxlongint是Pascal语言中的常数，它等于2147483647L，即int类型可以取到的最大值。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 bool found; int answer[MAXDEPTH], d[MAXDEPTH]; int gcd(int a, int b) { int t=a%b; while(t) { a=b; b=t; t=a%b; } return b; } void search(int a, int b, int k) { int i,m,s,t; if (k==depth+1) return; else if (b%a==0 && b/a>d[k-1]) { d[k]=b/a; if (!found || d[k] memcpy(answer,d,sizeof(d)); found = true; return; } // 确定上下界 s = max(b/a, d[k-1]) + 1; t=(depth-k+1)*b/a; t=min(t, maxlongint/b); if (found) t=min(t,answer[depth]-1); for (i=s; i<=t; i++) { // 更新最优解 // 从a/b中减去那个埃及分数 d[k]=i; m=gcd(i*a-b, b*i); search((i*a-b)/m, b*i/m, k+1); } } int main() { 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 } int a,b; int i; found = false; d[0] = 1; cin>>a>>b; for (depth=1; depth<=MAXDEPTH; depth++) { search(a,b,1); if (found) { for(i=1;i<=depth;i++) cout< cout< break; } } return 0; 3.5 Mayan游戏① 由于题目很长，这里不再描述。大家可以“百度一下”，或在百度文库中查NOIP2011试题。 【分析】 问题的性质加上3s的运行时间告诉我们：这个世界需要暴力。 一个块向右交换，与它右边的块向左交换是等价的，但前者的字典序更小，所以不必考虑后者。 此外，如果一种颜色的数量在1～2之间，就可以直接剪枝。 与其说本题在考察搜索，不如说本题在考察选手的编程习惯和心理素质。很多人没有清晰明确的思路和良好的编码习惯，结果“投降”，输出了“-1”，或者写了数KB代码却没有得到多少分。所以大家要养成好的编程习惯，包括变量的命名、代码缩进、注释等，同时要发扬敢于使用暴力的精神。 【代码】 下面代码没有任何剪枝，但已经测试通过了。 #include #include using namespace std; inline void swap(int &a, int &b) { int t=a; a=b; b=t; } // 程序中使用横向棋盘，5行7列，水平移动变竖直移动，竖直移动变水平运动。 int n; int map[7][6][9]; int a[6],b[6],c[6]; // 每一步的变化，a是棋盘倒放之后的行，b是列 ① 题目来源：NOIP2011 day1第三题。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 // 方块下落 void fall(int depth) { for (int i=1; i<=5; i++) { int *m=map[depth][i]; } // 在第i行中，寻找第一个0，然后再寻找非0，接下来移动。不过不一定正确…… int j=1,k=0; while (m[j]) j++; if (j==8) continue; k=j+1; while (m[k]==0 && k<8) k++; while (k<8) swap(m[j++],m[k++]); } // 检查是否可以消除方块。如果可以，就消除方块。 bool mark[6][8]; // 消除方块时用 bool check(int depth) { bool changed=false; memset(mark,0,sizeof(mark)); // 检查是否可以消除 // 水平方向 for (int i=1; i<=5; i++) for (int delta=7; delta>=3; delta--) // 连通的方块数 for (int j=1; j<=8-delta; j++) { int a=map[depth][i][j]; for (int k=j+1; k<=j+delta-1; k++) if (map[depth][i][k]!=a) { a=0; break; } if (a) for (int k=j; k<=j+delta-1; k++) mark[i][k]=true; } // 竖直方向 for (int j=1; j<=7; j++) for (int delta=5; delta>=3; delta--) for (int i=1; i<=6-delta; i++) 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 } { int a=map[depth][i][j]; for (int k=i+1; k<=i+delta-1; k++) if (map[depth][k][j]!=a) { a=0; break; } if (a) for (int k=i; k<=i+delta-1; k++) mark[k][j]=true; } // 消除 for (int i=1; i<=5; i++) for (int j=1; j<=7; j++) if (mark[i][j]) map[depth][i][j]=0, changed=true; return changed; // 进行搜索，如果有解则返回true，否则返回false。 bool DFS(int depth) { if (depth>n) { for (int i=1; i<=5; i++) if (map[n+1][i][1]) return false; return true; } for (int i=1; i<=5; i++) for (int j=1; j<=7; j++) { /* 移动一种方块。分四种情况： ① 方块本身就是0，那么直接跳过； ② 在左边界，只能向右移动； ③ 在右边界，只能向左移动。如果左边有方块，那么可以忽略这一步， 因为那个方块右移和这个方块左移效果相同，但字典序更小。 也就是说，在右边界时，如果左边为空，则向左移动，否则不移动。 ④ 不在边界，如果左边为空，就既向左又向右（特殊考虑，因为要多一段代码）； 如果左边不为空，那么不管右边是什么都向右移动。 */ if (map[depth][i][j]==0) continue; a[depth]=i; b[depth]=j; int &dir=c[depth]; // 移动方向 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 if (i<5) dir=1; // 第②种情况＋第④种情况的第一部分 // 第③种情况 else if (i==5 && map[depth][4][j]==0) dir=-1; else continue; memcpy(map[depth+1], map[depth], sizeof(map[depth])); swap(map[depth+1][i][j], map[depth+1][i+dir][j]); // 下落与消除方块 do { fall(depth+1); } while (check(depth+1)); // 继续搜索 if (DFS(depth+1)) return true; if (i>1 && i<5 && map[depth][i-1][j]==0) // 第④种情况的第二部分 { a[depth]=i; b[depth]=j; dir=-1; memcpy(map[depth+1], map[depth], sizeof(map[depth])); swap(map[depth+1][i][j], map[depth+1][i+dir][j]); // 和上面一样 do { fall(depth+1); } while (check(depth+1)); if (DFS(depth+1)) return true; } } return false; } int main() { memset(map,0,sizeof(map)); cin>>n; for (int i=1; i<=5; i++) { int temp, j=1; 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 } } do { cin>>temp; map[1][i][j++]=temp; } while (temp); if (DFS(1)) for (int i=1; i<=n; i++) cout<<(a[i]-1)<<" "<<(b[i]-1)<<" "< else cout<<"-1"< return 0; 3.6 预处理和优化 (1) 预处理 1. 数学性分析，找出一定规律，减少搜索范围。 【问题描述】在IOI98①的节日宴会上,我们有N（10≤N≤100）盏彩色灯，他们分别从1到N被标上号码。这些灯都连接到四个按钮。 按钮1：当按下此按钮，将改变所有的灯，使本来亮着的灯熄灭，本来是关着的灯被点亮。 按钮2：当按下此按钮，将改变所有奇数号的灯。 按钮3：当按下此按钮，将改变所有偶数号的灯。 按钮4：当按下此按钮,将改变所有序号是 3k＋1(k≥0)的灯，例如1，4，7…… 此外一个计数器C记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器C为0。 你将得到计数器C（0≤C≤10000）上的数值和经过若干操作后所有灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态，并且没有重复。 【分析】 灯的状态多达2100个，似乎无法枚举。 为了找到按钮之间的联系和控制规律，我们不妨列个表说明一下（“√”表示能被按钮控制）： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 … √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ … … … … #1 √ √ √ √ #2 √ √ #3 √ √ #4 √ √ 我们发现，控制情况是“循环”的，每6个灯为一个周期。1、7、13、19……，2、8、14、20……灯的状态是相同的。所以只需枚举前6个灯的状态，至于后面的灯，直接对6取模即可。 2. 保存一些运算结果。如记忆化搜索。 3. 优先在更小的搜索树中搜索，减少搜索量。 ① 这是IOI98的一道题，名为Party Lamps（派对灯）。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 【问题描述】①输出a到b（5≤a≤b≤100000000）之间既是质数，又是回文数的数。 【分析】 有两种判断方法：一种是先找质数后找回文数，另一种方法是先找回文数然后找质数。 应用素数定理可以估算，100000000以内约有540万个素数，所以显然不能先找质数。 即使是先找回文数，也不能全找。 仔细分析，由于质数的末位不能是2、4、5、6、8、0（数字5本身要特殊考虑），所以只需搜尾数为1、3、7、9的回文数。 如果数学基础牢固，你还会发现，由偶数个数字组成的回文数可以被11整除。于是搜索树又小了许多。 4. 有序化处理。 常见的做法是把输入数据排序或分类。有序化搜索往往可以简化问题，帮助分析问题的本质。 (2) 通用优化方法 1. DFS 剪枝：可行性剪枝、最优化剪枝 记忆化：这种方法常用于动态规划的动态转移方程中。 状态压缩 2. BFS 用散列表来判重：为了避免重复扩展结点，可以使用散列表存储已经扩展的状态，并在扩展结点之前进行判重。如果散列表中找到了对应的状态，就不要再入队了。对于图的遍历，判重可以很大程度地提升速度，减少空间的浪费。 对于有些问题，布尔数组、二叉排序树等也能起到相同的作用。 双向搜索：由于代码比较复杂，这种搜索方法在竞赛时不推荐使用。 启发式搜索：如果能够构造出好的估价函数，就可以大大减少搜索量。 状态压缩 (3) 剪枝 剪枝主要有两种，一种是可行性剪枝，另一种是最优化剪枝。它们都可以帮助程序不做“无用功”。 举一个可行性剪枝的例子：在N皇后问题中，放置第i个皇后时，要进行判断。如果这个皇后和已有的皇后发生冲突，回溯。 如果不进行剪枝，那么就应该继续放置这个皇后，继续搜索。继续搜索的结果是可想而知的。 举一个最优化剪枝的例子：在解决某类最值问题时，如果搜索到一个较优的方案，可以把这个方案记录下来。接下来再进行搜索时，每扩展一个结点，就用估价函数判断一下是否能达到已记录的最优值。如果不能，果断剪枝。 合理的估价函数是最优化剪枝的关键。当然，解最小值问题时可以不用估价函数。 ① 题目名称为Prime Palindromes（回文质数），题目来源：USACO Training Gateway。 只供学习与交流 资料收集于网络，如有侵权 请联系网站删除 3.7 代码模板 (1) DFS（递归实现）! void DFS(int depth) { if (depth==n) { // 深度超过范围，说明找到了一个解。 // 找到了一个解，对这个解进行处理，如：输出、解的数量加1、更新目前搜索到的最优值等 return; } // 扩展结点，如 for (int i=0; i { // 处理结点 … // 继续搜索 DFS(depth+1); // 部分问题需要恢复状态，如N皇后问题 … } } 非递归版本见99页“(2) DFS和栈”。稳妥的做法是先写递归版本，如果有空闲时间和改写的可能，再把递归版本改写成非递归版本。 (2) BFS! BFS占用存储空间比较大，尤其是在状态比较复杂的时候。 树的BFS不用判重，因为不会重复。但对于图来说，如果不判重，时间和空间会造成极大的浪费。 queue // bool try_to_insert(int state); // 结点入队前判断状态是否重复，以免重复搜索 // 使用散列表可以提高查找的效率。 // void init_lookup_table(); void BFS() { // init_lookup_table(); (…); while (!()) { // 判重之前的初始化 // 初始状态入队 int s = (); (); // 处理结点 if (s达到某种条件) { // 输出，或做些什么 // 获取状态 只供学习与交流
发布者：admin，转转请注明出处：http://www.yc00.com/xiaochengxu/1690719264a407234.html
评论列表（0条）