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

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

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

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

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.

ATOYOTA -- is a mirrored palindrome.

【代码实现】

// 刘汝佳

#include <bits/stdc++.h>

using namespace std;

string rev = "A   3  HIL JM O   2TUVWXY51SE Z  8 ",

  msg[] = {

    "not a palindrome",

    "a regular palindrome",

    "a mirrored string",

    "a mirrored palindrome"

  };

char r(char c) {

  if (isalpha(c)) return rev[c - 'A'];

  return rev[c - '0' + 25];

}

int main() {

  char s[32];

  while (scanf("%s", s) == 1) {

    int len = strlen(s), p = 1, m = 1;

    for (int i = 0; i < (len + 1) / 2; i++) {

      if (s[i] != s[len - 1 - i]) p = 0;        // 不是回文串

      if (r(s[i]) != s[len - 1 - i]) m = 0;     // 不是镜像串

    }

    printf("%s -- is %s.\n\n", s, msg[m * 2 + p]);

  }

  return 0;

}

/*

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

注意：本题中输入字符串应该使用scanf而不是gets，以避免出现读入空行的问题

*/

例1-4  【字典序】环状序列（Circular Sequence, ACM/ICPC Seoul 2004, UVa 1584）

长度为n的环状串有n种表示方法，分别为从某个位置开始顺时针得到的字母序列。例如，图1-2所示的环状串有10种表示方法：CGAGTCAGCT、GAGTCAGCTC、AGTCAGCTCG等。在这些表示法中，字典序最小的称为“最小表示”。

输入一个长度为n（n≤100）的环状DNA串（只包含A、C、G、T这4种字符）。输入样式对应该串所有表示方法中的一种表示法，你的任务是输出该环状串的最小表示。例如， CTCC的最小表示是CCCT，CGAGTCAGCT的最小表示为AGCTCGAGTC。

【代码实现】

// 刘汝佳

#include <bits/stdc++.h>

using namespace std;

// 环状串s的表示法p是否比表示法q的字典序小

int less_than(const string& s, int p, int q) {

  int n = s.length();

  for (int i = 0; i < n; i++) {

    char cp = s[(p + i) % n], cq = s[(q + i) % n];

    if (cp != cq) return cp < cq;

  }

  return 0;  // 相等

}

int main() {

  ios::sync_with_stdio(false), cin.tie(0);

  int T;

  string s;

  cin >> T;

  while (T--) {

    cin >> s;

    int ans = 0, n = s.length();

    for (int i = 1; i < n; i++)

      if (less_than(s, i, ans)) ans = i;

    for (int i = 0; i < n; i++) cout << (s[(ans + i) % n]);

    cout << endl;

  }

  return 0;

}

/*

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

注意：main()函数的第一行可以加速STL的IO操作，但不能再和stdio中的printf混用

同类问题：Periodic Strings, UVa 455

*/

目录

第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