作者：谈文蓉 校景中 周绪川
出版社：人民邮电出版社有限公司
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
大学生程序竞赛算法基础教程试读：
前言
云计算、大数据和人工智能技术的发展，对算法能力提出了更高的要求，高等院校计算机类专业越来越重视程序能力和算法能力的培养。以ACM/ICPC为代表的程序类竞赛为算法类人才的培养提供了一个很好的平台，本书作者在高校长期从事算法类的竞赛培训工作，《大学生程序竞赛算法基础教程》一书的出版可帮助读者对基础算法快速入门。
本书的特点如下。
本书是作者十余年带队参加ACM国际大学生程序竞赛积累下来的讲义资料，贴近实战。
本书注重理论与实践相结合，书中提供的程序样例较多，以便学生学以致用。
本书的内容编排力求循序渐进、由浅入深，以保证教材的易用性和可读性。
全书共7章，各章主要内容介绍如下。
第1章C/C++简介。介绍程序竞赛中必备的C/C++语法。
第2章基础算法。介绍算法复杂度、枚举、递归、贪心、二分法等基本算法分析方法和策略。
第3章基础数学。介绍最大公约数、素数、欧拉函数、算术基本原理、快速幂等算法所需数学知识。
第4章数据结构。讲解栈和队列、优先队列、二叉树、并查集、树状数组、RMQ和线段树等程序竞赛中常用数据结构。
第5章动态规划。讲解基本动态规划、背包、01背包、完全背包、单调队列、数位DP、区间DP和概率DP等主流动态规划算法。
第6章图论。介绍建图与遍历、邻接矩阵、Vector邻接表、链式前向星、搜索、深度优先搜索、广度优先搜索、Prim算法、Kruskal算法、Floyed算法、Dijkstra算法和拓扑排序等图论算法。
第7章字符串。讲述KMP和AC自动机等字符串匹配算法。
本书是作者长期开展高校教育教学改革的成果，得到了国家民委高等教育教学改革项目（No.17025）、西南民族大学教育教学改革项目（No.2017ZDPY06）、教育部高等教育司产学合作协同育人项目（No.201702108001）的资助。教材在编写的过程中，得到了相关教师和ACM/ICPC参赛队员的帮助，在此深表感谢。
本书由谈文蓉教授主编，校景中副教授和周绪川教授副主编，万师敏等同学参与。书中的全部程序均经过调试。由于编者水平所限，加之时间仓促，书中不妥之处在所难免，望广大读者不吝赐教。编者2018年10月第1章 C/C++简介
首先，阅读一段完整的C语言代码。
1.#include
2.int main（）
3.{
4. int sum = 0 ，a，b；
5. scanf（＂%d %d＂，&a，&b）；
6. sum = a + b；
7. printf（＂%d\n＂，sum）；
8. return 0；
9.}
#include
main（）是主函数名，函数体用一对大括号表示。在一个程序中，有且仅能有一个以main（）命名的函数，程序从main（）函数的第一行开始运行，最后一行结束。通常将主函数的返回值设为一个int类型的数据，返回0表示程序无异常，返回其他值表示程序出错。
int sum = 0，a，b； 定义了3个int类型的数据，分别为sum，a，b，并把sum值初始化为0。
scanf（）是C语言中的输入函数，被声明在头文件stdio.h中，此行代码表示输入了两个值，并把这两个值分别赋给a和b这两个变量。函数的第一个参数是格式字符串，它指定了输入的格式。例如，%d 为 int 型数据的格式字符串，%c 为char型数据的格式字符串，%f为float型数据的格式字符串。&a、&b中的&是寻址操作符，&a表示对象a在内存中的地址。
prinf（）是C语言中的输出函数，同样被声明在头文件stdio.h中，此行代码表示输出sum的值。
return 0表示函数的返回值为0，表示程序无异常，正常结束。
接下来，再来看一段完整的C++代码。
1.#include
2.using namespace std；
3.
4.int main（）
5.{
6. int sum = 0 ，a，b；
7. cin >> a >> b；
8. sum = a + b；
9. cout << sum << endl；
10. return 0；
11.}
这段代码与上述C语言代码功能类似，主要区别在于输入输出的方式不同。在 C++语言中，使用了 iostream的标准头文件，输入函数改为输入流对象，输出函数改为输出流对象。同时，using namespace std指明了命名空间为std，由于C++标准库中的所有组件都是在一个名为 std 的命名空间中，为了防止许多对象出现同名而混淆的情况，程序都要加上命名空间。
虽然这么看上去，C语言和C++语言出入不大，但C语言基本上是C++的一个子集，C++在C语言基础上增加了基于对象、面向对象的通用模板化编程以及标准模板库。语法上因此也稍有不同。（1）在C语言中，文件名的后缀为.c，而在C++中以.cpp为后缀。（2）在C语言中，变量必须在程序的开始部分集中定义，而在C++中可以在用到的时候再定义。（3）C++语言中允许多个函数使用相同的函数名，构成重载，但C语言中是万万不行的。（4）在C语言中，struct类型的定义必须要加上struct的前缀，而在C++中，struct可以直接使用其类型名定义。
接下来，对C/C++语法进行简单介绍。
基本数据类型
C/C++拥有丰富的数据结构，如整数类型、实数类型、字符串类型等。以下是Windows平台下32位操作系统下的数据。【注】C语言中不包括布尔类型，它是包括在C++语言中的。
整型有无符号（unsigned）和有符号（signed）两种类型，在默认情况下，声明的整型变量都是有符号的类型，如果要声明无符号类型，就需要在类型前加上unsigned。无符号类型和有符号类型的区别是有符号类型需要使用一个比特来表示数字的正负，如32位系统中一个short能存储的数据范围为–32768 ～ 32767（16位二进制的最高位作为符号位，“1”为负，“0”为正），而 unsigned 能存储的数据16范围则是0～65535（这个最高位不用作符号位，所以是2，共65536）。使用无符号整型，可使正整数的数据范围扩大一倍。
一个char的大小和一个机器字符一样，布尔类型（bool）的取值是真（true）或者假（false）。
变量
在程序的运行过程中，值可以改变的被称为变量。变量命名时，只能由数字、字母和下划线组成，且第一个字符只能为字母或者下划线，如下。
1. int sum = 0；
2. char ch；
在一段程序中，每个变量都有作用域和生存周期。在函数或者代码块内部声明的变量称为局部变量，局部变量在函数调用完毕或者代码块运行完之后就结束了生命周期。在所有函数外声明的变量称为全局变量，全局变量在整个代码结束后才结束其生命周期。
局部变量只在函数内或者代码块内使用，而全局变量可以在整个程序中使用。二者可以同名，但在函数内，局部变量会覆盖全局变量的值。请看下面一段代码。
1.#include
2.using namespace std；
3.
4.int main（）
5.{
6. int i = 10；
7. cout <<＂全局变量 ＂<< i << endl；
8. for（int i = 0 ； i<3； i++）
9. {
10. cout <<＂局部变量 ＂<< i << endl；
11. }
12. i++；
13. cout <<＂全局变量 ＂<< i << endl；
14. return 0；
15.}
运行结果如下。
全局变量 10
局部变量 0
局部变量 1
局部变量 2
全局变量 11
在此段代码中，全局变量和局部变量同名，但在代码块内，局部变量覆盖了全局变量。
常量
在程序的运行过程中，值不能改变的被称为常量，常量可以是任何的基本数据类型，一旦被定义就不能修改。常量的定义方法分为两种：（1）使用#define宏定义；（2）使用const关键字。
使用方法如下。
1.#define age 20
2.const int age = 20；【注】使用define宏定义，句末不需要加分号；const定义必须赋值。
宏定义是字符替换，没有数据类型的区别，编译时直接将字段进行替换，容易产生错误。const关键字定义，有类型区别，在编译时会进行类型检验。
数组
当变量很少时，可以直接定义，但当有成千上万个相同类型的变量时，逐一定义就显得力不从心，这时就引入了数组的概念。数组是有序数据的集合，可以定义任何数据类型的数组，它在内存中开辟了一段连续的空间。在C语言中是不能对数组的长度做动态定义的，但在C++中可以实现。数组又分为一维数组和多维数组，以二维数组为例，二维数组的每个元素又是一个一维数组。例如，a[4][2]这个二维数组，我们可以看成是一个含有4个元素的一维数组，但每个元素是一个包含2个元素的二维数组。
1.#include
2.using namespace std；
3.
4.const int N = 10；
5.int main（）
6.{
7. int a[N][N]；
8. for（int i=0；i 9. { 10. for（int j=0；j 11. { 12. a[i][j] = i+j； 13. } 14. } 15. //memset（a，0，sizeof（a））； 16. return 0； 17.} 数组清零的时候，可以遍历一次将每个元素的值设为0，也可以使用memset函数，它是对较大的数组或结构体清零最快的方法，使用方法为void *memset（void*s，int ch，size_t n）。 函数 为了使程序更清晰易懂，通常将程序模块化，每个模块独立完成自己的功能，这个模块称为函数。在 C/C++程序中至少包括一个函数，程序是由一个主函数和若干个函数构成的，同一个函数可以被不同的函数多次调用，但主函数不能被其他函数调用，只能调用其他函数。 函数是由一个函数头和一个函数主体构成的，函数头又分为返回类型、函数名、参数。 返回类型分为两种：一种为void型，即不返回任何数据类型；另一种为其他数据类型，return _type是其返回的数据类型。参数列表可以为空，也可以传入某些值供函数内使用，这些值称为实参。 函数有3种调用方式，分别为传值调用、指针调用和引用调用。 使用传值调用时，把参数的实际值赋值给形式参数，在函数内做的一系列修改对被调用函数中的实际参数没有任何影响。指针调用是把参数的地址复制给形式参数，此时的修改会对实际参数产生影响。引用调用是把参数的引用复制给形式参数，修改也会对实际参数产生影响。 1.#include 2.using namespace std； 3. 4.void fun1（int a，int b） 5.{ 6. a = 10； 7. b = 1； 8. return； 9.} 10.void fun2（int &a，int &b） 11.{ 12. a = 10； 13. b = 1； 14. return； 15.} 16.int main（） 17.{ 18. int a = 1，b = 10； 19. cout << a << ＂ ＂ << b << endl； 20. fun1（a，b）； 21. cout << a << ＂ ＂ << b << endl； 22. fun2（a，b）； 23. cout << a << ＂ ＂ << b << endl； 24. return 0； 25.} 运行结果如下。 1 10 1 10 10 1 结构体 结构体通俗讲就像打包封装，把一些有共同特征（如同属于某一类事物的属性，往往是某种业务相关属性的聚合）的变量封装在内部，通过一定方法访问修改内部变量。 结构体的定义如下。 1.struct Node{ 2. int a[20]； 3. char b； 4. float c； 5.} struct是声明结构体类型时所必须使用的关键字，不能省略。Node是这个结构体的名称。大括号内是该结构体中的各个成员，由它们组成一个结构体。 结构体有以下几种声明变量方式。 结构体在定义的时候不能申请内存空间，但如果是结构体变量，声明的时候可以分配，两者关系就像C++的类与对象，对象才分配内存。结构体的大小通常（只是通常）是结构体所含变量大小的总和。第2章 基础算法2.1 算法复杂度 掌握了基本的编程语言，我们就可以用其来解决各种不同类型的问题，但解决问题的途径多种多样，每种途径又对应一种算法。算法是解决问题的步骤，一个高效稳定的算法可以快速让问题得到完美解答，达到事半功倍的效果，然而，算法的复杂度决定了算法的优劣。 算法的复杂度一般从时间复杂度和空间复杂度这两个方面进行评估。2.1.1 时间复杂度 时间复杂度是指执行算法所需要的计算工作量。在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的执行时间，整个算法的执行时间与基本操作重复执行的次数成正比。n 时间复杂度常用大O符号表示，如O（n）、O（log）等，其中，n为问题规模，即数据输入的大小。在计算时间复杂度时，先计算基本操作的次数，用f（n）表示，O（f（n））代表该算法复杂度是与f（n）成正比的，相当于把f（n）数量级化。222222 例如，下面这段计算1+ 2+ 3+ 4+ 5+ … + n的代码。 1.for（int i=1；i<=n；i++） 2.{ 3. for（int j=1；j<=i；j++） 4. { 5. sum += i； 6. } 7.} 循环内的语句执行了次，取数量级，则这个算法2的时间复杂度为O（n）。当然，对于一些复杂或庞大的算法，这样精确的计算复杂度显得不太可行，通常，我们采用估算方式，取最大数量级。当运算次数不随着问题规模n增长，则时间复杂度为O（1），称为常数级。当运算次数随着问题规模n增长，根据嵌套循环、递归nn等次数，会有对数级O（log）、线性级O（n）、指数级O（C）、阶乘级O（n!）等（其中，n为问题规模大小，C为一常量）。 常见的几种复杂度的关系为。2.1.2 空间复杂度 空间复杂度是指算法在计算机内执行时所需存储空间的度量。算法在执行过程中，本身程序中的变量、数组、结构体和一些数据结构会占用一些空间，也会需要额外的空间，在实际问题中，为了减少空间复杂度，可采用压缩存储的方法。 当数据的输入量不同时，我们可以根据时间和空间复杂度判断算法是否可行，在满足可行的条件下，尽可能使用高效的算法。假设时78间限制为1 s，时间复杂度在1×10以下一般能流畅运行，达到1×10且算法结构简单时，或许可勉强运行。而对于空间复杂度，尽量少开6一些不必要的空间，数组大约在 1×10，具体复杂度预估可根据实际问题判断。2.2 枚举 把问题所有可能的解一一进行检验，排除后得到正确可行解的过程称为枚举，这种方法是牺牲时间和空间来换取较高的准确性，所以当可能的解范围较大时，一般不建议采取这种方法。枚举的时间复杂度一般为所有可能解的范围，但在绝大多数情况下，可以进行优化处理，缩小可能解的范围，或者根据问题的相关性质有选择性地跳跃搜索正解。 枚举简单粗暴，当可能的解范围确定时，暴力枚举所有可能的解，使用枚举算法时，要保证可能的解范围确定，并且一定能在这个范围内找到正解，其本质上就是搜索。【题面描述1】 水仙花数是指一个n位数（n≥3），它每个位上数字的n次幂之和333等于它本身（如1+5+3=153），求出所有三位数的水仙花数。【思路分析】 方法1：直接遍历100～999，判断每个数是否满足是水仙花数的条件。判断的时候，先把每个数的个位、十位、百位拆分出来，然后求三次幂之和是否为此数。【参考代码】 1.#include 2.#include 3. 4.int main（） 5.{ 6. int i，a，b，c； 7. for（i=100；i<=999；i++） 8. { 9. a=i%10； //取出个位数字 10. b=i/10%10； //取出十位数字 11. c=i/100； //取出百位数字 12. if（pow（a，3）+pow（b，3）+pow（c，3）==i）bprintf（＂%d＂，i）；//pow（a，b）为数学函数，表示a，使用时要加上头文件 13. } 14. return 0； 15.} 方法2：方法1只有一个循环，还可以利用3个循环，每重循环分别模拟百位、十位、个位，两种方法的时间复杂度相同，都是遍历了所有可能解的范围，只不过遍历方式不同。【参考代码】 1.#include 2.#include 3. 4.int main（） 5.{ 6. int i，a，b，c； 7. for（a=1；a<=9；a++） //百位从1开头 8. { 9. for（b=0；b<=9；b++） //模拟十位 10. { 11. for（c=0；c<=9；c++） //模拟个位 12. { 13. i=a＊100+b＊10+c； 14. if（pow（a，3）+pow（b，3）+pow（c，3）==i） printf（＂%d ＂，i）； 15. } 16. } 17. } 18. return 0； 19.}【题面描述2】 百钱买百鸡问题：一个人有100元钱，打算买100只鸡。到市场一看，公鸡一只3元，母鸡一只5元，小鸡3只1元，试求用100元买100只鸡，各买多少合适？【思路分析】 根据题意，假设买x只公鸡，y只母鸡，z只小鸡，可以得到方程组 其中，0≤x，y，z≤100&z%3==0，然后可以写出最为简单的代码，一一对所有解进行枚举。【参考代码】 1.#include 2. 3.int main（） 4.{ 5. int x，y，z； 6. for（ x = 0； x <= 100； x++ ） 7. { 8. for（ y = 0； y <= 100 ； y++ ） 9. { 10. for（ z = 0； z <= 100；z+=3 ） 11. { 12. if（ x + y + z == 100 && 3 ＊ x + 5 ＊ y + z / 3 == 100 ） 13. { 14. cout << x << ＂ ＂ << y << ＂ ＂ << z << endl； 15. } 16. } 17. } 18. } 19. return 0； 20.} 我们可以根据已知条件来优化代码，减少枚举的次数：3种鸡的和是固定的，我们只要枚举两种鸡（x，y），第3种鸡就可以根据约束条件z=100−x−y求得，这样就缩小了枚举范围。另外，我们根据方程特点，可以消去一个未知数，得到 其中，0≤x，y，z≤100&z%3==0中的x值可以缩小范围为0≤x≤25。代码优化如下所示。 1.#include 2. 3.int main（） 4.{ 5. int x，y，z； 6. for（ x = 0； x <= 25； x++ ） 7. { 8. y = 100-4 ＊ x； 9. if（ y % 7 == 0 && y >= 0 ） 10. { 11. y /= 7； 12. z = 100-x-y； 13. if（ z % 3 == 0 && 3 ＊ x + 5 ＊ y + z / 3 == 100 ） 14. cout << x << ＂ ＂ << y << ＂ ＂ << z << endl； 15. } 16. } 17. return 0； 18.}【题面描述3（HDU 1172）】 计算机随机产生一个四位数，让玩家猜这个四位数是什么，每猜一个数，计算机都会告诉玩家猜对了几个数，其中有几个数在正确的位置上。例如，计算机随机产生的四位数为1122，如果玩家猜1234，因为1、2这两个数字同时存在于这两个数中，而且1在两个数的位置中是相同的，计算机会告诉玩家猜对了2个数字，其中1个在正确的位置；如果玩家猜1111，那么计算机会告诉玩家猜对了2 个数字，有 2 个在正确位置上。现在给出一段玩家与计算机的对话过程，根据这段对话确定这个四位数是什么。【输入】 输入数据有多组。每组的第一行为一个正整数 N（1≤N≤100），表示在这段对话中共有N次问答。在接下来的N行中，每行3个整数A、B、C。玩家猜这个四位数为A，然后计算机回答猜对了B个数字，其中C个在正确的位置上。当N=0时，输入数据结束。【输出】 每组输入数据对应一行输出。如果根据这段对话能确定这个四位数，则输出这个四位数，若不能，则输出“Not sure”。【Sample Input】 6 4815 2 1 5716 1 0 7842 1 0 4901 0 0 8585 3 3 8555 3 2 2 4815 0 0 2999 3 3 0【Sample Output】 3585 Not sure【思路分析】 因为随机产生的数一定是四位数，所以求解范围不大，可以使用枚举的方法。对于每一个四位数，判断其是否与输入中的对话冲突，但是在找到一个符合条件的数时，仍要继续枚举，直到出现第二个符合条件的数或者枚举完所有四位数时，枚举结束。当有两个符合条件的数或者枚举结束都没找到一个符合条件的数时，输出“Not sure”，当且仅当只有一个符合条件的数时，输出这个数。当然，对于每个数都要进行判断，所以在输入的过程中利用结构体把对话存储进来，然后在判断每个数时读取结构体。【参考代码】 1.#include 2.#include 3.#include 4.#include 5.using namespace std； 6. 7.const int N = 110； 8.struct Arr{ 9. int a，b，c； 10.}arr[N]； 11. 12.int hashA[10]，hashB[10]； 13. 14.bool judge（int y，int n） 15.{ 16. memset（hashA，0，sizeof（hashA））； 17. 18. 19. int A1，B1，C1，D1，A2，B2，C2，D2； 20. A1 = y % 10； hashA[A1]++； 21. B1 = y/10 % 10； hashA[B1]++； 22. C1 = y/100 % 10； hashA[C1]++； 23. D1 = y/1000； hashA[D1]++； 24. 25. for（int i=0；i 26. { 27. memset（hashB，0，sizeof（hashB））； 28. 29. int x = arr[i].a； 30. A2 = x % 10； hashB[A2]++； 31. B2 = x/10 % 10； hashB[B2]++； 32. C2 = x/100 % 10； hashB[C2]++； 33. D2 = x/1000； hashB[D2]++； 34. 35. int cnt1 = 0，cnt2 = 0； 36. if（A1==A2） cnt1++； 37. if（B1==B2） cnt1++； 38. if（C1==C2） cnt1++； 39. if（D1==D2） cnt1++； 40. if（cnt1！=arr[i].c） return false； 41. 42. for（int q=0；q<10；q++） cnt2 += min（hashA[q]，hashB[q]）； 43. if（cnt2！=arr[i].b） return false； 44. } 45. return true； 46.} 47.int main（） 48.{ 49. int n； 50. while（scanf（＂%d＂，&n）！=EOF && n！=0 ） 51. { 52. for（int i=0；i 53. scanf（＂%d %d %d＂，&arr[i].a，&arr[i].b，&arr[i].c）； 54. int ans =-1； 55. for（int i=1000；i<=9999；i++） 56. { 57. if（judge（i，n）） 58. { 59. if（ans！=-1） {ans =-1；break；} 60. ans = i； 61. } 62. } 63. if（ans==-1） printf（＂Not sure\n＂）； 64. else printf（＂%d\n＂，ans）； 65. } 66. return 0； 67.}【习题推荐】 POJ.1753 POJ.29652.3 递归 一个函数直接或者间接调用自己本身，这种函数称为递归函数，而递归算法是把问题转化为规模缩小了的同类问题的子问题，然后调用递归函数表示问题的解，其思想是将一个大型而且复杂的问题层层简化，转化为一个与原问题相似的规模较小且简单的子问题，通过多次调用子问题得到最终复杂问题的解。 在递归调用的过程中，系统为每一层的返回点、局部量等开辟了栈来存储，为了避免栈溢出的问题，递归需要有边界条件，必须有一个明确的递归出口。【题面描述1（HDU 2018）】 有一头母牛，它每年年初生一头小母牛。每头小母牛从第4个年头开始，每年年初也生一头小母牛。请编程实现在第n年时，共有多少头母牛？【输入】 输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n（0 对于每个测试实例，输出在第n年时母牛的数量。每个输出占一行。【Sample Input】 2 4 5 0【Sample Output】 2 4 6【思路分析】 假设第n年母牛数为cow[n]，根据题意可以知道cow[1] = cow[2] = cow[3] = 1；当n＞3时，就要推公式再进行递归求解。第n年的母牛数可以分为两部分：第一部分为第n−1年的母牛总数；第二部分为第n年年初刚生育的小牛数，而第n年年初刚生育的小牛数等于第n−3年的母牛总数。所以，当n＞3时，cow[n] = cow[n−1] +cow[n−3]。【参考代码】 1.#include 2.#include 3.#include 4.#include 5.using namespace std； 6. 7.const int N = 60； 8.int CowNumber（int n） 9.{ 10. if（n<4） return n； 11. else return CowNumber（n-1） + CowNumber（n-3）； 12.} 13.int main（） 14.{ 15. int n； 16. while（scanf（＂%d＂，&n）！=EOF && n！=0） 17. { 18. printf（＂%d\n＂，CowNumber（n））； 19. } 20. return 0； 21.}【注意】直接return CowNumber（n−1） + CowNumber（n−3），会出现多次重复不必要的调用，可以使用数组Cow[i]进行记忆化递归，如下。 1.int Cow[N]； 2.int CowNumber（int n） 3.{ 4. if（Cow[n]） return Cow[n]； 5. 6. if（n<4） return Cow[n] = n； 7. else return Cow[n] = CowNumber（n-1） + CowNumber（n-3）； 8.} 使用数组后，可以避免重复计算，当Cow[n]计算之后，直接返回值，不需要继续进行递归求值。【题面描述2（HDU 2047）】 某一年的ACM暑期集训队共有18人，分为6支队伍。其中有一个叫EOF的队伍，由2004级的阿牛、XC以及2005级的COY组成。在共同的集训生活中，大家建立了深厚的友谊，阿牛准备做点什么来纪念这段激情燃烧的岁月，想了想，阿牛从家里拿来一块上等的牛肉干，准备在上面刻下一个长度为n的只由“E” “O”“F”这3种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符），阿牛同时禁止在串中出现 O 相邻的情况，他认为，“OO”看起来就像一双发怒的眼睛，效果不好。 你能帮阿牛算一下共有多少种满足要求的不同的字符串吗？【输入】 输入数据包含多个测试实例，每个测试实例占一行，由一个整数n（0 < n < 40）组成。【输出】 对于每个测试实例，请输出全部满足要求的刻法，每个实例的输出占一行。【Sample Input】 1 2【Sample Output】 3 8【思路分析】 因为两个 O 不能连在一起，所以考虑两种单独的情况。设长度为 n 时的x[n]=a[n]+b[n]，其中，a[n]代表长度为n时末尾为O的情况总和，b[n]代表长度为n时末尾不为O的情况总和。 那么分情况讨论： 当长度为n，末尾为O时，再加一个单位的长度有两种加法，即E，F。 当长度为n，末尾不为O时，再加一个单位的长度有3种加法，即E，O，F。 所以x[n+1]=a[n+1]+b[n+1]=2*a[n]+3*b[n]=2*x[n]+b[n]。 而b[n]又由x[n−1]推来，x[n−1]=a[n−1]+b[n−1]，在长度为n−1且末尾为O时，要将它变成长度为n且末尾不为O有两种方法（E，F），即2*a[n−1]。 同理，在长度为n−1且末尾不为O时，要将它变成长度为n且末尾不为O有两种方法（E，F），即2*b[n−1]。 所以x[n+1]=2*x[n]+b[n]=2*x[n]+2*x[n−1]。【参考代码】 1.#include 2. 3.int main（） 4.{ 5. arr[1]=3； 6. arr[2]=8； 7. for（int i=3；i 8. int n； 9. while（～scanf（＂%d＂，&n）） 10. { 11. printf（＂%lld\n＂，arr[n]）； 12. } 13. return 0； 14.}【题面描述3（HDU 2045）】 著名的RPG难题如下。 有排成一行的n个方格，用红（Red）、粉（Pink）、绿（Green）3色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色，求全部满足要求的涂法。【输入】 输入数据包含多个测试实例，每个测试实例占一行，由一个整数组（0，50]组成。【输出】 对于每个测试实例，请输出全部满足要求的涂法，每个实例的输出占一行。【Sample Input】 1 2【Sample Output】 3 6【思路分析】 与例题2类似，当长度为n时，满足要求的涂法为x[n]，设3种颜色为A、B、C，由x[n]推出x[n+1]。 若长度为 n 时，序列为 ABC…BAC，那么在后面加一个，只有一种加法，因为既要与开头不一样又要与末尾不一样，所以只能加B，因此从n变为n+1只有一种方法。 然而，还有种情况忽略了，就是当长度为n−1时，序列为ABC…CB时，若在其后加一个A变成ABC…CBA 是不符合题意的，但可以在后面加两个让其变得有意义，如ABC…CBAC或者ABC…CBAB，可得出从n−1变为n+1有两种方法。所以，可以推出公式x[n]=x[n−1]+2*x[n−2]。【参考代码】 1.#include 2. 3.int main（） 4.{ 5. arr[1]=3； 6. arr[2]=arr[3]=6； 7. for（int i=4；i 8. { 9. arr[i]=arr[i-1]+2＊arr[i-2]； 10. } 11. int n； 12. while（～scanf（＂%d＂，&n）） 13. { 14. printf（＂%lld\n＂，arr[n]）； 15. } 16. return 0； 17.}【习题推荐】 HDU.2044 HDU.2049 HDU.20502.4 贪心 贪心算法是指在对问题求解时，总是选取当前最优策略的算法，其不是从整体上考虑，而是从某种意义上得到局部的最优解。使用贪心算法时，一定要保证无后效性，即当前选择的状态不会对以后的状态产生影响。求解时，把问题分为若干个子问题，对每个子问题进行求解，得到子问题的局部最优解，因为其满足无后效性，局部最优能导致全局最优。2.4.1 从局部分析【题面描述1（HDU1789）】 Ignatius有很多作业要做，每门作业都有一个最迟期限，如果没有在最迟期限内完成，就会扣除相应的分数。假设做每门作业都要一天的时间，你能帮他规划出扣分最少的做作业顺序吗？【输入】 输入包含多组测试。输入的第一行为一个数T，表示测试组数，接下来包括T组测试数据，每组测试数据的第一行为一个整数N（1≤N≤1000），表示作业门数，接下来有两行，第一行有N个数字，分别表示每门作业的最迟期限，第二行有N个数字，分别表示未完成作业扣除的相应分数。【输出】 对于每组测试数据，输出扣除的最少分数，每行对应一个数据答案。【Sample Input】 3 3 3 3 3 10 5 1 3 1 3 1 6 2 3 7 1 4 6 4 2 4 3 3 2 1 7 6 5 4【Sample Output】 0 3 5【思路分析】 题目中求解扣除的最少分数，那么从分数下手，优先完成分数高的作业，所以将作业按照分数进行排序，其次考虑怎样安排顺序。用样例3来分析，假如第一天做了分数为3的作业，第二天做了分数为6的作业，第三天做了分数为4的作业，那么第四天会选择分数更高的7来完成作业，若这样安排，扣除的分数为7，很明显不是最优。其实可以把第三天的时间用来做分数为5的作业，第一天拿来做分数为4的作业，这样就能达到最优，所以我们不能正向考虑，应该把时间用来做尽可能分数高的作业，直接按照时间从大到小进行枚举，判断在最迟期限前是否能完成它，需要用到一个标记数组来辅助判断该天是否已被占用。【参考代码】 1.#include 2.#include 3.#include 4.#include 5.using namespace std； 6. 7.const int N = 1010； 8. 9.struct Work{ 10. int time； 11. int score； 12. friend bool operator < （const Work &a，const Work &b） 13. { 14. return a.score > b.score； //时间按照从大到小排序 15. } 16.}work[N]； 17. 18.bool done[N]； 19. 20.int main（） 21.{ 22. int T； 23. scanf（＂%d＂，&T）； 24. while（T--） 25. { 26. int n； 27. scanf（＂%d＂，&n）； 28. for（int i=1；i<=n；i++） scanf（＂%d＂，&work[i].time）； 29. for（int i=1；i<=n；i++） scanf（＂%d＂，&work[i].score）； 30. 31. sort（work+1，work+1+n）； 32. 33. int ans = 0； 34. memset（done，false，sizeof（done））； 35. for（int i=1；i<=n；i++） 36. { 37. if（done[work[i].time]） //如果最迟期限那天被占用了 38. { 39. int x = work[i].time； 40. while（x && done[x]） x--； //向前枚举，寻找是否有空闲天 41. if（x） done[x] = true； //如果找到，标记这天已被占用 42. else ans += work[i].score； //否则，表示这门作业无法完成 43. } 44. else done[work[i].time] = true； //如果最迟期限没被占用，则在当天完成该作业 45. } 46. printf（＂%d\n＂，ans）； 47. } 48. return 0； 49.}2.4.2 根据不等式确定贪心策略【题面描述2（POJ 3262）】 农夫去砍柴，留下了N（2≤N≤100 000）头牛吃草，等农夫砍柴回来发现所有的牛在花园中破坏花朵。农夫决定依次把每头牛牵回牛棚，但在这个过程中，其他仍留在花园中的牛会继续破坏花朵，牵一头牛回牛棚的单程时间为 Ti（1≤Ti≤2，000，000），牛在花园中每分钟破坏花朵数为Di（1≤Di≤100）。请编写一段程序，决定牵牛回牛棚的顺序以保证破坏的总花朵数最少。【输入】 第一行：一个整数N 第二行到第N−1行：每一行包括两个整数，分别表示为Ti和Di。【输出】 输出一个数字表示被破坏的最少花朵数。【Sample Input】 6 31 25 23 32 41 16【Sample Output】 86【思路分析】 因为牵一头牛的单程时间是Ti，当把一头牛牵到牛棚再回来牵第二头牛的时间为2*Ti，假设两头牛分别为CowX、CowY，分别对应CowXt、CowXd、CowYt、CowYd。 如果先牵CowX，那么被破坏的花朵数为2*CowXt*CowYd。 如果先牵CowY，那么被破坏的花朵数为2*CowYt*CowXd。 对于上面两个式子同时除以2*CowXt*CowYt；可以分别得到CowYd/CowYt，CowXd/CowXt。 那么当 CowYd/CowYt＜CowXd/CowXt 时，表示先牵 CowX 更优，反之则牵Cow Y更优，综上把每头牛的Di和Ti相除按照从大到小的顺序排序，再枚举可求值。【参考代码】 1.#include 2.#include 3.#include 4.#include 5.using namespace std； 6.typedef long long LL； 7.const int N = 100000 + 100； 8.struct Node 9.{ 10. int t，d； 11. friend bool operator < （const Node a，const Node b） 12. { 13. return 1.0＊a.d/a.t > 1.0＊b.d/b.t； 14. } 15.}arr[N]； 16.int main（） 17.{ 18. int n； 19. while（～scanf（＂%d＂，&n）） 20. { 21. LL sumd = 0； 22. for（int i=1；i<=n；i++）scanf（＂%d %d＂，&arr[i].t，&arr[i].d），sumd += arr[i].d； 23. sort（arr+1，arr+1+n）； 24. LL ans = 0； 25. for（int i=1；i<=n；i++） 26. { 27. sumd-= arr[i].d； 28. ans += arr[i].t ＊2 ＊ sumd； 29. } 30. cout << ans< 31. } 32. return 0； 33.}2.5 二分 二分搜索又称为折半搜索。使用二分时，要确保数列是具有有序性的，通过比较中间值，不断将搜索范围缩小为原来的一半，大大缩n短了查找的时间，其时间复杂度为O（log）。2.5.1 从有序数组中查找值 在算法竞赛中，二分使用的频率十分广泛，常见的二分问题包括：判断某个值是否出现在数组中，如果出现则求出坐标；找出第一个比X值大的数的坐标；X 值第一次出现在数组中的位置等。这些问题都可以统称为“从有序数组中查找值”，求解的过程大致相似，区别在于二分的迭代条件不同，需要根据具体的情况调整。【题面描述1】 一个长度为N的有序且不重复的数组，请判断数字X是否出现在数组中。【输入】 第一行两个整数 N（1≤N≤1000）和 X，第二行 N 个数，按照从小到大的顺序。【输出】 如果X出现在数组中，请输出X的下标，否则输出−1（数组下标从1开始）。【Sample Input】 65 1 2 4 5 8 11【Sample Output】 4【思路分析】 用图示来表示二分的过程，如图2-1所示。图2-1 二分过程 从图2-1中可以看出二分的过程：先找到搜索区间[l，r]，然后对比mid位置的值与待查找值的大小。当 value[mid]大于待查找的值时，说明待查找的值位于[l，mid−1]内；当value[mid]小于待查找的值时，说明待查找的值位于[mid+1，r]内；若二者值相等，则成功匹配。【参考代码】 1.#include 2.#include 3.#include 4.using namespace std； 5. 6.const int N = 1010； 7.int a[N]； 8. 9.int main（） 10.{ 11. int n，x； 12. scanf（＂%d %d＂，&n，&x）； 13. for（int i=1；i<=n；i++） scanf（＂%d＂，&a[i]）； 14. int ans =-1； 15. int l = 1，r = n； 16. while（l<=r） 17. { 18. int mid = （l+r）/2； 19. if（x==a[mid]） 20. { 21. ans = mid； 22. break； 23. } 24. else if（x>a[mid]） l = mid+1； 25. else r = mid-1； 26. } 27. printf（＂%d\n＂，ans）； 28. return 0； 29.}【题面描述2（HDU 2578）】 有n个数和一个整数K，从这n个数中找出两个数，使这两个数的和为K，请问有多少组数满足该条件（两个数的位置不同也算一种情况）。【输入】 第一行，一个整数T，表示有T组数据。 第二行，两个整数，分别为N，K，n（2≤n≤100000），k（0≤31k<2）。 第三行，N个数。【输出】 对于每组数据，输出这个问题的解。【Sample Input】 2 54 1 2 3 4 5 88 1 4 5 7 8 9 2 6【Sample Output】 3 5【思路分析】 此题可以枚举这N个数，对于枚举的数X，判断K−X是否存在于数组中，由于K值范围较大，建立相应的hash表可能超出内存，于是就转化为经典的二分问题，二分时要先将数组排序。【参考代码】 1.#include 2.#include 3.#define INF 0x3f3f3f3f 4.using namespace std； 5.int a[100005]，n，k； 6.int judge（int l，int r，int x） 7.{ 8. while（l<=r） 9. { 10. int mid=（l+r）/2； 11. if（a[mid]+x==k） 12. return 1； 13. else 14. { 15. if（a[mid]+x>k） 16. r=mid-1； 17. else 18. l=mid+1； 19. } 20. } 21. return 0； 22.} 23.int main（） 24.{ 25. int t； 26. scanf（＂%d＂，&t）； 27. while（t--） 28. { 29. int ans=0； 30. scanf（＂%d%d＂，&n，&k）； 31. for（int i=1； i<=n； i++） 32. scanf（＂%d＂，&a[i]）； 33. a[0]=-INF； 34. sort（a，a+n+1）； 35. for（int i=1； i<=n； i++） 36. { 37. if（a[i]>k||a[i]==a[i-1]） 38. continue； 39. if（judge（1，n，a[i]））//从a[1]到a[n]中查找与a[i]相加符合条件的 40. ans++； 41. } 42. printf（＂%d\n＂，ans）； 43. } 44. return 0； 45.} 在C++的标准库中，有两个二分函数：upper_bound（）和lower_bound（）。两个函数的用法类似，在一个左闭右开的有序区间中进行二分查找，需要查找的值由第3个参数给出。 对于 upper_bound 来说，返回的是被查序列中第一个大于查找值的指针，即返回指向被查值>查找值的最小指针；lower_bound则是返回被查序列中第一个大于等于查找值的指针，即返回指向被查值≥查找值的最小指针。例如，map中已经插入了1，2，2，3，4，lower_bound（2）返回的是map[1] = 2，而upper_bound （2）返回的是map[3] = 3。 1.#include 2.#include 3. 4.using namespace std； 5. 6.int main（） 7.{ 8. int point[10] = {1，2，2，3，4}； 9. int pos1 = upper_bound（point，point+5，2）-point； 10. int pos2 = lower_bound（point，point+5，2）-point； 11. cout << pos1 << ＂ ＂<< pos2 << endl； 12. cout << point[pos1] << ＂ ＂ << point[pos2] < 13. return 0； 14.} 输出为 3 1 3 22.5.2 “最小值最大化”问题【题面描述3（POJ2456）】 在一条水平线上有N（2≤N≤100 000）个牛棚，每个牛棚都有一个坐标，把C（2≤C≤N）头牛分别拴在这些牛棚中，由于这些牛易怒，
试读结束[说明：试读内容隐藏了图片]