近三年，笔者在工作及创作之余，一直在参与大学生ACM/ICPC以及中学生NOI系列竞赛的培训工作，在此期间认识了很多朋友，大家一起交流算法学习及比赛趣事，互相促进，甚是开心。

    很多算法初学者，甚至一些算法高手，都跟我反馈，弄明白算法的基本原理之后，迫切地希望能有一本介绍相关算法代码实现的图书，以方便大家在练习环节和比赛时作为参考。对于大学生来说，因为ICPC竞赛允许自带资料，因此他们对这样的算法代码实现书有着更迫切的期望，通过调用这些简洁、规范的代码实现，可以大大减轻他们比赛时因来回琢磨代码实现细节而导致调试时间大幅增加的压力。

    而在省选以及NOI赛场上也出现过因为没有掌握较好的模板代码，导致考场上实现时间大幅度增加，终与奖牌失之交臂的憾事。许多中学生在学习计算几何时并不知道刘汝佳老师在《算法竞赛入门经典（第2版）》《算法竞赛入门经典——训练指南》中提供了简洁、完整的模板代码，这也是本书创作的一个动机。

    本书内容

    本书不介绍具体的算法理论知识，而是精选《算法竞赛入门经典（第2版）》和《算法竞赛入门经典——训练指南》中的典型题目，按算法要点和竞赛考点重新进行分拆和归类，并提供240余套简洁、高效、规范、完整的实现代码模板。此外，也加入了一些虽然未在两本书中出现，但实际上对初学者入门非常重要的题目代码。

    全书共分为7章，各章的具体内容如下。

    第1章介绍C 编程基础与STL中的常用算法实现，共计15道真题的算法实现。 

    第2章介绍算法设计与优化，包含算法优化策略、贪心算法、搜索算法、动态规划算法等内容，共计56道真题的算法实现。

    第3章介绍数学相关算法，包含数论、组合计数、概率与期望、组合游戏、置换、矩阵和线性方程组、快速傅里叶变换（FFT）、数值方法、数学专题等内容，共计46道真题的算法实现。

    第4章介绍数据结构相关算法，包含基础数据结构、区间信息维护、排序二叉树、树的经典问题与方法、动态树与LCT、离线算法、kd-tree、可持久化数据结构、嵌套和分块数据结构等内容，共计52道真题的算法实现。

    第5章介绍字符串相关算法，包含Trie与KMP以及AC自动机、后缀数组、后缀自动机等内容，共计13道真题的算法实现。

    第6章介绍计算几何相关算法，包含二维几何基础、圆有关的计算问题、二维几何常用算法、三维几何基础、几何专题算法等内容，共计21道真题的算法实现。

    第7章介绍图论相关算法，共包含深度优先遍历、短路问题、生成树相关问题、二分图匹配、网络流问题，共计36道真题的算法实现。

    本书只关注近些年在正式比赛（包括ACM/ICPC区域赛、NOIP以及NOI这样的全国性比赛）中常见的算法实现。书中所有真题都极具典型性，每道题在求解过程中都经过了严密、仔细的剖析和反复的优化，终择选较优的算法代码进行实现。

    系列书学习说明

    至此，“算法艺术与信息学竞赛”系列已包含如下4本书。

    《算法竞赛入门经典（第2版）》（以下简称《入门经典》），是系列中的核心算法理论书。如果你是个新手，刚刚步入信息学奥赛大阵营，欢迎你学习此书，它将系统地讲解C/C 语言基础知识，数据结构知识，以及信息学奥赛和ACM/ICPC中的常考必考算法知识点、技巧和剖析。

    《算法竞赛入门经典——训练指南》是《入门经典》的姊妹篇，主要针对更多的算法竞赛题型进行横向拓展，以及更广范围内的讲解和训练，“覆盖面广，点到为止，注重代码”是本书的特点。

    《算法竞赛入门经典——习题与解答》是《入门经典》的配套习题详解，将其中的多数练习题，尤其是限于篇幅无法展开的练习题，进行了细致的解析，使其更简单、易学，快速提升读者的算法思维能力。更适合初学者配合着《入门经典》一起学习。

    《算法竞赛入门经典——算法实现》是一本高效备考工具书，择选近些年来信息学奥赛中、经典的比赛真题，给出优化过的各类代码实现模板，通过它可快速备考各类竞赛。

    读者可以根据自己的学习情况和备战目标，分时分段选择不同的图书，以效果地发挥“1 1>2”的事半功倍的效果。

    感谢广大读者朋友们，你们的信任和支持是我在算法道路上能持续前行的动力。

    祝大家读书快乐！

    《算法竞赛入门经典——算法实现》精选《算法竞赛入门经典（第2版）》和《算法竞赛入门经典——训练指南（升级版）》中的经典题目，按算法要点和竞赛考点重新进行分拆和归类，提供了240余套简洁、高效、规范的完整代码模板。此外，也加入了一些虽然未在两本书中出现，但实际上对初学者入门非常重要的题目代码。借助于这些模板，读者在练习环节和比赛时，可大大减轻因来回琢磨代码实现细节而导致调试时间大幅增加的压力。

    《算法竞赛入门经典——算法实现》共分7章，第1章介绍C 编程基础与STL，第2章介绍算法设计与优化，第3章介绍数学相关算法，第4章介绍数据结构，第5章介绍字符串，第6章介绍计算几何，第7章介绍图论。

    《算法竞赛入门经典——算法实现》题目覆盖了ACM/ICPC/NOI/NOIP等算法竞赛的大多数经典题型和细分算法要点，内容全面，信息量大，非常适合选手在练习环节和比赛时参考使用。

    陈锋，任职于厦门宇道信隆信息科技有限公司，担任技术总监职务，专注于人工智能以及算法技术在金融科技领域的应用。同时担任四川大学ACM/ICPC算法竞赛集训队特邀指导老师，榕阳编程NOI、NOIP指导教练。所带学员多次获得ICPC金/银牌，进入NOI省队等。曾出版《算法竞赛入门经典——训练指南》《算法竞赛入门经典——习题与解答》《算法竞赛入门经典——算法实现》等畅销书。

第1章 C 编程基础与STL 1

第2章 算法设计与优化 20

2.1 算法优化策略 20

2.2 贪心算法 28

2.3 搜索算法 34

2.4 动态规划算法 60

第3章 数学 91

3.1 数论 91

3.2 组合计数 113

3.3 概率与期望 127

3.4 组合游戏 134

3.5 置换 136

3.6 矩阵和线性方程组 139

3.7 快速傅里叶变换（FFT） 146

3.8 数值方法 156

3.9 数学专题 159

第4章 数据结构 165

4.1 基础数据结构 165

4.2 区间信息维护 188

4.3 排序二叉树 202

4.4 树的经典问题与方法 212

4.5 动态树与LCT 229

4.6 离线算法 237

4.7 kd-Tree 249

4.8 可持久化数据结构 254

4.9 嵌套和分块数据结构 263

第5章 字符串 275

5.1 Trie、KMP以及AC自动机 275

5.2 后缀数组、Hash和Manacher 282

5.3 后缀自动机 287

第6章 计算几何 298

6.1 二维几何基础 298

6.2 与圆有关的计算问题 302

6.3 二维几何常用算法 311

6.4 三维几何基础 328

6.5 几何专题算法 342

第7章 图论 362

7.1 深度优先遍历 362

7.2 短路问题 374

7.3 生成树相关问题 395

7.4 二分图匹配 404

7.5 网络流问题 420

    《算法竞赛入门经典——算法实现》精选《算法竞赛入门经典（第2版）》和《算法竞赛入门经典——训练指南（升级版）》中的经典题目，按算法要点和竞赛考点重新进行分拆和归类，提供了240余套简洁、高效、规范的完整代码模板。此外，也加入了一些虽然未在两本书中出现，但实际上对初学者入门非常重要的题目代码。借助于这些模板，读者在练习环节和比赛时，可大大减轻因来回琢磨代码实现细节而导致调试时间大幅增加的压力。

    《算法竞赛入门经典——算法实现》共分7章，第1章介绍C 编程基础与STL，第2章介绍算法设计与优化，第3章介绍数学相关算法，第4章介绍数据结构，第5章介绍字符串，第6章介绍计算几何，第7章介绍图论。

    《算法竞赛入门经典——算法实现》题目覆盖了ACM/ICPC/NOI/NOIP等算法竞赛的大多数经典题型和细分算法要点，内容全面，信息量大，非常适合选手在练习环节和比赛时参考使用。

    陈锋，任职于厦门宇道信隆信息科技有限公司，担任技术总监职务，专注于人工智能以及算法技术在金融科技领域的应用。同时担任四川大学ACM/ICPC算法竞赛集训队特邀指导老师，榕阳编程NOI、NOIP指导教练。所带学员多次获得ICPC金/银牌，进入NOI省队等。曾出版《算法竞赛入门经典——训练指南》《算法竞赛入门经典——习题与解答》《算法竞赛入门经典——算法实现》等畅销书。

第1章  C 编程基础与STL

STL是C 标准模板库（Standard Template Library）的简称，使用得当能够省去不少代码篇幅。

例1-1  【输入输出函数】TeX中的引号（Tex Quotes, UVa 272）

在TeX中，左双引号是“``”，右双引号是“''”。输入一篇包含双引号的文章，你的任务是把它转换成TeX的格式。

【样例输入】

"To be or not to be," quoth the Bard, "that

is the question".

【样例输出】

``To be or not to be, '' quoth the Bard, ``that

is the question''.

【代码实现】

// 陈锋

#include <cstdio>

int main() {

  int c, first = 1;

  char s[2][4] = {"''", "``"};

  while ((c = getchar()) != EOF) {

    if (c == '"')

      printf("%s", s[first]), first ^= 1;

    else

      printf("%c", c);

  }

  return 0;

}

/*

算法分析请参考:《算法竞赛入门经典（第2版）》例题3-1

注意：本题是如何使用first变量及其xor运算来控制是否为首次输出的

*/

例1-2  【计数排序与IO优化】年龄排序（Age Sort, UVa 11462）

给定n（0＜n≤2 000 000）个居民的年龄（都是1～100的整数），把它们按照从小到大的顺序输出。

【代码实现】

// 陈锋

#include <bits/stdc .h>

using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); i)

typedef long long LL;

const int MAXN = 100;

int main() {

  int n, a, cnt[MAXN 4];

  while (scanf("%d", &n) == 1 && n) {

    fill_n(cnt, MAXN 4, 0);

    _for(i, 0, n) scanf("%d", &a), cnt[a];

    _for(i, 0, MAXN) _for(j, 0, cnt[i])

      printf("%d%s", i, (i == MAXN - 1 && j == cnt[i] - 1) ? "" : " ");

    puts("");

  }

}

/*

算法分析请参考:《算法竞赛入门经典—训练指南》升级版1.3节例题17

注意：本题中的fill_n函数比memset更方便，性能更好

*/

如果还要精益求精，可以优化输入输出，进一步降低运行时间，程序如下。

// 刘汝佳

#include <cstdio>

#include <cstring>

#include <cctype>               // 为了使用isdigit宏

inline int readint() {

  char c = getchar();

  while(!isdigit(c)) c = getchar();

  int x = 0;

  while(isdigit(c)) {

    x = x * 10 c - '0';

    c = getchar();

  }    

  return x;

}

int buf[10];                    // 声明为全局变量可以减小开销

inline void writeint(int i) {

  int p = 0;if(i < 0) putchar('-'), i = -i;

  if(i == 0) p ;               // 特殊情况：i等于0时需要输出0，而不是什么也不输出

  else while(i) {

    buf[p ] = i % 10,i /= 10;

  }

  for(int j = p - 1; j >= 0; j--) putchar('0' buf[j]); // 逆序输出

}

int main() {

  int n, x, c[101];

  while(n = readint()) {

    memset(c, 0, sizeof(c));

    for(int i = 0; i < n; i ) c[readint()] ;

    int first = 1;

    for(int i = 1; i <= 100; i )

      for(int j = 0; j < c[i]; j ) {

        if(!first) putchar(' ');

        first = 0;

        writeint(i);

      }

    putchar('\n');

  }

  return 0;

}

例1-3  【字符函数；常量数组】回文词（Palindromes, UVa 401）

输入一个字符串，判断它是否为回文串以及镜像串。输入字符串保证不含数字0。所谓回文串，就是反转以后和原串相同，如abba和madam。所谓镜像串，就是左右镜像之后和原串相同，如2S和3AIAE。注意，并不是每个字符在镜像之后都能得到一个合法字符。在本题中，每个字符的镜像如图1-1所示（空白项表示该字符镜像后不能得到一个合法字符）。

图1-1  镜像字符

输入的每行包含一个字符串（保证只有上述字符，不含空白字符），判断它是否为回文串和镜像串（共4种组合）。每组数据之后输出一个空行。

【样例输入】

NOTAPALINDROME

ISAPALINILAPASI

2A3MEAS

ATOYOTA

【样例输出】

NOTAPALINDROME -- is not a palindrome.

ISAPALINILAPASI -- is a regular palindrome.

2A3MEAS -- is a mirrored string.<