算法竞赛入门经典：习题与解答 - (EPUB全文下载)

文件大小：1.07 mb。
文件格式：epub 格式。
书籍内容：

算法竞赛入门经典：习题与解答
第1章　编程技巧与C＋＋11语法特性介绍
第2章　 《算法竞赛入门经典（第2版）》习题选解
第3章　比赛真题分类选解
第4章　比赛真题选译
第5章　比赛难题选译
第1章　编程技巧与C＋＋11语法特性介绍
对编程技巧和编程语言语法的熟练掌握有助于提高编码速度和准确率。本章介绍一些笔者在训练过程中总结出来的编程技巧和代码片段，以及C＋＋11的语法新特性，希望能够对读者有所帮助。
1.1　编　程　技　巧
本节介绍一些在使用C＋＋语言进行代码编写以及调试时可能用到的技巧以及常见问题。
1.1.1　排序性能问题
相对于C语言内置的qsort函数，C＋＋中提供的sort函数使用起来更加方便，不需要做指针类型转换。sort有两种用法：第一种是传入一个functor对象，另外一种是直接传入一个排序函数，而笔者发现这两种用法语义上都是正确的，但是笔者实际测试发现使用functor的版本比直接使用函数的版本快不少，测试代码如下：
笔者的机器上测试发现，STL的sort使用functor的版本是最快的，比qsort都快一倍多。而使用sort传入函数指针的版本速度是最慢的，相对于前两者有大约6倍和3倍的差距，会在一些对排序性能要求很高的题目中形成比较明显的瓶颈，提醒读者注意。
1.1.2　整数输入
最经常输入的数据类型就是int，经常需要输入之后直接插入到一个集合或者数组中，一般的做法是建立一个临时变量，使用cin或者scanf输入之后，再将这个临时变量插入到集合中。这样稍显烦琐。可以封装读取的函数并且这样调用：
1.1.3　循环宏定义
算法比赛中，写得最多的代码就是像这样的循环代码：
这里N也可能是一个STL中集合的大小，如vector．size之类的。许多竞赛选手习惯使用大量的宏定义来简化代码，笔者最常用的宏定义是简化这个循环的：
这样写循环时，就会简化成_for（i，0，N），这里的a、b两个参数都可传入表达式，例如：
宏使用得当，可以大量简化代码，最典型的例子是本书习题9-18中有一个五维的DP，里面有一个5层for循环，使用宏之后，可精简的代码非常可观。
另外一个比较有用的是：
1.1.4　STL容器内容调试输出
比赛中经常用到STL中的容器类，如vector和set，而且在调试过程中经常需要输出这些容器的内容，每次都要写循环来输出，非常烦琐。笔者封装了两个泛型函数使用C＋＋的IO流对集合进行输出：
1.1.5　二维几何运算类
在许多牵涉位置计算的题目（如本书习题3-5）中，需要模拟物体位置并且进行移动和转向，如果每次都直接用x和y坐标分别计算，非常烦琐，其实可以使用《算法竞赛入门经典—训练指南》一书第4章中的几何操作类，复用向量的移动、旋转等逻辑，详细代码请参考相关章节。
1.1.6　内存池
在一些题目中，需要动态分配对象。例如，表达式解析时需要动态分配语法树的结点对象。一般的做法是直接用数组开辟空间，但是未必容易事先估计出需要开辟的空间大小，在逻辑控制中还要维护一个变量进行分配和释放，如果是多种对象都要动态分配，则更加烦琐。笔者基于vector容器和C＋＋的内存分配机制，编写了一个内存池：
然后在每次需要释放时直接调用dispose方法即可，不需要再维护各种中间变量。
1.1.7　泛型参数的使用
入门经典中很多算法的封装都会在某个结构体内部开一个数组，并且使用一个类似于MAXSIZE的结构来全局定义这个数组的大小，典型的如图论中的Dijkstra等算法：
如果同一个题目（如《算法竞赛入门经典—训练指南》中的习题UVa10269 Adventure of Super Mario）中需要在两个不同的部分都用到Dijkstra算法怎么办？这个时候一般的做法就是定义多个MAXSIZE变量，但是会比较烦琐，也容易出错。
其实可以引入C＋＋的泛型参数来解决这个问题：
使用时，就可以通过下面的方式来指定不同的MAXSIZE：
具体使用可以参考训练指南中UVa10269的实现代码。
1.1.8　位运算操作封装
在使用位向量表示集合或进行状态压缩时，有个常用操作就是取得一个整数中某一位或者连续几位对应的int值。这些代码写起来较为烦琐，如果一个题目中多处调用，会增加出错的可能，笔者针对这种情况封装了一个位运算的操作类：
如果是32位整数位运算可以使用BitOp＜long＞来调用，64位可以使用BitOp＜long long＞来调用。
1.1.9　编译脚本
一般都是使用g＋＋编译然后在命令行运行，每次编译都要输入一堆命令，效率较低，所以笔者使用Windows命令行开发了两个脚本。
（1）编译脚本（ojc．bat）：这里假设ojc．bat以及g＋＋．exe所在的目录已经加入到系统PATH环境变量中：
使用方法如下：
（2）编译并且直接运行（ojr．bat）：这里同样假设ojr．bat以及g＋＋．exe所在的目录已经加入到系统PATH环境变量中。ojr．bat的内容如下：
以下命令会直接编译源文件，然后直接从UVa100．in读入数据运行：
1.2　C＋＋11语言特性介绍
笔者写作本书时主流的算法比赛以及在线OJ平台均已支持最新的C＋＋11语言标准。从开发者的角度来看，新标准中提供了不少能提高开发效率的新特性。本节选择了一些在算法比赛中常用特性进行介绍，希望读者通过练习掌握这些语言特性，提高在比赛中的编码速度和正确率。本书后文中的题解代码也有较多使用C＋＋11的案例，请读者参考。
需要注意的是，如果是使用g＋＋编译，编译器需要加命令行参数－std＝c＋＋11。如果用Visual Studio，则至少需要2013版本。在各大OJ在线提交时，也要选择C＋＋11。
1.2.1　类型推导（auto）
如果要使用比较长的类型声明，最常见的就是STL中的枚举器（iterator），就要写得很长，例如：
而在C＋＋11中就可以这么写：
编译器遇到auto之后会根据右边的表达式自动推导出其具体类型。同时也支持引用类型的变量：
............

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。