第 2 章 经典入门

一 排序

例 2.1 排序

• 代码 2.1

  冒泡排序（时间复杂度 $O(n^2)$）

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  #include <algorithm>
  using std::swap;
  
  bool bubble(int lo, int hi, vector<int> &ivec) {
      bool sorted = true;     // 整体有序标志
      while (++lo < hi)       // 自左向右，逐一检查各对相邻元素
          if (ivec[lo - 1] > ivec[lo]) {  // 若逆序，则
              sorted = false; // 意味着尚未整体有序，并需要
              swap(ivec[lo - 1], ivec[lo]);   // 交换
          }
      return sorted;
  }
  
  void bubbleSort(int lo, int hi, vector<int> &ivec) {
      while (!bubble(lo, hi--, ivec));   // 逐趟做扫描交换，直至全序
  }
  
  int main() {
      int n;
      vector<int> ivec;
      cin >> n;
      while (n--) {
          int temp;
          cin >> temp;
          ivec.push_back(temp);
      }
      bubbleSort(0, ivec.size(), ivec);   // 对区间 [0, ivec.size()) 冒泡排序
      for (auto e : ivec)
          cout << e << " " << endl;
      return 0;
  }
  

  冒泡排序改进版：

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  #include <algorithm>
  using std::swap;
  
  int bubble(int lo, int hi, vector<int> &ivec) {
      int last = lo;      // 最右侧的逆序对初始化为 [lo - 1, lo]
      while (++lo < hi)   // 自左向右，逐一检查各对相邻元素
          if (ivec[lo - 1] > ivec[lo]) {  // 若逆序，则
              last = lo;  // 更新最右侧逆序对位置记录，并
              swap(ivec[lo - 1], ivec[lo]);   // 交换
          }
      return last;
  }   // 前一版本中的逻辑型标志 sorted，改为秩 last
  
  void bubbleSort(int lo, int hi, vector<int> &ivec) {
      while (lo < (hi = bubble(lo, hi, ivec)));   // 逐趟做扫描交换，直至全序
  }
  
  int main() {
      int n;
      vector<int> ivec;
      cin >> n;
      while (n--) {
          int temp;
          cin >> temp;
          ivec.push_back(temp);
      }
      bubbleSort(0, ivec.size(), ivec);   // 对区间 [0, ivec.size()) 冒泡排序
      for (auto e : ivec)
          cout << e << " " << endl;
      return 0;
  }
  

• 代码 2.2

  快速排序（时间复杂度 $O(nlogn)$）

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  #include <algorithm>
  using std::sort;
  
  int main() {
      int n;
      vector<int> ivec;
      cin >> n;
      while (n--) {
          int temp;
          cin >> temp;
          ivec.push_back(temp);
      }
      sort(ivec.begin(), ivec.end());		// C++ sort 底层实现是快速排序
      // sort(ivec.begin(), ivec.end(), less<int>());		// 也可以自己指定第三个参数
      for (auto e : ivec)
          cout << e << " " << endl;
      return 0;
  }
  

  Standard library header

  也可以自定义 sort 的第三个参数

  比如将该例题降序排列：

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  #include <algorithm>
  using std::sort;
  
  #include <functional>
  using std::greater;
  
  bool cmp(int x, int y) {
      return x > y;
  }
  
  int main() {
      int n;
      vector<int> ivec;
      cin >> n;
      while (n--) {
          int temp;
          cin >> temp;
          ivec.push_back(temp);
      }
      // sort(ivec.begin(), ivec.end(), greater<int>());
      sort(ivec.begin(), ivec.end(), cmp);
      for (auto e : ivec)
          cout << e << " " << endl;
      return 0;
  }
  

  各种排序算法（选择排序+有序向量合并+归并排序+快速排序）

  template <typename T>
  Rank Vector<T>::max(Rank lo, Rank hi) {     // 在 [lo, hi] 内找出最大者
      Rank mx = hi;
      while (lo < hi--)   // 逆向扫描
          if (_elem[hi] > _elem[mx])  // 且严格比较
              mx = hi;    // 故能在 max 有多个时保证后者有先，进而保证 selectionSort 稳定
      return mx;
  }
  
  template <typename T>   // 向量选择排序
  void Vector<T>::selectionSort(Rank lo, Rank hi) {   // 0 <= lo < hi <= size
      cout << "\tSELECTIONsort [" << lo << ", " << hi << "]" << endl;
      while (lo < hi) {
          swap(_elem[max(lo, hi)], _elem[hi]);    // 将 [hi] 与 [lo, hi] 中的最大者交换
          --hi;
      }
  }
  
  template <typename T>   // 有序向量（区间）的归并
  void Vector<T>::merge(Rank lo, Rank mi, Rank hi) {  // 各自有序的子向量 [lo, mi) 和 [mi, hi)
      T* A = _elem + lo;  // 合并后的向量 A[0, hi - lo) = _elem[lo, hi)
      int lb = mi - lo; T* B = new T[lb];     // 前子向量B[0, lb) = _elem[lo, mi)
      for (Rank i = 0; i < lb; B[i] = A[i++]);    // 复制前子向量B[0, lb) = _elem[lo, mi)
      int lc = hi - mi; T* C = _elem + mi;    // 后子向量C[0, lc) = _elem[mi, hi)
      for (Rank i = 0, j = 0, k = 0; j < lb || k < lc; ) {    // B[j]和C[k]中小者转至A的末尾
          if (j < lb && (lc <= k || B[j] <= C[k])) A[i++] = B[j++];   // C[k]已无或不小
          if (k < lc && (lb <= j || C[k] < B[j])) A[i++] = C[k++];    // B[j]已无或更大
      }
      delete [] B;    // 释放临时空间B
  }
  
  template <typename T>   // 向量归并排序
  void Vector<T>::mergeSort(Rank lo, Rank hi) {   // 0 <= lo < hi <= size
      cout << "\tMERGEsort [" << lo << ", " << hi << ")\n";
      if (hi - lo < 2) return;    // 单元素区间自然有序，否则...
      int mi = (lo + hi) / 2;     // 以中点为界
      mergeSort(lo, mi); mergeSort(mi, hi);   // 分别排序
      merge(lo, mi, hi);          // 归并
  }
  
  template <typename T>   // 轴点构造算法：通过调整元素位置构造区间[lo, hi)的轴点，并返回其秩
  Rank Vector<T>::partition(Rank lo, Rank hi) {   // 版本A：基本形式
      swap(_elem[lo], _elem[lo + rand() % (hi - lo)]);    // 任选一个元素与首元素交换
      hi--;   // [lo, hi)
      T pivot = _elem[lo];    // 以首元素为候选轴点（经以上swap函数交换，等效于随机选取
      while (lo < hi) {   // 从向量的两端交替地向中间扫描
          while ((lo < hi) && (pivot <= _elem[hi]))   // 在不小于pivot的前提下
              hi--;   // 向左拓展右端子向量
          _elem[lo] = _elem[hi];  // 小于pivot者归入左侧子序列
          while ((lo < hi) && (_elem[lo] <= pivot))   // 在不大于pivot的前提下
              lo++;   // 向右拓展左端子序列
          _elem[hi] = _elem[lo];  // 大于pivot者归入右侧子序列
      }   // assert: lo == hi
      _elem[lo] = pivot;  // 将备份的轴点记录置于前、后子向量之间
      return lo;  // 返回轴点的秩
  }
  
  template <typename T>   // 向量快速排序
  void Vector<T>::quickSort(Rank lo, Rank hi) {   // 0 <= lo < hi <= size
      cout << "\tQUICKsort [" << lo << ", " << hi << ")\n";
      if (hi - lo < 2) return;    // 单个元素区间自然有序，否则...
      Rank mi = partition(lo, hi);    // 在[lo, hi)内构造轴点
      quickSort(lo, mi);  // 对前缀递归排序
      quickSort(mi + 1, hi);  // 对后缀递归排序
  }
  

例 2.2 成绩排序

• 代码 2.4

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  #include <algorithm>
  using std::sort;
  
  #include <string>
  using std::string;
  
  class Students {
  private:
      string _name;
      unsigned _age;
      unsigned _score;
  public:
      bool operator<(const Students &b) const;   // C++ 运算符重载
      void setName(string studentName) { _name = studentName; }
      string getName() { return _name; }
      void setAge(unsigned studentAge) { _age = studentAge; }
      unsigned getAge() { return _age; }
      void setScore(unsigned studentScore) { _score = studentScore; }
      unsigned getScore() { return _score; }
  };
  
  bool Students::operator<(const Students &b) const {
      if (_score != b._score)   // 若分数不相同则分数低者在前
          return _score < b._score;
      int tmp = _name.string::compare(b._name);
      if (!tmp)               // 若分数相同则名字字典序小者在前
          return tmp < 0;
      else                    // 若名字也相同则年龄小者在前
          return _age < b._age;
  }
  
  int main() {
      int n;
      cin >> n;
      // Create a vector of Students objects
      vector<Students> v;
      string name;
      unsigned age, score;
      Students *p;
      while (n--) {
          cin >> name >> age >> score;
          p = new Students;
          p->setName(name), p->setAge(age), p->setScore(score);
          v.push_back(*p);
      }
      sort (v.begin(), v.end());  // 使用类 Students 自定义的 < 重载运算符
      for (auto e : v)
          cout << e.getName() << " "
               << e.getAge() << " "
               << e.getScore() << endl;
      return 0;
  }
  

  std::string::compare() in C++

二 日期类问题

例 2.3 日期差值

• 代码 2.6

  #include <stdio.h>
  
  // 定义宏判断是否是闰年，方便计算每月天数
  #define ISYEAP(y) y % 100 != 0 && y % 4 == 0 || y % 400 == 0 ? 1 : 0
  
  int dayOfMonth[13][2] = {
          {0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31},
          {30, 30}, {31, 31}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}
  };      // 预存每月的天数，注意二月配合宏定义做特殊处理
  struct Date {   // 日期类，方便日期的推移
      int Day, Month, Year;
      void nextDay();     // 计算下一天的日期
  };
  void Date::nextDay() {
      Day++;
      if (Day > dayOfMonth[Month][ISYEAP(Year)]) {    // 若日数超过了当月最大日数
          Day = 1;
          Month++;            // 进入下一月
          if (Month > 12) {   // 月数超过 12
              Month = 1;
              Year++;         // 进入下一年
          }
      }
  }
  int buf[3001][13][32];      // 保存预处理的天数
  int Abs(int x) {            // 求绝对值
      return x < 0 ? -x : x;
  }
  int main() {
      Date tmp;
      int cnt = 0;            // 天数计算
      tmp.Day = 1;
      tmp.Month = 1;
      tmp.Year = 0;           // 初始化日期类对象为 0 年 1 月 1 日
      while (tmp.Year != 3001) {      // 日期不超过 3000 年
          // 将该日期与 0 年 1 月 1 日的天数差保存起来
          buf[tmp.Year][tmp.Month][tmp.Day] = cnt;
          tmp.nextDay();      // 计算下一天日期
          // 计数器累加，每经过一天计数器即+1，代表与原点日期的间隔又增加一天
          cnt++;
      }
  
      int d1, m1, y1;
      int d2, m2, y2;
      while (scanf("%4d%2d%2d", &y1, &m1, &d1) != EOF) {
          scanf("%4d%2d%2d", &y2, &m2, &d2);      // 读入要计算的两个日期
          // 用预处理的数据计算两个日期差值，注意需对其求绝地值
          printf("%d\n", Abs(buf[y2][m2][d2] - buf[y1][m1][d1]) + 1);
      }
  
      return 0;
  }
  

  样例输入：

  20110412
  20110422
  

  样例输出：

  11
  

例 2.4 Day of week

• 代码 2.7

  #include <stdio.h>
  #include <cstring>  // using strcmp function
  
  // 定义宏判断是否是闰年，方便计算每月天数
  #define ISYEAP(y) y % 100 != 0 && y % 4 == 0 || y % 400 == 0 ? 1 : 0
  
  int dayOfMonth[13][2] = {
          {0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31},
          {30, 30}, {31, 31}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}
  };      // 预存每月的天数，注意二月配合宏定义做特殊处理
  struct Date {   // 日期类，方便日期的推移
      int Day, Month, Year;
      void nextDay();     // 计算下一天的日期
  };
  void Date::nextDay() {
      Day++;
      if (Day > dayOfMonth[Month][ISYEAP(Year)]) {    // 若日数超过了当月最大日数
          Day = 1;
          Month++;            // 进入下一月
          if (Month > 12) {   // 月数超过 12
              Month = 1;
              Year++;         // 进入下一年
          }
      }
  }
  int buf[3001][13][32];      // 保存预处理的天数
  char monthOfName[13][20] = {    // 下标1～12对应月名
          "", "January", "February", "March", "April", "May", "June",
          "July", "August", "September", "October", "November", "December"
  };
  char weekName[7][20] = {        // 下标0～6对应周名
          "Sunday", "Monday", "Tuesday", "Wednesday",
          "Thursday", "Friday", "Saturday"
  };
  int main() {
      Date tmp;
      int cnt = 0;            // 天数计算
      tmp.Day = 1;
      tmp.Month = 1;
      tmp.Year = 0;           // 初始化日期类对象为 0 年 1 月 1 日
      while (tmp.Year != 3001) {      // 日期不超过 3000 年
          // 将该日期与 0 年 1 月 1 日的天数差保存起来
          buf[tmp.Year][tmp.Month][tmp.Day] = cnt;
          tmp.nextDay();      // 计算下一天日期
          // 计数器累加，每经过一天计数器即+1，代表与原点日期的间隔又增加一天
          cnt++;
      }
  
      int d, m, y;
      char s[20];
      while (scanf("%d%s%d", &d, s, &y) != EOF) {
          for (m = 1; m <= 12; m++) {
              if (strcmp(s, monthOfName[m]) == 0) {
                  break;  // 将输入字符串与月名比较得出月数
              }
          }
          // 计算给定日期与今日日期的天数间隔（注意可能为负）
          int days = buf[y][m][d] - buf[2019][12][6];
          // 今天（2019.12.06）为星期一，对应数组下标为 1，则计算 1 经过 days 天后的下标
          days += 1;
          // 将计算后得出的下标用 7 对其取模，并且保证其为非负数，则该下标即为答案所对应的下标，输出即可
          puts(weekName[(days % 7 + 7) % 7]);
      }
  
      return 0;
  }
  

  样例输入：

  1 December 2019
  10 December 2019
  

  样例输出：

  Sunday
  Tuesday
  

三 Hash 的应用

例 2.5 统计相同成绩学生人数

• 代码 2.8

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <map>
  using std::map;
  
  int main() {
      int n;
      while (cin >> n && n != 0) {    // 输入判断增加对 n 是否等于零进行判断
          map<unsigned, unsigned> score_count;
          unsigned score;
          // 不能写为 cin >> score && n--，否则循环结束时，&& 短路求值，cin >> score 得到 x 的值
          while (n-- && cin >> score)
              ++score_count[score];
          unsigned x;
          cin >> x;
          cout << score_count[x] << endl;
      }
  
      return 0;
  }
  

  样例输入：

  3
  80 60 90
  60
  2
  85 66
  0
  5
  60 75 90 55 75 75
  0
  

  样例输出：

  1
  0
  2
  

例 2.6 Sort

• 代码 2.9

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <map>
  using std::map;
  
  #define OFFSET 500000   // 偏移量，用于补偿实际数字与数组下标之间偏移
  int main() {
      int n, m;
      cin >> n >> m;
      map<unsigned, unsigned> h;
      for (int i = 500000; i >= -500000; i--) {
          h[i + OFFSET] = 0;
      }   // 初始化，将每个数字都标记为未出现，即 0
      for (int i = 0; i < n; i++) {
          int x; cin >> x;
          ++h[x + OFFSET];   // 凡是出现过的数字，累计加 1
      }
      for (int i = 500000; i >= -500000; i--) {   // 输出前 m 大的数
          if (h[i + OFFSET]) {
              cout << i << " ";
              m--;
          }
          if (!m) {   // 若 m 个数已经输出完毕，则在输出的数字后面紧跟一个换行，并跳出循环
              cout << "\n";
              break;
          }
      }
  
      return 0;
  }
  

四 排版题

例 2.7 输出梯形

• 代码 2.10（规律性强，直接按规律输出）

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  int main() {
      // 每行 ' ' 和 '*' 总个数 s = h + 2 * (h - 1)
      // 第一行 '*' 有 h 个，以后每行 '*' 的个数较前一行加 2
      // 第一行 ' ' 有 s - h 个，以后每行 ' ' 的个数较前一行减 2
      // 总共输出 h 行
      int h;
      while (cin >> h) {
          int s = h + 2 * (h - 1);
          int row = h;
          for (int i = 0; i < row; i++) {     // 依次输出每行信息
              for (int j = 0; j < s; j++) {   // 依次输出每行当中的空格或星号
                  if (j < s - h - 2 * i)      // 输出空格
                      cout << " ";
                  else                        // 输出星号
                      cout << "*";
              }
              cout << endl;                   // 输出换行
          }
      }
  
      return 0;
  }
  

例 2.8 叠筐

• 代码 2.11（规律性不若，先排版后输出）

  #include <iostream>
  using std::cin; using std::cout;
  
  #define N 80
  int main() {
      int outPutBuf[N][N];    // 用于预排版的输出缓存
      char a, b;              // 输入的两个字符
      int n;                  // 叠筐大小
      bool firstCase = true;  // 是否为第一组数据标志，初始值为 true
      while (cin >> n >> a >> b) {
          if (firstCase == true) {    // 若是第一组数据
              firstCase = false;      // 将第一组数据标志记成 false
          } else                      // 否则输出换行
              cout << "\n";
          // i 表示每圈边长长度
          // j 的奇偶性确定每圈字符，以及用来辅助动态确定每圈左上角坐标
          for (int i = 1, j = 1; i <= n; i += 2, j++) {   // 从里到外
              int x = n / 2 + 1, y = x;
              x -= j - 1; y = x;              // 计算每个圈左上角点的坐标
              char c = j % 2 == 1 ? a : b;    // 计算当前圈的字符
              for (int k = 1; k <= i; k++) {  // 对当前圈进行赋值
                  outPutBuf[x + k - 1][y] = c;            // 左边赋值
                  outPutBuf[x][y + k - 1] = c;            // 上边赋值
                  outPutBuf[x + i - 1][y + k - 1] = c;    // 右边赋值
                  outPutBuf[x + k - 1][y + i - 1] = c;    // 下边赋值
              }
          }
          if (n != 1) {   // 注意，当 n 为 1 时，不需要此步骤
              outPutBuf[1][1] = ' ';
              outPutBuf[1][n] = ' ';
              outPutBuf[n][1] = ' ';
              outPutBuf[n][n] = ' ';      // 将四角置为空格
          }
          for (int i = 1; i <= n; i++) {  // 输出经过排版的在输出缓存中的数据
              for (int j = 1; j <= n; j++)
                  cout << (char)outPutBuf[i][j];
              cout << "\n";
          }
      }
  
      return 0;
  }
  

五 查找

例 2.9 找 x

• 代码 2.12

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  int main() {
      int n; cin >> n;
      int* A = new int[n];
      for (int i = 0; i < n; ++i) {
          int tmp; cin >> tmp;
          A[i] = tmp;
      }
      int x, ans = -1;    // 初始化答案为 -1，以期在找不到答案时能正确的输出 -1
      cin >> x;
      for (int j = 0; j < n; ++j) {   // 依次遍历数组元素
          if (x == A[j]) {    // 目标数字与数组元素依次比较
              ans = j;
              break;          // 找到答案后跳出
          }
      }
      cout << ans << endl;
      delete [] A;
  
      return 0;
  }
  

例 2.10 查找学生信息

• 代码 2.13

  #include <iostream>
  using std::cin; using std::cout;
  
  #include <string>
  using std::string;
  
  #include <algorithm>
  using std::sort;
  
  class Student {     // 用于表示学生个体的类
  private:
      string _no;     // 学号
      string _name;   // 姓名
      unsigned _age;  // 年龄
      string _sex;    // 性别
  public:
      void setNo(string no) { _no = no; }
      string getNo() { return _no; }
      void setName(string name) { _name = name; }
      string getName() { return _name; }
      void setSex(string sex) { _sex = sex; }
      string getSex() { return _sex; }
      void setAge(unsigned age) { _age = age; }
      unsigned getAge() { return _age; }
      bool operator<(const Student & b) const; // 重载小于运算符使其能使用 sort 函数排序
  };
  bool Student::operator<(const class Student & b) const {
      return _no.string::compare(b._no) < 0;
  }
  
  int main () {
      int n; cin >> n;
      Student* stu = new Student[n];
      for (int i = 0; i < n; ++i) {
          string no, name, sex;
          unsigned age;
          cin >> no >> name >> sex >> age;
          stu[i].setNo(no); stu[i].setName(name);
          stu[i].setSex(sex); stu[i].setAge(age);
      }   // 输入
      sort(stu, stu + n);     // 对数组排序使其按学号升序排列
      int m; cin >> m;        // 有 m 组询问
      while (m--) {   // while 循环保证查询次数 m
          int ans = -1;   // 目标元素下标，初始化为 -1
          string tmp;     // 待查找学号
          cin >> tmp;
          int hi = n, lo = 0;     // Student 对象数组 stu 的 [lo, hi) 区间二分查找 tmp
          while (lo < hi) {   // 每步迭代可能要做两次比较判断，有三个分支
              int mi = (lo + hi) >> 1;    // 以中点为轴点
              if (tmp < stu[mi].getNo())
                  hi = mi;    // 深入前半段 [lo, mi) 继续查找
              else if (stu[mi].getNo() < tmp)
                  lo = mi + 1;    // 深入后半段 (mi, hi) 继续查找
              else {
                  ans = mi;   // 在 mi 处命中
                  cout << stu[ans].getNo() << ' ' << stu[ans].getName() << ' '
                       << stu[ans].getSex() << ' ' << stu[ans].getAge() << "\n";
                  break;      // 查找成功则终止本轮查找
              }
          } // 成功查找可以提前终止
          if (ans == -1)      // 若查找失败
              cout << "No Answer!\n";
      }
  
      delete [] stu;
  
      return 0;
  }
  

六 贪心算法

例 2.11 FatMouse’ Trade

• 代码 2.14

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <algorithm>
  using std::sort;
  
  #include <iomanip>
  using std::fixed; using std::setprecision;
  
  struct goods {  // 表示可买物品的结构体
      double j;   // 该物品总重
      double f;   // 该物品总价值
      double s;   // 该物品性价比
      // 重载小于运算符，确保可用 sort 函数将数组按照性价比降序排列
      bool operator<(const goods &b) const {
          return s > b.s;
      }
  } buf[1000];
  
  int main() {
      double m;
      int n;
      while (cin >> m >> n) {
          if (m == -1 && n == -1)
              break;  // 当 m、n 为 -1 时，跳出循环，程序运行结束
          for (int i = 0; i < n; i++) {
              double j, f;
              cin >> buf[i].j >> buf[i].f;    // 输入
              buf[i].s = buf[i].j / buf[i].f; // 计算性价比
          }
          sort(buf, buf + n); // 使各物品按照性价比降序排列
          int idx = 0;    // 当前货物下标
          double ans = 0.0;   // 累加所能得到的总重量
          while (0 < m && idx < n) {  // 各类物品有剩余（idx < n）还有钱剩余（m > 0）时继续循环
              if (m > buf[idx].f) {   // 若能买下全部该种类物品
                  ans += buf[idx].j;
                  m -= buf[idx].f;
              } else {    // 若只能买下部分该物品
                  ans += m * buf[idx].j / buf[idx].f;
                  m = 0;
              }
              ++idx;  // 继续下一种类物品
          }
          cout << fixed << setprecision(3) << ans << endl;
      }
  
      return 0;
  }
  

  C++数字的输出处理问题(保留几位小数，或保留几位有效数字）

例 2.12 今年暑假不 AC

• 代码 2.15

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <algorithm>
  using std::sort;
  
  struct program {    // 电视节目结构体
      int _startTime;  // 节目开始时间
      int _endTime;    // 节目结束时间
      // 重载小于号，保证 sort 函数能够按照结束时间升序排列
      bool operator<(const program &second) const {
          return _endTime < second._endTime;
      }
  };
  program buf[100];
  int main() {
      int n;
      while (cin >> n) {
          if (n == 0)
              break;
          for (int i = 0; i < n; i++) {   // 输入
              cin >> buf[i]._startTime >> buf[i]._endTime;
          }
          sort (buf, buf + n);    // 按照结束时间升序排列
          // 记录当前时间，初始化为 0；所求能看的节目个数，初始化为 0
          int currentTime = 0, ans = 0;
          for (int i = 0; i < n; i++) {   // 按照结束时间升序遍历所有节目
              // 若当前时间小于等于该节目开始时间，那么收看该在剩余节目里结束时间最早的节目
              if (currentTime <= buf[i]._startTime) {
                  currentTime = buf[i]._endTime;  // 当前时间变为该节目结束时间
                  ++ans;  // 又收看了一个节目
              }
          }
          cout << ans << endl;    // 输出
      }
  }
  

第 3 章 数据结构

一 栈的应用

例 3.1 括号匹配问题

• 代码 3.1

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <stack>
  using std::stack;
  
  #include <string>
  using std::string;
  
  int main() {
      stack<int> S;   // 定义一个堆栈
      string str;     // 保存输入字符串
      while (cin >> str) {
          string ans(str.size(), ' ');    // 保存输出字符串，初始化为与输入等长的空字符串
          int i;
          for (i = 0; i < str.size(); i++) {    // 从左到右遍历输入字符串
              if (str[i] == '(') {     // 若遇到左括号
                  S.push(i);  // 将其下标放入堆栈中
                  // ans[i] += ' ';  // 暂且将对应的输出字符串位置字符改为空格
              } else if (str[i] == ')') {     // 若遇到右括号
                  if (S.empty() == false) {   // 若此时堆栈非空
                      S.pop();    // 栈顶位置左括号与其匹配，从栈中弹出该已经匹配的左括号下标
                  } else {    // 若堆栈为空，则无法找到左括号与其匹配，修改输出字符串该位为 '?'
                      ans[i] = '?';
                  }
              }
          }
          while (S.empty() == false) {    // 当字符串遍历完成后，尚留在堆栈中的左括号无法匹配
              ans[S.top()] = '$';     // 修改其在输出中的位置为 '$'
              S.pop();    // 弹出栈顶元素
          }
          cout << str << '\n' << ans << endl;    // 输出原字符串与答案字符串
      }
  
      return 0;
  }
  

例 3.2 简单计算器

代码 3.2

#include <stack>
#include <stdio.h>
using namespace std;

char str[220];  // 保存表达式字符串
/*
 * 优先级矩阵,若mat[i][j] == 1，则表示i号运算符优先级大于j号
 * 运算符，运算符编码规则为+为1号，-为2号，*为3号，/为4号,我们
 * 人为添加在表达式首尾的标记运算符为0号
 */
int mat[][5] = {
        1, 0, 0, 0, 0,
        1, 0, 0, 0, 0,
        1, 0, 0, 0, 0,
        1, 1, 1, 0, 0,
        1, 1, 1, 0, 0
};
stack<int> op;  // 运算符栈,保存运算符编号
stack<double> in;   // 数字栈,运算结果可能存在浮点数,所以保存元素为double
/*
 * 该函数获得表达式下一个元素,若函数运行结束时,引用变量reto为true,则表示该元
 * 素为一个运算符,其编号保存在引用变量retn中; 否则，表示该元素为一个数字，其
 * 值保存在引用变量retn中.引用变量i表示遍历到的字符串下标
 */
void getOp(bool &reto, int &retn, int &i) {
    // 若此时遍历字符串第一个字符,且运算符栈为空,我们人为添加编号为0的标记字符
    if (i == 0 && op.empty() == true) {
        reto = true;    // 为运算符
        retn = 0;   // 编号为0
        return; // 返回
    }
    if (str[i] == 0) {  // 若此时遍历字符为空字符,则表示字符串已经被遍历完
        reto = true;    // 为运算符
        retn = 0;   // 编号为0的标记字符
        return; // 返回
    }
    if (str[i] >= '0' && str[i] <= '9') {   // 若当前字符为数字
        reto = false;   // 返回为数字
    } else {    // 否则
        reto = true;    // 返回为运算符
        if (str[i] == '+')          // 加号返回1
            retn = 1;
        else if (str[i] == '-')     // 减号返回2
            retn = 2;
        else if (str[i] == '*')     // 乘号返回3
            retn = 3;
        else if (str[i] == '/')     // 除号返回4
            retn = 4;
        i += 2;     // i递增，跳过该运算符和紧邻的空格字符
        return;     // 返回
    }
    retn = 0;   // 返回结果为数字
    // 若字符串未被遍历完,且下一个字符不是空格,则依次遍历其后数字,计算当前连续数字字符表示的数值
    for ( ; str[i] != ' ' && str[i] != 0; i++) {
        retn *= 10;
        retn += str[i] - '0';
    }
    if (str[i] == ' ')  // 若其后字符为空格,则表示字符串未被遍历完
        ++i;    // i递增.跳过该空格
    return;     // 返回
}

int main() {
    while (gets(str)) {     // 输入字符串,当其位于文件尾时,gets返回0
        if (str[0] == '0' && str[1] == 0) break;    // 若输入只有一个0,则退出
        bool retop; int retnum; // 定义函数所需的引用变量
        int idx = 0;    // 定义遍历到的字符串下标,初始值为0
        while (!op.empty()) op.pop();
        while (!in.empty()) in.pop();   // 清空数字栈,和运算符栈
        while (true) {  // 循环遍历表达式字符串
            getOp(retop, retnum, idx);  // 获取表达式中下一个元素
            if (retop == false) {   // 若该元素为数字
                in.push((double)retnum);    // 将其压入数字栈中
            } else {    // 否则
                // 若运算符堆栈为空或者当前遍历到的运算符优先级大于栈顶运算符,将该运
                // 算符压入运算符堆栈
                double tmp;
                if (op.empty() == true || mat[retnum][op.top()] == 1) {
                    op.push(retnum);
                } else {    // 否则
                    // 只要当前运算符优先级小于栈顶元素运算符,则重复循环
                    while (mat[retnum][op.top()] == 0) {
                        int ret = op.top(); // 保存栈顶运算符
                        op.pop();   // 弹出
                        double b = in.top();
                        in.pop();
                        double a = in.top();
                        in.pop();   // 从数字堆栈栈顶弹出两个数字,依次保存在a、b中
                        if (ret == 1) tmp = a + b;
                        else if (ret == 2) tmp = a - b;
                        else if (ret == 3) tmp = a * b;
                        else if (ret == 4) tmp = a / b;
                        in.push(tmp);   // 将结果压回数字堆栈
                    }
                    op.push(retnum);    // 将当前运算符压入运算符堆栈
                }
            }
            // 若运算符堆栈只有两个元素,且其栈顶元素为标记运算符,则表示表达式求值结束
            if (op.size() == 2 && op.top() == 0)
                break;
        }
        printf("%.2f\n", in.top());     // 输出数字栈中唯一的数字,即为答案
    }
    return 0;
}

二 哈夫曼树

例 3.3 哈夫曼树

• 代码 3.3

  #include <queue>
  using std::priority_queue;
  
  #include <vector>
  using std::vector;
  
  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <functional>
  using std::greater;
  
  priority_queue<int, vector<int>, greater<int>> Q;   // 建立一个小顶堆
  
  int main() {
      int n;
      while (cin >> n) {
          while (Q.empty() == false)
              Q.pop();    // 清空堆中元素
          for (int i = 1; i <= n; i++) {  // 输入n个叶子节点权值
              int x;
              cin >> x;
              Q.push(x);  // 将权值放入堆中
          }
          int ans = 0;    // 保存答案
          while (Q.size() > 1) {  // 当堆中元素大于1个
              // 取出堆中两个最小元素，他们为同一节点的左右儿子，且该双亲节点的权值为他们的和
              int a = Q.top(); Q.pop();
              int b = Q.top(); Q.pop();
              ans += a + b;   // 该父节点必为非叶子节点，故累加其权值
              Q.push(a + b);  // 将该双亲节点的权值放回堆中
          }
          cout << ans << endl;    // 输出
      }
  
      return 0;
  }
  

三 二叉树

例 3.4 二叉树遍历

• 代码 3.4

  #include <stdio.h>
  #include <string.h>
  struct Node {   // 树结点结构体
      Node *lChild;   // 左儿子指针
      Node *rChild;   // 右儿子指针
      char c;         // 结点字符信息
  } Tree[50];     // 静态内存分配数组
  int loc;    // 静态数组中已经分配的结点个数
  Node *creat() { // 申请一个结点空间，返回指向其的指针
      Tree[loc].lChild = Tree[loc].rChild = nullptr;  // 初始化左右儿子为空
      return &Tree[loc++];    // 返回指针，且loc累加
  }
  char str1[30], str2[30];    // 保存前序和中序遍历结果字符串
  void postOrder(Node *T) {   // 后序遍历
      if (T->lChild != nullptr) { // 若左子树不为空
          postOrder(T->lChild);   // 递归遍历其左子树
      }
      if (T->rChild != nullptr) { // 若右子树不为空
          postOrder(T->rChild);   // 递归遍历其右子树
      }
      printf("%c", T->c);     // 遍历该结点，输出其字符信息
  }
  Node *build(int s1, int e1, int s2, int e2) {
      // 由字符串的前序遍历和中序遍历还原树,并返回其根节点,其中前序遍历结果
      // 为由str1[s1]到str2[e1]，中序遍历结果为str2[s2]到str2[e2]
      Node* ret = creat();    // 为该树根结点申请空间
      ret->c = str1[s1];      // 该节点字符为前序遍历中第一个字符
      int rootIdx;
      for (int i = s2; i <= e2; i++) {    // 查找该根结点字符在中序遍历中的位置
          if (str2[i] == str1[s1]) {
              rootIdx = i;
              break;
          }
      }
      if (rootIdx != s2) {    // 若左子树不为空
          // 递归还原其左子树
          ret->lChild = build(s1 + 1, s1 + (rootIdx - s2), s2, rootIdx - 1);
      }
      if (rootIdx != e2) {    // 若右子树不为空
          // 递归还原其右子树
          ret->rChild = build(s1 + (rootIdx - s2) + 1, e1, rootIdx + 1, e2);
      }
      return ret;     // 返回根结点指针
  }
  int main() {
      while (scanf("%s", str1) != EOF) {
          scanf("%s", str2);  // 输入
          loc = 0;    // 初始化静态内存空间中已经使用结点个数为0
          int L1 = strlen(str1);
          int L2 = strlen(str2);  // 计算两个字符串长度
          // 还原整棵树，其根结点指针保存在T中
          Node *T = build(0, L1 - 1, 0, L2 - 1);
          postOrder(T);   // 后序遍历
          printf("\n");   // 输出后换行
      }
      return 0;
  }
  

四 二叉排序树

例 3.5 二叉排序树

• 代码 3.5

  #include <cstdio>
  
  struct Node {   // 二叉树结构体
      Node* lChild;   // 左儿子指针
      Node* rChild;   // 右儿子指针
      int c;  // 保存数字
  } Tree[110];    // 静态数组
  
  int loc;    // 静态数组中被使用的元素个数
  
  Node* creat() { // 申请未使用的结点
      Tree[loc].lChild = Tree[loc].rChild = nullptr;
      return &Tree[loc++];
  }
  
  // 后序遍历
  void postOrder(Node* T) {
      if (T->lChild != nullptr) { // 左子树不空，则
          postOrder(T->lChild);   // 递归遍历左子树
      }
      if (T->rChild != nullptr) { // 右子树不空，则
          postOrder(T->rChild);   // 递归遍历右子树
      }
      printf("%d ", T->c);    // 访问当前结点（根）
  }
  
  // 中序遍历
  void inOrder(Node* T) {
      if (T->lChild != nullptr) {
          inOrder(T->lChild);
      }
      printf("%d ", T->c);
      if (T->rChild != nullptr) {
          inOrder(T->rChild);
      }
  }
  
  // 前序遍历
  void preOrder(Node* T) {
      printf("%d ", T->c);
      if (T->lChild != nullptr) {
          preOrder(T->lChild);
      }
      if (T->rChild != nullptr) {
          preOrder(T->rChild);
      }
  }
  
  // 二叉排序树插入结点
  Node* Insert(Node* T, int x) {
      if (T == nullptr) {     // 若当前树为空
          T = creat();        // 建立结点
          T->c = x;   // 数字直接插入其根结点
          return T;   // 返回根结点指针
      } else if (x < T->c)    // 若 x 小于根结点数值
          T->lChild = Insert(T->lChild, x);   // 插入到左子树上
          else if (x > T->c)  // 若 x 大于根结点数值
              T->rChild = Insert(T->rChild, x);   // 插入到右子
              // 树上，若根结点数值与 x 一样，根据题目要求直接忽略
  
      return T;   // 返回根结点指针
  }
  
  int main() {
      int n;
      while (scanf("%d", &n) != EOF) {
          loc = 0;
          Node* T = nullptr;  // 二叉排序树树根结点为空
          for (int i = 0; i < n; i++) {   // 依次输入 n 个数字
              int x; scanf("%d", &x);
              T = Insert(T, x);   // 插入到排序树中
          }
          preOrder(T);    // 前序遍历
          printf("\n");   // 输出空行
          inOrder(T);     // 中序遍历
          printf("\n");
          postOrder(T);   // 后序遍历
          printf("\n");
      }
      
      return 0;
  }
  

例 3.6 二叉搜索树

• 代码 3.6

  #include <cstdio>
  #include <cstring>
  
  struct Node {   // 二叉树结构体
      Node* lChild;   // 左儿子指针
      Node* rChild;   // 右儿子指针
      int c;  // 保存数字
  } Tree[110];    // 静态数组
  
  int loc;    // 静态数组中被使用的元素个数
  
  Node* creat() { // 申请未使用的结点
      Tree[loc].lChild = Tree[loc].rChild = nullptr;
      return &Tree[loc++];
  }
  
  char str1[25], str2[25];    // 保存二叉排序树的遍历结果,将每
  // 一棵树的前序遍历得到的字符串与中序遍历得到的字符串连接,得到遍历结果字符串
  
  int size1, size2;   // 保存在字符数组中的遍历得到字符个数
  char* currStr;  // 当前正在保存字符串
  int* currSize;  // 当前正在保存字符串中字符个数
  
  // 中序遍历
  void inOrder(Node* T) {
      if (T->lChild != nullptr) {
          inOrder(T->lChild);
      }
      currStr[(*currSize)++] = T->c + '0';    // 将结点中的字符放入正在保存的字符串中
      if (T->rChild != nullptr) {
          inOrder(T->rChild);
      }
  }
  
  // 前序遍历
  void preOrder(Node* T) {
      currStr[(*currSize)++] = T->c + '0';
      if (T->lChild != nullptr) {
          preOrder(T->lChild);
      }
      if (T->rChild != nullptr) {
          preOrder(T->rChild);
      }
  }
  
  // 二叉排序树插入结点
  Node* Insert(Node* T, int x) {
      if (T == nullptr) {     // 若当前树为空
          T = creat();        // 建立结点
          T->c = x;   // 数字直接插入其根结点
          return T;   // 返回根结点指针
      } else if (x < T->c)    // 若 x 小于根结点数值
          T->lChild = Insert(T->lChild, x);   // 插入到左子树上
          else if (x > T->c)  // 若 x 大于根结点数值
              T->rChild = Insert(T->rChild, x);   // 插入到右子
              // 树上，若根结点数值与 x 一样，根据题目要求直接忽略
  
      return T;   // 返回根结点指针
  }
  
  int main() {
      int n;
      char tmp[12];
      while (scanf("%d", &n) != EOF && n != 0) {
          loc = 0;    // 初始化静态空间为未使用
          Node* T = nullptr;
          scanf("%s", tmp);   // 输入字符串
          for (int i = 0; tmp[i] != '\0'; i++) {
              T = Insert(T, tmp[i] - '0');    // 按顺序将数字插入二叉排序树
          }
          size1 = 0;      // 保存在第一个字符串中的字符，初始化为0
          currStr = str1;     // 将正在保存字符串设定为第一个字符串
          currSize = &size1;  // 将正在保存字符串中的字符个数指针指向 size1
          preOrder(T);    // 前序遍历
          inOrder(T);     // 中序遍历
          str1[size1] = '\0';    // 向第一个字符串的最后一个字符后添加字符串结束符,方便使用字符串函数
          while (n-- != 0) {  // 输入 n 个其它字符串
              scanf("%s", tmp);   // 输入
              Node* T2 = nullptr;
              for (int i = 0; tmp[i] != '\0'; i++) {   // 建立二叉排序树
                  T2 = Insert(T2, tmp[i] - '0');
              }
              size2 = 0;  // 保存在第二个字符串中的字符，初始化为0
              currStr = str2; // 将正在保存字符串设定为第二个字符串
              currSize = &size2;  // 正在保存字符串中字符数量指针指向 size2
              preOrder(T2);   // 前序遍历
              inOrder(T2);    // 中序遍历
              str2[size2] = '\0';    // 字符串最后添加字符串结束符
              // 比较两个遍历字符串,若相同则输出YES,否则输出NO
              puts(strcmp(str1, str2) == 0 ? "YES" : "NO");
          }
      }
  
      return 0;
  }
  

  C++ 运算符优先级

• 代码 3.6（迭代版）

  #include <cstdio>
  
  #include <stack>
  using std::stack;
  
  #include <utility>
  using std::pair;
  
  struct Node {   // 二叉树结构体
      Node* lChild;   // 左儿子指针
      Node* rChild;   // 右儿子指针
      int c;  // 保存数字
  } Tree[110];    // 静态数组
  
  int loc;    // 静态数组中被使用的元素个数
  
  Node* creat() { // 申请未使用的结点
      Tree[loc].lChild = Tree[loc].rChild = nullptr;
      return &Tree[loc++];
  }
  
  // 后序遍历迭代版
  void postOrder_I(Node* T) {     // 二叉树的后序遍历（迭代版）
      stack<pair<Node*, bool>> S; // 辅助栈
      do{
          while (T) {
              S.push({T, false});
              T = T->lChild;
          }
          while (!S.empty()) {
              pair<Node*, bool> tmp = S.top();    // 当前栈顶元素
              if (tmp.second) {
                  printf("%d ", tmp.first->c);
                  S.pop();
              } else {
                  T = tmp.first->rChild;
                  // 修改栈顶元素 pair<Node*, bool> 的 bool 域为 true
                  S.top().second = true;
                  break;
              }
          }
      } while (!S.empty());
  }
  
  // 中序遍历迭代版#1（借助一个辅助栈，若当前结点为根结点，则根结点入栈）
  static void goAlongLeftBranch (Node* T, stack<Node*> &S) {
      // 从当前结点出发，沿左分支不断深入，直至没有左分支的结点
      while (T) {
          S.push(T);  // 当前结点入栈后
          // 随即向左侧分支深入，迭代直到无左孩子
          T = T->lChild;
      }
  }
  void inOrder_I1(Node* T) {  // 二叉树中序遍历算法（迭代版#1）
      stack<Node*> S; // 辅助栈
      while (true) {
          goAlongLeftBranch(T, S);    // 从当前结点出发，逐批入栈
          if (S.empty())  // 直至所有节点处理完毕
              break;
          T = S.top();
          S.pop();
          printf("%d ", T->c);    // 访问当前结点
          T = T->rChild;  // 转向右子树
      }
  }
  
  // 中序遍历迭代版#2（版本2只不过是版本1的等价形式，但借助它可便捷地设计和实现版本3）
  void inOrder_I2(Node* T) {  // 二叉树中序遍历算法（迭代版#2）
      stack<Node*> S;     // 辅助栈；
      while (true)
          if (T) {
              S.push(T);  // 根结点入栈
              T = T->lChild;  // 深入遍历左子树
          } else if (!S.empty()) {
              T = S.top();    // 将 T 更新为尚未访问的最低祖先结点
              S.pop();    // 并退栈该节点
              printf("%d ", T->c);    // 访问当前结点
              T = T->rChild;  // 遍历祖先的右子树
          } else
              break;  // 遍历完成
  }
  
  // 中序遍历迭代版#3（因引入父结点指针和判断左右孩子函数，实现稍复杂。
  // 可参考邓俊辉老师《数据结构与算法》P130、P131实现，这里省略）
  
  // 前序遍历迭代版（借助一个辅助栈，若当前结点右孩子非空，则右孩子入栈）
  static void visitAlongLeftBranch(Node* T, stack<Node*> &S) {
      // 从当前结点出发，沿左分支不断深入，直至没有左分支的结点；沿途结点遇到后立即访问
      while (T) {
          printf("%d ", T->c);    // 访问当前结点
          S.push(T->rChild);      // 右孩子入栈暂存（可优化：通过判断，避免空的右孩子入栈）
          T = T->lChild;      // 沿左分支深入一层
      }
  }
  void preOrder_I(Node* T) {
      stack<Node*> S;     // 辅助栈
      while (true) {
          visitAlongLeftBranch(T, S);
          if (S.empty())  // 直到栈空
              break;
          T = S.top();    // 更新结点指针 T 为下一批的起点
          S.pop();    // 弹出下一批的起点
      }
  }
  
  // 二叉排序树插入结点
  Node* Insert(Node* T, int x) {
      if (T == nullptr) {     // 若当前树为空
          T = creat();        // 建立结点
          T->c = x;   // 数字直接插入其根结点
          return T;   // 返回根结点指针
      } else if (x < T->c)    // 若 x 小于根结点数值
          T->lChild = Insert(T->lChild, x);   // 插入到左子树上
      else if (x > T->c)  // 若 x 大于根结点数值
          T->rChild = Insert(T->rChild, x);   // 插入到右子
      // 树上，若根结点数值与 x 一样，根据题目要求直接忽略
  
      return T;   // 返回根结点指针
  }
  
  int main() {
      int n;
      while (scanf("%d", &n) != EOF) {
          loc = 0;
          Node* T = nullptr;  // 二叉排序树树根结点为空
          for (int i = 0; i < n; i++) {   // 依次输入 n 个数字
              int x; scanf("%d", &x);
              T = Insert(T, x);   // 插入到排序树中
          }
          printf("********** 前序遍历迭代版 ************\n");
          preOrder_I(T);    // 前序遍历
          printf("\n");   // 输出空行
          printf("********** 中遍历迭代版#1 ************\n");
          inOrder_I1(T);     // 中序遍历
          printf("\n");
          printf("********** 中遍历迭代版#2 ************\n");
          inOrder_I2(T);     // 中序遍历
          printf("\n");
          printf("********** 后遍历迭代版 ************\n");
          postOrder_I(T);   // 后序遍历
          printf("\n");
      }
  
      return 0;
  }
  

第 4 章 数学问题

一 %运算

二 数位拆解

例 4.1 特殊乘法

• 代码 4.1

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <vector>
  using std::vector;
  
  int main() {
      int a, b;
      while (cin >> a >> b) {
          vector<int> ivec_a, ivec_b;
          while (a != 0) {
              ivec_a.push_back(a % 10);   // 取得当前个位上的数字,将其保存
              a /= 10;    // 将所有数位上的数字右移一位
          }
          while (b != 0) {
              ivec_b.push_back(b % 10);
              b /= 10;
          }
          int ans = 0;    // 计算答案
          for (auto elemOfA : ivec_a) {
              for (auto elemOfB : ivec_b)
                  ans += elemOfA * elemOfB;
          }
          cout << ans << endl;
      }
  
      return 0;
  }
  

• 代码 4.2

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <string>
  using std::string;
  
  int main() {
      string a, b;
      while (cin >> a >> b) {
          int ans = 0;    // 累加变量
          for (char elemOfA : a) {    // char 改为 auto 也可
              for (char elemOfB : b) {
                  ans += (elemOfA - '0') * (elemOfB - '0');
                  // char - '0' 实现将字符转为整型
              }
          }
          cout << ans << endl;
      }
  
      return 0;
  }
  

三 进制转换

例 4.2 又一版 A+B

• 代码 4.3

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <stack>
  using std::stack;
  
  int main() {
      long long a, b;
      int m;
      while (cin >> m && m) {     // 当 m 等于 0 时退出
          cin >> a >> b;
          a += b;     // 计算 a + b，结果放到 a 中
          stack<int> S;
          do {    // 即使被转换数字是 0，程序也能正常工作
              S.push(a % m);
              a /= m;
          } while (a);    // a 非零，重复该过程
          while (!S.empty()) {
              cout << S.top();
              S.pop();
          }
          cout << endl;
      }
  
      return 0;
  }
  

例 4.3 数制转换

• 代码 4.4

  #include <iostream>
  using std::cin; using std::cout; using std::endl;
  
  #include <string>
  using std::string;
  
  #include <algorithm>
  using std::reverse;
  
  int main() {
      int a, b;
      string str;
      while (cin >> a >> str >> b) {
          // tmp为我们将要计算的 a 进制对应的十进制数；w 为各个数位的权重，初
          // 始化为1,表示最低位数位权重为1,之后每位权重都是前一位权重的a倍
          int tmp = 0, w = 1;
          for (string::reverse_iterator riter = str.rbegin(); riter != str.rend(); ++riter) {
              int x;  // 计算该位上的数字
              if (*riter >= '0' && *riter <= '9')
                  x = *riter - '0';       // 当字符在0到9之间,计算其代表的数字
              else if (*riter >= 'a' && *riter <= 'z')
                  x = *riter - 'a' + 10;  // 当字符为小写字母时,计算其代表的数字
              else
                  x = *riter - 'A' + 10;  // 当字符为大写字母时,计算其代表的数字
  
              tmp += x * w;   // 累加该位数字与该数位权重的积
              w *= a;     // 计算下一位数位权重
          }
          string ans;     // 用 ans 保存转换到 b 进制的各个数位数字
          do {    // do-while 保证 0 也能实现转换
              int x = tmp % b;
              ans += (x < 10) ? x + '0' : x - 10 + 'A';   // 将数字转换为大写字符
              tmp /= b;
          } while (tmp);
          reverse(ans.begin(), ans.end());    // 也可将转换结果保存在栈中
          cout << ans << endl;
      }
  
      return 0;
  }
  

四 最大公约数（GCD）

例 4.4 最大公约数

• 代码 4.5

  #include <iostream>
  using std::cin; using std::endl; using std::cout;
  
  int gcd(int x1, int x2) {
      if (x2 == 0)
          return x1;
      else
          return gcd(x2, x1 % x2);
  }
  
  int gcd_I(int x1, int x2) {
      while (x2 != 0) {
          int tmp = x1 % x2;
          x1 = x2;
          x2 = tmp;
      }
      return x1;
  }
  
  int main() {
      int a, b;
      while (cin >> a >> b) {
          cout << "****** 递归版 ******\n" << gcd(a, b) << endl;
          cout << "****** 迭代版 ******\n" << gcd_I(a, b) << endl;
      }
  
      return 0;
  }
  

五 最小公倍数（LCM）

• 代码 4.7

  #include <iostream>
  using std::cin; using std::endl; using std::cout;
  
  int gcd(int x1, int x2) {		// 求 x1 和 x2 的最大公约数
      return x2 == 0 ? x1 : gcd(x2, x1 % x2);
  }
  
  int main() {
      int a, b;
      while (cin >> a >> b) {
          cout << a * b / gcd(a, b) << endl;		// 输出最小公倍数
      }
  
      return 0;
  }
  

六 素数筛法

例 4.6 素数判定

• 代码 4.8

  #include <iostream>
  #include <cmath>
  
  bool judge(int x) {     // 判断一个数是否为素数
      if (x <= 1)     // 若其小于等于1,必不是
          return false;
      // 计算枚举上界,为防止 double 值带来的精度损失, 所以采用根号值取整后再
      // 加 1,即宁愿多枚举一个数也不能少枚举一个数
      int bound = static_cast<int>(sqrt(x)) + 1;
      for (int i = 2; i < bound; ++i)
          if (x % i == 0)
              return false;
      return true;
  }
  
  int main() {
      int x;
      while (std::cin >> x)
          std::cout << (judge(x) ? "yes" : "no") << std::endl;
  
      return 0;
  }
  

例 4.7 素数

• 代码 4.9

  #include <iostream>
  #include <map>
  #include <vector>
  
  std::map<int, bool> M;  // 若 bool 值为 true，则表示该数 int 已被标记成非素数
  std::vector<int> ivec;  // 保存 1～10000 的素数
  
  void init() {       // 素数筛法
      for (int i = 1; i <= 10000; ++i)    // 初始化，所有数字标记为 false（素数）
          M.insert({i, false});
      for (int i = 2; i <= 10000; ++i) {  // 依次遍历 2～10000 所有数字
          if (M[i] == true)   // 若该数字已经被标记为非素数,则跳过
              continue;
          else    // 否则得到一个素数
              ivec.push_back(i);  // 保存到 ivec 中
  
          for (int j = i * i; j <= 10000; j += i) {   // 并将该数的所有倍数均标记成非素数
              M[j] = true;
          }
      }
  }
  
  int main() {
      init();     // 在程序一开始首先取得2到10000中所有素数
      int n;
      while (std::cin >> n) {
          bool isFirstOutPut = false; // 表示是否输出了一个符合条件的数
          for (int i = 0; i < ivec.size(); ++i) { // 依次遍历得到的所有素数
              if (ivec[i] < n && ivec[i] % 10 == 1) { // 测试当前素数是否符合条件
                  // 若当前输出为第一个输出的数字,则标记已经输出了符合条件的数字,且该数字前不输出空格
                  if (isFirstOutPut == false) {
                      isFirstOutPut = true;
                      std::cout << ivec[i];
                  } else {    // 否则在输出这个数字前输出一个空格
                      std::cout << " " << ivec[i];
                  }
              }
          }
  
          if (isFirstOutPut == false)     // 若始终不存在符合条件的数字
              std::cout << "-1\n";    // 输出-1并换行
          else    // 否则
              std::cout << "\n";   // 换行
      }
  
      return 0;
  }
  

七 分解素因数

例 4.8 质因数的个数

• 代码 4.10

  #include <iostream>
  #include <map>
  #include <vector>
  
  std::map<int, bool> M;  // 若 bool 值为 true，则表示该数 int 已被标记成非素数
  std::vector<int> ivec;  // 保存 1～100000 的素数
  
  void init() {       // 素数筛法
      for (int i = 1; i <= 100000; ++i)    // 初始化，所有数字标记为 false（素数）
          M.insert({i, false});
      for (int i = 2; i <= 100000; ++i) {  // 依次遍历 2～100000 所有数字
          if (M[i] == true)   // 若该数字已经被标记为非素数,则跳过
              continue;
          else    // 否则得到一个素数
              ivec.push_back(i);  // 保存到 ivec 中
  
          if (i >= 1000) continue;
          for (int j = i * i; j <= 100000; j += i) {   // 并将该数的所有倍数均标记成非素数
              M[j] = true;
          }
      }
  }   // 以上与上例一致，用素数筛法筛选出2到100000内的所有素数
  
  int main() {
      init();     // 在程序一开始首先取得2到100000中所有素数
      int n;
      while (std::cin >> n) {
          std::vector<int> ansPrime;     // 按顺序保存分解出的素因数
          int ansSize = 0;    // 分解出素因数的个数
          std::vector<int> ansNum;    // 保存分解出的素因数对应的幂指数
          // 注意 i 与 ansSize 并不同步增加
          for (int i = 0; i < ivec.size(); ++i) { // 依次测试每一个素数
              if (n % ivec[i] == 0) { // 若该素数ivec[i]能整除被分解数n
                  ansPrime.push_back(ivec[i]);    // 则该素数为其素因数
                  ansNum.push_back(0);    // 初始化幂指数为0
                  while (n % ivec[i] == 0) {  // 从被测试数中将该素数分解出来,并统计其幂指数
                      ++ansNum[ansSize];
                      n /= ivec[i];
                  }
                  ++ansSize;      // 素因数个数增加
                  if (n == 1) break;      // 若已被分解成1,则分解提前终止
              }
          }
          if (n != 1) {   // 若测试完2到100000内所有素因数,n仍未被分解至1,则剩余的因
                          // 数一定一个大于100000的素因数
              ansPrime.push_back(n);  // 记录该大素因数
              ansNum.push_back(1);    // 其幂指数只能为1
          }
          int ans = 0;
          for (auto e : ansNum)   // 统计各个素因数的幂指数
              ans += e;
          std::cout << ans << std::endl;
      }
  
      return 0;
  }
  

例 4.9 整除问题

• 代码 4.9

  #include <iostream>
  #include <map>
  #include <vector>
  
  std::map<int, bool> M;  // 若 bool 值为 true，则表示该数 int 已被标记成非素数
  std::vector<int> ivec;  // 保存 1～1000 的素数
  
  void init() {       // 素数筛法
      for (int i = 1; i <= 1000; ++i)    // 初始化，所有数字标记为 false（素数）
          M.insert({i, false});
      for (int i = 2; i <= 1000; ++i) {  // 依次遍历 2～1000 所有数字
          if (M[i] == true)   // 若该数字已经被标记为非素数,则跳过
              continue;
          else    // 否则得到一个素数
              ivec.push_back(i);  // 保存到 ivec 中
  
          for (int j = i * i; j <= 1000; j += i) {   // 并将该数的所有倍数均标记成非素数
              M[j] = true;
          }
      }
  }   // 以上与上例一致，用素数筛法筛选出2到1000内的所有素数
  
  int main() {
      init();     // 在程序一开始首先取得2到1000中所有素数
      int n, a;
      while (std::cin >> n >> a) {
          // 统计 n! 分解素因子后，素因子 ivec[i] 所对应的幂指数，可能为 0
          // 因为我们是以 2～1000 内从小到大的素数 ivec[i]，依次统计 ivec[i]
          // 可整除 n! 的累计次数存入 cntExpN，故某个 ivec[i] 素数可能不
          // 是 n! 的素因子，其累计次数为 0
          std::vector<int> cntExpN;
          std::vector<int> cntExpA;   // 同理
          for (int i = 0; i < ivec.size(); ++i) {
              cntExpN.push_back(0);   // 初始化ivec[i]的幂指数为0
              int tmp = n;    // 用临时变量保存 n 的值
              // 依次计算 tmp / ivec[i]^k，累加其值，直到 tmp / ivec[i]^k 变为 0
              while (tmp) {
                  cntExpN[i] += tmp / ivec[i];
                  tmp /= ivec[i];
              }
          }
          int ans = INT_MAX;      // 答案初始值为一个大整数,为取最小值做准备
          for (int i = 0; i < ivec.size(); ++i) {     // 对 a 分解素因数
              cntExpA.push_back(0);   // 同理
              // 计算 a 中素因数 ivec[i] 对应的幂指数
              while (a % ivec[i] == 0) {
                  ++cntExpA[i];
                  a /= ivec[i];
              }
              // 若素数 ivec[i] 不能从 a 分解到，即 ivec[i] 对应的幂指数为 0，则
              // 其不影响整除性，跳过
              if (cntExpA[i] == 0)
                  continue;
              else {
                  if (cntExpN[i] / cntExpA[i] < ans)  // 计算素数ivec[i]在两个数中幂指数的商
                      ans = cntExpN[i] / cntExpA[i];  // 统计这些商的最小值
              }   // 根据题意 cntExpN[i] / cntExpA[i] 能够保证整除（不会出现商为小数）
          }
          std::cout << ans << std::endl;
      }
  
      return 0;
  }
  

八 二分求幂

例 4.10 人见人爱 $A^B$

• 代码 4.10

  #include <iostream>
  
  int main() {
      int a, b;
      while (std::cin >> a >> b) {
          if (a == 0 && b == 0)
              break;
  
          int ans = 1;    // 保存最终结果变量，初始值为1
          // 一边计算b的二进制值，一边计算a的2^k次，并将需要的部分累乘到变量ans上
          while (b != 0) {    // 若b不为0，即对b转换二进制过程未结束
              if (b % 2 == 1) {   // 若当前二进制位为1，则需要累乘a的2^k次至变量ans，其
                  // 中2^k次为当前二进制位的权重
                  ans *= a;   // 最终结果累乘a
                  ans %= 1000;    // 求其后三位数
              }
              b /= 2;     // b除以2
              a *= a;     // 求下一位二进制位的权重，a求其平方，即从a的1次开始，依次求的a的2次，a的4次...
              a %= 1000;  // 求a的后三位
          }
          std::cout << ans << std::endl;
      }
  
      return 0;
  }
  

九 高精度整数

例 4.11 a+b

• 代码 4.11

  #include <iostream>
  #include <string>
  #include <iomanip>
  
  struct bigInteger {     // 高精度整数结构体
      int digit[1000];    // 按四位数一个单位保存数值
      int size;   // 下一个我们未使用的数组单元
      void init() {   // 对结构体的初始化
          for (int i = 0; i < 1000; i++)
              digit[i] = 0;   // 所有数位清0
          size = 0;   // 下一个未使用数组单元为0,即没有一个单元被使用
      }
      void set(std::string str);  // 从字符串中提取整数
      void output();  // 将该高精度整数输出
      bigInteger operator+(const bigInteger &B) const;    // 重载加法运算符
  } a, b, c;
  
  void bigInteger::set(std::string str) {
      init();     // 对结构体初始化
      int L = str.size();     // 计算字符串长度
      for (int i = L - 1, j = 0, t = 0, c = 1; 0 <= i; --i) {
          // 从最后一个字符开始倒序遍历字符串,j控制每4个字符转换为一个数字存入数组,t临
          // 时保存字符转换为数字的中间值,c表示当前位的权重,按1,10,100,1000顺序变化
          t += (str[i] - '0') * c;    // 计算这个四位数中当前字符代表的数字,即数字乘以当前位权重
          ++j;    // 当前转换字符数增加
          c *= 10;    // 计算下一位权重
          if (j == 4 || i == 0) {     // 若已经连续转换四个字符,或者已经到达最后一个字符
              digit[size++] = t;  // 将这四个字符代表的四位数存入数组,size移动到下一个数组单元
              j = 0;      // 重新开始计算下4个字符
              t = 0;      // 临时变量清0
              c = 1;      // 权重重置为1（个位数）
          }
      }
  }
  
  void bigInteger::output() {
      for (int i = size - 1; i >= 0; --i) {
          if (i != size - 1)  // 若当前输出的数字不是最高位数字,当前数字不足4位时高位由0补充
              std::cout << std::setw(4) << std::setfill('0') << digit[i];
          else
              std::cout << digit[i];      // 若是最高位,则无需输出前导零
      }
      std::cout << "\n";      // 换行
  }
  
  bigInteger bigInteger::operator+(const bigInteger & B) const {
      bigInteger ret;     // 返回值,即两数相加的结果
      ret.init();     // 对其初始化
      int carry = 0;  // 进位，初始化为0
      for (int i = 0; i < B.size || i < size; ++i) {
          int tmp = B.digit[i] + digit[i] + carry;    // 计算两个整数当前位以及来自低位的进位和
          carry = tmp / 10000;    // 计算该位的进位
          tmp %= 10000;   // 去除进位部分,取后四位
          ret.digit[ret.size++] = tmp;    // 保存该位结果
      }
      if (carry != 0) {   // 计算结束后若最高位有进位
          ret.digit[ret.size++] = carry;  // 保存该进位
      }
      return ret;
  }
  
  int main() {
      std::string str1, str2;
      while (std::cin >> str1 >> str2) {
          a.set(str1); b.set(str2);       // 用两个字符串分别设置两个高精度整数
          c = a + b;      // 计算它们的和
          c.output();     // 输出结果
      }
  
      return 0;
  }
  

例 4.12 N 的阶乘

• 代码 4.12

  #include <iostream>
  #include <iomanip>
  
  struct bigInteger {     // 高精度整数结构体
      int digit[1000];    // 按四位数一个单位保存数值
      int size;   // 下一个我们未使用的数组单元
      void init() {   // 对结构体的初始化
          for (int i = 0; i < 1000; i++)
              digit[i] = 0;   // 所有数位清0
          size = 0;   // 下一个未使用数组单元为0,即没有一个单元被使用
      }
      void set(int x);  // 用一个小整数设置高精度整数
      void output();  // 将该高精度整数输出
      bigInteger operator*(const int x) const;    // 重载乘法运算符
  } a;
  
  void bigInteger::set(int x) {
      init();     // 对结构体初始化
      do {    // 对小整数4位为一个单位分解依次存入digit当中
          digit[size++] = x % 10000;
          x /= 10000;
      } while (x != 0);
  }
  
  void bigInteger::output() {
      for (int i = size - 1; i >= 0; --i) {
          if (i != size - 1)  // 若当前输出的数字不是最高位数字,当前数字不足4位时高位由0补充
              std::cout << std::setw(4) << std::setfill('0') << digit[i];
          else
              std::cout << digit[i];      // 若是最高位,则无需输出前导零
      }
      std::cout << "\n";      // 换行
  }
  
  bigInteger bigInteger::operator*(const int x) const {
      bigInteger ret;     // 返回值,即两数相乘的结果
      ret.init();     // 对其初始化
      int carry = 0;  // 进位，初始化为0
      for (int i = 0; i < size; ++i) {
          int tmp = x * digit[i] + carry;    // 用小整数x乘以当前位数字并加上来自低位的进位
          carry = tmp / 10000;    // 计算进位
          tmp %= 10000;   // 去除进位部分,取后四位
          ret.digit[ret.size++] = tmp;    // 保存该位结果
      }
      if (carry != 0) {   // 计算结束后若最高位有进位
          ret.digit[ret.size++] = carry;  // 保存该进位
      }
      return ret;
  }
  
  int main() {
      int n;
      while (std::cin >> n) {
          a.init();       // 初始化a
          a.set(1);       // a初始值为1
          for (int i = 1; i <= n; ++i) {
              a = a * i;
          }
          a.output();     // 输出a
      }
  
      return 0;
  }
  

例 4.13 进制转换

• 代码 4.13

  #include <stdio.h>
  #include <string.h>
  #define maxDigits 100
  
  struct bigInteger {     // 高精度整数结构体
      int digit[maxDigits];    // 按四位数一个单位保存数值
      int size;   // 下一个我们未使用的数组单元
      void init() {   // 对结构体的初始化
          for (int i = 0; i < maxDigits; i++)
              digit[i] = 0;   // 所有数位清0
          size = 0;   // 下一个未使用数组单元为0,即没有一个单元被使用
      }
      void set(int x);  // 用一个普通整数初始化高精度整数
      void output();  // 将该高精度整数输出
      bigInteger operator*(const int x) const;    // 重载乘法运算符
      bigInteger operator+(const bigInteger &B) const;
      bigInteger operator/(const int x) const;
      int operator%(const int x) const;
  } a, b;
  
  void bigInteger::set(int x) {
      init();     // 对结构体初始化
      do {    // 将该普通整数4位为一个单位分解依次存入digit当中
          digit[size++] = x % 10000;
          x /= 10000;
      } while (x != 0);
  }
  
  void bigInteger::output() {
      for (int i = size - 1; i >= 0; --i) {
          if (i != size - 1)  // 若当前输出的数字不是最高位数字,当前数字不足4位时高位由0补充
              printf("%04d", digit[i]);
          else
              printf("%d", digit[i]);      // 若是最高位,则无需输出前导零
      }
      printf("\n");      // 换行
  }
  
  bigInteger bigInteger::operator*(const int x) const {
      bigInteger ret;     // 返回值,即两数相乘的结果
      ret.init();     // 对其初始化
      int carry = 0;  // 进位，初始化为0
      for (int i = 0; i < size; ++i) {
          int tmp = x * digit[i] + carry;
          carry = tmp / 10000;    // 计算进位
          tmp %= 10000;   // 去除进位部分,取后四位
          ret.digit[ret.size++] = tmp;    // 保存该位结果
      }
      if (carry != 0) {   // 计算结束后若最高位有进位
          ret.digit[ret.size++] = carry;  // 保存该进位
      }
      return ret;
  }
  
  bigInteger bigInteger::operator+(const bigInteger &B) const {
      bigInteger ret;
      ret.init();
      int carry = 0;
      for (int i = 0; i < B.size || i < size; ++i) {
          int tmp = B.digit[i] + digit[i] + carry;
          carry = tmp / 10000;
          tmp %= 10000;
          ret.digit[ret.size++] = tmp;
      }
      if (carry != 0) {
          ret.digit[ret.size++] = carry;
      }
      return ret;
  }
  
  bigInteger bigInteger::operator/(const int x) const {   // 高精度整数除以普通整数
      bigInteger ret;     // 返回的高精度整数
      ret.init();     // 返回值初始化
      int remainder = 0;      // 余数
      for (int i = size - 1; 0 <= i; --i) {  // 从最高位至最低位依次完成计算
          // 计算当前位数值加上高位剩余的余数的和对x求得的商
          int t = (remainder * 10000 + digit[i]) / x;
          // 计算当前位数值加上高位剩余的余数的和对x求模后得的余数
          int r = (remainder * 10000 + digit[i]) % x;
          ret.digit[i] = t;   // 保存本位的值
          remainder = r;  // 保存至本位为止的余数
      }
      // 返回高精度整数的size初始值为0,即当所有位数字都为0 时,digit[0]代表数字0,作为最高
      // 有效位,高精度整数即为数字0
      ret.size = 0;
      // 若存在非0位,确定最高的非0位,作为最高有效位
      for (int i = 0; i < maxDigits; ++i) {
          if (digit[i] != 0)
              ret.size = i;
      }
      ++ret.size;     // 最高有效位的下一位即为下一个我们不曾使用的digit数组单元,确定为size的值
      return ret;
  }
  
  int bigInteger::operator%(const int x) const {   // 高精度整数对普通整数求余数
      int remainder = 0;      // 余数
      // 过程同高精度整数对普通整数求商
      for (int i = size - 1; 0 <= i; --i) {
          // int t = (remainder * 10000 + digit[i]) / x;
          int r = (remainder * 10000 + digit[i]) % x;
          remainder = r;
      }
      return remainder;   // 返回余数
  }
  
  char str[10000];
  char ans[10000];
  int main() {
      int m, n;
      while (scanf("%d%d", &m, &n) != EOF) {
          scanf("%s", str);    // 输入m进制数
          int L = strlen(str);
          a.set(0);   // a初始值为0,用来保存转换成10进制的m进制数
          b.set(1);   // b初始值为1,在m进制向10进制转换的过程中,依次代表每一位的权重
          // 由低位至高位转换m进制数至相应的10进制数
          for (int i = L - 1; 0 <= i; --i) {
              int t;
              if (str[i] >= '0' && str[i] <= '9') {
                  t = str[i] - '0';
              } else {
                  t = str[i] - 'A' + 10;  // 确定当前位字符代表的数字
              }
              a = a + b * t;      // 累加当前数字乘当前位权重的积
              b = b * m;      // 计算下一位权重
          }
  
          int size = 0;   // 代表转换为n进制后的字符个数
          do {    // 对转换后的10进制数求其n进制值
              int t = a % n;  // 求余数
              if (t >= 10)
                  ans[size++] = t - 10 + 'a';
              else
                  ans[size++] = t + '0';     // 确定当前位字符
              a = a / n;      // 求商
          } while (a.digit[0] != 0 || a.size != 1);   // 当a不为0时重复该过程
  
          for (int i = size - 1; 0 <= i; --i)
              printf("%c", ans[i]);
          printf("\n");
      }
  
      return 0;
  }
  

第 5 章 图论

一 预备知识

二 并查集

例 5.1 畅通工程

• 代码 5.1

  #include <iostream>
  #define N 1000
  int Tree[N];
  
  int findRoot(int x) {   // 查找某个结点所在树的根结点，并压缩路径
      if (Tree[x] == -1)
          return x;
      else {
          int tmp = findRoot(Tree[x]);
          Tree[x] = tmp;  // 将当前结点的双亲结点设置为查找返回的根结点编号
          return tmp;
      }
  }
  
  int main() {
      int n, m;
      while (std::cin >> n && n) {    // n 非零
          // 初始时,所有结点都是孤立的集合,即其所在集合只有一个结点,其本身就是所在树根结点
          for (int i = 1; i <= n; ++i) Tree[i] = -1;
          std::cin >> m;
          while (m--) {   // 读入边信息
              int a, b;
              std::cin >> a >> b;
              // 查找边的两个顶点所在集合信息
              a = findRoot(a); b = findRoot(b);
              // 若两个顶点不在同一个集合则合并这两个集合
              if (a != b) Tree[a] = b;
          }
          int ans = 0;
          for (int i = 1; i <=n; ++i) {
              if (Tree[i] == -1)  // 统计所有结点中根结点的个数
                  ++ans;
          }
          std::cout << ans - 1 << std::endl;
      }
  
      return 0;
  }
  

例 5.2 More is better

• 代码 5.2

  #include <iostream>
  #define N 10000001
  int Tree[N];
  
  int findRoot(int x) {   // 查找某个结点 x 所在树的根结点，并压缩路径
      if (Tree[x] == -1)
          return x;
      else {
          int tmp = findRoot(Tree[x]);
          Tree[x] = tmp;  // 将当前结点的双亲结点设置为查找返回的根结点编号
          return tmp;
      }
  }
  
  // 用sum[i]表示以结点i为根的树的结点个数,其中保存数据仅当Tree[i]为-1即该结点为树的根结点时有效
  int sum[N];
  
  int main() {
      int n;
      while (std::cin >> n) {
          for (int i = 1; i < N; ++i) {   // 初始化结点信息
              Tree[i] = -1;       // 所有结点为孤立集合
              sum[i] = 1;     // 所有集合的元素个数为1
          }
          while (n--) {
              int a, b;
              std::cin >> a >> b;
              a = findRoot(a); b = findRoot(b);
              if (a != b) {
                  Tree[a] = b;
                  // 合并两集合时,将成为子树的树根结点上保存的该集合元素个数的数字累加到合并后新树的树根
                  sum[b] += sum[a];
              }
          }
          int ans = 1;    // 答案,答案至少为1。固这里先出初始化为1
          for (int i = 1; i <= N; ++i) {
              if (Tree[i] == -1 && sum[i] > ans)
                  ans = sum[i];   // 统计最大值
          }
          std::cout << ans << std::endl;      // 输出
      }
      return 0;
  }
  

三 最小生成树（MST）

例 5.3 还是畅通工程

• 代码 5.3

  #include <iostream>
  #include <algorithm>
  #define N 101
  int Tree[N];
  
  int findRoot(int x) {   // 查找某个结点 x 所在树的根结点，并压缩路径
      if (Tree[x] == -1)
          return x;
      else {
          int tmp = findRoot(Tree[x]);
          Tree[x] = tmp;  // 将当前结点的双亲结点设置为查找返回的根结点编号
          return tmp;
      }
  }
  
  struct Edge {   // 边结构体
      int a, b;   // 边两个顶点的编号
      int cost;   // 该边的的权值
      bool operator<(const Edge &B) const {   // 重载小于号，方便边权值从小到大排列
          return cost < B.cost;
      }
  } edge[6000];
  
  int main() {
      int n;
      while (std::cin >> n && n != 0) {
          for (int i = 1; i <= n * (n - 1) / 2; ++i) {    // 输入
              std::cin >> edge[i].a >> edge[i].b >> edge[i].cost;
          }
          // 按照边权值递增排列所有的边
          std::sort(edge + 1, edge + 1 + n * (n - 1) / 2);
          for (int i = 1; i <= n; ++i)
              Tree[i] = -1;   // 初始时所有的结点都属于孤立的集合
          int ans = 0;    // 最小生成树上边权的和,初始值为0
          for (int i = 1; i <= n * (n - 1) / 2; ++i) {    // 按照边权值递增顺序遍历所边
              // 查找该边两个顶点的集合信息
              int a = findRoot(edge[i].a), b = findRoot(edge[i].b);
              if (a != b) {   // 若它们属于不同集合,则选用该边
                  Tree[a] = b;    // 合并两个集合
                  ans += edge[i].cost;    // 累加该边权值
              }
          }
          std::cout << ans << std::endl;  // 输出
      }
      return 0;
  }
  

例 5.4 Freckles

• 代码 5.4

  #include <iostream>
  #include <algorithm>
  #include <cmath>
  
  #define N 101
  int Tree[N];
  
  int findRoot(int x) {   // 查找某个结点 x 所在树的根结点，并压缩路径
      if (Tree[x] == -1)
          return x;
      else {
          int tmp = findRoot(Tree[x]);
          Tree[x] = tmp;  // 将当前结点的双亲结点设置为查找返回的根结点编号
          return tmp;
      }
  }
  
  struct Edge {   // 边结构体
      int a, b;   // 边两个顶点的编号
      double cost;   // 该边的的权值（两点之间的距离）
      bool operator<(const Edge &B) const {   // 重载小于号，方便边权值从小到大排列
          return cost < B.cost;
      }
  } edge[6000];
  
  struct Point {  // 点结构体
      double x, y;    // 点横纵坐标
      double getDistance(Point B) {   // 计算点之间的距离
          double tmp = (x - B.x) * (x - B.x) + (y - B.y) * (y - B.y);
          return sqrt(tmp);
      }
  } list[101];
  
  int main() {
      int n;
      while (std::cin >> n) {
          for (int i = 1; i <= n; ++i) {    // 输入
              std::cin >> list[i].x >> list[i].y;
          }
          int size = 0;   // 抽象出的边的总数
          // 遍历所有两两点
          for (int i = 1; i <= n; ++i) {
              for (int j = i + 1; j <= n; ++j) {  // 连接两点的线段抽象成边
                  // 该边的两个顶点编号
                  edge[size].a = i; edge[size].b = j;
                  // 边权值为两点之间的长度
                  edge[size].cost = list[i].getDistance(list[j]);
                  ++size;     // 边的总数增加
              }
          }
          std::sort(edge, edge + size);   // 对边按权值递增排序
          for (int i = 1; i <= n; ++i)
              Tree[i] = -1;
          double ans = 0;
          // 最小生成树
          for (int i = 0; i < size; ++i) {
              int a = findRoot(edge[i].a), b = findRoot(edge[i].b);
              if (a != b) {
                  Tree[a] = b;
                  ans += edge[i].cost;
              }
          }
          std::cout << ans << std::endl;
      }
      return 0;
  }
  

四 最短路径

两种常见的最短路径问题：

• 单源最短路径算法（Dijkstra：适用于图用邻接链表表示）：某个顶点到其它所有顶点的最短路径，时间复杂度$O{(n^2)}$；

• 所有顶点对之间的最短路径（Floyd：适用于图用邻接矩阵表示）

  • 方法一：每次以一个顶点为源点，重复执行 Dijkstra 算法 n 次，时间复杂度$O{(n^3)}$；
  • 方法二：Floyd算法

例 5.5 最短路

• 代码 5.5（Floyd）

  #include <iostream>
  int ans[101][101];  // 二维数组，其初始值即为该图的邻接矩阵
  int main() {
      int n, m;
      while (std::cin >> n >> m) {
          if (n == 0 && m == 0) break;
          // 对邻接矩阵初始化,我们用-1代表无穷
          for (int i = 1; i <= n; ++i) {
              for (int j = 1; j <= n; ++j) {
                  ans[i][j] = -1;
              }
              ans[i][i] = 0;  // 自己到自己的路径长度设为0
          }
  
          while (m--) {
              int a, b, c;
              std::cin >> a >> b >> c;
              // 对邻接矩阵赋值,由于是无向图,该赋值操作要进行两次
              ans[a][b] = ans[b][a] = c;
          }
          // k从1到N循环,依次代表允许经过的中间结点编号小于等于k
          for (int k = 1; k <= n; ++k) {
              for (int i = 1; i <= n; ++i) {
                  // 遍历所有ans[i][j]，判断其值保持原值还是将要被更新
                  for (int j = 1; j <= n; ++j) {
                      // 若两值中有一个值为无穷，则ans[i][j]不能由于经过结点k而被更新，跳过循环，保持原值
                      if (ans[i][k] == -1 || ans[k][j] == -1) continue;
                      // 当由于经过k可以获得更短的最短路径时,更新该值
                      if (ans[i][j] == -1 || ans[i][k] + ans[k][j] < ans[i][j])
                          ans[i][j] = ans[i][k] + ans[k][j];
                  }
              }
          }
          std::cout << ans[1][n] << std::endl;    // 循环结束后输出答案
      }
  
      return 0;
  }
  

• 代码 5.6

  #include <iostream>
  #include <vector>
  struct E {      // 邻接链表中的链表元素结构体
      int next;   // 代表直接相邻的结点
      int c;      // 代表该边的权值(长度)
  };
  std::vector<E> edge[101];   // 邻接链表
  bool mark[101]; // 标记,当mark[j]为true时表示结点j的最短路
  // 径长度已经得到,该结点已经加入集合K
  int Dis[101];   // 距离向量,当mark[i]为true时,表示已得的最
  // 短路径长度;否则,表示所有从结点1出发，经过已知的最短路径达到
  // 集合K中的某结点，再经过一条边到达结点i的路径中最短的距离
  int main() {
      int n, m;
      while (std::cin >> n >> m) {
          if (n == 0 && m == 0) break;
          for (int i = 1; i <= n; ++i)
              edge[i].clear();    // 初试化邻接链表
          while (m--) {
              int a, b, c;
              std::cin >> a >> b >> c;
              E tmp;
              tmp.c = c;
              // 将邻接信息加入邻接链表,由于原图为无向图,固每条边信息
              // 都要添加到其两个顶点的两条单链表中
              tmp.next = b;
              edge[a].push_back(tmp);
              tmp.next = a;
              edge[b].push_back(tmp);
          }
          for (int i = 1; i <= n; ++i) {  // 初始化
              Dis[i] = -1;    // 所有距离为-1，即不可达
              mark[i] = false;    // 所有结点不属于集合K
          }
          Dis[1] = 0; // 得到最近的点为结点1,长度为0
          mark[1] = true; // 将结点1加入集合K
          int newP = 1;   // 集合K中新加入的点为结点1
          // 循环n-1次,按照最短路径递增的顺序确定其他n-1个点的最短路径长度
          for (int i = 1; i < n; ++i) {
              // 遍历与该新加入集合K中的结点直接相邻的边
              for (int j = 0; j < edge[newP].size(); ++j) {
                  int t = edge[newP][j].next;     // 该边的另一个结点
                  int c = edge[newP][j].c;    // 该边的长度
                  if (mark[t] == true)
                      continue;  // 若另一个结点也属于集合K,则跳过
                  // 若该结点尚不可达,或者该结点从新加入的结点经过一条边到
                  // 达时比以往距离更短
                  if (Dis[t] == -1 || Dis[t] > Dis[newP] + c)
                      Dis[t] = Dis[newP] + c; // 更新其距离信息
              }
              int min = INT_MAX;  // 最小值初始化为一个大整数,为找最小值做准备
              for (int j = 1; j <= n; ++j) {  // 遍历所有结点
                  if (mark[j] == true) continue;  // 若其属于集合K则跳过
                  if (Dis[j] == -1) continue; // 若该结点仍不可达则跳过
                  if (Dis[j] < min) { // 若该结点经由结点1至集合K中的某点再
                      // 经过一条边到达时距离小于当前最小值
                      min = Dis[j];   // 更新其为最小值
                      newP = j;   // 新加入的点暂定为该点
                  }
              }
              mark[newP] = true;  // 将新加入的点加入集合K,Dis[newP]虽然数值
              // 不变，但意义发生变化，由所有经过集合K中的结点再经过一条边到达时
              // 的距离中的最小值变为从结点1到结点newP的最短距离
          }
          std::cout << Dis[n] << std::endl;   // 输出
      }
      return 0;
  }
  

例 5.6 最短路径问题

• 代码 5.7

  #include <iostream>
  #include <vector>
  struct E {      // 邻接链表中的链表元素结构体
      int next;   // 代表直接相邻的结点
      int c;      // 代表该边的权值(长度)
      int cost;
  };
  std::vector<E> edge[1001];   // 邻接链表
  bool mark[1001]; // 是否属于集合K数组
  int Dis[1001];   // 距离数组
  int cost[1001];     // 花费数组
  // 短路径长度;否则,表示所有从结点1出发，经过已知的最短路径达到
  // 集合K中的某结点，再经过一条边到达结点i的路径中最短的距离
  int main() {
      int n, m;
      int S, T;   // 起点，终点
      while (std::cin >> n >> m) {
          if (n == 0 && m == 0) break;
          for (int i = 1; i <= n; ++i)
              edge[i].clear();    // 初试化邻接链表
          while (m--) {
              int a, b, c, cost;
              std::cin >> a >> b >> c >> cost;
              E tmp;
              tmp.c = c;
              tmp.cost = cost;    // 邻接链表中增加了该边的花费信息
              // 将邻接信息加入邻接链表,由于原图为无向图,固每条边信息
              // 都要添加到其两个顶点的两条单链表中
              tmp.next = b;
              edge[a].push_back(tmp);
              tmp.next = a;
              edge[b].push_back(tmp);
          }
          std::cin >> S >> T;     // 输入起点终点信息
          for (int i = 1; i <= n; ++i) {  // 初始化
              Dis[i] = -1;
              mark[i] = false;
          }
          Dis[S] = 0;
          mark[S] = true;
          int newP = S;   // 起点为S,将其加入集合K,且其最短距离确定为0
          // 循环n-1次,按照最短路径递增的顺序确定其他n-1个点的最短路径长度
          for (int i = 1; i < n; ++i) {
              // 遍历与该新加入集合K中的结点直接相邻的边
              for (int j = 0; j < edge[newP].size(); ++j) {
                  int t = edge[newP][j].next;
                  int c = edge[newP][j].c;
                  int co = edge[newP][j].cost;    // 花费
                  if (mark[t] == true)
                      continue;
                  // 比较大小时,将距离相同但花费更短也作为更新的条件之一
                  if (Dis[t] == -1 || Dis[t] > Dis[newP] + c
                  || Dis[t] == Dis[newP] + c && cost[t] > cost[newP] + co) {
                      Dis[t] = Dis[newP] + c;
                      cost[t] = cost[newP] + co;  // 更新花费
                  }
              }
              int min = INT_MAX;  // 最小值初始化为一个大整数,为找最小值做准备
              for (int j = 1; j <= n; ++j) {  // 遍历所有结点。选择最小值,选择时
                  // 不用考虑花费的因素,因为距离最近的点的花费已经不可能由于经过其它
                  // 点而发生改变了
                  if (mark[j] == true) continue;
                  if (Dis[j] == -1) continue;
                  if (Dis[j] < min) {
                      min = Dis[j];
                      newP = j;
                  }
              }
              mark[newP] = true;
          }
          std::cout << Dis[T]  << " " << cost[T] << std::endl;   // 输出
  
      }
      return 0;
  }
  

五 拓扑排序

例 5.7

• 代码 5.8

  #include <stdio.h>
  #include <vector>
  #include <queue>
  using namespace std;
  vector<int> edge[501]; // 邻接链表,因为边不存在权值,只需保存与
  // 其邻接的结点编号即可,所以vector中的元素为int
  queue<int> Q; // 保存入度为0的结点的队列
  int main() {
      int inDegree[501]; // 统计每个结点的入度
      int n, m;
      while (scanf("%d%d", &n, &m) != EOF) {
          if (n == 0 && m == 0) break;
          for (int i = 0; i < n; i++) { // 初始化所有结点,注意本题结点编号由0到n-1
              inDegree[i] = 0; // 初始化入度信息,所有结点入度均为0
              edge[i].clear(); // 清空邻接链表
          }
          while (m--) {
              int a, b;
              scanf("%d%d", &a, &b); // 读入一条由a指向b的有向边
              inDegree[b]++; // 又出现了一条弧头指向b的边,累加结点b的入度
              edge[a].push_back(b); // 将b加入a的邻接链表
          }
          while (Q.empty() == false) Q.pop(); // 若队列非空,则一直弹出队头元素,该操
                                              // 作的目的为清空队列中所有的元素(可
                                              // 能为上一组测试数据中遗留的数据)
          for (int i = 0; i < n; i++) { // 统计所有结点的入度
              if (inDegree[i] == 0) Q.push(i); // 若结点入度为0,则将其放入队列
          }
          int cnt = 0; // 计数器,初始值为0,用于累加已经确定拓扑序列的结点个数
          while (Q.empty() == false) { // 当队列中入度为0的结点未被取完时,重复
              int nowP = Q.front(); // 读出队头结点编号,本例不需要求出确定的拓扑序列,
                                    // 固不做处理;若要求求出确定的拓扑次序,则将该结点
                                    // 紧接着放在已经确定的拓扑序列之后
              Q.pop(); // 弹出对头元素
              cnt++; // 被确定的结点个数加一
              // 将该结点以及以其为弧尾的所有边去除
              for (int i = 0; i < edge[nowP].size(); i++) {
                  inDegree[edge[nowP][i]]--; // 去除某条边后,该边所指后继结点入度减一
                  if (inDegree[edge[nowP][i]] == 0) { // 若该结点入度变为0
                      Q.push(edge[nowP][i]); // 将其放入队列当中
                  }
              }
          }
          if (cnt == n)
              puts("YES"); // 若所有结点都能被确定拓扑序列,则原图为有向无环图
          else
              puts("NO"); // 否则,原图为非有向无环图
      }
      return 0;
  }
  

第 6 章 搜索

一 枚举

例 6.1 百鸡问题

• 代码 6.1

  #include <iostream>
  
  int main() {
      int n;
      while (std::cin >> n) {
          for (int x = 0; x <= 100; ++x)  // 枚举x的值
              for (int y = 0; y <= 100 - x; ++y) {    // 枚举y的值,注意它们的和不可能超过100
                  int z = 100 - x - y;
                  // 考虑到一只小小鸡 的价格为1/3,为避免除法带来的精度损失,这里采用了对不等式两端
                  // 所有数字都乘3的操作,这也是 避免除法的常用技巧
                  if (x * 5 * 3 + y * 3 * 3 + z <= n * 3)
                      std::cout << x << " " << y << " " << z << std::endl;
              }
      }
  
      return 0;
  }