![算法竞赛入门经典:习题与解答](https://wfqqreader-1252317822.image.myqcloud.com/cover/371/26793371/b_26793371.jpg)
1.1 编 程 技 巧
本节介绍一些在使用C++语言进行代码编写以及调试时可能用到的技巧以及常见问题。
1.1.1 排序性能问题
相对于C语言内置的qsort函数,C++中提供的sort函数使用起来更加方便,不需要做指针类型转换。sort有两种用法:第一种是传入一个functor对象,另外一种是直接传入一个排序函数,而笔者发现这两种用法语义上都是正确的,但是笔者实际测试发现使用functor的版本比直接使用函数的版本快不少,测试代码如下:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P10_1.jpg?sign=1734466034-89i97gqBeBojKbVQo7juCCXqcpf83OQm-0-1a36b7275c12881c1196f295e18768ee)
笔者的机器上测试发现,STL的sort使用functor的版本是最快的,比qsort都快一倍多。而使用sort传入函数指针的版本速度是最慢的,相对于前两者有大约6倍和3倍的差距,会在一些对排序性能要求很高的题目中形成比较明显的瓶颈,提醒读者注意。
1.1.2 整数输入
最经常输入的数据类型就是int,经常需要输入之后直接插入到一个集合或者数组中,一般的做法是建立一个临时变量,使用cin或者scanf输入之后,再将这个临时变量插入到集合中。这样稍显烦琐。可以封装读取的函数并且这样调用:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P12_2.jpg?sign=1734466034-0VludkzX5dGpEszY7bl6GIg4XxObllkH-0-53dd76ebe47a48ac657d7ce49ca95191)
1.1.3 循环宏定义
算法比赛中,写得最多的代码就是像这样的循环代码:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P12_3.jpg?sign=1734466034-8MMaCjEf3cTsmZBg8I1EbW7HJo01WkfU-0-01d4cb55337a379bb2c4124731f7bf9d)
这里N也可能是一个STL中集合的大小,如vector.size之类的。许多竞赛选手习惯使用大量的宏定义来简化代码,笔者最常用的宏定义是简化这个循环的:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P12_4.jpg?sign=1734466034-5sEviEYaDG7Zc6D1q6m2CiB8Wdgm3p39-0-333a5fdadbca54759d04a2f0c0101823)
这样写循环时,就会简化成_for(i,0,N),这里的a、b两个参数都可传入表达式,例如:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P12_5.jpg?sign=1734466034-tpnpuIXYpFT8ini7uZftUBBKtMmWJeWW-0-1a40a0a69e8b34ad86bfd91697bd8686)
宏使用得当,可以大量简化代码,最典型的例子是本书习题9-18中有一个五维的DP,里面有一个5层for循环,使用宏之后,可精简的代码非常可观。
另外一个比较有用的是:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P12_6.jpg?sign=1734466034-Mu6DkW1CV41cwgu2FhngZpVw21Z5bv9U-0-4c4b7c73a5df202c43006f7030c6b941)
1.1.4 STL容器内容调试输出
比赛中经常用到STL中的容器类,如vector和set,而且在调试过程中经常需要输出这些容器的内容,每次都要写循环来输出,非常烦琐。笔者封装了两个泛型函数使用C++的IO流对集合进行输出:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P13_1.jpg?sign=1734466034-whDpm233O6PIpQJH9dUF50HNkptrEo7F-0-1f96dfa967096a6aad6463b1feb5e997)
1.1.5 二维几何运算类
在许多牵涉位置计算的题目(如本书习题3-5)中,需要模拟物体位置并且进行移动和转向,如果每次都直接用x和y坐标分别计算,非常烦琐,其实可以使用《算法竞赛入门经典—训练指南》一书第4章中的几何操作类,复用向量的移动、旋转等逻辑,详细代码请参考相关章节。
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P13_2.jpg?sign=1734466034-FyppTyLMDKq60Zh5xehTDEfRHM8BFXB7-0-4ba6362f79817f37011679157c753a98)
1.1.6 内存池
在一些题目中,需要动态分配对象。例如,表达式解析时需要动态分配语法树的结点对象。一般的做法是直接用数组开辟空间,但是未必容易事先估计出需要开辟的空间大小,在逻辑控制中还要维护一个变量进行分配和释放,如果是多种对象都要动态分配,则更加烦琐。笔者基于vector容器和C++的内存分配机制,编写了一个内存池:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P14_2.jpg?sign=1734466034-R1zk8AgH4BQtLb3wzhgXMCnzoeQTW9pu-0-9fb22b2d33470f45ca60bc5854e1fa8d)
然后在每次需要释放时直接调用dispose方法即可,不需要再维护各种中间变量。
1.1.7 泛型参数的使用
入门经典中很多算法的封装都会在某个结构体内部开一个数组,并且使用一个类似于MAXSIZE的结构来全局定义这个数组的大小,典型的如图论中的Dijkstra等算法:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P14_3.jpg?sign=1734466034-freT578dI5sx8dvOSbAdA9YvxqkXtIGQ-0-4ee07d899388d2cc435cf9c0eabf4166)
如果同一个题目(如《算法竞赛入门经典—训练指南》中的习题UVa10269 Adventure of Super Mario)中需要在两个不同的部分都用到Dijkstra算法怎么办?这个时候一般的做法就是定义多个MAXSIZE变量,但是会比较烦琐,也容易出错。
其实可以引入C++的泛型参数来解决这个问题:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P15_2.jpg?sign=1734466034-KbfYwZTbvNvaYIt2LaQ9W8KHvmsiMZsX-0-3750760ddb66ee73b303efcc812c7c5b)
使用时,就可以通过下面的方式来指定不同的MAXSIZE:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P15_3.jpg?sign=1734466034-KMNi8ZnZPsVjUBXCbhwNMOVl3A08gVXc-0-2099b60e5441bb6ea725281a39d0f407)
具体使用可以参考训练指南中UVa10269的实现代码。
1.1.8 位运算操作封装
在使用位向量表示集合或进行状态压缩时,有个常用操作就是取得一个整数中某一位或者连续几位对应的int值。这些代码写起来较为烦琐,如果一个题目中多处调用,会增加出错的可能,笔者针对这种情况封装了一个位运算的操作类:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P16_1.jpg?sign=1734466034-rDasgH0h39Z5I7fhH9kNht8rkDPohaAk-0-7200becd2174ce791569ea3dfa9ed8b1)
如果是32位整数位运算可以使用BitOp<long>来调用,64位可以使用BitOp<long long>来调用。
1.1.9 编译脚本
一般都是使用g++编译然后在命令行运行,每次编译都要输入一堆命令,效率较低,所以笔者使用Windows命令行开发了两个脚本。
(1)编译脚本(ojc.bat):这里假设ojc.bat以及g++.exe所在的目录已经加入到系统PATH环境变量中:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P16_2.jpg?sign=1734466034-0TO5onllr0Pl7f8GMt1Dx2JWeibuU7f3-0-6769248991b0aec7d80be907baa536f7)
使用方法如下:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P16_3.jpg?sign=1734466034-44thdLwTLc3mnq58FE0P1BDEuXM5Y2dY-0-0d39f779264225acb459e425cb976ed9)
(2)编译并且直接运行(ojr.bat):这里同样假设ojr.bat以及g++.exe所在的目录已经加入到系统PATH环境变量中。ojr.bat的内容如下:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P16_4.jpg?sign=1734466034-dNoB5dQrf3ICcdcQtCHYJNLDVu4AYYs3-0-23eca51bdb9515d9e774f3cc591f0571)
以下命令会直接编译源文件,然后直接从UVa100.in读入数据运行:
![](https://epubservercos.yuewen.com/BD1DD6/15253382405216406/epubprivate/OEBPS/Images/Figure-P16_5.jpg?sign=1734466034-dpYNFWRCY3rmTtTyJt3quuN21k998w5I-0-54b06144eb93e5afede4c511f0d5f979)