《算法笔记》学习笔记

第 2 章 C/C++ 快速入门

2.1 基本数据类型

2.1.2 变量类型

long long 类型赋大于$2^{31}-1$的初值，需要在初值后面加 LL，否则会 CE

long long bignum = 1234567890123456LL;

简而言之，题目要求$10^{9}$以内，就用 int；$10^{18}$以内，就用 longlong

浮点型：不要用 float，只用 double 就可以了

char：小写字母比大写字母的 ASCII 值大 32

字符常量必须用单引号标注，以区分是作为字符变量还是字符常量

转义字符

\n 代表换行
\0 代表空字符NULL，其ASCII码为0

字符串常量：由双引号标记的字符集，可以作为初值赋值给字符数组并使用%s的形式输出

不能把字符串常量赋值给字符变量

char c="abcd"

的写法是不允许的

布尔型

只有 0 才是 False，别的整数都是 True

2.1.3 强制类型转换

(新类型名)变量名

如果把一个类型的变量赋值给另一个类型的变量却没有写强转，那么 IDE 会自动强转

但是计算的时候需要强转，那就不能等到算完再强转

2.1.4 符号常量和 const 常量

格式为

#define 标识符 常量

或者

const 数据类型 变量名 = 常量;

常量的值一旦确定之后就不能改变了。

define 除了定义常量以外，还可以定义任何语句或者片段（宏定义），格式如下

#define 标识符 任何语句或者片段

比如

#include<stdio.h>
#define ADD(a,b) ((a)+(b)) //为什么要加这么多括号？是因为宏定义是直接将对应的部分替换，然后才进行编译和运行
int main(){
    int num1 =3, num2 =5;
    prints("%d", ADD(num1,num2)); //8
    return 0;
}

所以，尽量不要用宏定义来做除了定义常量以外的事情

2.1.5 运算符

只复习位运算符 详见 Oiwiki

2.2 顺序结构

常见数据类型变量的 scanf 格式符

数据类型	格式符
int	%d
long long	%lld
float	%f
double	%lf
char	%c
字符串 (char 数组)	%s

录入字符串不需要加&

另外，如果要输入“3 4”这种用空格隔开的两个数字，两个%d直接可以不加空格

int a, b;
scanf("%d%d", &a, &b);

原因：除了%c以外，scanf 对于其他格式符 (如%d) 的输入是以空白符（空格、tab）座位结束判断标志的
另外，字符数组使用%s读入的时候以空格和换行座位读入结束的标识
即 scanf 的%c格式是可以读入空格和换行的！

常见数据类型变量的 printf 格式符

数据类型	格式符
int	%d
long long	%lld
float	%f
double	%f
char	%c
字符串 (char 数组)	%s

与 scanf 的区别只在于 double

三种实用的输出格式

1. %md
   %md 可以使不足 m 位的 int 型变量以 m 位进行右对齐输出，其中高位用空格补齐，如果变量本身超过 m 位则保持原样（不会截断）

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    int a=123, b=1234567;
    printf("%5d\n",a);
    printf("%5d\n",b);
    return 0;
}

输出格式

  123
1234567

在 123 的前面补了两个空格
2. %0md 补上前导 0

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    int a=123, b=1234567;
    printf("%05d\n",a);
    printf("%05d\n",b);
    return 0;
}

输出格式

00123
1234567

3. %.mf 保留 m 位小数输出（不等价于四舍五入）

2.2.3 使用 getchar 和 putchar 来输入/输出字符

getchar 用来输入单个字符，putchar 用来输出单个字符，在某些 scanf 函数使用不便的场合可以使用 getchar 来输入字符。

#include <stdio.h>
int main(){
char cl，c2，c3;
c1 =getchar();
getchar();
c2 =getchar();
c3 = getchar();
putchar(c1);
putchar(c2);putchar(c3);
return 0
}

输入数据

abcd

输出结果

acd

此处第一个字符'a'被 c1 接收;第二个字符'b'虽然被接收，但是没有将它存储在某个变量中;第三个字符 c 被 c2 接收;第四个字符'd"被 c3 接收。之后，连续三次 putchar 将把 c1、c2、c3 连续输出。而如果输入"ab"，然后按 Enter 键，再输入 c，再按 Enter 键，输出结果会是这样：

a
c

这是因为 getchar 可以识别换行符，所以 c2 实际上储存的是换行符\n，因此在 a 和 c 之间会有一个换行出现。

2.2.4 注释

2.2.5 typedef

可以给复杂的数据类型取一个别名

#include <cstdio>
Ltypedef long long LL;//给 1ong 1ong 起个别名
int main(){
LL a=123456789012345，b=234567890123456;//直接使用 LL
printf("lld\n"，a+b);
return 0;
}

2.2.6 常用 math 函数

1. fabs(double x)
   用于对 double 型变量取绝对值

2. floor(double x) ceil(double x)

3. pow(double r, double p)
   返回$r^{p}$

4. sqrt(double x)

5. log(double x)
   返回 lnx
   C 语言中不能指定底数，因此必须通过换底公式来求。

6. sin(double x) cso(double x) tan(double x)
   要求参数是弧度制

7. asin(double x) acos(double x) atan(double x)
   反三角函数

8. round(double x)
   将 double 型变量四舍五入，返回值仍然是 double 类型

2.3 选择结构

2.3.1 if 语句

2.3.3 switch 语句

记得什么是 break 穿透

2.4 循环结构

2.4.1 while 语句

2.4.2 do...while 语句

#include <iostream>

int main() {
    int sum = 0;
    int i = 1;

    do {
        sum += i;
        i++;
    } while (i <= 100);

    std::cout << "The sum of numbers from 1 to 100 is: " << sum << std::endl;

    return 0;
}

do...while 会先执行循环体一次，再去判断循环条件是不是为真

2.4.3 for 语句

引用for (int x : s) 是 C++11 引入的一种范围-based for 循环（range-based for loop）语法。它的作...

for (int x : s) 是 C++11 引入的一种范围-based for 循环（range-based for loop）语法。它的作用是遍历容器 s 中的每一个元素，并将每个元素赋值给变量 x，然后在循环体中处理 x。

---

语法解析

for (int x : s) {
 // 循环体
}

• int x：定义一个变量 x，用于存储容器 s 中的每个元素。x 的类型应与容器 s 中元素的类型一致。
• s：一个可迭代的容器（如 std::vector、std::set、std::list 等）。
• :：表示遍历容器 s 中的每个元素。
• {}：循环体，对每个元素 x 执行的操作。

---

与传统 for 循环的对比

传统 for 循环

for (auto it = s.begin(); it != s.end(); ++it) {
    int x = *it;
    // 循环体
}

范围-based for 循环

for (int x : s) {
    // 循环体
}

范围-based for 循环的优点是：

1. 简洁：不需要手动管理迭代器。
2. 易读：直接表达“遍历容器中的每个元素”的意图。
3. 安全：避免迭代器越界或错误。

示例：遍历 std::set

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {10, 20, 30};

    for (int x : s) {
        std::cout << x << " "; // 输出 10 20 30
    }

    return 0;
}

注意事项

1. 元素类型匹配：

   • x 的类型必须与容器 s 中元素的类型一致。如果不确定类型，可以使用 auto：

     for (auto x : s) {
         // 循环体
     }

2. 避免拷贝：

   • 如果容器中的元素是复杂类型（如 std::string 或自定义类），直接使用 for (auto x : s) 会导致元素的拷贝。为了避免拷贝，可以使用引用：

     for (const auto& x : s) {
         // 循环体
     }

3. 修改元素：

   • 如果需要修改容器中的元素，可以使用非 const 引用：

     for (auto& x : s) {
         x = x * 2; // 修改元素
     }

2.4.4 break 和 continue 语句

2.5 数组

2.5.1 一维数组

记得初赋值，有两种赋值为 0 的方法：把第一个元素赋为 0，或者只用一个大括号表示

int a[10]={0};
int a[10]={};

递推：

for(int i=1;i<10;i++){
    a[0] =1;
    a[1] =1;
    a[i+1]=a[i]+a[i-1];
} //斐波那契数列

2.5.2 冒泡排序

for (int j = 0; j < len - 1; j++){      //长度为 n 的数组，只需要执行这样的排序循环 n-1 次
    for (int i = 0; i < len - 1 - j; i++){
            int temp = arr[i];
            if (arr[i] > arr[i + 1]){
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    }

别忘记交换两个数的固定写法

2.5.3 二维数组

初始化的方式

int a[5][6] = {{}}; //默认全部赋值 0

如果数组大小较大（大概$10^{6}$级别），则需要定义在 main 函数外面

2.5.4 memset——对数组中每一个元素赋相同的值

格式为

memset(数组名, 值, sizeof(数组名))；

只建议使用 memset 赋值 0 或者 -1，因为 memset 是对每个字节赋同样的值。如果要赋值其他数字，用 fill 函数。

2.5.5 字符数组

字符数组的初始化

除了赋值的时候一个一个赋值

char str[3] = {'a', 'b','\0'};

也可以通过直接赋值字符串来初始化仅限于初始化，程序其他位置不允许这样直接赋值整个字符串

char str[15] = "Good Day!";

字符数组的输入输出

1. scanf 输入 printf 输出
   %s识别空格作为字符串的结尾
2. getchar 输入，putchar 输出

代码CPP · 19 行

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    char str[5][5];
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            str[i][j]=getchar();
            getchar(); //这句是为了把输入中每行末尾的换行符吸收掉
        }
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            putchar(str[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

这段代码就是一个二维数组的示例，输入什么就输出什么。
3. gets 输入，puts 输出
在 C11 之后被弃用
现在想要读取一行字符串可以使用 while c!=\n或者 getline

字符数组的存放方式

结尾是一个'\0 只有 char 型数组要注意，千万要注意长度要比实际存储字符串的长度至少多 1

2.5.6 string.h 头文件

1. strlen()，得到字符数组中第一个\0前字符的个数

2. strcmp(), 返回两个字符串大小的比较结果，比较原则是按照字典序

   引用在 C++ 中，字符串的字典序比较是基于字符的 ASCII 值逐字符进行的。字典序比较的规则类似于英语词典中单词的排序规则。以下是字符串字典序比...

   在 C++ 中，字符串的字典序比较是基于字符的 ASCII 值逐字符进行的。字典序比较的规则类似于英语词典中单词的排序规则。以下是字符串字典序比较的详细说明：

   ---

   1. 字典序比较规则

   1. 逐字符比较：

      • 从字符串的第一个字符开始，逐个比较对应位置的字符。
      • 如果两个字符的 ASCII 值不同，则 ASCII 值较小的字符所在的字符串较小。

   2. 长度比较：

      • 如果两个字符串的前缀完全相同，但一个字符串比另一个字符串长，则较短的字符串较小。

   ---

   2. 示例说明

   示例 1

   • 字符串 "apple" 和 "banana"：
     • 比较第一个字符：'a'（ASCII 97）和 'b'（ASCII 98）。
     • 因为 'a' < 'b'，所以 "apple" < "banana"。

   示例 2

   • 字符串 "apple" 和 "apricot"：
     • 前两个字符相同（'a' 和 'p'）。
     • 比较第三个字符：'p'（ASCII 112）和 'r'（ASCII 114）。
     • 因为 'p' < 'r'，所以 "apple" < "apricot"。

   示例 3

   • 字符串 "apple" 和 "app"：
     • 前三个字符相同（'a'、'p'、'p'）。
     • "app" 比 "apple" 短，所以 "app" < "apple"。

   ---

   3. C++ 中的字符串比较

   在 C++ 中，字符串的比较可以通过以下方式实现：

   1. 使用比较运算符：

      • ==：判断两个字符串是否相等。
      • !=：判断两个字符串是否不相等。
      • <：判断第一个字符串是否小于第二个字符串。
      • >：判断第一个字符串是否大于第二个字符串。
      • <=：判断第一个字符串是否小于或等于第二个字符串。
      • >=：判断第一个字符串是否大于或等于第二个字符串。

   2. 示例代码：

      代码CPP · 18 行

      #include <iostream>
      #include <string>
      using namespace std;
                                                                                                                                                                                                
      int main() {
          string s1 = "apple";
          string s2 = "banana";
                                                                                                                                                                                                
          if (s1 < s2) {
              cout << s1 << " is less than " << s2 << endl;
          } else if (s1 > s2) {
              cout << s1 << " is greater than " << s2 << endl;
          } else {
              cout << s1 << " is equal to " << s2 << endl;
          }
                                                                                                                                                                                                
          return 0;
      }

   输出

   apple is less than banana

   ---

   4. 字典序的应用

   字典序比较在以下场景中非常有用：

   1. 字符串排序：

      • 例如，对一组单词按字典序排序。
      • 示例：

        vector<string> words = {"banana", "apple", "apricot"};
        sort(words.begin(), words.end());
        // 排序后：["apple", "apricot", "banana"]

   2. 拼数问题：

      • 在拼数问题中，通过比较字符串拼接后的字典序，可以找到最大的拼接结果。

   3. 查找最小或最大字符串：

      • 例如，在一组字符串中找到字典序最小或最大的字符串。

   ---

   5. 注意事项

   1. 大小写敏感：

      • 字典序比较是大小写敏感的。例如，'A'（ASCII 65）和 'a'（ASCII 97）是不同的字符。
      • 如果需要忽略大小写，可以先将字符串转换为统一的大小写形式。

   2. 数字字符串的比较：

      • 对于数字字符串（如 "123" 和 "45"），字典序比较可能不符合数值大小的比较结果。
      • 例如，"123" < "45"（因为 '1' < '4'），但数值上 123 > 45。

   ---

   6. 总结

   • 字符串的字典序比较是基于字符的 ASCII 值逐字符进行的。
   • 如果两个字符串的前缀相同，较短的字符串较小。
   • 在 C++ 中，可以直接使用比较运算符（如 <、>）来比较字符串的字典序。
   • 字典序比较在字符串排序、拼数问题等场景中非常有用。

   如果你有其他问题，欢迎继续提问！

3. strcpy()

strcpy(字符数组1， 字符数组2);

注意：是把字符数组 2 赋值给字符数组 1，这里的复制也包括了\0

4. strcat()

strcat(字符数组1， 字符数组2);

注意：是把字符数组 2 接到字符数组 1 后面去

2.5.7 sscanf 与 sprintf

sscanf 从单词上可以理解为 string+scanf,sprintf 则可以理解为 string+printf，均在 stdio.h 头文件下。
先来回顾一下 scanf 与 printf，其实可以写成这种形式

scanf(screen, "%d", &n);
printf(screen, "%d", n);

可以发现，scanf 的输入其实是把 screen 的内容以"%d"的格式传输到 n 中 (即从左至右)
而 printf 的输出则是把 n 以"%d"的格式传输到 screen 上 (即从右至左)。 sscanf 与 sprintf 与上面的格式是相同的，只不过把 screen 换成了字符数组
(假设定义了一个 char 数组 str[100])，如下所示：

sscanf(str, "%d", &n);
sprintf(str, "%d", n);

上面 sscanf 写法的作用是把字符数组 str 中的内容以"%d"的格式写到 n 中 (还是从左至右)
而 sprintf 写法的作用是把 n 以"%d"的格式写到 str 字符数组中 (还是从右至左)。示例如下

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    int n=233;
    char str[100];
    sprintf(str,"%d", n);
    printf("%s\n", str);
    return 0;
}

输出结果

233

上面只是一些简单的应用，事实上，可以像使用 scanf 与 printf 那样进行复杂的格式输入和输出。例如下面的代码使用 sscanf 将字符数组 str 中的内容按"%d:%lf,%s"的格式写到 int 型变量 n、double 型变量 db、char 型数组 str2 中。

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    int n;
    double db;
    char str[1000] = "2048:3.14,hello", str2[100];
    sscanf(str, "%d:%lf,%s",&n, &db, str2);
    printf("n=%d,db=%.2f,str2=%s\n",n,db,str2);
    return 0;
}

输出结果为

n=2048,db=3.14,str2=hello

类似的

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    int n=12;
    double db=3.1415;
    char str[1000], str2[100]="good";
    sprintf(str, "%d:%.2f,%s",n, db, str2);
    printf("str=%s\n",str);
    return 0;
}

输出结果

str=12:3.14,good

2.6 函数

2.6.1 函数的定义

• 全局变量：定义在所有函数之前，对于定义之后的所有程序段之内都有效的变量
• 局部变量：定义在函数内部且只在函数内部生效，函数结束之后局部变量销毁
• 函数定义内的小括号内的参数被称为形式参数简称形参，而在实际调用时小括号之内的参数称为实际参数或者实参

2.6.2 再谈 main 函数

return 0；是告知系统，程序正常终止

2.6.3 以数组作为函数参数

数组作为参数时，数组中的第一维不需要填写长度（如果是二维数组，那么第二维需要填写长度），实际调用时也只需要填写数组名。
数组作为参数时，在函数中对数组元素的修改就等同是对原数组元素的修改（这与普通的局部变量不同） 比如

void change(int b[][5]){ //第二维要注明长度

}

数组可以作为参数传入，但是不能作为返回类型。

2.6.4 函数的嵌套调用

2.6.5 函数的递归调用

递归是函数自己调用自身的过程，会在第四章详细介绍

#include <bits/stdc++.h>
using namespace std;   

int F(int n){
    if(n==0) return 1;
    else return F(n-1)*n;
}
int main()
{
    int n=12;
    cin>>n;
    return 0;
}

2.7 指针

指针是一个 unsigned 类型的 int

2.7.2 指针变量

指针变量用来存放指针（或者可以理解成地址），意思是把地址当做常量，然后专门定义了一种指针变量来存放它，在某种数据类型后加型号*来表示这是一个指针变量

如果要同时定义几个指针变量，星号只会结合于第一个变量名

int* p1, p2; //p1 是 int*类型的 p2 是 int 类型的

一种给指针变量赋值的方式，给指针变量赋值的方式一般是把变量的地址取出来 (使用取地址运算符&)，然后赋值给对应的指针变量：

int a;
int *p = &a;

或者

int a;
int *p;
p = &a;

地址&a 是赋值给 p 的而不是赋值给*p 的，需要铭记星号是类型的一部分

对于一个指针变量，它的解引用也是使用星号*，比如如下的代码

int main(){
    int a;
    int *p=&a;
    a=233;
    printf("%d",*p); //输出 233
}

上述代码中首先定义 int 型变量 a，但是没有初始化。然后定义指针变量 p，并将 a 的地址赋值给 p。这时 p 存放了 a 的地址。之后 a 被赋值为 233，也就是说a 所在地址的房间内的内容被改变了，但是这不影响它的地址。而在后面的输出中使用星号*作为开启房间的钥匙，放在了 p 的前面，这样*p 就能获取到房间里的东西，即储存的数据。

由此可以延伸到，既然 p 保存的是地址，*p 是这个地址存放的元素，那么直接对*进行赋值也可以起到改变保存的元素的功能

int main(){
    int a;
    int *p=&a;
    *p=233;
    printf("%d",a); //输出 233
}

指针变量可以进行加减法，对 int*型变量 p 来说，p+1 是 p 所指的 int 变量的下一个 int 型变量地址

2.7.3 指针与数组

数组名称可以作为数组的首地址使用 即定义 int arr[], 则有a==&a[0];
且有*a+i==&a[i], (a+i)==a[i]; 两个 int 类型的指针相减，等价于求这两个指针之间相差了几个 int，比如下面这段代码

int a[5];
int *p=a;
int *q=a+5;
cout<<q-p;

会输出 5，这个解释对于其他类型的指针同样适用

2.7.4 使用指针变量作为函数参数

这时视为把变量的地址传入函数，如果在函数中对这个地址的元素进行改变，那么原先的数据就确实地会被改变。
经典例子，使用指针作为参数交换两个数。

void _swap(int *a, int *b){
    int temp=*a; 
    *a=*b;
    *b=temp;
}

经典错误 1

void _swap(int *a, int *b){
    int *temp; 
    *temp=*a;
    *a=*b;
}

错因：指针 temp 没有初始化，是野指针，很大可能指向系统工作区间，随机地址出错概率特别大。

解决方案：

void _swap(int *a, int *b){
    int x;
    int *temp=&x; 
    *temp=*a;
    *a=*b;
}

经典错误 2

void _swap(int *a, int *b){
    int *temp=a;
    a=b;
    b=temp;
}

错因：回顾前面所说的，函数参数的传送方式是单向一次性的，main 函数传给 swap 函数的“地址”其实只是一个 unsigned int，swap 对地址本身修改并不能对 main 函数里面的地址进行修改，能够使 main 函数里面的数据发生变化的只能是 swap 函数中对地址指向的数据进行的修改。这个函数其实就很类似于为什么不可以写一个这样的函数

void _swap(int a, int b){
    int temp=a; 
    a=b;
    b=temp;
}

因为其实都只是副本罢了。

2.7.5 引用

引用的含义

C++ 中特有的语法，给原变量起一个别名，且对引用变量的操作就是对于原变量的操作 引用不产生副本
方法：在函数的参数类型后面加一个&就可以了
注意与取地址运算符的&区分开

#include <bits/stdc++.h>
using namespace std;   

void change(int&x){
    x=2;
}
int main()
{
    int n=1;
    change(n);
    cout<<n;
}

指针的引用

可以运用引用，改造上面的经典错误 2

void _swap(int* &p1, int* &p2){
    int *temp=p1;
    p1=p2;
    p2=temp;
}

这里相当于把 int*视作一个 unsigned int 类型，而对这样的两个整型变量进行交换是需要加引用的
传入的是指针的别名。
常量不可以使用引用

引用在 C++ 中，引用（Reference）是一种特殊的变量类型，它为另一个变量提供了一个别名。引用本身并不占用额外的内存空间，它只是指向另一个变...

在 C++ 中，引用（Reference）是一种特殊的变量类型，它为另一个变量提供了一个别名。引用本身并不占用额外的内存空间，它只是指向另一个变量的内存地址。通过引用，你可以直接操作被引用的变量，而不需要通过指针来间接访问。

引用的声明语法如下：

类型 &引用名 = 变量名;

• 类型：被引用变量的类型。
• 引用名：引用的名称，用于后续操作。
• 变量名：被引用的变量的名称。

示例：

#include <iostream>

int main() {
    int a = 10;  // 定义一个整型变量 a
    int &ref = a;  // 定义一个引用 ref，它指向变量 a

    std::cout << "a = " << a << std::endl;  // 输出：a = 10
    std::cout << "ref = " << ref << std::endl;  // 输出：ref = 10

    ref = 20;  // 通过引用修改 a 的值

    std::cout << "a = " << a << std::endl;  // 输出：a = 20
    std::cout << "ref = " << ref << std::endl;  // 输出：ref = 20

    return 0;
}

关键点：

1. 初始化：引用必须在声明时进行初始化，并且一旦初始化后，就不能再引用其他变量。

   int a = 10;
   int &ref = a;  // 正确
   int &ref2;  // 错误，引用必须初始化

2. 别名：引用实际上是变量的别名，对引用的操作就是对原变量的操作。

   int a = 10;
   int &ref = a;
   ref = 20;  // 等同于 a = 20;

3. 不能为空：引用不能为空，它必须始终引用某个有效的对象。

   int &ref = nullptr;  // 错误，引用不能为空

4. 常量引用：你可以声明一个常量引用，这样引用就不能修改被引用的变量。

   int a = 10;
   const int &ref = a;  // 常量引用
   ref = 20;  // 错误，常量引用不能修改被引用的变量

5. 引用作为函数参数：引用常用于函数参数传递，以避免拷贝大对象，并且可以直接修改传入的参数。

   void increment(int &value) {
       value++;
   }
                                                                                                                                                                                                                                                                                       
   int main() {
       int a = 10;
       increment(a);
       std::cout << a << std::endl;  // 输出：11
       return 0;
   }

总结：

引用在 C++ 中是一个非常强大的工具，它允许你以更直观的方式操作变量，避免了指针的复杂性。通过引用，你可以直接修改被引用的变量，而不需要通过指针来间接访问。引用在函数参数传递、返回值等方面都有广泛的应用。

2.8 结构体的使用

2.8.1 结构体的定义

一个例子

typedef struct
{
    char name;
    int count;
}spot;

定义结构体变量的方式

typedef struct
{
    char name;
    int count;
}spot;
spot A;
spot B;
spot str[100];

或者

struct spot
{
    char name;
    int count;
}A, B, str[100];

结构体里面不能定义自己本身，但是可以定义自身类型的指针变量
一个例子

代码CPP · 40 行

#include <iostream>

// 定义一个链表节点结构体
struct Node {
 int data;           // 节点数据
 Node* next;         // 指向下一个节点的指针
};

int main() {
 // 创建链表节点
 Node* head = new Node();
 head->data = 1;
 head->next = nullptr;

 Node* second = new Node();
 second->data = 2;
 second->next = nullptr;

 Node* third = new Node();
 third->data = 3;
 third->next = nullptr;

 // 将节点连接起来
 head->next = second;
 second->next = third;

 // 遍历链表并输出数据
 Node* current = head;
 while (current != nullptr) {
     std::cout << current->data << " ";
     current = current->next;
 }

 // 释放链表内存
 delete head;
 delete second;
 delete third;

 return 0;
}

2.8.2 访问结构体内的元素

两种方法

struct StudentInfo{
    int id;
    char name[20];
    studentInto *next;
}stu, *p;

访问变量写法

stu.id
stu.name
stu.next

而访问指针变量 p

(*p).id //先解引用为一个 struct 变量
(*p).name
(*p).next

另一种写法

p->id
p->name
p->next

赋值的写法

stu.id = 10086;
int getID = stu.id;

2.8.3 结构体的初始化

使用构造函数，一种用来初始化结构体的函数，有如下几个特征

1. 直接定义在结构体中
2. 不需要写返回类型
3. 函数名与结构体名相同
4. 默认生成，无形参，无函数体，需要自己写

代码CPP · 21 行

struct StudentInfo {
    int id;
    char gender;

    //用以不初始化就定义结构体变量
    StudentInfo(){}
    // 构造函数，用于初始化结构体内部变量
    StudentInfo(int _id, char _gender) {
        id = _id;
        gender = _gender;
    }
    /* 另一种写法，使用成员初始化列表
    StudentInfo(int _id, char _gender) : id(_id), gender(_gender) {}
    */
    //只初始化 gender
    StudentInfo(char _gender){
        gender = _gender;
    }
};

StudentInfo student(12345, 'M');

只要参数个数与类型不完全相同，就可以任意定义多个构造函数，以适应不同的初始化场合。
注意：正是因为没有自己重新定义的构造函数什么都没有，才能够不经初始化就定义结构体变量（思考不初始化构造函数时候是怎么定义的？），所以如果自己重新定义了构造函数，就不能不经过初始化就定义结构体变量！

2.9 补充

2.9.1 cin 和 cout

1. cin 的输入不指定格式，也不需要加取地址运算符&，直接写变量名就可以了
   同时读入多个变量的方法

cin>>n>>db>>c>>str;

如果想要读入一整行，使用 getline 函数

char str[100];
cin.getline(str,100);

引用getline 是 C++ 标准库中的一个函数，用于从输入流（如 cin）中读取一行文本。与 cin 的 >> 操作符不同，getline 可以...

getline 是 C++ 标准库中的一个函数，用于从输入流（如 cin）中读取一行文本。与 cin 的 >> 操作符不同，getline 可以读取包含空格的整行文本，直到遇到换行符（\n）为止。

语法

getline 函数的基本语法如下：

std::getline(std::cin, string_variable);

• std::cin：输入流对象，通常是标准输入流。
• string_variable：一个 std::string 类型的变量，用于存储读取的文本。

示例

以下是一个简单的示例，展示了如何使用 getline 函数搭配 cin 读取用户输入的一行文本：

#include <iostream>
#include <string>

int main() {
    std::string name;

    std::cout << "请输入你的名字：";
    std::getline(std::cin, name);

    std::cout << "你好，" << name << "！" << std::endl;

    return 0;
}

解释

1. 包含头文件：

   #include <iostream>
   #include <string>

   包含必要的头文件，<iostream> 用于输入输出流操作，<string> 用于使用 std::string 类型。

2. 定义字符串变量：

   std::string name;

   定义一个 std::string 类型的变量 name，用于存储用户输入的文本。

3. 提示用户输入：

   std::cout << "请输入你的名字：";

   使用 std::cout 输出提示信息，要求用户输入名字。

4. 读取用户输入：

   std::getline(std::cin, name);

   使用 std::getline 函数从 std::cin 读取一行文本，并将其存储在 name 变量中。

5. 输出结果：

   std::cout << "你好，" << name << "！" << std::endl;

   使用 std::cout 输出欢迎信息，其中包含用户输入的名字。

注意事项

• 读取整行文本：getline 函数会读取整行文本，包括空格和制表符，直到遇到换行符（\n）为止。
• 处理换行符：getline 会自动处理换行符，不会将其包含在读取的文本中。
• 与 cin >> 的区别：cin >> 操作符在读取字符串时会忽略空格和换行符，只读取第一个非空白字符到下一个空白字符之间的内容。

总结

getline 函数是一个非常有用的工具，特别是在需要读取包含空格的整行文本时。通过搭配 cin，你可以方便地从用户输入中读取一行文本，并进行后续处理。 char str[100]; cin.getline(str,100);

2. cout 控制精度好麻烦，还不如 scanf,printf

2.9.2 浮点数的比较

引入一个小量 eps 来对计算机的浮点误差进行修正，再通过一系列的宏定义来实现修正误差的程序一般取

const double eps = 1e-8;

核心部分 (画几个数轴来理解)

const double eps=1e-8;
const double PI=acos(-1.0)

#define Equ(a,b) ((fabs((a)-(b)))<(eps))
#define More(a,b) (((a)-(b))>(eps))
#define Less(a,b) (((a)-(b))<(-eps))
#define MoreEqu(a,b) (((a)-(b))>(-eps))
#define LessEqu(a,b) (((a)-(b))<(eps))

由于精度问题，可能一个 0 在经过一系列运算之后变为一个很小的负数了，那么这个时候进行一些运算比如 sqrt 就会报错，那么这个时候就需要用 eps 保证变量本身在定义域内 比如

代码CPP · 20 行

#include <iostream>
#include <cmath>

const double eps = 1e-9;

int main() {
    double x = -1e-15;

    // 确保 x 在定义域内
    if (x < 0) {
        x = eps;
    }

    // 计算平方根
    double result = std::sqrt(x);

    std::cout << "sqrt(" << x << ") = " << result << std::endl;

    return 0;
}

2.9.3 复杂度

时间复杂度

定义：算法需要执行基本运算的次数所处的等级
基本运算：加减乘除之类可以直接执行的运算

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

for 循环执行了 n 次，时间复杂度为 O(n)，也就是线性增长

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        sum+=arr[i][j];
    }
}

基本运算次数为$n^{2}$次，因此时间复杂度为 O($n^{2}$)
类似无穷小，高等级的幂次会覆盖低等级的幂次
评估时间复杂度：一般 OJ 系统一秒能承受的运算次数大概是$10^{7}$到$10^{8}$，以此作为判断依据

空间复杂度

表示算法需要消耗的最大空间，但是一般都是空间够时间不够，所以可以以时间换空间

编码复杂度

就是看你觉得代码是不是很复杂了，比较泛泛而又定性的一个概念

2.10 黑盒测试

建议直接回去看书，不过这里有一点是值得提一下的
scanf() 函数其实是有返回值的，返回值也就是传入参数的数量，而当没有参数传入时会返回 -1，而且可以用 EOF 来代表 -1

while(scanf("%d",&a)!=EOF){
    ......
}

2.11 lambda 表达式

lambda 表达式是一种可以在代码中随时声明的匿名函数。换句话说，lambda 表达式允许你直接在需要使用函数的地方声明一个临时的函数，而不需要先定义它。

[捕获列表](参数列表) -> 返回类型 { 函数体 };

• 捕获列表：这个让 lambda 可以访问外部变量。
• 参数列表：就像普通函数的参数列表。
• 返回类型：这个可以省略，编译器会自动推导返回类型。
• 函数体：lambda 的真正执行内容，就像一个小型的函数。

一个例子，假设需要在代码中临时计算两个数字的乘积：

#include<bits/stdc++.h>
using namespace std;

int main(){
  int x,y;
  auto multiply=[](int a,int b)->int{
    return a*b;
  }
  cout<<multiply(x,y)<<endl;
  return 0;
}

在这段代码中，我们通过 auto multiply = [](int a, int b) -> int { return a * b; }; 创建了一个 lambda 表达式，这个 lambda 函数接受两个参数 a 和 b，并返回它们的乘积。然后我们调用 multiply(x, y)，输出结果。

再来一个例子：判断一个函数是否是偶数

auto isEven=[](int x)->bool{return x%2==0;}

关于捕获列表

捕获列表决定了 lambda 能够访问哪些外部变量，并且是否以值或引用的方式捕获它们。

#include<bits/stdc++.h>
using namespace std;

int main(){
  int factor=2;
  auto multiplyByFactor=[factor](int x)->int{return x*factor;}
  return 0;
}

在这个例子中，lambda 表达式 multiplyByFactor 捕获了外部变量 factor，并在它的函数体中使用它。捕获列表 [factor] 让 lambda 能够“记住”这个变量的值，即使是在函数调用时这个值已经改变了。

lambda 表达式的一些特殊使用

存储到变量中并调用

#include <iostream>

int main() {
    // 将 lambda 表达式存储在变量中
    auto printMessage = []() {
        std::cout << "Hello, World!" << std::endl;
    };

    // 在后面需要的时候调用它
    printMessage(); // 输出：Hello, World!
    printMessage(); // 可以多次调用
    return 0;
}

返回值为 Lambda 表达式

可以编写一个函数，返回一个 lambda 表达式供后续调用：

#include <iostream>

auto createMultiplier(int factor) {
    return [factor](int x) { return x * factor; };
}

int main() {
    auto doubleValue = createMultiplier(2); // 创建一个将值乘以 2 的 lambda
    auto tripleValue = createMultiplier(3); // 创建一个将值乘以 3 的 lambda

    std::cout << doubleValue(5) << std::endl; // 输出：10
    std::cout << tripleValue(5) << std::endl; // 输出：15

    return 0;
}

引用在 C++ 的 lambda 表达式中，[&] 表示按引用捕获所有在 lambda 函数体中使用到的外部变量。这意味着： 如果在 lambda...

在 C++ 的 lambda 表达式中，[&] 表示按引用捕获所有在 lambda 函数体中使用到的外部变量。这意味着：

• 如果在 lambda 内部使用了外部变量，那么该变量是以引用的方式捕获的。
• 你在 lambda 内对这些变量的修改会直接影响到它们在外部的值。

示例

#include <iostream>

int main() {
    int a = 5, b = 10;
    
    // 定义一个 lambda 表达式，按引用捕获所有外部变量
    auto func = [&]() {
        a += 1;
        b += 1;
        std::cout << "Inside lambda: a = " << a << ", b = " << b << std::endl;
    };
    
    func();  // 调用 lambda 表达式
    std::cout << "Outside lambda: a = " << a << ", b = " << b << std::endl;
    
    return 0;
}

输出：

Inside lambda: a = 6, b = 11
Outside lambda: a = 6, b = 11

如上所示，由于 [&] 按引用捕获，所以 lambda 内对 a 和 b 的修改会直接影响外部的变量。

与其他捕获方式的对比

• [=]：按值捕获所有外部变量，lambda 内对变量的修改不会影响外部变量。
• [a, &b]：对变量 a 按值捕获，对变量 b 按引用捕获。这种方式可以混合使用捕获方式。

总结一下，[&] 是一种便捷的捕获方式，当你需要在 lambda 内使用外部变量并希望能直接修改它们时，这种方式非常有用。

lambda 表达式递归的例子（返回值无法确定时）

#include <functional> // 需要添加此头文件

// 在 main 函数内：
std::function<void(int, int)> dfs; // 显式声明为 function 类型
dfs = [&](int now, int step) {
    if (step >= f[now]) return;
    f[now] = step;
    if (now == b) return;
    vis[now] = true;
    if (now + k[now] <= n && !vis[now + k[now]]) {
        dfs(now + k[now], step + 1); // 现在可以正确递归
    }
    if (now - k[now] >= 1 && !vis[now - k[now]]) {
        dfs(now - k[now], step + 1);
    }
    vis[now] = false;
};

第 4 章 入门篇（2）——算法初步

4.1 排序

4.1.1 选择排序

4.1.2 插入排序

4.1.3 排序题与 sort 函数的应用

引用当然可以！std::sort 中的比较函数用于定义排序的顺序。比较函数需要返回一个布尔值，表示两个元素的相对顺序。具体来说，比较函数应该满足以下...

当然可以！std::sort 中的比较函数用于定义排序的顺序。比较函数需要返回一个布尔值，表示两个元素的相对顺序。具体来说，比较函数应该满足以下条件：

1. 严格弱序（Strict Weak Ordering）：比较函数必须定义一个严格弱序关系，这意味着它必须满足以下条件：

   • 反自反性（Irreflexivity）：对于所有 x，comp(x, x) 必须返回 false。
   • 反对称性（Antisymmetry）：如果 comp(x, y) 返回 true，那么 comp(y, x) 必须返回 false。
   • 传递性（Transitivity）：如果 comp(x, y) 返回 true 且 comp(y, z) 返回 true，那么 comp(x, z) 必须返回 true。

2. 一致性（Consistency）：如果 comp(x, y) 和 comp(y, x) 都返回 false，那么 x 和 y 被认为是相等的。

示例：比较整数

假设我们有一个整数数组，我们希望按升序排序：

代码CPP · 21 行

#include <iostream>
#include <algorithm>  // 包含 std::sort
#include <vector>     // 包含 std::vector

// 比较函数：按升序排序
bool compareAscending(int a, int b) {
    return a < b;
}

int main() {
    std::vector<int> numbers = {5, 3, 8, 1, 2};

    std::sort(numbers.begin(), numbers.end(), compareAscending);

    for (int number : numbers) {
        std::cout << number << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果：

1 2 3 5 8

示例：比较字符串

假设我们有一个字符串数组，我们希望按字典序（字母顺序）排序：

代码CPP · 22 行

#include <iostream>
#include <algorithm>  // 包含 std::sort
#include <vector>     // 包含 std::vector
#include <string>     // 包含 std::string

// 比较函数：按字典序排序
bool compareLexicographically(const std::string &a, const std::string &b) {
    return a < b;
}

int main() {
    std::vector<std::string> names = {"Alice", "Bob", "Charlie", "David", "Eve"};

    std::sort(names.begin(), names.end(), compareLexicographically);

    for (const auto &name : names) {
        std::cout << name << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果：

Alice Bob Charlie David Eve

示例：比较结构体

假设我们有一个包含学生信息的结构体数组，我们希望按年龄排序：

代码CPP · 33 行

#include <iostream>
#include <algorithm>  // 包含 std::sort
#include <vector>     // 包含 std::vector
#include <string>     // 包含 std::string

struct Student {
    std::string name;
    int age;
    float gpa;
};

// 比较函数：按年龄排序
bool compareStudentsByAge(const Student &a, const Student &b) {
    return a.age < b.age;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 20, 3.8},
        {"Bob", 22, 3.5},
        {"Charlie", 21, 3.7},
        {"David", 19, 3.9},
        {"Eve", 23, 3.6}
    };

    std::sort(students.begin(), students.end(), compareStudentsByAge);

    for (const auto &student : students) {
        std::cout << "Name: " << student.name << ", Age: " << student.age << ", GPA: " << student.gpa << std::endl;
    }

    return 0;
}

输出结果：

Name: David, Age: 19, GPA: 3.9
Name: Alice, Age: 20, GPA: 3.8
Name: Charlie, Age: 21, GPA: 3.7
Name: Bob, Age: 22, GPA: 3.5
Name: Eve, Age: 23, GPA: 3.6

示例：多条件比较

假设我们希望在年龄相同的情况下，按 GPA 排序，如果 GPA 也相同，则按名字排序：

代码CPP · 39 行

#include <iostream>
#include <algorithm>  // 包含 std::sort
#include <vector>     // 包含 std::vector
#include <string>     // 包含 std::string

struct Student {
    std::string name;
    int age;
    float gpa;
};

// 比较函数：按年龄、GPA、名字排序
bool compareStudents(const Student &a, const Student &b) {
    if (a.age != b.age) {
        return a.age < b.age;
    }
    if (a.gpa != b.gpa) {
        return a.gpa > b.gpa;  // 按 GPA 降序排序
    }
    return a.name < b.name;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 20, 3.8},
        {"Bob", 22, 3.5},
        {"Charlie", 21, 3.7},
        {"David", 19, 3.9},
        {"Eve", 23, 3.6}
    };

    std::sort(students.begin(), students.end(), compareStudents);

    for (const auto &student : students) {
        std::cout << "Name: " << student.name << ", Age: " << student.age << ", GPA: " << student.gpa << std::endl;
    }

    return 0;
}

输出结果：

Name: David, Age: 19, GPA: 3.9
Name: Alice, Age: 20, GPA: 3.8
Name: Charlie, Age: 21, GPA: 3.7
Name: Bob, Age: 22, GPA: 3.5
Name: Eve, Age: 23, GPA: 3.6

总结

比较函数是 std::sort 的核心部分，它决定了排序的顺序。比较函数需要返回一个布尔值，表示两个元素的相对顺序。通过编写不同的比较函数，你可以实现各种排序需求。

1. 相关结构体的定义

排序题一般会给出个体的许多信息，为了方便常常把这些信息统统存在一个结构体中

struct Student{
	char name[10];
	char id[10];
	int score;
}stu[100100];

2.cmp 函数的编写 (strcmp 函数依据字典序返回两个字符串大小的比较结果)

比如一个排序规则：如果两个学生分数不相同那么分数高的排在前面，否则将姓名字典序小的排在前面
就可以写出这样的 cmp 函数

bool cmp(Student a,Student b){
    if(a.score!=b.score) return a.score>b.score;
    else return strcmp(a.name,b.name)<0;
}//注意 strcmp 的返回值不一定是 1 或者 -1，与 IDE 有关

3.排名的实现

规则一般是：分数不同的排名不同，分数相同的排名相同但是占用一个排位

对这种要求一般需要在结构体类型定义的时候就把排名这一项加入结构体中，于是在数序排序完成之后就有两种方法来实现排名的计算

1. 先将数组第一个个体排名记作 1（这个个体数组下标为 0），然后遍历剩余的个体：

   • 如果当前个体的分数等于上一个个体的分数，那么当前个体的排名=上一个个体的排名
   • 否则，当前个体的排名=数组下标 +1

   stu[0].r=1;
   for(int i=1;i<n;i++){
       if(stu[i].score==stu.[i-1].score){
           stu[i].r=stu[i-1].r;
       }
       else{
           stu[i].r=i+1;
       }
   }

2. 而有些时候也不一定需要记下来排名，直接输出就好了

   int r=1;
   for(int i=0;i<n;i++){
       if(i>0&&stu[i].score!=stu[i-1].score){
           r=i+1;
       }
       //输出当前个体信息
   }

4.2 散列

4.2.1 散列的定义与整数散列

散列 (hash) 是一种常用的算法思想

比如用 hashTable 的 bool/int 数组去判断一个数是否出现过 即：把输入的数作为数组的下标来对这个数的性质进行统计,是一个很好的以空间换时间的策略，因为查询的复杂度是 O(1)

下面我们给出 hash 的定义，可以浓缩成一句话：将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素，其中这个转换函数被称为散列函数 H

即：如果元素在转换前为 key，那么转换之后就是一个整数 H(key),再把转换完的 hash 值用一个数组去记录

对于key 为整数的情况：常用的散列函数有：

• 直接定址法：H(key)=key 或者 H(key)=a*key+b 做一个线性变换

• 平方取中法：取 key 的平方中间的若干位作为 hash 值

• 除留余数法：把 key 除以一个数 mod 得到的余数作为 hash 值的方法，即H(key)=key%mod

  通过这个散列函数可以把很大的数转化为不超过 mod 的整数，这样就可以把它视为可行的数组下标 (需要注意表长>=mod)。显然当 mod 是一个素数时，H(key) 尽可能覆盖[0,mod) 范围内的每一个数。因此一般为了方便起见取 TSize 为一个素数，而 mod 直接取成与 TSize 相等

  但是很容易注意到这个方法可能会有两个不同的数 key1 与 key2 使得 H(key1)==H(key2)，这种情况叫“冲突”

  下面有三种方法解决冲突，其中第一种和第二种方法都计算了新的 hash 值，又称为开放定址法

  1. 线性探查法：当得到 key 的 hash 值 H(key),但是表中下标为 H(key) 的位置已经被某个其他元素使用了那么就检査下一个位置 H(key)+1 是否被占，如果没有，就使用这个位置;否则就继续检查下一个位置 (也就是将 hash 值不断加 1)。如果检查过程中超过了表长，那么就回到表的首位继续循环，直到找到一个可以使用的位置，或者是发现表中所有位置都已被使用。显然，这个做法容易导致扎堆，即表中连续若于个位置都被使用，这在一定程度上会降低效率。

  2. 平方探査法：在平方探查法中，为了尽可能避免扎堆现象，当表中下标为 H(key) 的位置被占时，将按下面的顺序检査表中的位置:H(key)+$1^{2}$、H(key)-$1^{2}$、H(key)+ $2^{2}$、H(key)- $2^{2}$、H(key)+ $3^{2}$…。如果检査过程中 H(key)+$k^{2}$超过了表长 TSize，那么就把 H(key)+$k^{2}$对表长 TSize 取模;

     如果检查过程中出现 H(key)-$k^{2}$<0 的情况 (假设表的首位为 0),那么将 ((H(key)-$k^{2}$)% TSize+ TSize)% TSize 作为结果 (等价于将 H(key)-$k^{2}$不断加上 TSize 直到出现第一个非负数)。如果想避免负数的麻烦，可以只进行正向的平方探查。可以证明，如果 k 在 [0,TSize) 范围内都无法找到位置，那么当 k>TSize 时，也一定无法找到位置。

  3. 链地址法（拉链法）：和上面两种方法不同，链地址法不计算新的 hash 值，而是把所有 H(key) 相同的 key 连接成一条单链表 (可以在学习完 7.3 小节后回过头来看)。这样可以设定一个数组 Link，范围是 Link[0]~ Link[mod]，其中 Link[h]存放 H(key)=h 的一条单链表，于是当多个关键字 key 的 hash 值都是 h 时，就可以直接把这些冲突的 key 直接用单链表连接起来，此时就可以遍历这条单链表来寻找所有 H(key)=h 的 key。当然，一般来说，可以使用标准库模板库中的 map(见 6.4 节) 来直接使用 hash 的功能 (C++11 以后可以用 unordered map，速度更快)，因此除非必须模拟这些方法或是对算法的效率要求比较高，一般不需要自己实现上面解决冲突的方法。

4.2.2 字符串 hash 初步

如果 key 不是整数，该如何设计散列函数？

一个例子是：如何将一个二维整点 P 的坐标映射为一个整数，使得整点 P 可以由该整数唯一地代表。假设一个整点 P 的坐标是 (x,y)，其中 0<x,y<Range，那么可以令 hash 函数为 H(P)=x*Range+y，这样对数据范围内的任意两个整点 P1 与 P2,H(P1) 都不会等于 H(P2),就可以用 H(P) 来唯一地代表该整点 P，接着便可以通过整数 hash 的方法来进一步映射到较小的范围。本节的重点在于字符串 hash。字符串 hash 是指将一个字符串 S 映射为一个整数，使得该整数可以尽可能唯一地代表字符串 S。本节只讨论将字符串转换为唯一的整数，进阶部分在 12.1 节。

为了讨论问题方便，先假设字符串均由大写字母 A~Z 构成。在这个基础上，不妨把 A~Z 视为 0~25，这样就把 26 个大写字母对应到了二十六进制中。接着，按照将二十六进制转换为十进制的思路，由进制转换的结论可知，在进制转换过程中，得到的十进制肯定是唯一的，由此便可实现将字符串映射为整数的需求 (注意：转换成的整数最大为是$26^{len}$-1(len 为字符串长度)，代码如下

int hashFunc(char s[],int len){ //hash 函数，将字符串 S 转换为整数
    int id=0;
    for(int i=0;i<len;i++){
        id=id*26+(s[i]-'A'); //将 26 进制转化为 10 进制
    }
    return id;
}

显然 len 不能太长了，如果里面还有小写字母可以把 26 进制变成 52 进制，也是一样的

而如果出现了数字，一般有两种处理方法: ① 按照小写字母的处理方法，增大进制数至 62。

②如果保证在字符串的末尾是确定个数的数字，那么就可以把前面英文字母的部分按上面的思路转换成整数，再将末尾的数字直接拼接上去。例如对由三个字符加一位数字组成的字符串“BCD4”来说，就可以先将前面的“BCD”转换为整数 731，然后直接拼接上末位的 4 变为 7314 即可。下面的代码体现了这个例子：

int hashFunc(char s[],int len){ //hash 函数，将字符串 S 转换为整数
    int id=0;
    for(int i=0;i<len-1;i++){
        id=id*26+(s[i]-'A'); //将 26 进制转化为 10 进制
    }
    id=id*10+(s[len]-'0');
    return id;
}

4.3 递归

4.3.1 分治

分治全称：分而治之，也就是将原问题划分成若干个规模较小而结构与原问题相同或相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到原问题的解，也就是说分治法可以分为三步

1. 分解
2. 解决
3. 合并

需要指出的是分治法分解出的子问题应该是相互独立而没有交叉的，如果存在两个子问题有交叉部分，那么就不应该用分治法求解

特别地，把子问题个数为 1 的情况称之为减治

分治作为一种算法思想，既可以使用递归的手段去实现，也可以同非递归的手段去实现，不过视情况而定

4.3.2 递归

在编写递归函数的时候，可以当系统库里有一个同名的函数可以实现所需要的功能；当函数编写完成之后，逻辑也就自洽了

递归，在于反复调用自身函数，但是每次把问题范围缩小，直到范围缩小到可以直接得到边界数据的结果，然后再在返回的路上求出对应的解，这样看来递归很适合实现分治思想

写递归的时候不要陷入无尽的分析子过程，分析好边界条件，写好本过程要处理什么东西，然后剩下的就是相信子过程能处理好你的求解问题就行了。和数学归纳法一个套路

• 确定问题
• 解决基准问题
• 拆解问题

递归的逻辑中一般有两个重要概念

1. 递归边界
2. 递归式（或称递归调用）

给出一个例子

//计算 n 的阶乘
//考虑 n! 的计算式，不难得出递归式 F(n)=nF(n-1)
//所以可以把 F(n) 变成 F(n-1),然后一直递归下去...
//什么时候是尽头呢？考虑 0!=1，不妨以 F(0)=1 作为递归边界
//即：规模减小到 n=0 的时候开始"回头"

#include<bits/stdc++.h>
using namespace std;

int F(int n){
    if(n==0) return 1; //到达递归边界时返回
    else return n*F(n-1); //没有到达边界时使用递归式递归下去
}

再给出一个例子

//计算 Fibonacci 数列的第 n 项
#include<bits/stdc++.h>
using namespace std;

int F(int n){
    if(n==1||n==2) return 1; //到达递归边界时返回
    else return F(n-1)+F(n-2); //没有到达边界时使用递归式递归下去
}
//其实这就是分治法的一种应用，
//对于给定的 n 把求解 F(n) 的问题分解成求 F(n-1) 和 F(n-2) 这两个子问题，
//而 F(0)==F(1)==1 是 n 很小的时候问题的直接解决

由上面两个例子可以知道，实现一个递归函数需要两样东西：递归边界与递归式，其中递归边界用来返回最简单底层的结果，递归式用来减少数据规模并向下一层递归。

再给出一个例子

代码CPP · 29 行

////按照字典序输出全排列
//可以分成若干个子问题：输出 1 开头的全排列，输出 2 开头的全排列
//...输出以 n 开头的全排列
//于是不妨设定一个数组 P 用以存放当前的排列
//再设定一个 hashTable，其中 hashTable[x]==true 表示 x 在数组 P 中

#include<bits/stdc++.h>
using namespace std;
const int maxn=11;
//P 为当前排列，hashTable 记录整数 x 是否已在 P 中
int n,P[maxn],hashTable[maxn]={false};
//当前处理排列的第 index 号位
void generateP(int index){
    if(index==n+1){//递归边界，已经处理完排列的 1~n 位
        for(int i=1;i<=n;i++){
            cout<<P[i]; //输出当前排列
        }
        cout<<endl;
        return;
    }
    for(int x=1;x<=n;x++){//枚举 1~n，试图将 x 填入 P[index] 中
        if(hashTable[x]==false){
            P[index]=x; //令 P 的第 index 位为 x，即把 x 加入当前排列
            hashTable[x]=true; //记 x 已在 P 中
            generateP(index+1); //处理排列的第 index+1 号
            hashTable[x]=false; //已处理完 P[index] 为 x 的子问题，还原状态
        }
    }
}

最后来看 n 皇后问题

指的是在一个 n*n 的棋盘上放置 n 个皇后使得这 n 个皇后两两均不在同一行、同一列、同一对角线上，求合法的方案数

代码CPP · 37 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=11;
//每行只能放置一个皇后，每列也只能放置一个
//把 n 列皇后所在的行号依次写出，就会是 1~n 的一个排列
//只需要筛选这每个排列中合法的即可
//考虑：递归边界、递归式
//由于到达递归边界时表示生成了一个排列，
//所以需要在其内部判断是否为合法方案
//如何判断？在一个排列中两两遍历两个皇后，
//判断他们是否在一条对角线上
//如果不是就 count++
int count=0;
int n,P[maxn],hashTable[maxn]={false};
void A(int index){
    if(index==n+1){//递归边界，表示生成了一个排列（类似上一题）
        bool flag=true;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(abs(i-j)==abs(P[i]-P[j])){//如果在一条对角线上，斜率为±1
                    flag=false;
                    break;
                }
            }
        }
        if(flag) count++;
        return;
    }
    for(int x=1;x<=n;x++){//就是上一题全排列，因为不能在同一行同一列和全排列的数学本质相同
        if(!hashTable[x]){//这一行还没被占用
            P[index]=x;
            hashTable[x]=true;
            A(index+1);
            hashTable[x]=false;
        }
    }
}

但是这种解法事实上太暴力了，因为已经生成一部分排列的时候就可以判断这个排列符不符合要求了，如果不符合也就没必要递归了，直接返回上一层，这种做法一般称之为回溯法

代码CPP · 28 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=11;
int count=0;
int n,P[maxn],hashTable[maxn]={false};
void A(int index){
    if(index==n+1){
        count++; //能到这里的一定符合要求
        return;
    }
    for(int x=1;x<=n;x++){//第 x 行
        if(!hashTable[x]){//第 x 行还没有皇后
            bool flag=true;
            for(int pre=1;pre<index;pre++){//遍历之前的皇后
                if(abs(index-pre)==abs(P[index]-P[pre])){
                    flag=false;
                    break;
                }
            }
            if(flag){
            P[index]=x;
            hashTable[x]=true;
            A(index+1);
            hashTable[x]=false;
            }
        }
    }
}

4.4 贪心

4.4.1 简单贪心

贪心是求解一类最优化问题的方法，它总是考虑在当前状态下局部最优（或较优）的策略，来使全局的结果达到最优（或较优）。平常来说，证明贪心法的思路是反证法，即假设策略不能导致最优解，然后通过一系列推导来得到矛盾

例题 PAT B1020 月饼

题意

现有月饼需求量为 D，已知 n 种月饼各自的库存量和总售价，问如何销售这些月饼，使得可以获得的收益最大，并求最大收益

思路

贪心策略：总是选择单价最高的月饼出售，可以获得最大的利润。因此对于每一种月饼都根据其库存量和总售价来计算出该种月饼的单价，之后再把所有单价由低到高排序

之后从单价高的月饼开始枚举，分两种情况

1. 如果该种月饼的库存量不足以填补需求量$\Rightarrow$全部卖出，需求量-=该种月饼库存量，收益值+=该种月饼总售价
2. 如果足够供应，则直接算

[!CAUTION] 需要注意的几点

1. 月饼的库存量和总售价可以是浮点数，虽然题目里只说了 D 是整数，但是为了计算方便最好也定义成 double 型
2. 当库存量>需求量时，不能先令需求量为 0 再计算收益，否则会使得该步收益为 0
3. 库存>需求时候记得中断循环

代码实现

代码CPP · 42 行

#include<bits/stdc++.h>
using namespace std;
int n,d;

struct mooncake{
    double storage;
    double price_all;
    double price;
}cake[1010];

bool cmp(mooncake a,mooncake b){
    return a.price>b.price;
}

int main(){
    scanf("%d%d",n,d);

    for(int i=0;i<n;i++){
        scanf("%d",cake[i].storage);
    }
    for(int i=0;i<n;i++){
        scanf("%d",cake[i].price_all);
        cake[i].price=cake[i].price_all/cake[i].storage;
    }

    sort(cake,cake+n,cmp);

    double ans=0;

    for(int i=0;i<n;i++){
        if(cake[i].storage>=d){
            ans+=d*cake[i].price;
            break;
        }
        else{
            ans+=cake[i].price_all;
            d-=cake[i].storage;
        }
    }
    printf("%.2f",ans);
    return 0;
}

例题 PAT B1023 组个最小数

题意

给定若干个数字 0~9，在 0 不做首位的前提下可以任意排列但必须全部使用，输出可以组成的最小的数

分析

先输出最高位：从 1-9 中选最小的输出

之后：依次按照 0-9 的顺序输出数字，输出顺序为其剩余的次数

代码实现

代码CPP · 25 行

#include<bits/stdc++.h>
using namespace std;

int n,cnt[10],temp;

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&temp);
        cnt[temp]++;
    }
    for(int i=1;i<=9;i++){
        if(cnt[i]!=0){
            printf("%d",i);
            cnt[i]--;
            break;
        }
    }
    for(int i=0;i<=9;i++){
        for(int j=0;j<cnt[i];j++){
            printf("%d",i);
        }
    }
    return 0;
}

引用【洛谷 P4447 [AHOI2018 初中组] 分组】 题目描述 小可可的学校信息组总共有 $n$ 个队员，每个人都有一个实力值 $a_i$。...

【洛谷 P4447 [AHOI2018 初中组] 分组】

题目描述

小可可的学校信息组总共有 $n$ 个队员，每个人都有一个实力值 $a_i$。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 $n$ 个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：$[1, 2, 3, 4, 5]$ 是合法的分组方案，因为实力值连续；$[1, 2, 3, 5]$ 不是合法的分组方案，因为实力值不连续；$[0, 1, 1, 2]$ 同样不是合法的分组方案，因为出现了两个实力值为 $1$ 的选手。

如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。

注意：实力值可能是负数，分组的数量没有限制。

输入格式

输入有两行：

第一行一个正整数 $n$，表示队员数量。
第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个队员的实力。

输出格式

输出一行，包括一个正整数，表示人数最少的组的人数最大值。

样例 #1

样例输入 #1

7
4 5 2 3 -4 -3 -5

样例输出 #1

3

提示

【样例解释】分为 $2$ 组，一组的队员实力值是 ${4, 5, 2, 3}$，一组是 ${-4, -3, -5}$，其中最小的组人数为 $3$，可以发现没有比 $3$ 更优的分法了。

【数据范围】

对于 $100%$ 的数据满足：$1\leq n\leq 100000$，$|a_i|\leq10^9$。

本题共 $10$ 个测试点，编号为 $1\sim10$，每个测试点额外保证如下：

测试点编号	数据限制
$1\sim2$	$n\leq 6, 1\leq a_i \leq 100$
$3\sim4$	$n\leq 1000, 1\leq a_i\leq 10^5$ 且 $a_i$ 互不相同
$5\sim6$	$n\leq 100000, a_i$ 互不相同
$7\sim8$	$n\leq 100000, 1\leq a_i \leq10^5$
$9\sim 10$	$n\leq 100000, -10^9 \leq a_i \leq 10^9$

思路：贪心，//贪心策略：每次加人都加在人数最少的那个队里面，这样可以最大化最小组的人数

代码CPP · 44 行

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const int inf=0x3f3f3f3f;

int main(){
  ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  //贪心策略：每次加人都加在人数最少的那个队里面，这样可以最大化最小组的人数
  
  map<int,priority_queue<int,vector<int>,greater<int>>> group;
  //map 的键是这个组的实力值最大值，值是用来存储已经组建的所有符合该最大实力值的组的人数，队首的是人数最少的
  
  //遍历每个队员的实力值，进行分组
  for(int i=0;i<n;i++){
    int groupSize=0; // 当前队员加入后的组大小

    auto it=group.find(a[i]-1); //查看当前实力值减去 1 的分组（前一个实力值的组）
    if(it!=group.end()){
      if(!it->second.empty()){ //这个其实是使用队列 (优先队列也是队列) 的好习惯，先判断非空再访问
        groupSize=it->second.top();
        it->second.pop();
      }
    }
    groupSize++;
    group[a[i]].push(groupSize);
  }
  
  int minGroupSize=inf;
  for(auto& now:group){ //区别上一个循环的 it 是迭代器 (指针)，这里的是 map 类型，所以访问值不需要用->
    if(!now.second.empty()){
      minGroupSize=min(minGroupSize,now.second.top());
    }
  }
  
  cout<<(minGroupSize==inf?0:minGroupSize)<<endl;
  return 0;
}

4.4.2 区间贪心

由一个问题引入：

区间不相交问题

给出 N 个开区间 (x,y)，从中选择尽可能多的开区间使得这些区间两两没有交集。输出满足条件的区间的个数。

例如对于开区间 (1,3) (2,4) (3,5) (6,7) 来说最多可以选出三个区间 (1,3) (3,5) (6,7) 满足题意

首先考虑最简单的情况，如果开区间$I_1$被开区间$I_2$包含，那么选择$I_1$会是更好的选择，因为如果选择$I_1$，就会有更大的空间去容纳别的开区间

接下来把开区间按左端点 x 从大到小排序，如果去掉区间包含的情况就必有$y_1>$$y_2 > \cdots$ $y_n $成立，观察图片可以发现$I_1$的右边必然有一段不与其他区间重合，如果把他去掉那么$I_1$的左边剩余部分就会包含于$I_2$，则由上一种情况又可知应当选择$I_1$，因此对于这种情况总是选择左端点最大的区间

代码实现

代码CPP · 33 行

#include<bits/stdc++.h>
using namespace std;

const int max1=100;

struct interval{
    int x,y;
}iv[max1+5];

bool cmp(interval a,interval b){
    if(a.x!=b.x) return a.x>b.x;
    else return a.y<b.y;
}
int n;

int main(){
    while(scanf("%d",&n),n!=0){ //这样可以保证 n 小于等于 0 的时候不会进行
        for(int i=0;i<n;i++){
        scanf("%d%d",&iv[i].x,&iv[i].y);
        }
        sort(iv,iv+n,cmp);
        //ans 记录满足条件的区间个数，lastX 记录上一次被选中的区间的左端点
        int ans=0,lastX=iv[0].x;
        for(int i=1;i<n;i++){
            if(iv[i].y<=lastX){
                lastX=iv[i].x;
                ans++;
            }
        }
        printf("%d",ans);
    }
    return 0;
}

上面这段代码中 while 里面的写法，复习一下逗号运算符

逗号运算符的作用是依次执行其左右两边的表达式，并返回右边表达式的结果。

while (scanf("%d", &n), n != 0) 的执行过程：

• 先执行 scanf("%d", &n)：从输入中读取一个整数并存储到变量 n 中。
• 然后计算 n != 0：判断 n 是否不等于 0。
• 整个逗号表达式的结果是 n != 0 的值（true 或 false）。
• while 循环会根据 n != 0 的结果决定是否继续循环

事实上总是选择右端点最小的区间的策略也是可行的

类似的问题还有区间选点问题，即给出 N 个闭区间，求最少需要确定多少个点使得每个闭区间中都至少存在一个点

4.5 二分

4.5.1 二分查找

由于每一步都可以去除当前区间的一半元素，因此时间复杂度是 O(logN)

要求：a[]为严格递增（递减）序列

代码实现

int binarysearch(int a[],int left,int right,int x){
    int mid;
    while(left<=right){ //因为 left>right 就无法形成闭区间了
        mid=(left+right)/2;
        if(a[mid]==x) return mid;
        else if(a[mid]<x){
            left=mid+1;
        }
        else{
            right=mid-1;
        }
    }
    return -1; //查找失败，返回 -1
}

序列严格递减的情况是同理的

如果二分上界超过 INTMAX/2，可能会导致 mid=(left+right)/2 中的 left+right 爆掉，所以一般使用等价语句mid=left+(right-left)/2

讨论一个更进一步的问题，如果序列并非严格单调，如何求出待查询元素的左闭右开的存在区间[L,R)，如果序列中没有 x，也可以把 L 和 R 理解成假设序列中存在 x，则 x 应该在的位置

可以把这个问题拆解成两个（分治）:

1.求序列中第一个≥x 的元素的位置

int lower_bound(int a[],int left,int right,int x){
    int mid;
    while(left<right){ //当 left=right 的时候就是所需的下界
        mid=left+(right-left)/2;
        if(a[mid]>=x){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;
}

1. 循环条件为left<right而非left≤right，因为需要的结果就是left=right夹出来的
2. 二分下界应为0，但是上界是n-1还是n？考虑到x可能不存在，而我们求出来的又是“假设x存在他应该在的位置”（也就是最大的地方），所以开始运行的时候应该取left=0，right=n

2.求序列中第一个大于x的元素的位置

int upper_bound(int a[],int left,int right,int x){
    int mid;
    while(left<right){
        mid=left+(right-left)/2;
        if(a[mid]>x){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;
}

容易注意到这两个函数的唯一区别就是把a[mid]>=x改成了a[mid]<x，其余完全一致

其实这两个函数都在解决这样一个问题：寻找有序序列中第一个满足某条件的元素

对于lower_bound函数而言，寻找的就是第一个满足条件“值大于等于x”的元素的位置，而对于upper_bound函数而言，寻找的就是第一个满足条件“值大于x”的元素的位置，则这样的一个“条件”在序列中一定是从左到右先不满足，然后满足（否则将此条件取反）

归纳

//解决“寻找有序序列中第一个满足某条件的元素的位置”的问题的固定模板
//二分区间为左闭右闭的[left,right]，初值必须能够覆盖解的所有可能取值
int solve(int left,int right){
    int mid;
    while(left<right){
        if(条件成立){ //条件成立，第一个满足条件的元素的位置<=mid
            right=mid;
        }
        else{ //条件不成立，则第一个满足条件的元素的位置>mid
            left=mid+1;
        }
    }
    return left;
}

另外，如果想要寻找最后一个满足“条件C”的元素的位置，则可以先求第一个满足“条件!C”的元素的位置，然后再把该元素的位置-1即可

另外，就算二分区间不是闭区间，也可以操作

比如当二分区间为左开右闭区间(left,right]，那么循环条件应当为left+1<right，也即退出循环的时候有left+1=right成立，使得夹逼得到的唯一，而由于变为了左开，left的初值要比解的最小取值要小1，同时语句left=mid+1应该改成left=mid，返回值也应该是right(毕竟闭区间是可以取到的)，代码如下

//解决“寻找有序序列中第一个满足某条件的元素的位置”的问题的固定模板
//二分区间为左开右闭区间 (left,right]，初值必须能够覆盖解的所有可能取值
int solve(int left,int right){
    int mid;
    while(left+1<right){
        if(条件成立){ //条件成立，第一个满足条件的元素的位置<=mid
            right=mid;
        }
        else{ //条件不成立，则第一个满足条件的元素的位置>mid
            left=mid;
        }
    }
    return right;
}

如何判断lower_bound函数和upper_bound函数的查询是否成功？可以判断上界是否为n

（因为upper_bound函数求的也是满足条件的元素的位置的后面的第一个）

4.5.2 二分法拓展

如何计算$\sqrt 2$的近似值

对于$f(x)=x^2$当$x>0$时$f(x)$单调递增，那么我们可以考虑使用二分法来逼近，取精确到$10^{-5}$为例

#include<bits/stdc++.h>
using namespace std;

const double eps = 1e-5; //精度为 10^{-5}
double f(double x){ //计算 f(x)
    return x*x;
}

double calsqrt(){
    double left=1,right=2,mid;
    while(right-left>eps){ //回顾之前学的高精度判断相等
        mid=left+(right-left)/2;
        if(f(mid)>2) right=mid;
        else left=mid;
    }
    return mid;
}

木棒切割问题

给出N根长度已知的木棒，现在希望通过切割他们来得到至少K段长度相等的木棒（长度必须是整数），问这些长度相等的木棒最长能有多长？

容易注意到K越大，则L越小，那么考虑到这个我们可以使用二分法

int F(L){
	给定长度，计算当前总段数
}

int 二分 (){
	left=1
	right=杆子最长的长度
	while(left<right){
		mid=直接算
		cnt=F(mid)
		if(cnt>=k) left=mid
		else right=mid
	}
	return mid;
}

4.5.3 快速幂

给定一个问题

给定三个正整数a、b、m（a<$10^9$，b<$10^6$，$1$<m<$10^9$），求$a^{b}$%m

可以采用这种代码，时间复杂度为O(b)

xxxxxxxxxx typedef long long LL;LL LLpow(LL a,LL b,LL m){    LL ans=1;    for(int i=0;i<b;i++){        ans=ans*a%m; //考虑模运算的性质 (a×b)modm=[(amodm)×(bmodm)]modm    }    return ans;}cpp

代码中使用LL而非int是防止两个int相乘之后溢出

考虑一个更进一步的问题

给定三个正整数a、b、m（a<$10^9$，b<$10^{18}$，$1$<m<$10^9$），求$a^{b}$%m

对于这个问题，如果还是按上面的做法显然是不行的

这里要使用快速幂的用法，它基于二分的思想，因此也常常被称之为二分幂，快速幂基于以下事实

1. 如果b是奇数，那么有$a^b=a*a^{b-1}$
2. 如果b是偶数，那么有$a^b=a^{b/2}*a^{b/2}$

显然，b是奇数的情况总可以在下一步转换为b是偶数的情况，而b是偶数的情况总可以在下一步转换为b/2的情况，这样在log(b)级别的转换后，就可以把b变为0，而任何正整数的0次方都是1

举个例子，如果需要求$2^{10}$

1. 对$2^{10}$来说，由于幂次10为偶数，因此需要先求$2^{5}$，然后有$2^{10}=2^{5}*2^{5}$
2. 对于$2^{5}$来说，由于幂次5为奇数，因此先要求$2^{4}$，然后有$2^5=2*2^4$
3. 对于$2^4$来说，由于幂次4为偶数，因此先要求$2^2$，然后有$2^4=2^2*2^2$
4. 对于$2^2$来说，由于幂次2为偶数，因此需要先求$2^1$，然后有$2^2=2^1*2^1$
5. 对于$2^1$来说，由于幂次1为奇数，因此需要先求$2^0$，然后有$2^1=2*2^0$
6. $2^0=1$，然后从下往上依次回退计算即可

这显然是递归的思想，于是可以得到快速幂的递归写法，时间复杂度为O(logb)

typedef long long LL;
LL binaryPow(LL a,LL b,LL m){
    if(b==0) return 1;
    if(b%2==1) return a*binaryPow(a,b-1,m)%m;
    else{
        LL mul=binaryPow(a,b/2,m);
        return mul*mul%m;
    }
}

上面的代码中，条件if(b%2==1)可以用if(b&1)代替，这是因为b&1进行位与操作，判断b的末位是否为1，因此当b为奇数时b&1返回1，if条件成立，这样写执行速度会快一点

还需要注意，当b%2==0时不要直接返回binaryPow(a,b/2,m)*binaryPow(a,b/2,m)，而应计算单个binaryPow(a,b/2,m)之后再乘起来，这是因为前者每次都会调用两个binaryPow函数，导致复杂度变为O($2^{log(b)}$)=O(b)。例如求binaryPow(8)时，会变成binaryPow(4)*binaryPow(4)，而这两个binaryPow(4)又会各自变成binaryPow(2)*binaryPow(2)，而每个binaryPow(2)又会变成binaryPow(1)*binaryPow(1)，因此最后需要求8次binaryPow(1)

另外，针对不同的题目可能有两个细节需要注意

1. 如果初始时a可能大于m，那么需要在进入函数前就让a对m取模
2. 如果m为1，可以直接在函数外部特判为0，不需要进入函数来计算（因为任何正整数对1取模一定等于0）

接下来研究一下快速幂的迭代写法（填坑）

4.6 two pointers

4.6.1 什么是two pointers

two pointers是算法编程中一种非常重要的思想，以一个例子来引入

给定一个递增的正整数序列和一个正整数M，求序列中两个不同位置的数a和b，使得他们的和恰好为M，输出所有满足条件的方案。

例如给定序列{1,2,3,4,5,6}和正整数M=8，就存在$2+6=8$和$3+5=8$成立

本题最直观的一个想法是使用二重循环枚举序列中的a和b，判断他们的和是否为M，代码实现如下

for(int i=0;i<n;i++){
    for(int j=i;j<=n;j++){
        if(a[i]+a[j]==M){
            cout<<i<<j<<endl;
        }
    }
}

这样的时间复杂度是O($n^2$)，太高了，来看看高复杂度的原因是什么：

1. 对于一个确定的a[i]来说，如果当前的a[j]满足a[i]+a[j]>M，显然也会有a[i]+a[j+1]>M（这是由于序列是递增的），因此就不需要对a[j]之后的数进行枚举。如果无视这个性质，就会导致对j进行了大量的无效枚举
2. 对某一个a[i]来说，如果找到一个a[j]，使得a[i]+a[j]>M恰好成立，那么对于a[i+1]来说也一定有a[i+1]+a[j]>M成立，因此在a[i]之后的元素也不必再去枚举

由上面两点可见：i和j的枚举是互相牵制的，事实上本题中two pointers将利用有序序列的枚举特性来有效降低复杂度，算法过程如下：

令下标i的初值为0，下标j的初值为n-1

a[0]	···	a[i]	a[i+1]	···	a[j-1]	a[j]	···	a[n-1]

然后我们就可以设想，只让i往右走（即i++），只让j往左走（即j--），然后根据a[i]+a[j]情况的不同来让i和j恰当地移动，就可以做到遍历所有情况

1. 若a[i]+a[j]=M，则不可能在固定i或者固定j的情况下使另外一个下标移动，二者的和仍为M，那么只能让i++，j--
2. 若a[i]+a[j]>M，那么要让其中一个后退，又只能是j后退，所以i不变，j--
3. 若i]+a[j]<M，同理有i++，j不变

反复执行上面三个判断直到i>=j成立（这样可以遍历所有的情况）

代码实现如下

int i=0,j=n-1;
while(i<j){
    if(a[i]+a[j]==M){
        printf("%d %d",i,j);
        i++;
        j--;
    }
    else if(a[i]+a[j]>M) j--;
    else i++;
}

显然时间复杂度为O(n)

再给一个例子

序列合并问题：给定两个递增序列a和b，合并成同一个递增序列c

同样可以设置两个下标i和j，利用类似的思路完成问题

int merge(int a[],int b[], int c[], int n, int m){
    //n 和 m 分别是数组 a 和 b 的长度
    int i=0,j=0,index=0;
    while(i<n&&j<m){
        if(a[i]<=b[j]) c[index++]=a[i++]; //相等的情况放 a 和 b 都一样
        else c[index++]=b[j++]; //把 b[j]放入序列中
    }
    while(i<n) c[index++]=a[i++]; //把 a 的剩余元素放入 c 中
    while(j<m) c[index++]=b[j++]; //把 b 的剩余元素放入 c 中
    return index; //返回序列 c 的长度
}

归纳

two pointers是利用问题本身和序列的特性，使用两个下标对序列进行扫描（可以同向也可以反向），以较低的复杂度解决问题

4.6.2 归并排序

归并排序是一种基于“归并”的排序方法，这里主要介绍最基本的2-路归并排序

思路：将序列两两分组，将序列归并为$\lceil \frac{n}{2} \rceil$个组，组内单独排序，然后再把这些组两两归并，生成$\lceil \frac{n}{4} \rceil$个组，组内再单独排序，以此类推，直到只剩下一个组位置，时间复杂度为O(nlogn)

代码实现：

1. 递归实现

   代码CPP · 25 行

   const int maxn=100;
   //将数组 a 的[l1,r1]与[l2,r2]区间合并为有序区间（此处 l2 即 r1+1）
   void merge(int a[],int l1,int r1,int l2,int r2){
       int i=l1,j=l2;
       int temp[maxn],index=0;
       while(i<=r1&&j<=r2){
           if(a[i]<=a[j]) temp[index++]=a[i++];
           else temp[index++]=a[j++];
       }
       while(i<=r1) temp[index++]=a[i++];
       while(j<=r2) temp[index++]=a[j++];
       for(int i=0;i<index;i++){
           a[l1+i]=temp[i]; //将合并之后的序列赋回给 a
       }
   }
   
   //将 a 数组当前区间[left,right]进行归并排序
   void mergeSort(int a[],int left,int right){
       if(left<right){
           int mid=left+(right-left)/2;
           mergeSort(a,left,mid); //递归，将左区间归并排序
           mergeSort(a,mid+1,right);  //递归，将右区间归并排序
           merge(a,left,mid,mid+1,right); //将左右子区间合并
       }
   }

2. 非递归实现

   主要要考虑到每次分组的时候组内元素个数上限都是 2 的幂次，令步长 step 的初值为 2，然后将数组中每 step 个元素作为一组，对其内部排序（即在长度为 step 的子组中，将左 step/2 和右 step/2 个元素合并，若元素个数不超过 step/2 则不操作），再令 step*2，反复操作直到 step/2>n，代码如下

   void mergeSort(int a[]){
       //step 为组内元素个数，step/2 为左子区间元素个数，注意等号可以不取
       for(int step=2;step/2<n;step*=2){
           //每 step 个元素一组
           for(int i=1;i<=n;i+=step){ //对于每一组
               int mid=i+step/2-1; //元素个数为 step/2
               if(mid+1<=n){
                   merge(a,i,mid,mid+1,min(n,i+step-1));
               }
           }
       }
   }

4.6.3 快速排序

快速排序时间复杂度为 O(nlogn)，其实现需要先解决一个问题：对于一个序列 a[]，调整序列中元素的位置，使得 a[0]（原序列中的 a[0]，下同）左侧的所有元素都小于等于 a[0]，右侧的所有元素都大于 a[0]。

由于显然存在很多方案，下面给出一种使用 two pointers 实现的做法，也是最快的方法

1. 先将 a[0]存入 temp，定义 left=0，right=len-1
2. right 一直左移，直到 a[right]≤a[0]，就将 a[right]指向的元素挪到 left 处（比如考虑第一次，第一次的时候 a[1]被挪走了，可以认为那个地方是空的，那么就可以直接把 a[right]指向的元素赋给 left 处）；之后 left 一直右移，直到 a[left]>a[0]，再把 a[left]处的元素赋给 right 处（因为可以认为之前的 right 处赋给了之前的 left 处，那个地方已经空了）；如此交替进行
3. 直到 right=left，再把 temp 赋给这个地方，则完成

一般化考虑 left 的初值就是划分区间的点，将划分区间的元素 a[left]称之为主元

代码实现

int Partition(int a[],int left,int right){
    int temp=a[left];
    while(left<right){
        while(left<right&&a[right]>=temp) right--; //注意这里还要同时满足 left<right，这样才能保证外层循环结束时一定有 left=right
        a[left]=a[right];
        while(left<right&&a[left]<temp) left++;
        a[right]=a[left];
    }
    a[left]=temp;
    return left; //返回相遇的下标
}

接下来就可以实现快速排序算法了，其思路是：

1. 调整序列中的元素，使当前序列最左端的元素在调整后满足左侧所有元素均不超过该元素、右侧所有元素均大于该元素
2. 对该元素的左侧和右侧分别递归进行 1.的调整，直到当前调整区间的长度不超过 1

递归实现如下

//快速排序，left 与 right 初值为序列首尾下标
void quickSort(int a[],int left,int right){
    if(left<right){ //当前区间的长度超过 1
        //将区间 [left,right] 按照 a[left] 一分为二
        int pos=Partition(a,left,right);
        quickSort(a,left,pos-1);
        quickSort(a,pos,right);
    }
}

但是会有一个缺陷：只有序列中的元素排列比较随机的时候效率最高。当序列中元素接近有序的时候会达到最坏时间复杂度 O($\mathrm{n}^2$)，产生这种情况的主要原因在于主元没有把当前区间划分为两个长度接近的子区间。解决这个问题的方法之一是随机选择主元，即从[left,right]中随机选择一个数作为主元，这样能保证对于任意输入数据的期望时间复杂度都能达到 O(nlogn)

下面来看看如何生成随机数

#include<bits/stdc++.h>
#include<time.h>
int random(int a, int b)
{
    srand((unsigned)time(NULL));
    return ((rand() % (b-a+1)) + a);
}

当 b-a>RAND_MAX 时，可以这样：

int random(int a,int b){
    srand((unsigned)time(NULL));
    //用 rand() 生成一个在 [0,RAND_MAX] 范围内的随机数，除以 RAND_MAX 得到一个 [0,1] 之间的浮点数再乘以 b-a 再+a 即可
    return (int)(round(1.0*rand()/RAND_MAX*(b-a)+a));
}

在此基础上继续讨论随机快速排序的写法

int randPartition(int a[],int left,int right){
    int p=(int)(round(1.0*rand()/RAND_MAX*(right-left))+left);
    swap(a[p],a[left]); //交换主元
    //之后一模一样
    int temp=a[left];
    while(left<right){
        while(left<right&&a[right]>=temp) right--; //注意这里还要同时满足 left<right，这样才能保证外层循环结束时一定有 left=right
        a[left]=a[right];
        while(left<right&&a[left]<temp) left++;
        a[right]=a[left];
    }
    a[left]=temp;
    return left; //返回相遇的下标
}

//quickSort 函数无需做出任何改变

4.7 其他高效技巧与算法

4.7.1 打表

打表：以空间换时间。一般是指把所有可能需要用到的结果事先计算出来，这样后面用到时就可以直接查表获得。打表的方式有以下几种：

1. 在程序中一次性计算出所有可能需要用到的结果事先计算出来，之后的查询直接取这些结果

   这个最常用。比如一个问题里面需要大量查询斐波那契数 F(n)，每查询一次时间复杂度就是 O(n)，查询 Q 次时间复杂度就是 O(Qn)，而如果预先先把给定范围内的斐波那契数全部计算出来，那么每次查询就是 O(1) 的复杂度，Q 次查询就是 O(Q+n)，n 为预处理时间

2. 在另一个程序中分一次或者多次计算出来需要用到的结果，手工把结果打到需要用程序的数组中，然后在这个程序里直接使用

3. 对于一些感觉不会的题目，先用暴力程序计算小范围数据的结果，然后找规律

4.7.2 活用递推

细心考虑题目中是否存在递推关系。例如就一类涉及序列的问题而言，假如序列的每一位所需要计算的值都可以通过该位左右两侧的结果来计算得到，那么就可以考虑所谓的“左右两侧的结果”是否可以通过递推进行预处理来得到，这样在后面的使用中就可以不必反复求解

【PAT A1093/B1040】有几个 PAT

字符串 APPAPT 包含了两个"PAT"，位数：2+4+6 和 3+4+6，现在给定一个字符串，问一共可以形成多少个 PAT？

输入格式：

一行包含一个字符串，长度不超过$10^5$

输出格式：

输入包含多少个 PAT，结果可能比较大，输出对 1000000007 取余的结果

思路：直接暴力会超时，可以这样分析：

对于每一个确定的 A，可以形成的 PAT 的数量=A 左边的 P 的数量*A 右边的 T 的数量，那么问题转化成求每个 A 左侧 P 和右侧 T 的数量

一个比较快的获得每一位左边 P 的个数的方法：设定一个数组 leftNumP，先 memset 为 0，然后如果下标 i 处为 P，那么就有 leftNumP[i]=leftNumP[i]+1，如果不是那么就有 leftNumP[i]=leftNumP[i]，由此可以在时间复杂度为 O(len) 内求出

求每一位右边的 T 也是同理的，但是可以在求出 T 的同时把 ans 也求出来，定义 int rightNumT，表示遍历到当前的位置的时候这个位置右边的 T 的数量。如果当前位置是 T 那么 rightNumT++，如果当前位置是 A 那么 ans=(ans+leftNumP[i]*rightNumT)%MOD

4.7.3 随机选择算法

本节主要讨论这个问题：如何从一个无序的数组中求出第 K 小的数（假设数组中的数两两不同）

如果直接快排，时间复杂度是 O(nlogn)，但是存在更优的随机选择算法，对于任何输入都可以达到 O(n) 的期望时间复杂度。

其原理比较类似于随机快速排序中的 randPartition 函数，分析这个函数：

当这个函数执行完一遍之后，假设被选择到的主元为 a[p]，那么主元左右两侧的元素个数就是确定的（设 p 为已知），即 a[p]是[left,right]中第 p-left+1 小的数。

不妨设 p-left+1=M，则当 K==M 时，第 K 小的数就是 a[p]，

当 K<M 时，第 K 小的数在主元左侧，即第 K 小的数是[left,p-1]中的第 K 大，往左侧递归即可

当 K>M 时，第 K 小的数在主元右侧，即第 K 小的数是[p+1,right]中的第 K-M 大，往右侧递归即可

分析：算法可以以 left=right 为递归边界，返回 a[left]，代码实现如下

//随机选择算法，返回 [left,right] 中第 k 小的数
int randSelect(int a[],int left,int right,int k){
    if(left==right) return a[left]; //递归边界
    int p=randPartition(a,left,right);
    int m=p-left+1;
    if(left<right&&k==m) return a[p];
    else if(left<right&&k<m) return randSelect(a,left,p-1,k);
    else if(left<right&&k>m) return randSelect(a,p+1,right,k-m); 
}

这个算法对于任意输入的期望时间复杂度均为 O(n)

下面给出一个应用的例题

给定一个由整数组成的集合，集合中的整数两两不同，现在需要将它分为两个子集合，使得这两个子集合的并为原集合，交为空集。同时在两个子集合元素个数之差的绝对值$|n_1-n_2|$的绝对值尽可能小的情况下，要求它们各自的元素之和的差的绝对值$|S_1-S_2|$尽可能大，求这个$|S_1-S_2|$等于多少

可以分成两类：当 n 为偶数时，显然有$n_1=n_2=\frac{n}{2}$；n 为奇数时，不妨取$n_1=\frac{n}{2}+1,n_2=\frac{n}{2}$（均为向下取整）

为了使得$|S_1-S_2|$尽可能大，显然应当把原集合从小到大排，前$n_1$个的和为$S_1$，后$n_2$的和为$S_2$

但是如果要把整个序列排序时间复杂度是 O(nlogn)，我们可以优化成 O(n)。这里我们可以考虑使用随机选择算法

只需要使用 randSelect 函数求出第$\frac{n}{2}$大的数即可，函数会自动切分好两个集合，然后让 i 从 0 遍历到 n/2 求和即可。

4.7.4 前缀和

int main(){
  vector<int> preFix(n);
  for(int i=0;i<n;++i){
    if(i==0) preFix[i]+=a[i];
    preFix[i]=preFix[i-1]+a[i];
  }
}

c++ 系统库中也有一个库函数partial_sum

代码CPP · 18 行

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5};
    std::vector<int> result(arr.size());  // 存储部分和的容器

    // 计算部分和并存储到 result
    std::partial_sum(arr.begin(), arr.end(), result.begin());

    // 输出结果
    for (int num : result) {
        std::cout << num << " ";
    }

    return 0;
}

第 5 章 入门篇（3）——数学问题

5.1 简单数学

【PAT B119/A1069 数字黑洞】

代码CPP · 39 行

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

void to_array(int a[],int b){
    for(int i=0;i<4;i++){
        a[i]=b%10;
        b/=10;
    }
}

int to_number(int a[]){
    int b=0;
    for(int i=0;i<4;i++){
        b=b*10+a[i];
    }
    return b;
}

bool cmp(int a,int b){
    return a>b;
}

int main(){
    int n;
    cin>>n;
    int ans,a1,a2;
    int t[5];
    while(ans!=6174){
        to_array(t,n);
        sort(t,t+4);
        a1=to_number(t);
        sort(t,t+4,cmp);
        a2=to_number(t);
        ans=a2-a1;
        n=ans;
        printf("%04d-%04d=%04d\n",a2,a1,ans);
    }
}

5.2 最大公约数和最小公倍数

5.2.1 最大公约数

基于欧几里得算法（辗转相除法）

gcd(a,b)=gcd(b,a%b)

上式可以看成递归式

又有递归边界gcd(a,0)=a

代码实现

int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
或者
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}

5.2.2 最小公倍数

先求最大公约数 d=gcd(a,b)，则有最小公倍数为$\frac{a}{d}*b$

5.3 分数的四则运算

5.3.1 分数的表示和化简

1.分数的表示

struct Fraction{
    int up,down;
};

其中需要对这种表示指定三项规则：

1. 使 down 为非负数，如果分数为负则令 up 为负数
2. 如果分数为 0 则令 up=0,down=1
3. 分子和分母互素

2.分数的化简

主要用来使 Fraction 变量满足分数的三项规定

Fraction reduction(Fraction result){
    if(result.down<0){ //满足第一条规定
        result.up=-result.up;
        result.down=-result.down;
    }
    if(result.up==0) result.down=1; //满足第二条规定
    else{ //满足第三条规定
        int d=gcd(abs(result.up),abs(result.down));
        result.up/=d;
        result.down/=d;
    }
    return result;
}

5.3.2 分数的四则运算

1.2.3.4 加减乘除

大同小异。就通分死算，记得最后返回 return reduction(result)

5.3.3 分数的输出

1. 先化简
2. 如果 f.down=1，直接输出 up
3. 带分数的输出：整数部分为 r.up/r.down，分子部分为 abs(r.up)%r.down，分母为 r.down

由于分数的乘法和除法的过程中可能使分子或分母超过 int 型表示范围，因此一般情况下分子和分母使用 long long 来存储

5.4 素数

5.4.1 素数的判断

bool isPrime(int n){
    if(n<=1) return false;
    int sqr=(int)sqrt(1.0*n); //在 n 前面乘上 1.0 使之变为浮点型
    for(int i=2;i<=sqr;i++){
        if(n%i==0) return false;
    }
    return true;
}

如果 n 比较小（i^2 没有解决 int 类型上线）也可以这样写

bool isPrime(int n){
    if(n<=1) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

5.4.2 素数表的获取

暴力法复杂度为 O($n \sqrt n$)，下面介绍效率更高的两种筛法

//埃氏筛法：从 2 开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的
int visit[maxn];  //maxn 是需要打的素数表（布尔数组）
void Prime(){
    memset(visit,0,sizeof(visit)); //初始化都是素数，如果是素数的话就是 1，不是素数才是 0
    for (int i = 2; i < maxn; i++) { //注意不能写成 i<=maxn
        if (!visit[i]) {         //如果 i 是素数，让 i 的所有倍数都不是素数
            for (int j = i+i; j < maxn; j += i) { 
                visit[j] = 0;
            }
        }
    }
}

时间复杂度为 O(nloglogn)

原理：从小到大到达某数 a 时，假如 a 还没有被前面的步骤筛去，那么 a 一定是素数。因为假设 a 不是素数，那么 a 必有小于 a 的因子，那么 a 一定会在之前的步骤中被筛掉

代码CPP · 18 行

//欧拉筛法：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
bool visit[maxn+5]; //1 表示是素数，0 表示不是素数
int prime[maxn+5]; //需要打的素数表
int cnt;
void findPrime(){
    memset(visit,1,sizeof(visit));
    for(int i=2;i<maxn;i++){
        if(visit[i]){
            prime[cnt++]=i;
        }
        //遍历已知的素数来标记合数
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++){
            //循环条件保证遍历的是已知的素数，以及标记的合数不超过 maxn
            visit[i*prime[j]]=0;
            if(i%prime[j]==0) break; //看下文
        }
    }
}

• 当 i % prime[j] == 0 时，说明 i 可以被 prime[j] 整除，即 i=k×prime[j]。
• 此时，i 乘上更大的素数的结果（如 i * prime[j+1]）一定会被 prime[j] 的倍数筛掉。（这里 break 之后，之后 i 增大总会到达一个程度使得 i 是原来时候的 i 的倍数）
• 例如，当 i=4 时：
  • prime[j] = 2，i * prime[j] = 8。
  • 因为 4 % 2 == 0，所以 4 * 3 = 12 会被 2 的倍数筛掉（即 6 * 2 = 12，i=6 的时候就可以筛掉了）。
  • 因此，不需要继续标记 4 * 3 = 12，直接跳出循环。

5.5 质因子分解

最后都要归结到若干不同质数的乘积，所以不妨先打个素数表，而打素数表的方法见上文。

由于每个质因子可能不止出现一次，可以定义一个结构体来存放一个数的质因子

struct Factor{
    int x,cnt;
    //x 为质因子，cnt 为其数目
}fac[10];

这里 fac[]数组是存放给定的正整数 n 的所有质因子，比如对于 n=20=2*2*5

fac[0].x=2
fac[0].cnt=2
fac[1].x=5
fac[1].cnt=1

由于$23571113171923*29>\mathrm{INT_MAX}$，fac[]开到 10 就足够了

我们不难注意到这样一个性质：对于一个合数 n，它的质因子要么全部小于等于$\sqrt n$，要么只有一个质因子大于$\sqrt n$，其余的质因子全部小于等于$\sqrt n$

利用这样的性质我们可以对一个合数 n 进行质因数分解

1. 首先在素数表中，枚举 2~$\sqrt n$的所有素数，试是不是 n 的质因子

   如果是的话就在 fac 数组中加入这个因子，然后反复除，每除一次 cnt++

2. 如果在上面的操作之后 n 仍然大于 1，说明 n 有且仅有一个大于$\sqrt n$的质因子，而且就是就是现在的 n

至此质因数分解完成，时间复杂度为 O($\sqrt n$)

代码实现

代码CPP · 23 行

struct Factor{
    int x,cnt=0;
}fac[10];

int main(){
    int n;
    int cnt=0;
    int prime[100];
    int temp=n; //要在外部用 n
    for(int i=2; prime[i]<=sqrt(temp);i++){
        if(n%prime[i]==0){
            fac[cnt].x=prime[i];
            while(n%prime[i]==0){
                fac[cnt].cnt++;
                n/=prime[i]; //注意这两个语句的顺序
            }
        }
    }
    if(n>1){
        fac[cnt++].x=n;
        fac[cnt].cnt=1;
    }
}

下面来看一道例题

【PAT A1059】 Prime Factors

给出一个 int 范围的整数，按照从小到大的顺序输出其分解为质因数的乘法形式

输入样例

97532468

输出样例

97532468=2^2*11*17*101*1291

代码实现

代码CPP · 58 行

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int maxn=100005;

struct Factor{
    int x,cnt=0;
}fac[10];


int prime[maxn],cnt;
int t[maxn]={0}; //0 表示是素数，1 表示不是素数
void findPrime(){
    for(int i=2;i<maxn;i++){
        if(!t[i]){
            prime[cnt]=i;
            cnt++;
            for(int j=i+i;j<maxn;j+=i){
                t[j]=1;
            }
        }
    }
}

int main(){ 
    int n;
    cin>>n;
    if(n==1){
        cout<<"1=1";
        return 0;
    }
    findPrime();
    int temp=n;
    int num=0;
    for(int i=0;prime[i]<=sqrt(1.0*temp);i++){
        if(n%prime[i]==0){
            fac[num].x=prime[i];
            while(n%prime[i]==0){
                fac[num].cnt++;
                n/=prime[i];
            }
            num++;
        }
    }
    if(n>1){
        fac[num].x=n;
        fac[num].cnt++;
        num++;
    }
    cout<<temp<<'=';
    for(int i=0;i<num;i++){
        if(i!=0) cout<<'*';
        if(fac[i].cnt==1) cout<<fac[i].x;
        else cout<<fac[i].x<<'^'<<fac[i].cnt; 
    }
    return 0;
}

易错点总结：

• 在 INT_MAX 范围内分解，素数表开到 10^5 就够了
• n==1 特判
• main 函数开头调用 findPrime()
• findPrime 函数中不要写成 i<=maxn是i<maxn
• 要在循环外定义变量储存 sqrt(n)

5.6 大整数运算（高精度）

代码CPP · 263 行

#include <iostream>
#include <cstring>
using namespace std;

class BigInt
{
private:
    static constexpr int N = 1000; // 位数上限
public:
    int a[N]; // 低位在前，高位在后

    // 默认构造函数，支持 int 初始化
    BigInt(int x = 0) : a{}
    {
        for (int i = 0; x; i++)
        {
            a[i] = x % 10;
            x /= 10;
        }
    }

    // 复制构造函数
    BigInt(const BigInt &b)
    {
        memcpy(a, b.a, sizeof(a));
    }

    // 赋值运算符
    BigInt &operator=(const BigInt &b)
    {
        if (this != &b)
        {
            memcpy(a, b.a, sizeof(a));
        }
        return *this;
    }

    // 加法（BigInt + BigInt）
    BigInt operator+(const BigInt &x) const
    {
        BigInt res = *this;
        res += x;
        return res;
    }

    // 加法（BigInt += BigInt）
    BigInt &operator+=(const BigInt &x)
    {
        for (int i = 0; i < N; i++)
        {
            a[i] += x.a[i];
            if (a[i] >= 10)
            {
                a[i + 1] += a[i] / 10;
                a[i] %= 10;
            }
        }
        return *this;
    }

    // 减法（BigInt - BigInt）
    BigInt operator-(const BigInt &x) const
    {
        BigInt res = *this;
        res -= x;
        return res;
    }

    // 减法（BigInt -= BigInt）
    BigInt &operator-=(const BigInt &x)
    {
        for (int i = 0; i < N; i++)
        {
            a[i] -= x.a[i];
            if (a[i] < 0)
            {
                a[i] += 10;
                a[i + 1] -= 1;
            }
        }
        return *this;
    }

    // 乘法（BigInt * int）
    BigInt operator*(int x) const
    {
        BigInt res = *this;
        res *= x;
        return res;
    }

    // 乘法（BigInt *= int）
    BigInt &operator*=(int x)
    {
        for (int i = 0; i < N; i++)
        {
            a[i] *= x;
        }
        for (int i = 0; i < N - 1; i++)
        {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        return *this;
    }

    // 乘法（BigInt * BigInt）
    BigInt operator*(const BigInt &x) const
    {
        BigInt res;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j + i < N; j++)
            {
                res.a[i + j] += a[i] * x.a[j];
                if (res.a[i + j] >= 10)
                {
                    res.a[i + j + 1] += res.a[i + j] / 10;
                    res.a[i + j] %= 10;
                }
            }
        }
        return res;
    }

    // 取模（BigInt % int）
    int operator%(int x) const
    {
        int remainder = 0;
        for (int i = N - 1; i >= 0; i--)
        {
            remainder = (remainder * 10 + a[i]) % x;
        }
        return remainder;
    }

    // 除法（BigInt /= int）
    BigInt &operator/=(int x)
    {
        for (int i = N - 1; i >= 0; i--)
        {
            if (i)
            {
                a[i - 1] += (a[i] % x) * 10;
            }
            a[i] /= x;
        }
        return *this;
    }

    // 比较运算（BigInt == BigInt）
    bool operator==(const BigInt &x) const
    {
        for (int i = 0; i < N; i++)
        {
            if (a[i] != x.a[i])
                return false;
        }
        return true;
    }
    // 比较运算（BigInt < BigInt）
    bool operator<(const BigInt &x) const
    {
        for (int i = N - 1; i >= 0; i--)
        {
            if (a[i] < x.a[i])
                return true;
            if (a[i] > x.a[i])
                return false;
        }
        return false;
    }
    // 比较运算（BigInt > BigInt）
    bool operator>(const BigInt &x) const
    {
        return x < *this;
    }
    // 比较运算（BigInt <= BigInt）
    bool operator<=(const BigInt &x) const
    {
        return !(x < *this);
    }
    // 比较运算（BigInt >= BigInt）
    bool operator>=(const BigInt &x) const
    {
        return !(*this < x);
    }
    // 一元负号（取反运算）
    BigInt operator-() const
    {
        BigInt res = *this;
        for (int i = 0; i < N; i++)
        {
            res.a[i] = -res.a[i];
        }
        return res;
    }
    // 括号运算符（获取某个位数）
    int operator()(int index) const
    {
        if (index < 0 || index >= N)
            return -1; // 返回 -1 代表超出范围
        return a[index];
    }


    // Pre-increment (++obj)
    BigInt& operator++() 
    {
        *this += BigInt(1);
        return *this;
    }

    // Post-increment (obj++)
    BigInt operator++(int) 
    {
        BigInt temp = *this; 
        ++(*this);
        return temp;
    }

    // Pre-decrement (--obj)
    BigInt& operator--() 
    {
        *this -= BigInt(1); 
        return *this;
    }

    // Post-decrement (obj--)
    BigInt operator--(int) 
    {
        BigInt temp = *this;
        --(*this);
        return temp;
    }
    
    // 输出运算符
    friend ostream &operator<<(ostream &o, const BigInt &b)
    {
        int t = N - 1;
        while (t > 0 && b.a[t] == 0)
        {
            t--;
        }
        for (int i = t; i >= 0; i--)
        {
            o << b.a[i];
        }
        return o;
    }
    // 输入运算符
    friend istream &operator>>(istream &in, BigInt &b)
    {
        string s;
        in >> s;
        memset(b.a, 0, sizeof(b.a));
        for (int i = 0; i < s.size(); i++)
        {
            b.a[i] = s[s.size() - 1 - i] - '0';
        }
        return in;
    }
};

5.7 扩展欧几里得算法

待填坑

5.8 组合数

待填坑

第 6 章 C++ 标准模板库 (STL) 介绍

6.1 vector 的常见用法详解

定义方式举例

vector<int> name;
vector<char> name;
vector<vector<int> > name; //两个>>之间加上空格以防止被识别成移位操作
//这个可以理解成两个维度都可以变成的二维数组

定义 vector 数组的方式

vector<int> arr[100]; //这种定义方式就是一维的长度被固定成 100 了

vector 容器内元素的访问

通过下标访问

就类似普通的数组

通过迭代器访问

迭代器 (iterator) 可以理解成一种类似指针的东西

vector<typename>::iterator it; //it 是一个 vector<typename>::iterator 型的变量

这样就得到了迭代器 it，并且可以通过*it 来访问 vector 中的元素，举例如下

vector<int> vi;
for(inti=1;i<=5;i++){
    vi.push_back(i); //push_back(i) 在 vi 的末尾添加元素 i，即依次添加 1 2 3 4 5
}

可以使用类似下标和指针访问数组的方式来访问容器中的元素

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vi;
    for(int i=1;i<=5;i++){
        vi.push_back(i);
    }
    //vi.begin() 为取 vi 的首元素地址，而 it 指向这个地址
    vector<int>::iterator it=vi.begin();
    for(int i=0;i<5;i++){
        printf("%d ",*(it+i));
    }
    return 0;
}

这里可以看出 vi[i]==*(vi.begin()+i)
再提一下 end() 函数：取尾元素地址的下一个地址，end() 作为迭代器末尾标志不存储任何元素。（美国人思维习惯左闭右开）

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vi;
    for(int i=1;i<=5;i++){
        vi.push_back(i);
    }
    //vector 的迭代器不支持 it<vi.end() 的元素，循环条件只能用 it!=vi.end()
    for(vector<int>::iterator it=vi.begin();it!=vi.end();it++){
        printf("%d ",*it);
    }
    return 0;
}

强调一下，STL 容器中只有在 vector 和 string 中才允许 vi.begin()+3 这种迭代器带上整数的写法

vector 常用函数实例解析

push_back()

在 vector 后面增加一个元素 (x),时间复杂度 O(1),实例见上文

pop_back()

直接使用不需要传参，用以删除 vector 的尾元素，时间复杂度 O(1)

size()

用以获取 vector 中元素的个数，返回值 unsigned 不过一般用%d就可以了，时间复杂度 O(1)

clear()

清空 vector 中的所有元素，时间复杂度 O(N),N 为 vector 中元素个数

insert()

insert(it,x) 用以向 vector 的任意迭代器 it 处插入一个元素 x，时间复杂度 O(N)

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vi;
    for(int i=1;i<=5;i++){
        vi.push_back(i);
    }
    vi.insert(vi.begin()+2,-1);
    for(int i=0;i<vi.size();i++){
        printf("%d ",vi[i]);
    }
    return 0;
}

引用是的，对于 std::vector<int> vi 而言，vi + i == vi[i] 并不成立。 原因分析 vi[i] 的含义： vi[i]...

是的，对于 std::vector<int> vi 而言，vi + i == vi[i] 并不成立。

原因分析

1. vi[i] 的含义：

   • vi[i] 是 std::vector 提供的操作符重载，用于访问向量中索引为 i 的元素。其底层实现相当于：

     *(vi.begin() + i)

     其中 vi.begin() 是一个指向 vi 开头元素的迭代器，而迭代器支持偏移。

2. vi + i 的含义：

   • vi 是 std::vector 类型的对象，不是指针或迭代器。C++ 中不允许直接对对象使用加法运算，因此 vi + i 是非法的，会导致编译错误。

---

正确用法

如果想通过指针或迭代器实现类似 vi[i] 的效果，应该使用 vi.begin() 或指针加偏移量。例如：

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> vi = {10, 20, 30, 40};
    
    // 使用下标访问
    cout << vi[2] << endl;  // 输出：30

    // 使用迭代器
    auto it = vi.begin();
    cout << *(it + 2) << endl;  // 输出：30

    return 0;
}

---

对比：普通数组中的 arr + i == arr[i]

对于普通数组（如 int arr[5]），arr 是指向数组首元素的指针，因此 arr + i 是合法的，指向数组第 i 个元素的地址。而 arr[i] 其实是通过指针偏移访问到值的语法糖，其本质是 *(arr + i)。

---

结论

在 std::vector 中：

• vi[i] 是通过索引访问元素的合法操作。
• vi + i 是非法的，因为 vi 是一个对象而不是指针。如果需要实现类似 vi[i] 的操作，应使用迭代器或下标索引。

erase()

有两种用法：删除单个元素，删除一个区间内的所有元素，时间复杂度均为 O(N)

1. 删除单个元素
   erase(it) 即删除迭代器处的元素

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vi;
    for(int i=1;i<=5;i++){
        vi.push_back(i); //1 2 3 4 5
    }
    vi.erase(vi.begin()+1); //删除 2 不是 vi.begin()+1 因为*(vi.begin())==vi[0]
    for(int i=0;i<vi.size();i++){
        printf("%d ",vi[i]);
    }
    return 0;
}

2. 删除一个区间之内的所有元素
   erase(first,last) 即删除[first,last) 内的所有元素
   由此可见 vi.clear() 等价于 vi.erase(vi.begin(),vi.end())

6.2 set 的常见用法详解

set，也就是集合，是一个内部自动有序而且不含重复元素的容器

set 的定义

set<typename> name;

类似 vector，或者说绝大部分 STL 的定义方式都是这样的

set 容器内元素的访问

set 只能通过迭代器访问

set<int>::iterator it;

除 vector 和 string 以外的 STL 容器都不支持*(it+i) 的访问方式所以只能这样枚举

#include <bits/stdc++.h>
using namespace std;
int main(){
    set<int> st;
    st.insert(2);
    st.insert(1);
    st.insert(3);
    st.insert(1);
    //不支持 it<st.end()
    for(set<int>::iterator it=st.begin();it!=st.end();it++){
        cout<<*it;
    } //要理解迭代器，不是针对一个对象，而是这个类中的一种数据类型
    return 0;
}

输出结果

1 2 3

由此可见 set 内的元素自动升序排序而且自动去除重复元素

set 常用函数实例解析

insert()

会有自动递增排序和去重，时间复杂度 O(logN)

find()

find(value) 返回 set 中对应值为 value 的迭代器，时间复杂度 O(logN)

#include <bits/stdc++.h>
using namespace std;
int main(){
    set<int> st;
    st.insert(2);
    st.insert(1);
    st.insert(3);
    st.insert(1);
    set<int>::iterator it=st.find(2);
    cout<<*it<<endl; //输出 2
    return 0;
}

如果查找不到就会返回 st.end()，可以用这个功能搭配 set实现复杂的 hash

erase()

1. • st.erase(it) 删除单个元素 (对应迭代器处的)，可以结合 find 函数来使用 时间复杂度为 O(1)
   • st.erase(value) 删除单个元素 (值为 value 的) 时间复杂度为 O(logN)
   • 为什么可以这样？因为 value 的类型是 typename，而 it 的类型是 set::iterator
2. 删除一个区间之内的所有元素 st.erase(first,last)，其中 first 和 last 都是迭代器，时间复杂度为 O(last-first)

size()

略了，O(1)

clear()

O(N)

6.3 string 的常见用法详解

string 的定义

string str;
string str1="abcd";

string 中内容的访问

通过下标访问

就像访问字符数组那样去访问 string

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str="abcd";
    for(int i=0;i<str.length();i++){
        printf("%c", str[i]); //输出 abcd
    }
    return 0;
}

如果要读入和输出整个字符串那就只能用cin和cout

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    cout<<str;
    return 0;
}

不过真的要使用printf也可以使用c_str()强转

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str="abcd";
    printf("%s\n", str.c_str());
    return 0;
}

通过迭代器访问

主要是有些函数比如insert()和erase()要求迭代器为参数
由于定义string的时候并没有<typename>这一项，因此可以直接这样定义

string::iterator it;

那么就可以使用迭代器来对string进行遍历了

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str="abcd";
    for(string::iterator it=str.begin();it!=end();it++){
        cout<<*it;
    }
    return 0;
}

这里循环条件也可以写成it<str.end()，因为只有vector和string支持这样的对迭代器比如str.begin()+3直接加减某个数字的操作

string常用函数实例解析

operator+=

可以把两个string直接拼接起来

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str1="abc",str2="xyz",str3;
    str3=str1+str2;
    cout<<str3; //abcxyz
}

compare operator

两个string类型直接用比较运算符比较大小，依据是字典序

if(str1>str2){

}

length() 或 size()

str.length();
str.size();

均返回string的长度且基本相同，时间复杂度O(1)

insert()

string的insert()函数有多种写法，时间复杂度均为O(N)

1. insert(pos,string),在pos号位置插入字符串string
   这个pos号位可以是0

string str1="abc",str2="opq";
str1.insert(3,str2); //往 str[3]处插入 opq，这里也可以直接写"opq"
cout<<str1<<endl; //abcopq

2. insert(it,it2,it3), it为原字符串的欲插入位置，it2和it3为待插入字符串的首尾迭代器，用以表示[it2,it3)将被插入it的位置上

string str1="abc",str2="opq";
str.insert(str.begin(),str2.begin,str2.end());
cout<<str1<<endl; //abcopq

erase()

时间复杂度均为O(N)

1. 删除单个元素

str.erase(it);

1. 删除一个区间内的所有元素 两种方法
   • str.erase(first,last) 均为迭代器
   • str.erase(pos,length) pos为起始位置(不是迭代器),length为删除的字符个数

   string str="abcdefg";
   str.erase(3,2); //删除 c 和 d，从第三位开始的两个 (包括第三位)

   这个 pos 号位可以是 0

clear()

O(1)

substr()

substr(pos,len) 返回从 pos 号位开始、长度为 len 的子串，时间复杂度为 O(len)，示例如下、

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str="Thank you for your smile.";
    cout<<str.substr(0,5)<<endl; //Thank
    cout<<str.substr(14,4)<<endl; //Your
}

这个 pos 号位可以是 0

string::npos

string::npos 是一个常数其本身的值为 -1，但是由于其本身是 unsigned_int 类型，也可以认为是 unsigned_int 类型的最大值。string::npos 作为 find 函数失配时候的返回值，可以认为 string::npos=-1 或 4294967295

find()

• str.find(str2),当 str2 是 str 的子串的时候，返回其在 str 中第一次出现的位置（不是迭代器）；如果 str2 不是 str 的子串，返回 string::npos
• str.find(str2,pos) 从 pos 位开始匹配 str2，返回值与上面的相同时间复杂度 O(mn)，m 和 n 分别是两个数组的长度

using namespace std;
int main{
string str ="Thank you for your smile."
string str2 "you";
string str3 "me";
if (str.find (str2) string!=npos)
cout << str.fånd (str2) << endl;
if (str.find(str2, 7) String:!=npos) (
cout str.find (str2, 7) endl;
if (str. find (str3) String:!=npos)
cout << Str. find(str3) endl;
) else {
cout "I know there is no position for me." << endl;}
return O;
}

输出结果

6
14
I know there is no position for me.

replace()

• str.replace(pos,len,str2) 将 str 从 pos 号位开始、长度为 len 的子串替换为 str2
• str.replace(it1,it2,str2) 把 str 的迭代器[it1,it2) 范围内的子串替换为 st2
• 时间复杂度为 O(str.length())

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str="Maybe you will turn around";
    string str2="will not";
    string str3="surely";
    cout<<str.replace(10,4,str2)<<endl;
    cout<<str.replace(str.begin(),str.begin()+5,str3);
    return 0;
}

输出

Maybe you will not turn around
surely you will not turn around

c.str()

可以将 string 转换成 char []，之后就可以使用 sprintf 和 sscanf 函数了。

sscanf(login_date.c_str(),"%d-%d",&year,&month);

PAT A1060 ARE THEY EQUAL

6.4 map 的常用用法详解

map 翻译为映射 (其实这里只能是一个单射),比如数组 typename arr[]就是 int 类型向其他类型的一个映射，但是 map 可以将任何基本类型（包括 STL 容器）映射到任何基本类型（包括 STL 容器）,比如 string 到 int 的映射

map 的定义

map<typename1,typename2> mp;

前一个是映射前类型 (键 key)，后一个是映射后类型 (value)
如果是字符串到整型的映射，必须使用 string 而不能使用 char 数组

map<string,int> mp;

这是因为 char 作为数组是不能作为键值的，所以只能使用 string
也有这样的 map

map<set<int>,string> mp;

map 容器内元素的访问

map 有两种访问方式

通过下标访问

和访问普通的数组的方式一样，比如对于一个定义为

map<char,int> mp;

的 map 来说，就可以使用

mp['c']

的方式来访问它的对应的 int
但是需要注意，和函数一样，map 中的键是唯一的，比如

map<char,int> mp;
mp['c']=20;
mp['c']=30; //20被覆盖
cout<<mp['c']; //输出30

通过迭代器访问

map<typename1,typename2>::iterator it;

由于 map 的每一对映射都有两个 typename，因此一个 it 必须可以同时访问键和值

it->first //访问键
it->second //访问值

比如下面这个例子

int main(){
    map<char,int> mp;
    mp['m']=20;
    mp['r']=30;
    mp['a']=40;
    for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++){
        printf("%c %d\n",it->first,it->second);
    }
    return 0;
}

输出如下：

a 40
m 20
r 30

其实由此可见，map 会按照键从小到大的顺序自动排序（因为 a<m<r）,这个就是类似 set 的（因为他的底层原理和 set 一样都是红黑树）

map 常用函数实例解析

find()

find(key) 返回键为 key 的映射的迭代器，时间复杂度 O(logN),N 为 map 中映射的个数

map<char,int> mp;
mp['a']=1;
mp['b']=2;
map<char,int>::iterator it=mp.find('b');
printf("%c %d", it->first,it->second);

输出结果为

b 2

erase() 可以类比 set 的学习

1. 删除单个元素
   • mp.erase(it),it 为需要删除的元素的迭代器，时间复杂度 O(1)，可以搭配 find() 函数使用

   map<char,int> mp;
   mp['a']=1;
   mp['b']=2;
   map<char,int>::iterator it=mp.find('b');
   mp.erase(it); //删除 b 2

   • mp.erase(key),key 为欲删除的映射的键，时间复杂度 O(logN)

   map<char,int> mp;
   mp['a']=1;
   mp['b']=2;
   mp.erase('b'); //删除 b 2

2. 删除一个区间之内的所有元素
   mp.erase(first,last),传入的都是迭代器，删除[first,last) 内的元素，时间复杂度 O(last-first)

size()

O(1)，获得映射的对数

clear()

O(N)

常见用途

1. 建立 char 或者 string 与 int 之间的映射
2. 把 map 当 bool 数组使用

6.5 queue 的常见用法详解

queue 的定义

queue <typename> name;

queue 容器内元素的访问

由于 queue 是先进先出的，因此在 STL 中只能通过 front() 来访问队首元素或者使用 back() 来访问队尾元素

#include<bits/stdc++.h>
using namespace std;

int main(){
    queue<int> q;
    for(int i=1;i<=5;i++){
        q.push(i);
    }
    cout<<q.front()<<' '<<q.back(); //输出 1 5
}

queue 常用函数实例解析

push()

把 x 推入 queue

front() back()

获得队首元素和队尾元素

pop()

令队首元素出队

int main(){
    queue<int> q;
    for(int i=1;i<=5;i++){
        q.push(i);
    }
    for(int i=1;i<=3;i++){
        q.pop(); //弹出 1 2 3
    }
    cout<<q.front()<<' '<<q.back(); //输出 4 5
}

empty()

返回 true 则为空，返回 false 则为非空

size()

返回 queue 内元素的个数

queue 的常见用途

广度优先搜索

需要注意的是使用 front() 和 pop() 之前需要使用 empty() 判断是否为空

6.5+ deque 的常见用法详解

deque 的定义

类似 queue

deque 容器内元素的访问

类似 queue

deque 常用函数

push_back()

在末尾添加元素

push_front()

在前端添加元素

pop_front() 和 pop_back()

front() 和 back()

size() 和 clear()

6.6 priority_queue 的常见用法详解

priority_queue 又称优先队列，底层使用堆来实现。在优先队列中队首元素一定是当前队列中优先级最大的那一个

例如在队列中有以下元素且指定好了优先级

桃子（优先级 3）
梨子（优先级 4）
苹果（优先级 1）

那么出队的顺序为梨子（优先级 4）→桃子（优先级 3）→苹果（优先级 1）

当然，可以在任何时候往优先队列里 push 元素，而优先队列底层的数据结构堆 (heap) 会随时调整结构，使得每次出来的队首元素都是优先级最大的

关于这里的优先级，则是规定出来的，在上面的例子中也可以规定数字越小的优先级越大

priority_queue 的定义

priority_queue<typename> name;

priority_queue 容器内元素的访问

与 queue 不一样的是 priority_queue 没有 front() 和 back() 函数，只能通过 top() 函数来访问队首元素，也就是优先级最高的元素

int main(){
    priority_queue<int> q;
    q.push(1);
    q.push(3);
    q.push(2);
    cout<<q.top(); //输出 3
}

priority_queue 常见函数实例解析

push()

O(logN)，N 为当前元素个数

top()

O(1)

访问堆顶元素

pop()

令队首元素出队

O(logN)

int main(){
    priority_queue<int> q;
    q.push(1);
    q.push(3);
    q.push(2);
    cout<<q.top(); //输出 3
    q.pop();
    cout<<q.top(); //输出 2
}

empty()

返回 true 则空，返回 false 则非空

O(1)

size()

返回优先队列内的元素个数

O(1)

priority_queue 内元素优先级的设置

基本数据类型的优先级设置

指的是 int double char 等可以直接使用的数据类型，优先队列对它们的优先级设置一般是数字大的优先级最高，因此队首元素就是优先队列中元素最大的那个（如果是 char 类型就是字典序最大的）。

对于基本数据类型来说下面两种优先队列的定义是等价的（以 int 类型为例）

priority_queue<int> q;
priority_queue<int,vector<int>,less<int> > q; //注意最后两个>之间有空格

• vector<int> 填写的是用来承载底层数据结构堆 (heap) 的容器，vector<typename> 与之前的 typename 保持一致
• less<int> 是对第一个参数的比较类，less<int> 表示数字大的优先级越大，而 greater<int> 表示数字小的优先级越大

因此如果想要优先队列总是把最小的元素放在队首，只需进行如下定义

priority_queue<int,vector<int>,greater<int> > q; //注意最后两个>之间有空格

事实上即使是基本数据类型也可以使用下面讲解的结构体的优先级设置方法，不过三个参数的写法不太一样了。

结构体的优先级设置

以本节开头的水果为例

struct Fruit{
	string name;
	int price;
};

现在希望按水果价格高的为优先级高，就需要重载小于号"<"。重载是指对已有的运算符进行重新定义，也就是说，可以改变小于号的功能，写法示例如下

struct Fruit {
    string name;
    int price;
    friend bool operator < (fruit f1,fruit f2) {
        	return f1.price<f2.price;
	}
};

可见 Fruit 结构体中增加了一个函数，

其中"friend"为友元，具体含义此处不赘述

后面的bool operator < (fruit f1,fruit f2)对 fruit 类型的操作符'<'进行了重载

重载运算符的本质是对这一种特定的类型而言，运算符的效果不同了！所以可以定义 int double set 也是可以的

（重载大于号会造成编译错误，因为从数学上来说只需要重载小于号，即 f1>f2 等价于判断 f2<f1，而 f1=f2 等价于判断 !(f1<f2)&&!(f2<f1)）

函数内部为return f1.price<f2.price，因此重载之后小于号还是小于号的作用，此时就可以直接定义 Fruit 类型的优先队列，其内部就是以价格高的水果为优先级高，如下

priority_queue<fruit> q;

同理如果想要价格低的水果优先级高，那么就只需要把 return 中的小于号改为大于号

struct Fruit {
    string name;
    int price;
    friend bool operator < (fruit f1,fruit f2) {
        	return f1.price>f2.price;
	}
};

不难注意到此处对于小于号的重载类似于 sort 中的 cmp 函数，的确有点相似。参数都是两个变量，返回值都是 bool 型，但是效果看上去是“相反”的。在排序中若是return f1.price>f2.price，那么则是从高到低排序，但是在优先队列中却是价格低的优先级高

优先队列的这个函数与 sort 中的 cmp 函数的效果是相反的

也可以像 sort 的 cmp 函数一样写在结构体外面，只需要把 friend 去掉，小于号改成一对小括号，然后把重载的函数写在结构体外面，同时将其拿 struct 包装起来

struct cmp {
    bool operator () (fruit f1,fruit f2){
		return f1.price>f2.price; //价格小的优先级大，仍然与 sort 的相反
    }
}

这种情况下使用之前说的第二种定义方式来定义优先队列

priority_queue<fruit,vector<fruit>,cmp> q;

应当注意到即使是基本数据类型或者其他 STL 容器（比如 set）也可以这样定义优先级

#include <set>
#include <iostream>
#include <functional>
using namespace std;
int main() {
    // 使用 greater 定义降序排序的 set
    set<int, greater<int>> s;
    s.insert(10);
    s.insert(5);
    s.insert(20);

    for (int x : s) {
        cout << x << " "; // 输出 20 10 5
    }
    return 0;
}

或者是

代码CPP · 35 行

#include<bits/stdc++.h>

using namespace std;

struct Fruit {
    string name;
    int price;
};

// 自定义比较函数对象
struct cmp {
    bool operator()(const Fruit& f1, const Fruit& f2) const {
        return f1.price > f2.price; // 按价格从大到小排序
    }
};

int main() {
    // 创建一个 set，使用自定义比较函数对象
    set<Fruit, cmp> fruitSet;

    // 添加元素
    fruitSet.insert({"Apple", 5});
    fruitSet.insert({"Banana", 3});
    fruitSet.insert({"Orange", 8});

    // 遍历并输出
    for (const Fruit& fruit : fruitSet) {
        cout << fruit.name << " (" << fruit.price << ")\n";
        // 输出 Orange (8)
        //      Apple (5)
        //      Banana (3)
    }

    return 0;
}

最后指出，如果结构体内的数据较为庞大（例如出现了字符串和数组），建议使用引用来提高效率，此时比较类的参数中需要加上 const 和 &，如下所示

friend bool operator < (const fruit &f1, const fruie &f2){
    return f1.price>f2.price;
}
bool opreator () (const fruit &f1, const fruie &f2) {
    return f1.price>f2.price;
}

priority_queue 的常见用途

可以解决一些贪心问题

在使用 top() 函数之前必须判断优先队列是否为空

6.7 stack 的常见用法详解

stack 的定义

#include<stack>
stack<typename> name;

typename 可以是任何基本数据类型或容器

stack 容器内元素的访问

由于 stack 本身就是一种后进先出的数据结构，在 STL 中的 stack 只能通过 top() 来访问栈顶元素

int main(){
    stack<int> st;
    st.push(1);
    st.push(2);
    cout<<st.top(); //输出 2
}

stack 常用函数实例解析

push()

O(1) push(x) 将 x 推入栈

top()

O(1) 获得栈顶元素

pop()

O(1) 弹出栈顶元素，示例如下

int main(){
    stack<int> st;
    for(int i=1;i<=5;i++){
        st.push(i); //分别把 1 2 3 4 5 推入栈中
    }
    for(int i=1;i<=3;i++){
        st.pop(); //相当于推出 5 4 3
    }
    cout<<st.top(); //输出 2
    return 0;
}

empty()

检测 stack 是否为空，返回 true 为空，返回 false 为非空

st.empty()

size()

返回 stack 中元素的个数 O(1)

st.size()

如何清空栈

没有自带的函数，可以这样写

while(!st.empty()){
	st.pop();
}

但是更常用的做法是重新定义一个栈来变相实现栈的清空。

stack 的常见用途

用来模拟实现一些递归，防止程序对栈内存的限制导致程序运行出错

6.8 pair 的常见用法详解

当想要将两个元素绑在一起作为一个合成元素、又不想因此定义结构体的时候，使用 pair 可以很方便地作为一个替代品。也就是说 pair 实际上可以看成一个内部有两个元素的结构体，而且这两个元素的类型是可以指定的。

有时候运行的速度会比结构体快

pair 的定义

pair <typename1,typename2> name;

等价于

struct pair {
    tyoename1 first;
    typename2 first;
}

初始化的方式如下 (举例)，在后面加一对小括号

pair<string,int> p("haha",5);

而如果想要在代码中临时构建一个 pair，有如下两种方法

1. 将类型定义写在前面，后面用小括号内两个元素的方式

2. 使用自带的 make_pair 函数

   make_pair("haha",5);

pair 中元素的访问

pair 中只有两个元素 first 和 second，按照正常结构体的方式去访问即可

pair<string,int> p("haha",5);
cout<<p.first; //输出 haha
cout<<p.second; //输出 5

pair 常用函数实例解析

比较操作数

两个 pair 型可以直接比较大小，比较规则是先以 first 的大小作为标准，只有当 first 相等时才去判别 second 的大小

pair 的常见用途

1. 用来代替二元结构体及其构造函数，可以节省编码时间

2. 作为 map 的键值对来进行插入，比如下面的例子

   #include<bits/stdc++.h>
   using namespace std;
   
   int main(){
       map<string,int> mp;
       mp.insert(make_pair("abc",123));
       mp.insert(make_pair("efg",456));
       for(auto x:mp){
           cout<<x.first<<' '<<x.second<<endl;
       }
   }

   输出

   abc 123
   efg 456

   这是因为 map 的内部实现中涉及到了 pair

6.9 常用算法函数

6.9.1 max()、min() 和 abs()

含义显然。

max() 和 min() 的参数可以是 int 也可以是浮点数；想求三个数的最大值的时候可以这样：

max(x,max(y,z));

也可以这样

max({x,y,z});

abs()的形参只能是整数

6.9.2 swap()

swap(x,y) 用来交换 x,y 的值

int x=1,y=2;
swap(x,y);
cout<<x<<' '<<y; //输出 2 1

6.9.3 reverse()

reverse(it1,it2) 可以将数组指针在 [it1，it2) 之间的元素或容器的迭代器在 [it1，it2) 范围内的元素进行反转

//对数组进行反转
#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[5]={1,2,3,4,5};
    reverse(a,a+5); //将 a[0]~a[4]反转
    for(int i=0;i<5;i++){
        cout<<a[i]<<' '; //输出 5 4 3 2 1
    }
}

容器也可以 一定得是迭代器

#include<bits/stdc++.h>
using namespace std;

int main(){
    string str="abcdefg";
    reverse(str.begin(),str.begin()+3); //对 str[0]~str[2]进行反转
    for(int i=0;i<str.length();i++){
        cout<<str[i]<<' '; //输出 cbadefg
    }
}

6.9.4 next_permutation()

next_permutation()给出一个序列在全排列中的下一个序列

比如当n==3时的全排列为

123
132
213
231
312
321

这样231的下一个序列就是312

示例如下

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[10]={1,2,3};
    //a[0]~a[2]之间的序列需要求解 next_permutation
    do{
        printf("%d%d%d\n",a[0],a[1],a[2]);
    }while(next_permutation(a,a+3));
    return 0;
}

输出结果

123
132
213
231
312
321

在上述代码中使用循环是因为next_permutation在已经到达全排列的最后一个时会返回false，这样方便退出循环。而使用do...while语句而不使用while是因为序列1 2 3本身也需要输出

6.9.5 fill()

fill()可以把数组或容器内某一段区间赋为某个相同的值。不同于memset只能赋0或-1，这里随便赋

int a[5];
fill(a,a+5,233);
//a[5]={233,233,233,233,233};

6.9.6 sort()

如何使用sort函数

sort(首元素地址（必填），尾元素地址的下一个地址，比较函数（非必填）);

不写比较函数则默认递增排序

如何实现比较函数cmp

基本数据类型数组的排序

比如要对一个数组实现降序排序

bool cmp(int a,int b){
    return a>b; //可以理解成当 a>b 的时候把 a 放在 b 前面
}

记忆方法：如果要升序，就用'<'，因为"a<b"就是左小右大；如果要降序，就用'>'，因为"a>b"就是左大右小

结构体数组的排序

比如如下的结构体

struct node{
    int x,y;
}ssd[10];

如果进行按照x的一级排序

bool cmp(node a,node b){
    return a.x>b.x;
}

二级排序

bool cmp(node a,node b){
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}

当然也可以使用重载运算符

struct node{
    int a;
    int b;
    bool operator < (const node &other) const{
        return x<other.x;
    }
}

容器的排序

在STL标准容器中只有vector,string,deque可以使用sort

//以 vector 为例
bool cmp(int a,int b){
    return a>b; //降序
}
int main(){
    vector<int> vi;
    vi.push_back(2);
    vi.push_back(3);
    vi.push_back(1;
   	sort(vi.begin(),vi.end(),cmp); //3 2 1
}

//以 string 为例
string str[3]={"aa","bbbb","ccc"};
sort(str,str+3); //按照字典序
//或者按照长度排序
bool cmp(string s1,string s2){
    return s1.length()<s2.length(); 
}

6.9.7 lower_bound()和upper_bound()

这两个函数需要用在一个有序数组或容器中，在4.5.1节已经讨论过了它们的实现

lower_bound(first,last,val)用来寻找在数组或容器的[first,last)范围内第一个值大于等于val的元素的位置，如果是数组则返回该位置的指针；如果是容器则返回该位置的迭代器

upper_bound(first,last,val)用来寻找在数组或容器的[first,last)范围内第一个值大于val的元素的位置，如果是数组则返回该位置的指针；如果是容器则返回该位置的迭代器

如果数组或容器中没有需要寻找的元素，则这两个函数均返回可以插入该元素位置的指针或迭代器（即假设存在该元素时，该元素应该在的位置）

时间复杂度O(log(last-first))

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[10]={1,2,2,3,3,3,5,5,5,5};
    int* lowerPos;
    int* upperPos;
    //寻找 3
    lowerPos=lower_bound(a,a+10,3);
    upperPos=upper_bound(a,a+10,3);
    printf("%d %d",lowerPos-a,upperPos-a); //输出 3 6
    return 0;
}

可见如果只是想获得欲查元素的下标，就可以不使用临时指针，直接令返回值减去数组首地址即可

二分函数的第四个参数：比较函数

当比较体没有明确的比较类型的时候：

struct ore{
  int w,v;
  bool operator<(const ore&other)const{
    return w<other.w;
  } //一定要有重载运算符
};

方法一：构造一个临时对象

// 假设 Ore 已经按 w 升序排序了
    vector<ore> Ore = { {1, 10}, {3, 20}, {5, 30}, {7, 40}, {9, 50} };
    
    int mid = 6;
    // 构造一个临时的 ore 对象，w 为 mid，v 可以为任意值
    ore tmp{mid, 0};
    
    auto it = lower_bound(Ore.begin(), Ore.end(), tmp);

方法二：使用自定义比较器 Lambda

// 假设 Ore 已经按 w 升序排序了
    vector<ore> Ore = { {1, 10}, {3, 20}, {5, 30}, {7, 40}, {9, 50} };
    
    int mid = 6;
    auto it = lower_bound(Ore.begin(), Ore.end(), mid, [](const ore &o, int value) {
        return o.w < value;
    });

这里传入了一个 lambda 作为比较器，lambda 定义为：给定一个 ore o 和一个 int value，如果 o.w < value 返回 true。

这样 lower_bound() 会查找第一个满足 !(o.w < mid)（即 o.w >= mid）的元素。

6.9.8 accumulate()

这个函数可以帮你计算一个范围内所有元素的累积和，还可以指定初始值和自定义操作。

#include <iostream>
#include <vector>
#include <numeric>  // 别忘了包含这个头文件
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    int sum = accumulate(nums.begin(), nums.end(), 0);

    cout << "累积和是：" << sum << endl; //15

    return 0;
}

在这个例子中，我们用 accumulate 计算了一个整型向量 nums 中所有元素的和。第三个参数 0 是累积的初始值，也就是从0开始加。最终，sum 变量中保存了所有元素的累积和。

6.9.10 unique()

它能帮助我们去除相邻的重复元素，并返回一个新的范围结束位置。

代码CPP · 18 行

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 2, 3, 4, 4, 5};
    auto it = unique(nums.begin(), nums.end());
    nums.erase(it, nums.end());

    cout << "去重后的元素是：";
    for(int num : nums) {
        cout << num << " ";
    }
    cout << endl;
	//去重后的元素是：1 2 3 4 5 
    return 0;
}

unique 会将相邻的重复元素移到向量的末尾，然后返回一个新的迭代器 it。接着，我们用 erase 将这些重复的元素移除，最终得到了一个没有相邻重复元素的向量。

6.9.11 find()

find 函数可以帮你在一个范围内找到第一个等于指定值的元素，并返回指向该元素的迭代器。下面是它的用法：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {10, 20, 30, 40, 50};
    auto it = find(nums.begin(), nums.end(), 30);

    if(it != nums.end()) {
        cout << "找到目标元素：" << *it << endl;
    } else {
        cout << "未找到目标元素。" << endl;
    }

    return 0;
}

在这个例子中，find 函数找到了向量 nums 中的元素 30，并返回了指向它的迭代器。如果找不到目标元素，find 会返回 end 迭代器。

6.9.12 count()

count 函数能帮你数数指定值在一个范围内出现了多少次。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 2, 3, 4, 2, 5};
    int count_of_2 = count(nums.begin(), nums.end(), 2);

    cout << "数字2出现的次数是：" << count_of_2 << endl;

    return 0;
}

在这个例子里，count 函数计算了数字 2 在向量 nums 中出现的次数，并将结果保存到 count_of_2 变量中。

6.9.13 partition()

partition 函数根据指定的条件将范围内的元素分为两部分，使得符合条件的元素位于前半部分。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    partition(nums.begin(), nums.end(), [](int x){ return x % 2 == 0; });

    cout << "分区后的结果是：";
    for(int num : nums) {
        cout << num << " ";
    }
    cout << endl;
	//分区后的结果是：8 2 6 4 5 3 7 1 9 
    return 0;
}

这里，我们用 partition 将向量 nums 中所有的偶数放在前面，奇数放在后面。这个分区操作利用了一个Lambda表达式来判断元素是否符合条件。

6.9.14 nth_element()

nth_element() 是 C++ 标准库中的一个算法函数，位于 <algorithm> 头文件中。其主要作用是对容器中的元素进行部分排序，使得第 n 小的元素位于容器的第 n 个位置（从零开始计数）。除此之外，函数保证该位置之前的所有元素都不大于该元素，之后的元素都不小于该元素，但它并不对整个容器进行排序。

用法如下

nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

• first：容器的起始迭代器，指向要处理的第一个元素。
• nth：一个迭代器，指向所需的 "n" 小元素的位置（即，想要排到第 n 小的位置）。
• last：容器的末尾迭代器。

代码CPP · 23 行

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 示例数据
    std::vector<int> vec = {1,2,3,9,4,5,8,6,10};

    // 求第 4 小的元素 (index 3)，即在排序后的数组中的第 4 个位置
    std::nth_element(vec.begin(), vec.begin() + 3, vec.end());

    // 输出第 4 小的元素和数组
    std::cout << "The 4th smallest element: " << vec[3] << std::endl;

    // 输出部分排序后的数组
    std::cout << "Array after nth_element: ";
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出

The 4th smallest element: 4
Array after nth_element: 2 1 3 4 9 5 8 6 10

注意，nth_element 并不会对数组做完整的排序。

6.9.15 is_sorted()

检查一个范围内的元素是否已经有序，默认是如果是升序或者降序排列就返回true否则返回false，当然也可以自己传入比较函数

bool is_sorted(InputIterator first, InputIterator last, Compare comp);

6.9.16 merge()

用于将两个已经排序的范围合并成一个新的排序范围。

std::vector<int> v1 = {1, 3, 5};
std::vector<int> v2 = {2, 4, 6};
std::vector<int> result(6);
    
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

其实就是这一段函数

int merge(int a[],int b[], int c[], int n, int m){
    //n 和 m 分别是数组 a 和 b 的长度
    int i=0,j=0,index=0;
    while(i<n&&j<m){
        if(a[i]<=b[j]) c[index++]=a[i++]; //相等的情况放 a 和 b 都一样
        else c[index++]=b[j++]; //把 b[j]放入序列中
    }
    while(i<n) c[index++]=a[i++]; //把 a 的剩余元素放入 c 中
    while(j<m) c[index++]=b[j++]; //把 b 的剩余元素放入 c 中
    return index; //返回序列 c 的长度
}

6.10 unordered_set的使用

非常接近于set 只是内部不有序

引用哈希集合的用法 哈希集合（Hash Set）是一个无序集合，主要用于快速查找、插入和删除操作。它的核心特点是： 元素唯一：集合中不能有重复的元素...

哈希集合的用法

哈希集合（Hash Set）是一个无序集合，主要用于快速查找、插入和删除操作。它的核心特点是：

• 元素唯一：集合中不能有重复的元素。
• 操作的时间复杂度为 O(1)O(1)（平均情况）。
• 哈希集合在C++中由 std::unordered_set 实现。

---

常用函数

以下是 std::unordered_set 的常用操作：

1. 插入元素

unordered_set<int> s;
s.insert(10);  // 插入元素 10
s.insert(20);  // 插入元素 20

2. 查找元素

if (s.find(10) != s.end()) {
    cout << "10 在集合中" << endl;
}

3. 删除元素

s.erase(10);  // 删除元素 10

4. 清空集合

s.clear();  // 清空集合

5. 获取集合大小

cout << "集合大小：" << s.size() << endl;

6. 判断集合是否为空

if (s.empty()) {
    cout << "集合为空" << endl;
}

7. 遍历集合

由于 unordered_set 是无序的，遍历时的顺序可能和插入顺序不同。

for (int x : s) {
    cout << x << " ";
}

8. 判断元素是否存在

使用 count 函数，返回值为 0 或 1。

if (s.count(10)) {
    cout << "10 在集合中" << endl;
}

---

实例解析

实例 1：判断数组中是否有重复元素

代码CPP · 32 行

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    int n;
    cout << "请输入数组长度：";
    cin >> n;

    unordered_set<int> s;
    bool hasDuplicate = false;
    cout << "请输入数组元素：" << endl;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        // 如果集合中已经有该元素，则有重复
        if (s.find(x) != s.end()) {
            hasDuplicate = true;
            break;
        }
        s.insert(x);  // 否则插入集合
    }

    if (hasDuplicate) {
        cout << "数组中有重复的元素！" << endl;
    } else {
        cout << "数组中没有重复的元素。" << endl;
    }

    return 0;
}

运行示例：

输入 1：

请输入数组长度：5
请输入数组元素：
1 2 3 4 5

输出 1：

数组中没有重复的元素。

输入 2：

请输入数组长度：5
请输入数组元素：
1 2 3 2 5

输出 2：

数组中有重复的元素！

---

实例 2：统计字符串中不重复字符的个数

代码CPP · 18 行

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    string str;
    cout << "请输入一个字符串：";
    cin >> str;

    unordered_set<char> s;  // 使用哈希集合存储字符
    for (char c : str) {
        s.insert(c);  // 每个字符插入集合
    }

    cout << "不重复字符的个数：" << s.size() << endl;

    return 0;
}

运行示例：

输入：

请输入一个字符串：hello

输出：

不重复字符的个数：4

---

实例 3：快速查找目标和对

给定一个数组，判断是否存在两个数的和等于目标值。

代码CPP · 28 行

#include <iostream>
#include <unordered_set>
using namespace std;

bool hasPairWithSum(int arr[], int n, int target) {
    unordered_set<int> s;  // 哈希集合存储访问过的元素
    for (int i = 0; i < n; i++) {
        int complement = target - arr[i];
        if (s.find(complement) != s.end()) {
            return true;  // 找到和为目标值的两个数
        }
        s.insert(arr[i]);  // 否则插入集合
    }
    return false;
}

int main() {
    int arr[] = {1, 4, 6, 8, 10};
    int target = 14;

    if (hasPairWithSum(arr, 5, target)) {
        cout << "存在和为 " << target << " 的两个数！" << endl;
    } else {
        cout << "不存在和为 " << target << " 的两个数！" << endl;
    }

    return 0;
}

运行示例：

输入数组：

[1, 4, 6, 8, 10], target = 14

输出：

存在和为 14 的两个数！

---

总结

• 优点：unordered_set 适合用于查找和去重，操作效率高（平均 O(1)O(1)）。
• 缺点：由于其无序性，无法直接获得有序结果。如果需要有序集合，可以使用 std::set（基于红黑树实现，操作复杂度为 O(log⁡n)O(\log n)）。

6.11 list 的使用

引用std::list 是 C++ 标准模板库（STL）中的一个容器，它实现了一个双向链表（doubly linked list）。与向量（std:...

std::list 是 C++ 标准模板库（STL）中的一个容器，它实现了一个双向链表（doubly linked list）。与向量（std::vector）不同，std::list 在以下场景中非常有用：

• 高效的插入与删除：在链表中，你可以在任意位置进行常数时间复杂度（O(1)）的插入和删除操作，而不需要像 std::vector 那样可能涉及大量数据的移动。
• 不支持随机访问：由于底层是链表，std::list 不支持下标访问（例如 list[i]），只能通过迭代器进行顺序遍历。

下面介绍一些常用的 std::list 操作，并附上示例代码：

---

1. 创建与初始化

代码CPP · 19 行

#include <iostream>
#include <list>
using namespace std;

int main() {
    // 创建一个空的 list，元素类型为 int
    list<int> myList;

    // 使用初始化列表创建 list
    list<int> numbers = {10, 20, 30, 40};

    // 输出 numbers 中的元素
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

---

2. 插入元素

• 在末尾插入：使用 push_back()
• 在开头插入：使用 push_front()
• 在任意位置插入：使用 insert()，insert(it, val) 成员函数用于在链表中插入元素。it 为该链表的一个迭代器，val 为待插入的值，插入后 val 位于 it 所指位置的前一位。返回值为一个迭代器，表示 val 插入到了哪个位置。

代码CPP · 26 行

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList;

    // 在末尾插入元素
    myList.push_back(10);
    myList.push_back(20);

    // 在开头插入元素
    myList.push_front(5);

    // 通过迭代器在第二个位置插入元素 15
    auto it = myList.begin();
    ++it; // 指向原来的第一个元素后面的位置
    myList.insert(it, 15);

    // 输出 list 中的元素
    for (int num : myList) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

---

3. 删除元素

• 删除开头元素：使用 pop_front()
• 删除末尾元素：使用 pop_back()
• 删除指定位置的元素：使用 erase()，传入对应的迭代器
• remove(it) 成员函数用于删除某个迭代器所指的节点。注意在删除之后 it 就失效了，除非给 it 重新赋值，否则对它的任何操作都会导致错误！
• 清空所有元素：使用 clear()

代码CPP · 22 行

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList = {5, 10, 15, 20};

    // 删除第一个元素
    myList.pop_front();

    // 删除最后一个元素
    myList.pop_back();

    // 删除中间的元素（例如，删除当前 list 中的第一个元素）
    auto it = myList.begin();
    myList.erase(it);

    // 此时 list 为空，或者可以再次添加元素
    myList.clear(); // 清空所有元素

    return 0;
}

---

4. 遍历与访问

由于 std::list 不支持随机访问（不能用下标访问），所以必须使用迭代器或范围 for 循环来遍历：

代码CPP · 21 行

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList = {10, 20, 30, 40};

    // 使用范围 for 循环遍历
    for (int num : myList) {
        cout << num << " ";
    }
    cout << endl;

    // 使用迭代器遍历
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

---

5. 常用算法成员函数

• sort()：对链表排序
• reverse()：将链表中的元素反转
• unique()：移除连续重复的元素
• merge()：合并两个已排序的 std::list

代码CPP · 39 行

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList = {30, 10, 20, 20, 40};

    // 排序
    myList.sort();  // 排序后：10, 20, 20, 30, 40

    // 移除连续重复的元素
    myList.unique(); // 结果：10, 20, 30, 40

    // 反转链表
    myList.reverse(); // 结果：40, 30, 20, 10

    // 输出结果
    for (int num : myList) {
        cout << num << " ";
    }
    cout << endl;

    // 合并两个已排序的 list
    list<int> list1 = {1, 3, 5};
    list<int> list2 = {2, 4, 6};

    // 确保两个 list 都已经排序
    list1.sort();
    list2.sort();
    list1.merge(list2);  // list1 合并了 list2，且 list2 变为空

    // 输出合并后的 list1
    for (int num : list1) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

---

6. 注意事项

• 迭代器失效：在对 std::list 进行插入或删除操作时，其他迭代器通常不会失效（与 std::vector 不同），但被删除元素对应的迭代器将无效。
• 内存使用：由于链表的每个节点都需要额外的指针存储前后节点的信息，因此在内存使用上可能比连续存储的容器（如 std::vector）稍高。
• 不支持随机访问：如果需要频繁地进行随机访问（例如，直接访问第 n 个元素），建议使用 std::vector 或 std::deque。

---

总的来说，std::list 提供了在任意位置快速插入和删除的能力，适用于对数据进行频繁修改的场景，但在需要随机访问和高空间效率

时，应考虑其他容器。

6.12 multiset 的使用

multiset 的定义

multiset 是一个集合容器，它可以存储多个相同的元素。换句话说，如果你有一堆重复的数，比如 3、5、5、5、7，你可以用multiset来妥善管理它们。与set不同的是，set不会允许重复的元素，而multiset非常欢迎重复元素的加入。

可以使用统一初始化的元素来创建

int main() {
    multiset<int> numbers = {3, 5, 5, 7, 3, 9};

    // 基于范围的 for 循环遍历 multiset
    for (int num : numbers) {
        cout << num << " ";
    }

    return 0;
}

注意，multiset会自动按升序排列元素。

如果是自定义类型，需要重载小于号

multiset 内元素的访问

使用迭代器

multiset 常用函数实例解析

insert()

略了

erase()

erase方法用来删除元素。但是要注意！如果你直接传入一个值，所有与这个值相同的元素都会被删除。如果你只想删除一个特定的元素，最好先找到它的迭代器，然后用这个迭代器来删除。

int main() {
    multiset<int> numbers = {3, 5, 5, 7};

    // 删除所有的 5
    numbers.erase(5);

    // 打印当前的 multiset
    for (int num : numbers) {
        cout << num << " ";
    }

    return 0;
}

如果只想删除第一个 5

auto it = numbers.find(5);  // 找到第一个 5
if (it != numbers.end()) {
    numbers.erase(it);  // 只删除找到的第一个 5
}

size()

略了

clear()

略了

empty()

略

lower_bound()

略 和 algorithm中的不一样

upper_bound()

略 和 algorithm中的不一样

第 7 章 提高篇（1）——数据结构专题（1）

7.1 栈的应用

栈 (stack) 是一种后进先出的数据结构。

可以把栈理解成一个箱子，箱子的长宽仅够一本书放入或拿出。每次可以把一本书放在箱子的最上方，也可以把箱子最上方的书拿出。

栈顶指针：始终指向栈的最上方元素的一个标记，当使用数组实现栈时，栈顶指针是一个 int 型的变量（数组下标从 0 开始），通常记作 TOP；而当使用链表实现栈时，则是一个 int*的指针。栈中没有元素（即栈空）时令 TOP=-1

下面使用数组 st[]来实现栈，int 型变量 TOP 表示栈顶元素的下标，对常用的几个操作进行示范实现

清空 clear

栈的清空操作指令 TOP=-1 表示栈中没有元素

void clear(){
	TOP=-1;
}

获取栈内元素个数 size

由于数组下标从 0 开始，元素个数为 TOP+1

int size(){
    return TOP+1;
}

判空 empty

bool empty(){
    if(TOP==-1) return true;
    else return false;
}

进栈 push

void push(int x){
	st[++TOP]=x; //先把 TOP+1，再把 x 存入 TOP 指向的位置
}

出栈 pop

void pop(){
	TOP--;
}

取栈顶元素 top

int top(){
	return st[TOP];
}

需要特别注意的是 pop 和 top 操作必须在栈非空的情况下才能使用，因此在这之前必须使用 empty() 函数判断

事实上使用 STL 的 stack 容器更简单。

需要注意的是 STL 中清空栈没有自带的函数，可以这样写

while(!st.empty()){
	st.pop();
}

但是更常用的做法是重新定义一个栈来变相实现栈的清空。

下面来看一个题

引用【codeup 1918】简单计算器 读入一个只包含 + - x / 的非负整数计算表达式，计算该表达式的值 输入格式： 一个长度不超过100的...

【codeup 1918】简单计算器

读入一个只包含 + - x / 的非负整数计算表达式，计算该表达式的值

输入格式：

一个长度不超过100的字符串，其中操作符和操作数仅由+、−、∗、/、整数（不小于1且不大于9）构成，且操作符和操作数之间用空格分隔。数据确保表达式一定合法，且计算过程的所有结果不会超过 10^9。

输出格式：

输出一行，即该表达式的值，精确到小数点后两位

样例输入

3 + 4 * 5

输出

23.00

引用1. 中缀表达式（Infix Expression） 中缀表达式是我们日常生活中最常见的数学表达式形式。它的特点是运算符位于两个操作数之间。例如...

1. 中缀表达式（Infix Expression）

中缀表达式是我们日常生活中最常见的数学表达式形式。它的特点是运算符位于两个操作数之间。例如：

• 3 + 4
• (5 - 2) * 6
• 2 + 3 * 4

特点

• 运算符位于操作数之间。
• 需要使用括号来明确运算顺序。
• 人类易于理解和书写，但计算机处理起来较为复杂。

示例

• 2 + 3 * 4 的中缀表达式需要根据运算符优先级计算：先计算 3 * 4，再计算 2 + 12，结果为 14。

---

2. 后缀表达式（Postfix Expression，也称为逆波兰表达式）

后缀表达式是一种不需要括号的表达式形式，它的特点是运算符位于操作数之后。例如：

• 3 4 +
• 5 2 - 6 *
• 2 3 4 * +

特点

• 运算符位于操作数之后。
• 不需要括号，运算顺序完全由运算符的位置决定。
• 计算机处理起来非常方便，适合用栈（Stack）来求值。

示例

• 2 3 4 * + 的后缀表达式计算过程：
  1. 遇到 3 4 *，计算 3 * 4 = 12。
  2. 表达式变为 2 12 +。
  3. 计算 2 + 12 = 14，结果为 14。

---

3. 中缀表达式转后缀表达式

将中缀表达式转换为后缀表达式是计算机科学中的一个常见任务，通常使用栈（Stack）来实现。以下是转换的步骤：

转换规则

1. 初始化一个空栈和一个空输出列表。
2. 从左到右扫描中缀表达式。
3. 如果遇到操作数，直接添加到输出列表。
4. 如果遇到左括号 (，将其压入栈。
5. 如果遇到右括号 )，将栈中的运算符弹出并添加到输出列表，直到遇到左括号 (。左括号弹出但不添加到输出列表。
6. 如果遇到运算符：
   • 弹出栈中优先级高于或等于当前运算符的所有运算符，并添加到输出列表。
   • 将当前运算符压入栈。
7. 扫描结束后，将栈中剩余的运算符依次弹出并添加到输出列表。

示例

将中缀表达式 2 + 3 * 4 转换为后缀表达式：

1. 输出列表：2
2. 栈：+
3. 输出列表：2 3
4. 栈：+ *
5. 输出列表：2 3 4
6. 栈：+ *（扫描结束，弹出栈中所有运算符）
7. 输出列表：2 3 4 * +

7.2 队列的应用

队列（queue）是一种先进先出的数据结构，与栈有所不同。

举一个例子来理解：食堂打饭排队，最先进去的先打到饭出队，也就是先进先出

一般来说需要一个队首指针 front 来指向队首元素的前一个位置，而使用一个队尾指针 rear 来指向队尾元素。

与栈类似，当使用数组来实现 queue 时，队首指针 front 和队尾指针 rear 为 int 型变量（下标从 0 开始）；而当使用链表来实现时则为 int*型变量的指针

下面使用数组 q[]来实现队列，而 int 型变量 front 存放队首元素的前一个下标，rear 存放队尾元素的下标（下标从 0 开始），下面演示常见操作：

清空 clear

初始状态为 front=-1、rear=-1

void clear(){
    front=rear=-1;
}

获取队列内元素的个数 size

in size(){
    return rear-front;
}

判空 empty

bool empty(){
    if(front==rear) return true;
    else return false;
}

入队 push

由于 rear 指向队尾元素，因此元素入队时需先把 rear+1，再存放到 rear 指向的位置

void push(){
    q[++rear]=x;
}

出队 pop

可以把队首指针 +1 来实现

void pop(){
	front++;
}

取队首元素 get_front

由于 front 指向的是队首元素的前一个元素，因此 front+1 才是队首元素的位置

int get_front(){
    return q[front+1];
}

取队尾元素 get_rear

int get_rear(){
	return q[rear];
}

与栈类似，这些操作必须在队列非空的情况下时候，要先判断

另外，多用 STL 比较好

7.3 链表处理

7.3.1 链表的概念

线性表：常用的一种数据结构

• 顺序表：可以简单地理解成“数组”
• 链表

按正常方式定义一个数组的时候，计算机会从内存中取出一块连续的地址来存放给定长度的数组；而链表则是由若干个结点组成（每个结点代表一个元素），且结点在内存中的存储位置通常是不连续的。除此之外，链表的两个结点之间一般通过一个指针来从一个结点指向另一个结点，因此链表的结点一般由两部分构成，即数据域和指针域：

struct node {
    typename data; //数据域
    node* next; //指针域
}

一般来说，数据域存放要储存的数据，而指针域指向下一个结点的地址，这样就会产生从某个节点开始的由指针链接的一条链式结构，即链表。

可以分为两类

• 带头结点的链表
• 不带头结点的链表

头结点一般称为 head，其数据域 data 不存放任何内容，而指针域 next 指向第一个数据域有内容的结点（一般直接把这个结点叫做第一个结点），我们在这里统一采用带头结点的写法。最后一个结点的 next 指针指向 NULL，表示一条链表的结尾

7.3.2 使用 malloc 函数或 new 运算符为链表节点分配内存空间

malloc 函数

C 语言中 stdlib.h 头文件下用于动态内存申请的函数，返回类型是申请的同变量类型的指针

typename* p=(typename*)malloc(sizeof(typename));

以申请一个 int 型变量和一个 node 型结构体变量为例：

int *p=(int*)malloc(sizeof(int));
node* p=(node*)malloc(sizeof(node));

这个写法的逻辑是：以需要申请的内存空间大小（即 sizeof(node)）为 malloc 函数的参数，这时 malloc 函数就会向内存申请一块大小为 sizeof(node) 的空间，并且返回指向这块空间的指针。但这时这个指针类型未确定 (void*)，因此需要将它强转为 node*型，这样等号右边就得到了一个 node*型的指针，并通过赋值等号把这个指针赋给了 node*型的指针变量 p，就成功申请了一块 node 类型大小的内存空间，即一个 node 型的结构体变量，并通过指针 p 来访问它。

new 运算符

new 是 C++ 中用来申请动态空间的运算符，其返回类型同 malloc 函数的返回类型，基本用法如下

tyoename* p=new typename;

同样以申请一个 int 型变量和一个 node 型变量为例

int *p=new int;
node* p=new node;

内存泄漏

指 malloc 与 new 开劈出来的内存空间在使用之后没有释放，导致其在程序结束之前始终占据该内存空间，所以在使用完 malloc 和 new 开辟出来的空间之后必须将其释放。

free 函数

free 函数是对应 malloc 函数的，同样在 stdlib.h 下面

//在 free 的参数中填写需要释放的内存空间的指针变量即可
free(p);

free 函数的效果：

1. 释放指针变量 p 所指向的内存空间
2. 将指针变量 p 指向空地址 NULL

需要注意的是 malloc 和 free 必须成对出现否则容易爆

delete 运算符

对应 new 运算符，使用方法和实现效果与 free 相同

delete(p);

delete 和 new 运算符必须成对出现

7.3.3 链表的基本操作

创建列表

现在可以通过 malloc 和 new 来获得若干个零散的结点，只需要把他们串起来，只需要让每个结点的 next 指针指向下一个结点的地址即可

1. -> 操作符的作用

-> 操作符用于通过指针访问对象的成员。它的作用相当于：

1. 解引用指针（*ptr）。
2. 访问对象的成员（(*ptr).member）。

换句话说，ptr->member 等价于 (*ptr).member。

---

2. 使用场景

-> 操作符通常用于以下场景：

1. 访问动态分配对象的成员：
   • 当对象是通过 new 动态分配时，返回的是指针，此时需要使用 -> 访问成员。
2. 访问结构体或类的指针成员：
   • 当结构体或类的实例是通过指针引用时，使用 -> 访问成员。
3. 访问智能指针的成员：
   • 对于智能指针（如 std::unique_ptr 或 std::shared_ptr），使用 -> 访问成员。

代码CPP · 38 行

#include<bits/stdc++.h>
using namespace std;

struct node {
    int data;
    node* next;
};

node *create(int a[],int len){
    node *p,*pre,*head; //当前结点 前驱结点 头结点
    head=new node; //创建头结点
    head->next=NULL; //初始化，让头结点指向 NULL
    //pre=new node; //创建前驱结点
    //上面一行不需要，因为前驱结点（pre）一开始就应该指向头结点，并不需要为 pre 创建一个新的结点，因为 pre 只需要作为指向头结点的指针
    pre=head; //最开始前驱结点就是头结点
    for(int i=0;i<len;++i){
        p=new node; //创建结点 即前驱结点的后继结点
        p->data=a[i]; //读入结点数据域 也可以 scanf
        p->next=NULL; //先初始化
        pre->next=p; //前驱结点的指针域（指向前驱结点的后继结点）设为当前新建结点的地址，把前后两个结点连接起来
        //必须要理解这里的 pre 和 p 都是指针，本质是地址
        //所以比如 i=0 的情况下，原本是 head->NULL 的，现在是 head->1 了，因为修改了 pre 就等同于修改了 head，因为 pre 和 head 的地址相同
        pre=p; //把 pre 作为 p，作为下一个结点的前驱结点
        //其实是把 pre 的地址换个地方，现在 pre 的地址是上面那一通操作生成的 p 的地址
    }
    return head; //返回头结点指针
}

int main(){
    int a[5]={1,2,3,4,5};
    node* L=create(a,5);
    L=L->next; //从第一个结点开始有数据域
    while(L!=NULL){
        printf("%d",L->data);
        L=L->next;
    } //输出 1 2 3 4 5
    return 0;
}

第 17 行和第 18 行：指针的传递

pre->next = p;  // 将前驱节点的指针域（next）指向新节点 p
pre = p;         // 将 pre 指向当前节点 p，作为下一个节点的前驱

这两行代码的目的是 更新链表中各个节点的链接关系。让我们逐一解释：

• pre->next = p;

  ：

  • 这行代码是将前一个节点（即 pre 指向的节点）的 next 指针指向新创建的节点 p。
  • 例如，假设链表目前有节点 A 和节点 B，此时 pre 指向节点 A，p 指向新创建的节点 B。你要做的是将 A->next 指向 B，也就是说，链表从 A 到 B 连接起来。

• pre = p;

  ：

  • 这行代码的作用是更新前驱节点 pre 的指向。
  • 将 pre 更新为当前的节点 p，也就是将 pre 指向 B。
  • 下一次循环时，pre 就是 B，此时它会作为前一个节点参与到 next 指针的更新。

换句话说， pre->next = p; 负责建立新节点的链接关系，而 pre = p; 则是更新 pre 为当前节点 p，为下一轮创建新的节点做准备。

查找元素

从第一个结点开始，不断判断当前结点的数据域是否等于 x，如果等于就 cnt++，这样结尾的时候 cnt 的值就是列表中元素 x 的个数

int search(node *head,int x){
    int cnt=0;
    node *p=head->next; //从第一个节点开始
    while(p!=NULL){
        if(p->data==x) cnt++;
        p=p->next;
    }
    return cnt;
}

插入元素

“在第 3 个位置插入元素 4”的意思是在插入完成之后第 3 个位置的元素是 4，意思是把原先第三个位置的元素让开（在第 2 和 3 之间插入）

假设原本是 6 7 8 9 10

在第三个位置插入 4 之后，就是 7 指向 4，而 4 指向 8，依此思路进行代码实现

//将 x 插入以 head 为头结点的链表的第 pos 个位置上
void insert(node *head,int pos,int x){
    node* p=head;
    for(int i=0;i<pos-1;i++){
        p=p->next; //pos-1 是为了插入位置的前一个结点，这里相当于移动 p 的指针
    }
    node *q=new node;
    q->data=x; //这个时候 q 还是野指针
    q->next=p->next;
    p->next=q;
}

这份代码可以直接写在“创建链表”部分的代码中进行使用，把 create 函数返回的头指针 L 直接作为第一个参数传入即可

顺序必须是先把新节点的指针域 next 指向后继结点，之后才能把前一个元素所在节点的指针指向新节点的地址

删除元素

对链表来说，删除元素是指删除链表上所有值为给定的数 x，操作是这样进行的：

1. 由指针变量 p 枚举结点，指针变量 pre 作为 p 指向的结点的前驱结点
2. 当 p 指向的结点的数据域恰好为 x 时，进行下面三个操作
   1. 令 pre 指向的结点的指针域指向指针变量 p 指向的结点的后继结点
   2. 释放 p 所指向结点的内存空间
   3. 令 p 指向 pre 指向的结点的后继结点

代码实现如下

//删除以 head 为头结点的链表中所有数据域为 x 的结点
void del(node* head,int x){
    node *p=head->next; //p 从第一个结点开始枚举
    node *pre=head; //pre 始终保存 p 的前驱结点的指针
    while(p!=NULL){
        if(p->data==x){ //数据域恰好为 x，说明要删除该结点
            pre->next=p->next;
            delete(p);
            p=pre->next;
        }
        else{ //数据域不是 x，把 pre 和 p 都往后移一位
            pre=p;
            p=p->next;
        }
    }
}

这份代码可以直接写在“创建链表”部分的代码中进行使用，把 create 函数返回的头指针 L 直接作为第一个参数传入即可

最后总结一下这几个板子

代码CPP · 59 行

#include<bits/stdc++.h>
using namespace std;
struct node {
    int data;
    node* next;
};

node *create(int a[],int len){
    node *p,*pre,*head;
    head=new node;
    head->next=NULL;
    pre=head;
    for(int i=0;i<len;i++){
        p=new node;
        p->next=NULL;
        p->data-a[i];
        pre->next=p;
        pre=p;
    }
    return head;
}
int search(node *head,int x){
    int cnt=0;
    node *p=head->next; //从第一个节点开始
    while(p!=NULL){
        if(p->data==x) cnt++;
        p=p->next;
    }
    return cnt;
}

//将 x 插入以 head 为头结点的链表的第 pos 个位置上
void insert(node *head,int pos,int x){
    node* p=head;
    for(int i=0;i<pos-1;i++){
        p=p->next; //pos-1 是为了插入位置的前一个结点，这里相当于移动 p 的指针
    }
    node *q=new node;
    q->data=x; //这个时候 q 还是野指针
    q->next=p->next;
    p->next=q;
}

//删除以 head 为头结点的链表中所有数据域为 x 的结点
void del(node* head,int x){
    node *p=head->next; //p 从第一个结点开始枚举
    node *pre=head; //pre 始终保存 p 的前驱结点的指针
    while(p!=NULL){
        if(p->data==x){ //数据域恰好为 x，说明要删除该结点
            pre->next=p->next;
            delete(p);
            p=pre->next;
        }
        else{ //数据域不是 x，把 pre 和 p 都往后移一位
            pre=p;
            p=p->next;
        }
    }
}

7.3.4 静态链表

对于有些问题来说，结点的地址是比较小的整数，这样无必要建立动态链表，应使用简单的静态链表

实现原理是 hash，通过建立一个结构体数组，并令数组的下标直接表示该结点的地址，来达到直接访问数组中的元素就能访问结点的效果，因为访问非常方便所以不需要头结点

struct Node{
    typename data; //数据域
    int next; //指针域
}node[size]; //注意数组名和结构体名不要相同

next=-1 表示没有后继结点

【PAT A1032】 Sharing

给出两条链表的首地址以及若干结点的地址、数据、下一个结点的地址，求两条链表的首个共用结点的地址。如果两条链表没有共用结点则输出 -1

注意：使用 map 容易超时

代码CPP · 34 行

#include<bits/stdc++.h>
using namespace std;

const int maxn=100010;
struct Node{
    char data;
    int next;
    bool flag; //数据是否在第一条链表里面出现
    Node(){
        flag=false;
        next=-1;
    }
}node[maxn];

int main(){
    int s1,s2,n; //s1 s2 分别表示两条链表的首地址
    scanf("%d%d%d",&s1,&s2,&n);
    char data;
    int address,next;
    for(int i=0;i<n;i++){
        scanf("%d %c %d",&address,&data,&next);
        node[address].data=data;
        node[address].next=next;
    }
    int p;
    for(int p=s1;p!=-1;p=node[p].next){
        node[p].flag=true;
    }
    for(int p=s2;p!=-1;p=node[p].next){
        if(node[p].flag) break;
    }
    if(p!=-1) printf("%05d",p);
    else printf("-1");
}

这是一道静态列表所能解决的比较简单的题，而对于稍微复杂一点的题此处归纳一种通法

1. 定义静态链表

   struct Node{
       typename data; //数据域
       int next; //指针域
       XXX; //结点的某个性质，不同的题目会有不同的设置
   }node[100010];

   例如可以设置结点是否为链表上的一个结点

2. 在程序的开始对静态链表进行初始化，一般来说需要对定义里的 XXX 进行初始化，定义为正常情况下达不到的数字（一般来说需要小于所有能达到的数字）

3. 题目一般都会给出一条链表的首结点的地址，那么我们就可以根据这个地址来遍历得到整条链表，同时需要注意这一步同时也是对性质 XXX 进行标记、并且对有效节点的个数进行计数的时候

4. 由于使用静态链表的时候是采用 hash 的方式，这就会使得数组下标的不连续，而很多时候题目给出的结点并不都是有效结点（即可能存在不在链表上的结点）。为了能够可控地访问有效结点，一般需要对数组进行排序，把有效结点移到数组左端，这样就可以用步骤 3 得到的 cnt 来访问它们。

   既然需要把有效结点移到前面，那么就可以使用之前定义的 XXX 来帮忙。在步骤 2 中 XXX 需要被初始化为比正常结点的 XXX 取值要小的数值，而由于无效结点的 XXX 在步骤 3 中并不会被修改，因此一定比有效结点的 XXX 小。于是可以使用特定的 cmp 函数来将 cmp 的两个参数结点中有无效结点时按 XXX 降序，这样就可以把有效结点全部移到数组左端

   bool cmp(Node a,Node b){
   	if(a.XXX==-1||b.XXX==-1){ //至少一个结点是无效结点 把它放在数组后面
           	return a.XXX>b.XXX;
       }
       else{
           //第二级排序
       }
   }

5. 在步骤 4 之后有效结点均位于数组左端，且已经按结点的顺序进行了排序，接下来依题目而定

【PAT A1052】 Linked List Sorting

给出 N 个结点的地址 address、数据域 data 以及指针域 next，然后给出链表的首地址，要求把这个链表上的结点按 data 值从大到小输出。（输入格式与输出格式相同）

代码CPP · 40 行

//给出 N 个结点的地址 address、数据域 data 以及指针域 next，然后给出链表的首地址，要求把这个链表上的结点按 data 值从大到小输出。（输入格式与输出格式相同）
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
struct Node{
    int address;
    int data;
    int next=-1;
    bool flag=false;
}node[maxn];
bool cmp(Node a,Node b){
    if(!a.flag||!b.flag) return a.flag>b.flag;
    else return a.data<b.data;
}
int main(){
    int headAddress,n;
    scanf("%d%d",&n,&headAddress);
    int address,data,next;
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&address,&data,&next);
        node[address].address=address;
        node[address].data=data;
        node[address].next=next;
    }
    int p,cnt=0;
    for(int p=headAddress;p!=-1;p=node[p].next){
        node[p].flag=true;
        cnt++;
    }
    if(!cnt) printf("0 -1");
    else{
        sort(node,node+maxn,cmp);
        printf("%d %05d\n",cnt,node[0].address);
        for(int i=0;i<cnt;i++){
            if(i!=cnt-1) printf("%05d %d %05d\n",node[i].address,node[i].data,node[i+1].address);
            //这里一定要注意第三项不要写成 node[i].next，因为 sort 完了，我们要打印的顺序并不是按照链表链接的顺序
            else printf("%05d %d -1",node[i].address,node[i].data);
        }
    }
}

第 8 章 提高篇（2）——搜索专题

8.1 深度优先搜索（DFS）

以枚举所有完整路径以遍历所有情况的搜索方法

dfs 可以用栈来实现，但是递归更简单

把递归式理解成岔道口，递归边界理解成死胡同

有 n 件物品，每件物品的重量为 w[i]，价值为 c[i]。现在需要选出若干件物品放入一个容量为 V 的背包中，使得在选入背包的物品重量和不超过容量 V 的前提下，让背包中物品的价值最大，求最大价值（1<=n<=20）

分析：

死胡同：物品重量总和超过 V

岔道口：每次选择的不同的物品

代码CPP · 34 行

#include<bits/stdc++.h>
using namespace std;

const int maxn=25;

int n,v,maxValue,w[maxn],c[maxn];

void dfs(int idx,int sumW,int sumC){
    //死胡同
    if(idx==n){ //已经完成对 n 件物品的选择
        if(sumW<=v&&sumC>maxValue){
            maxValue=sumC;
        }
        return;
    }
    //岔路口
    dfs(idx+1,sumW,sumC); //不选第 idx 件物品
    //如果不选第 idx 件物品无法做到最大的话
    dfs(idx+1,sumW+w[idx],sumC+c[idx]); //选第 idx 件物品（0 起计）
    //因为数组下标 0 起计，w[idx] 其实就是已经选了 idx+1 件
}

int main(){
    cin>>n>>v;
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    for(int i=0;i<n;i++){
        cin>>c[i];
    }
    dfs(0,0,0); //初始时第 0 件物品，总重量和总价值均为 0
    cout<<maxValue;
    return 0;
}

由于每件物品有两种选择，时间复杂度 O($2^n$)，但是可以稍加优化来让效率更高。

上述代码中总是把 n 件物品的选择全部确定之后才更新最大价值，但是事实上忽略了背包容量不超过 v 这个特点。也就是说完全可以把 sumW 的判断加入“岔道口”，只有当 sumW<=V 的时候才进入岔道，修改如下

void dfs(int idx,int sumW,int sumC){
    if(idx==n) return; //已经完成了对 n 件物品的选择
    //岔道口
    dfs(idx+1,sumW,sumC); //不选第 idx 件物品
    //只有加入第 idx 件物品后未超过容量 v 才能继续
    if(sumW+w[idx]<=v){
        if(sumC+c[idx]>maxValue) maxValue=sumC+c[idx];
    }
    dfs(idx+1,sumW+w[idx],sumC+c[idx]); //选第 idx 件物品
}

这样优化了时间复杂度。

这种通过题目条件限制来节省 DFS 计算量的方法叫做剪枝

事实上下面给出了一类 DFS 问题的解决方法：给定一个序列，枚举这个序列中的所有子序列（可以不连续）

给定 n 个整数（可能有负数），从中选择恰好 k 个数，使这 k 个数的和恰好等于一个给定的数 x；如果有多种方案，选择平方和最大的那一个

void dfs(int idx,int nowK,int sum,int sumSqu){
    if(nowK==k&&sum==x){
        if(sumSqu>maxSumSqu){
            maxSumSqu=sumSqu;
            ans=temp;
        }
        return;
    }
    //已经处理完n个数，或者超过k个数，或者和超过x，返回
    if(idx==n||nowK>k||sum>x) return;
    //选idx号数
    temp.push_back(a[idx]);
    dfs(idx+1,nowK+1,sum+a[idx],sumSqu+a[idx]*a[idx]);
    temp.pop_back();
    //不选
    dfs(idx+1,nowK,sum,sumSqu);
}

dfs 的一些剪枝技巧

先给出一段深搜模板

int ans = 最坏情况, now;  // now 为当前答案
这个模板要求在调用dfs之前先将起点标记，防止回溯出现环路。
void dfs(传入数值) {
  if (到达目的地) ans = 从当前解与已有解中选最优;
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

其中的 ans 可以是解的记录，那么从当前解与已有解中选最优就变成了输出解。

记忆化搜索

代码CPP · 19 行

int g[MAXN];  // 定义记忆化数组
int ans = 最坏情况, now;

void dfs f(传入数值) {
  if (g[规模] != 无效数值) return;  // 或记录解，视情况而定
  if (到达目的地) ans = 从当前解与已有解中选最优;  // 输出解，视情况而定
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

int main() {
  // ...
  memset(g, 无效数值, sizeof(g));  // 初始化记忆化数组
  // ...
}

最优性剪枝

int ans = 最坏情况, now;

void dfs(传入数值) {
  if (now比ans的答案还要差) return;
  if (到达目的地) ans = 从当前解与已有解中选最优;
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

可行性剪枝

int ans = 最坏情况, now;

void dfs(传入数值) {
  if (当前解已不可用) return;
  if (到达目的地) ans = 从当前解与已有解中选最优;
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

8.2 广度优先搜索（BFS）

以广度为第一关键词。当碰到岔道口时，总是先依次访问从该岔道口能直接到达的所有结点，然后再按这些结点被访问的顺序去依次访问它们能直接到达的所有结点。

算法依靠队列来实现。

void BFS(int s){ //s 为起点
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        取出队首元素top;
        访问队首元素top; //访问可以是任何事情，例如输出
        将队首元素出队; 
        将top的下一层结点中未曾入队的结点全部入队,并设置为已入队;
        //并标记它们的层号为 now++，同时设置这些结点已入队
    }
}

例题

给出一个 m*n 的矩阵，矩阵中的元素为 0 或 1。称位置 (x,y) 与其上下左右四个位置是相邻的。如果矩阵中有若干（1 个也算若干个）个 1 是相邻的（不必两两相邻），那么称这些 1 构成了一个“块”，求给定的矩阵中块的个数。

使用 bfs 的思想：枚举每一个位置的元素，如果是 0 就跳过，如果是 1 就使用 bfs 查询与该位置相邻的 4 个元素（前提是不出界），判断是否为 1，如果是 1 那么继续查询，直到整个 1 块访问完毕。而为了避免走回头路可以定义一个 bool 数组 inq(即 in queue 的缩写) 来记录每个位置是否在 bfs 中已经入过队。

对于当前位置 (x,y) 而言，可以设置两个增量数组来访问相邻的 4 个位置。

int X[]={0,0,1,-1};
int Y[]={1,-1,0,0};

分别对应 (x,y+1) (x,y-1) (x+1,y) (x-1,y)

这样就可以用 for 循环去枚举 4 个方向，以确定当前坐标 (nowX,nowY) 相邻的 4 个位置

for(int i=0;i<4;i++){
    newX=nowX+X[i];
    newY=nowY+Y[i];
}

本题的 bfs 代码实现如下

代码CPP · 53 行

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=105;
struct node{
    int x,y; //存放位置
}Node;
int n,m; //矩阵大小
int matrix[maxn][maxn]; //01 矩阵
bool inq[maxn][maxn]; //记录是否入过队
int X[4]={0,0,1,-1},Y[4]={1,-1,0,0}; //坐标增量数组
bool judge(int x,int y){
    if(x>m||x<1||y>n||y<1||inq[x][y]||matrix[x][y]==0) return false;
    //只要出界||入过队||在该点不为 1，就不访问
    return true;
}
//访问位置 (x,y) 所在的块，设置一个块内的 1 的 inq 为 true
void bfs(int x,int y){
    queue<node> q;
    Node.x=x;Node.y=y;
    q.push(Node);
    while(!q.empty()){
        node top=q.front(); //取队首元素 top
        q.pop();
        for(int i=0;i<4;i++){ //得到相邻位置
            int newX=top.x+X[i],newY=top.y+Y[i];
            if(judge(newX,newY)){ //如果这个新位置是符合要求的，需要访问
                Node.x=newX;Node.y=newY;
                q.push(Node); //入队
                inq[newX][newY]=true; //已经入过队
            }
        }
    }
}
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>matrix[i][j];
        }
    }
    int ans=0; //记录答案（块数
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(matrix[i][j]==1&&!inq[i][j]){ //如果这个位置是 1 而且没有被访问过
                ans++; //块数++
                bfs(i,j);
            }
        }
    }
    cout<<ans;
}

当然也可以使用 dfs 来实现

代码CPP · 42 行

#include<iostream>
#include<algorithm>
using namespace std;
/*dfs 的思路：
从输入的点开始搜索，如果碰到 0 了就 return
否则走岔路口：往四个方向走*/
const int maxn=105;
int m,n,matrix[maxn][maxn];
int X[4]={0,0,1,-1},Y[4]={1,-1,0,0}; //坐标增量数组
bool visited[maxn][maxn];//记录是否查询过
bool judge(int x,int y){
    if(x<1||x>m||y<1||y>n||visited[x][y]||!matrix[x][y]) return false;
    //只要出界||入过队||在该点不为 1，就不访问
    return true;
}
//搜索一个块内，并标记为 true
void dfs(int x,int y){
    if(!judge(x,y)) return;
    visited[x][y]=true;
    for(int i=0;i<4;i++){
        int newX=x+X[i],newY=y+Y[i];
        dfs(newX,newY);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>matrix[i][j];
        }
    }
    int ans=0; //记录答案（块数
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(matrix[i][j]&&!visited[i][j]){ //如果这个位置是 1 而且没有被访问过
                dfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans;
}

接下来再来看一个例题

给定一个大小为 n*m 的迷宫，其中*代表不可通过的墙壁，而'.'代表平地，S 表示起点，T 表示终点。在移动过程中，如果当前位置是 (x,y) （下标从 0 开始），且每次只能前往上下左右四个位置的平地，求从起点 S 到终点 T 的最少步数。

由于求的是最少步数，而 bfs 是按照层次的顺序来遍历的，因此可以从 S 开始计数遍历的层数，到达终点 T 时的层数就是需要求解的起点 S 到终点 T 的最少步数。

代码CPP · 47 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n,m;
int X[4]={0,0,-1,1},Y[4]={1,-1,0,0}; //增量数组
char maze[maxn][maxn]; //迷宫
bool inq[maxn][maxn]={false}; //是否已入过队
struct node{
    int x,y;
    int step; //从起点 S 到该位置的最少步数（即层数）
}S,T,Node; ///起点、终点、临时结点
//判断这个路径是否可行
bool judge(int x,int y){
    if(x<0||x>=n||y<0||y>=m||maze[x][y]=='*'||inq[x][y]) return false;
    return true;
}
//找到一条最短的路径
int bfs(){
    queue<node> q;
    q.push(S);
    while(!q.empty()){
        node top=q.front();
        q.pop();
        if(top.x==T.x&&top.y==T.y) return top.step;
        for(int i=0;i<4;i++){
            int newX=top.x+X[i],newY=top.y+Y[i];
            if(judge(newX,newY)){
                Node.x=newX,Node.y=newY;
                Node.step=top.step+1;
                q.push(Node);
                inq[newX][newY]=true;
            }
        }
    }
    return -1; //无法到达的时候返回 -1
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>maze[i][j];
        }
    }
    cin>>S.x>>S.y>>T.x>>T.y;
    S.step=0; //初始化
    cout<<bfs();
}

这里如果要改成“输出最短的路径”

代码CPP · 51 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
struct node{
    int x,y;
    vector<pair<int,int> > path;
}S,T,Node; //起点、终点、临时结点
int n,m,maze[maxn][maxn],X[4]={0,0,-1,1},Y[4]={1,-1,0,0};
bool inq[maxn][maxn]={false};//是否已入过队
//判断这个路径是否可行
bool judge(int x,int y){
    if(x<1||x>n||y<1||y>m||maze[x][y]||inq[x][y]) return false;
    return true;
}
void bfs(){
    queue<node> q;
    q.push(S);
    inq[S.x][S.y]=true; //起点入队
    while(!q.empty()){
        node top=q.front();
        q.pop();
        if(top.x==T.x&&top.y==T.y){ //到达终点
            for(const auto& x:top.path){
                cout<<x.first<<' '<<x.second<<endl;
            }
            return;
        }
        for(int i=0;i<4;i++){
            int nowX=top.x+X[i],nowY=top.y+Y[i]; //得到相邻的点
            if(judge(nowX,nowY)){ //如果可以走
                Node.x=nowX,Node.y=nowY;
                Node.path=top.path; //复制之前的路径
                Node.path.push_back({Node.x,Node.y}); //加上现在的路径
                q.push(Node); //入队
                inq[Node.x][Node.y]=true;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>maze[i][j];
        }
    }
    S.x=1,S.y=1,S.path.push_back({1,1});
    T.x=n,T.y=m;
    bfs();
    return 0;
}

在 BFS 中设置的 inq 数组的含义是结点是否已经入过队，而非结点是否已经被访问。

区别：如果设置成是结点是否已经被访问，有可能某个结点正在队列中（但还未被访问）的时候由于其他结点可以到达他而将这个结点再次入队，导致很多结点反复入队。

由于元素入队的时候相当于是在队列里面创造了一个副本，因此在对应的容器中修改并不会修改到另一个元素。

所以当需要对队列中的元素进行修改而不仅仅是访问的时候，队列中存放的元素最好不要是元素本身而应该是它们的编号。

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

struct node{
    int data;
}a[10];
int main(){
    queue<int> q;
    for(int i=1;i<=3;i++){
        a[i].data=i;
        q.push(i); //这里存放的是下标
    }
    a[q.front()].data=100;
    cout<<a[1].data; //输出 100
}

第 9 章 提高篇（3）——数据结构专题（2）

9.1 树与二叉树

9.1.1 树的定义与性质

数据结构中将树枝分叉处、树叶、树根抽象为结点（node），其中树根抽象为根节点（root），且对于一棵树最多只存在一个根节点；把树叶抽象为叶子结点（leaf），且叶子结点不再延伸出新的结点；把茎干和树枝统一抽象为边（edge），且一条边只用来连接两个结点（一个端点一个）。

在数据结构中一般把根节点置于最上方（与现实中相反），然后向下延伸出若干条边到达子结点（从而向下形成子树 (child），而子结点又向下延伸出边并连接一些结点，直至到达叶子结点。

下面给出树的几个比较实用的概念和性质，其中 1,5 经常用来出边界数据

1. 树可以没有结点，这种情况称之为空树
2. 树的层次从根节点开始算起，即根结点为第一层，根结点子树的根结点为第二层，以此类推
3. 二叉树的宽度（Width of a Binary Tree）通常指的是同一层中节点的最大个数。
4. 由于一条边连接两个结点，且树中不存在环，因此对于有 n 个结点的树，边数一定是 n-1，且满足连通、边数=顶点数 -1 的结构一定是一棵树
5. 叶子结点被定义为度为 0 的结点，因此当树中只有一个结点（即只有根节点）时，根节点也算做叶子结点
6. 结点的深度（depth）是指从根节点（深度为 1）开始自顶而下逐层累加至该结点时的深度值，结点的高度（height）是指从最底层叶子结点（高度为 1）开始自底向上逐层累加至该结点的高度值。树的深度是指树中结点的最大深度，树的高度是指树中结点的最大高度。对树而言深度==高度，但是具体到某个结点就不一定了。
7. 多棵树组合在一起称之为森林（forest）

9.1.2 二叉树的递归定义

直接给出二叉树的递归定义

1. 要么二叉树没有根节点，是一颗空树
2. 要么二叉树由根节点、左子树、右子树组成，且左子树和右子树都是二叉树

递归定义：用自身来定义自身（比如斐波那契数列 F(n)=F(n-1)+F(n-2) 就是一种递归定义，用自身序列的元素来定义这个序列本身）

或者说一个家族里面，爷爷是父亲的父亲，曾爷爷是父亲的父亲的父亲，这样直系血缘关系的男性都可以用父亲这个定义来定义

再分析二叉树的递归定义的递归边界和递归式：

• 递归边界：如果当前结点为空，递归就到达了树的边界
• 递归式：一个结点连接的两个子树都是二叉树

介绍几种特殊的二叉树

1. 满二叉树：每一层的结点个数都达到了当层能达到的最大结点数
2. 完全二叉树：除了最下面一层以外每一层的结点个数都达到了当层能达到的最大结点数，且最下面一层只是从左到右存在若干的连续结点，而这些连续结点右边的结点全部不存在

从二叉树的角度来理解几个树的概念

1. 层次：把二叉树看作家谱，那么层次就是辈分
2. 孩子结点、父亲结点、兄弟节点、祖先节点、子孙节点：一个结点的子树的根节点称之为该节点的孩子结点，而它称之为该孩子结点的父亲结点，与该结点同父亲的结点称之为该结点的兄弟节点（同一层次非同父亲的结点称之为堂兄弟节点）。如果存在一个从结点 X 到结点 Y 从上而下的路径，称 X 是 Y 的祖先结点，Y 是 X 的子孙结点。自己就是自己的祖先节点，也是自己的子孙结点。

9.1.3 二叉树的存储结构与基本操作

1.二叉树的存储结构

使用链表来定义，区别是由于二叉树每个结点有两条出边，指针域也变成了两个。如果子树是空树，那么就指向 NULL，也把这种链表称为二叉链表

struct node{
    typename data; //数据域
    node* lchild; //指向左子树根节点的指针
    node* rchild; //指向右子树根节点的指针
}

由于二叉树建树之前根节点不存在，地址一般设置为 NULL

node *root=NULL;

如果需要新建节点（比如往二叉树里面插入结点的时候）可以使用这个函数

node* newNode(int v){
    node *Node=new node;
    Node->data=v; //结点的数据/权值为 v
    Node->lchild=Node->rchild=NULL; //初始状态下没有左右孩子
    return Node;
}

2.二叉树结点的查找、修改

查找：在给定数据域的条件下，在二叉树中找到所有数据域为给定数据域的结点

修改：在查找的基础上，将它们的数据域修改为给定的数据域

void search(node* root,int x,int newData){
    if(root==NULL) return;
    if(root->data==x) root->data=newData;
    //往左右子树递归查找
    search(root->lchild,x,newData);
    search(root->rchild,x,newData);
}

3.二叉树结点的插入

可以这样考虑：查找失败的位置就是该插入的位置

//insert 函数将在二叉树中插入一个数据域为 x 的新结点
//注意根结点 root 要使用引用
void insert(node* &root,int x){
    if(root==NULL){ //查找失败：插入位置：递归边界
        root=newNode(x);
        return;
    }
    if(由二叉树的性质，x应该插在左子树){
        insert(root->lchild,x);
    }
    else{
        insert(root->rchild,x);
    }
}

为什么 root 一定要引用呢？这是因为在 insert 函数中将新建的结点赋给了 root，如果不使用引用这个语句就无法作用到原变量（即上一层的 root->lchild 和 root->rchild）上去，也就不能把新结点接到二叉树上面去，因此 insert 函数必须加引用

判断是否需要加引用的方法：如果函数中需要新建结点，即对二叉树的结构进行修改，就需要加引用；如果是指修改当前已有结点的内容或只是遍历树，就不需要加引用。

至于有时候可能判断不出来，不妨试一下加引用和不加引用的区别再来进行选择。

新建结点之后务必令新结点的左右指针域为 NULL，表示这个新结点暂时没有左右子树

4.二叉树的创建

二叉树的创建其实就是二叉树结点的插入过程，而插入所需要的结点数据域一般都会由题目给出。一般是把需要插入的数据存在数组中然后再一个一个 insert 进去，最终返回指向根节点的指针 root

//二叉树的建立
node* Create(int data[],int len){
    node* root=NULL;
    for(int i=0;i<len;i++){
        insert(root,data[i]);
    }
    return root;
}

5.二叉树存储结构图示

root==NULL 是结点地址为 NULL，也即结点不存在

而*root==NULL 是错误的，因为这个意思是 root 指向的空间为空，但无法说明地址是否为空

6.完全二叉树的存储结构

对于完全二叉树来说有更方便的存储方法。假设从上到下从左到右从 1 开始编号：

对于完全二叉树中的任何一个结点（设编号为 x）则其左孩子的编号一定是 2x 而右孩子的编号一定是 2x+1

因此可以建立一个大小为$2^k$的数组存放所有结点的信息，其中 k 为完全二叉树的最大高度，其中 1 号位存放的是根节点（不从 0 开始）

且该数组中元素存放的顺序恰好为该完全二叉树的层序遍历序列，而判断某个结点是否为叶结点的标志是：该结点（记下标为 root）的左子节点（为什么是左子节点？因为完全二叉树允许右边全空）的编号 root*2 大于结点总个数；判断某个结点是否为空节点的标志是该结点下标大于结点总个数 n

9.2 二叉树的遍历

指通过一定顺序访问二叉树中的所有节点。

把一颗二叉树分为 3 个部分：根结点、左子树、右子树，然后这样就可以递归遍历。

前三种遍历无论是哪一种，都有左子树一定先于右子树遍历，且所谓的”先中后“都是指根结点 root 在遍历中的位置。

9.2.1 先序遍历

1.先序遍历的实现

先访问根结点 root，再访问左子树和右子树。顺序为根->左->右

考虑递归式：顺序为根->左->右

递归边界：访问到子树为空树即死胡同

void preorder(node *root){
	if(root==NULL) return;
	//访问根结点 root，例如将其数据域输出
	cout<<root->data;
	//访问左子树
	preorder(root->lchild);
	//访问右子树
	preorder(root->lchild);
}

2.先序遍历序列的性质

由于先序遍历先访问根结点，因此对于一棵二叉树的先序遍历序列，序列的第一个一定是根结点。

9.2.2 中序遍历

1.中序遍历的实现

左子树->根节点->右子树

void inorder(node *root){
	if(root==NULL) return;
	//访问左子树
	inorder(root->lchild);
	cout<<root->data; //把根结点的访问放在左右子树之间
	inorder(root->rchild);
}

2.中序遍历序列的性质

只要知道根结点，就可以通过根结点在中序遍历序列中的位置区分出左右子树。

9.2.3 后序遍历

1.后序遍历的实现

左子树->右子树->根节点

void postorder(node* root){
	if(root==NULL) return;
	postorder(root->lchild);
	postorder(root->rchild);
	cout<<root->data;
}

2.后序遍历序列的性质

序列的最后一个一定是根节点。

无论是先序遍历序列还是后序遍历序列，都必须知道中序遍历序列才能唯一地确定一棵树。

因为只有通过中序遍历序列才能利用根结点把左右子树分开从而递归生成一棵二叉树。

当然这个做法必须要保证元素两两不同才能使用。

9.2.4 层序遍历

按照层次的顺序从根结点往下逐层进行遍历，且对同一层的结点从左到右进行遍历。这个比较像 BFS。基本思路如下

1. 将根节点加入队列 q
2. 取出队首结点并访问之
3. 如果该节点有左孩子，将左孩子入队
4. 如果该节点有右孩子，将右孩子入队
5. 返回 2.直到队列为空

void LayerOrder(node *root){
	queue<node*> q; //注意队列里面是存放地址
	q.push(root);
	while(!q.empty()){
		node* top=q.front();
		q.pop();
		//（访问队首元素）
		if(top->lchild!=NULL) q.push(top->lchild);
		if(top->rchild!=NULL) q.push(top->rchild);
	}
}

可以发现这里队列中的元素是 node*而不是 node，这是因为之前提到过 queue 中存放的只是元素的副本，如果想要对原元素进行修改就存放地址也就是 node*型变量。

另外，许多时候题目要求计算出每个结点所在的层次，这个时候需要在二叉树结点的定义中添加一个 layer 变量

代码CPP · 23 行

struct node{
    int data,layer;
    node* lchild;
    node* rchild;
};
void LayerOrder(node *root){
    queue<node*> q;
    root->layer=0; //设置根结点的层号为 0
    q.push(root);
    while(!q.empty()){
        node* top=q.front();
        q.pop();
        //访问队首元素
        if(top->lchild!=NULL){
            top->lchild->layer=top->layer+1;
            q.push(top->lchild);
        }
        if(top->rchild!=NULL){
            top->rchild->layer=top->layer+1;
            q.push(top->rchild);
        }
    }
}

最后解决一个重要的问题，给定一棵二叉树的先序遍历序列和中序遍历序列，重建这棵二叉树。

设已知先序序列为$pre_1、pre_2、\cdots、pre_n$，中序序列为$in_1、in_2、\cdots、in_n$，则$pre_1$是当前二叉树根结点。

又由中序序列可知，当前二叉树的根结点将中序序列划分为左子树和右子树。因此需要在中序序列中找到$in_k=pre_1$这样就在中序序列中找到了根结点。易知左子树结点个数为 numLeft=k-1，于是左子树的先序序列区间就是[2,k]，中序序列区间是[1,k-1]；右子树的先序序列区间是[k+1,n]，中序序列区间是[k+1,n]，于是就只需要往左子树和右子树递归构建二叉树即可。

事实上如果当前递归过程中先序序列的区间为[preL,preR]，中序序列的区间为[inL,inR]，那么左子树的结点个数为 numLeft=k-inL，这样左子树的先序序列区间就是[preL+1,preL+numLeft]，左子树的中序序列区间是[inL,k-1]；右子树的先序序列区间是[preL+numLeft+1,preR]，中序序列区间是[k+1,inR]。

递归边界是当先序序列的长度小于 0 时，当前二叉树不存在。

代码CPP · 19 行

int pre[],in[]; //先序序列和中序序列
//当前先序序列区间为 [preL,preR]，中序序列区间为 [inL,inR]，返回根结点地址]
node* create(int preL,int preR,int inL,int inR){
    if(preL>preR) return NULL;
    node* root=new node;
    root->data=pre[preL];
    int k;
    for(k=inL;k<=inR;k++){ //这里循环变量可以不使用 i
        if(in[k]==root->data) break; //在中序序列中找到根结点
    }
    int numLeft=k-inL;
    //左子树的结点个数为 numLeft=k-inL，左子树的先序序列区间就是 [preL+1,preL+numLeft]，左子树的中序序列区间是 [inL,k-1]；
    //右子树的先序序列区间是 [preL+numLeft+1,preR]，中序序列区间是 [k+1,inR]
    //返回左子树的根结点地址，赋值给 root 的左指针
    root->lchiild=create(preL+1,preL+numLeft,inL,k-1);
    //返回右子树的根结点地址，赋值给 root 的右指针
    root->rchild=create(preL+numLeft+1,preR,k+1,inR);
    return root; //返回根结点地址
}

如果使用静态实现

代码CPP · 22 行

struct node{
    char data;
    int lchild;
    int rchild;
}Node[30];
int idx=0	;
//Node[0] 为根结点

int create(int preL,int preR,int inL,int inR){
    if(preL>preR) return -1;
    int cur=idx++;
    Node[cur].data=pre[preL];
    int k;
    for(k=inL;k<=inR;k++){
        if(in[k]==pre[preL]) break;
    }
    int numLeft=k-inL;
    
    Node[cur].lchild=create(preL+1,preL+numLeft,inL,k-1);
    Node[cur].rchild=create(preL+numLeft+1,preR,k+1,inR);
    return cur;
}

结论：中序序列可以与先序序列、后序序列、层序序列中的任意一个来构建一棵唯一的二叉树，而后面三个两两搭配均不可以。

【PAT A1020】 Tree Traversals

给出一棵二叉树的后序遍历序列和中序遍历序列，求这颗二叉树的层序遍历序列。

考虑先用后序遍历序列和中序遍历序来重建二叉树，再对二叉树进行层序遍历。

代码CPP · 46 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=35;
struct node{
    int data;
    node *lchild,*rchild;
};
int n,in[maxn],post[maxn];
//中序序列的开始和结尾，后序序列的开始和结尾
//返回构建出的二叉树的根结点
node *create(int inL,int inR,int postL,int postR){
    if(postL>postR) return NULL;
    //初始化根结点
    node* root=new node;
    root->data=post[postR];
    //先找到根节点所在的位置
    int k;
    for(k=inL;k<=inR;k++){
        if(in[k]==post[postR]) break;
    }
    int numLeft=k-inL; //左子树的结点个数
    //左子树：中序序列区间为 [inL,k-1] 后序序列区间为 [postL,postL+numLeft-1]
    root->lchild=create(inL,k-1,postL,postL+numLeft-1);
    //右子树：中序序列区间为 [k+1,inR] 后序序列区间为 [postL+numLeft,postR-1]
    root->rchild=create(k+1,inR,postL+numLeft,postR-1);
    return root;
}
//对二叉树进行层序遍历
void layerOrder(node *root){
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node *top=q.front();
        q.pop();
        cout<<top->data<<' ';
        if(top->lchild!=NULL) q.push(top->lchild);
        if(top->rchild!=NULL) q.push(top->rchild);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>post[i];
    for(int i=1;i<=n;i++) cin>>in[i];
    node *root=create(1,n,1,n);
    layerOrder(root);
}

9.2.5 二叉树的静态实现

struct node{
    typename data;
    int lchild;
    int rchild;
}Node[maxn];

int idx=0;
int newNode(int v){
    Node[idx].data=v;
    Node[idx].lchild=-1; // 以 -1 表示空
    Node[idx].rchild=-1;
    return idx++;
}

诸如此类的。反正就是静态化。

需要注意的是与非静态的二叉树的层序遍历相同，静态实现的二叉树的层序遍历在定义队列的时候应该是queue<int> q，其中 int 是下标，而不应该是queue<node> q。

9.3 树的遍历

一般意义上的树，即子结点个数不限且子结点没有先后次序。

9.3.1 树的静态写法

令指针域存放其所有子结点的地址（或者为其单开一个数组存放所有子结点的地址）。

静态写法如下：

struct node{
    typename data; //数据域
    vector<int> child; //指针域，存放所有子结点的下标
}Node[maxn];

与二叉树的静态实现类似，当需要新建一个结点时，就按顺序从数组中取出一个下标即可。

int idx=0;
int newNode(int v){
    Node[idx].data=v;
    Node[idx].child.clear(); //清空子结点
    return idx++; //返回结点下标并令 idx 自增
}

不过一般题目里涉及非二叉树的树的考察的时候都会给出结点的编号，且一般都是 0-n-1，所以不需要 newNode 函数。

9.3.2 树的先根遍历

即先访问根结点，再去访问所有子树。

void preOrder(int root){
    //访问当前结点，比如输出
    for(const auto&x:Node[root].child){
	preOrder(x); //递归访问结点 root 的所有子结点
    }
}

在树的先根遍历代码中，虽然没有显式地写出递归边界，但实际上递归边界是存在的。递归边界是由树的结构决定的，具体来说，当遍历到一个叶子节点时，该节点没有子节点，因此不会进入 for 循环，递归调用自然终止。

9.3.3 树的层序遍历

代码CPP · 21 行

struct node{
    int layer;
    int data;
    vector<int> child;
}Node[maxn];
void layerOrder(int root){
    queue<int> q; //记得 queue 里面存放的是指针/下标
    Node[root].layer=0;
    q.push(root);
    while(!q.empty()){
        int top=q.front();
        q.pop();
        cout<<Node[top].data;
        for(const auto&x:Node[top].child){
            if(x!=-1){
                Node[x].layer=Node[top].layer+1;
                q.push(x);
            }
        }
    }
}

9.3.4 从树的遍历看 DFS 和 BFS

1.DFS 与先根遍历

对于所有合法的 DFS 求解过程，都可以把它画成树的形式，此时死胡同等价于树中的叶子结点，而岔道口等价于树中的非叶子结点，而且对这棵树的 DFS 遍历过程就是树的先根遍历的过程。

2.BFS 与层序遍历

对所有合法的 BFS 求解过程，也可以画成树的形式。

【PAT A1053] Path of Equal Weight

给定一棵树和每个结点的权值，求所有从根结点到叶子结点的路径，使得每条路径上的结点的权值之和等于给定的常数 S。如果有多条这样的路径则按路径非递增的顺序输出。其中路径的大小指的是类似于字典序的排序 (a1->a2->....an)

代码CPP · 51 行

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=105;
int n,m,S; //树的结点数，非叶子结点个数（边数），给定权
int id,k,child;
//记录路径 (记录的是结点的编号)，有更高权值的路径应优先输出，而读入时已经对权值排好了序，因此 dfs 的时候总是会优先访问权值更大的进行输出
vector<int> path;
struct node{
    int data;
    int layer;
    vector<int> child;
}Node[maxn];
bool cmp(int a,int b){
    return Node[a].data>Node[b].data;
}
void dfs(int idx,int sum){ //idx 是目前访问的结点编号，sum 是目前的权值和
    if(sum>S) return; //剪枝
    if(sum==S){
        if(Node[idx].child.empty()){ //如果这个时候是叶子结点才输出，否则直接 return
            for(const auto&x:path) printf("%d ",Node[x].data);
            printf("\n");
        }
        return;
    }
    for(const auto&x:Node[idx].child){//枚举所有孩子结点
        //选择这个孩子结点
        path.push_back(x); //将结点 child 加到路径 path 末尾 
        dfs(x,sum+Node[x].data); //递归进入下一层
        //不选择这个孩子结点，回溯
        path.pop_back();
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&S);
    for(int i=0;i<n;i++){
        scanf("%d",&Node[i].data);
    }
    for(int i=0;i<m;i++){
        scanf("%d%d",&id,&k);
        for(int i=0;i<k;i++){
            scanf("%d",&child);
            Node[id].child.push_back(child); 
        }
        //输出的时候按照路径的权值输出，先把孩子的权值排好序
        sort(Node[id].child.begin(),Node[id].child.end(),cmp);
    }
    path.push_back(0); //插入根结点
    dfs(0,Node[0].data);
}

9.4 二叉查找树（BST）

9.4.1 二叉查找树的定义

• 要么是空树
• 若左子树不空，则左子树上所有结点的值均小于等于它的根结点的值
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 左、右子树也分别为二叉排序树

其实有两种定义方式，还有一种是

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 没有权值相等的结点

这种情况下在结点里面加一个 cnt 变量记录这个权值的出现次数。

9.4.2 二叉查找树的基本操作

1.查找

代码CPP · 19 行

struct node{
    int v;
    int lchild,rchild;
    int siz; //(两子树 + 自己本身) 的大小（结点数之和）
}bst[maxn];

int search(int v,int idx){
    if(idx==0) return 0; //查找失败
    
    if(v==bst[idx].v){
        return idx;
    }
    else if(v<bst[idx].v){
        search(v,bst[idx].lchild);
    }
    else{
        search(v,bst[idx].rchild);
    }
}

注：统一采用静态实现

2.插入

代码CPP · 25 行

void insert(int v,int idx){ //v 表示权值，idx 表示当前的结点编号
    bst[idx].siz++;
    if(v>bst[idx].v){ //说明 v 应该插入到右子树
        if(bst[idx].rchild!=0){
            insert(v,bst[idx].rchild);
        }
        else{ //不存在右孩子
            cnt++;
            bst[cnt].v=v;
            bst[cnt].siz=1;
            bst[idx].rchild=cnt;
        }
    }
    else{
        if(bst[idx].lchild!=0){
            insert(v,bst[idx].lchild);
        }
        else{
            cnt++;
            bst[cnt].v=v;
            bst[cnt].siz=1;
            bst[idx].lchild=cnt;
        }
    }
}

3.删除

删除二叉搜索树（BST）中的节点有三种情况：

1. 目标节点是叶子节点：直接删除即可。
2. 目标节点只有一个子节点：用它的唯一子节点代替它。
3. 目标节点有两个子节点：找到它的前驱（左子树的最大值）或后继（右子树的最小值）替换它，然后递归删除这个前驱或后继节点。

先给出找前驱和后继的函数

代码CPP · 29 行

int findPre(int v){
    int idx=1; //从根结点开始搜索
    int ans=-inf;
    while(idx){
        if(bst[idx].v<v){
            ans=bst[idx].v;
            idx=bst[idx].rchild;
        }
        else{
            idx=bst[idx].lchild;
        }
    }
    return ans;
}

int findPost(int v){
    int idx=1;
    int ans=inf;
    while(idx){
        if(bst[idx].v>v){
            ans=bst[idx].v;
            idx=bst[idx].lchild;
        }
        else{
            idx=bst[idx].rchild;
        }
    }
    return ans;
}

再给出删除的函数

代码CPP · 35 行

void remove(int &idx, int v) {
    if (idx == 0) return; // 树为空，直接返回

    if (v < bst[idx].v) {
        // 目标值在左子树
        remove(bst[idx].lchild, v);
    } else if (v > bst[idx].v) {
        // 目标值在右子树
        remove(bst[idx].rchild, v);
    } else {
        // 找到目标节点
        if (bst[idx].lchild == 0 && bst[idx].rchild == 0) {
            // 情况 1：叶子节点，直接删除
            idx = 0;
        } else if (bst[idx].lchild == 0) {
            // 情况 2：只有右子树
            idx = bst[idx].rchild;
        } else if (bst[idx].rchild == 0) {
            // 情况 2：只有左子树
            idx = bst[idx].lchild;
        } else {
            // 情况 3：有两个子节点
            int preIdx = bst[idx].lchild;
            while (bst[preIdx].rchild) { // 找前驱
                preIdx = bst[preIdx].rchild;
            }
            bst[idx].v = bst[preIdx].v; // 用前驱值替换
            remove(bst[idx].lchild, bst[preIdx].v); // 递归删除前驱
        }
    }

    if (idx != 0) { // 维护子树大小信息
        bst[idx].siz = 1 + bst[bst[idx].lchild].siz + bst[bst[idx].rchild].siz;
    }
}

9.4.3 二叉查找树的性质

9.5 平衡二叉树（AVL 树）

9.5.1 平衡二叉树的定义

9.5.2 平衡二叉树的基本操作

9.6 并查集

9.6.1 并查集的定义

并查集是一种维护集合的数据结构。

“并”“查”“集”分别取自合并、查找、集合。

并查集支持以下两个操作

1. 合并：合并两个集合
2. 查找：判断两个元素是否在一个集合

实现方式：

int father[N];

其中father[i]表示元素i的父亲结点，而父亲结点本身也是这个集合内的元素。比如father[1]=2表示元素 1 的父亲结点是元素 2，以这种父系关系来表示元素所属的集合。另外如果father[i]==i则说明元素 i 是该集合的根结点，但对于同一个集合来说只存在一个根结点，且将其作为所属集合的标识。

9.6.2 并查集的基本操作

1.初始化

一开始每个元素都是独立的一个集合，只需要全令father[i]=i或令father[i]=-1

2.查找

由于规定了同一个集合只存在一个根结点，因此查找操作就是对给定的结点去寻找其根结点的过程，实现的方式可以是递推或者递推。思路都是反复寻找父亲结点直到寻找到根结点。

int findFather(int x){
    while(x!=father[x]){
        x=father[x];
    }
    return x;
}

int findFather(int x){
    if(x==father[x]) return x;
    else return findFather(father[x]);
}

3.合并

合并指的是把两个集合并成一个集合。题目中一般给出两个元素然后要求把这两个元素所在的集合合并。具体实现是先判断两个元素是否属于一个集合，只有当两个元素属于不同集合的时候才合并，而合并的过程一般是把其中一个集合的根结点的父亲指向另一个集合的根结点。思路如下：

1. 对于给定的两个元素 a b，先判断他们是否属于同一个集合，调用查找函数判断根结点是否相同即可。
2. 合并两个集合：在 1 中已经获得了两个元素的根结点 faA 和 faB，因此只需要把其中一个的父亲结点指向另一个结点。比如令father[faA]=faB或者反过来都可以。

void Union(int a,int b){
    int faA=findFather(a);
    int faB=findFather(b);
    if(faA!=faB){
        father[faA]=faB;
    }
}

9.6.3 路径压缩

上面提到的函数都没有进行优化。下面考虑一种极端情况，即题目给出的元素数量很多而且形成一条链，那么这个查找函数的效率就会很低。下面提出一种优化思路。

因为我们findFather()函数就只是为了寻找根结点，我们完全可以把当前查询结点的路径上的所有结点的父亲都指向根结点，查找的时候就不需要一直回溯去寻找父亲，时间复杂度降为$O(1)$。

进行转换的步骤可以这样概括：

1. 按照原来的写法获得 x 的根结点 r
2. 重新从 x 开始走一遍寻找根结点的过程，把路径上经过的所有结点的父亲全部改为根结点 r。

int findFather(int x){
    int a=x; //由于 x 在下面的 while 循环会变成根结点，先存一下原来的 x
    while(x!=father[x]){
        x=father[x];
    }
    //到这里 x 存放的是根结点，下面把路径上所有结点的 father 都改成根结点。
    while(a!=father[a]){
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}

也有递归写法

int findFather(int x){
    return x==father[x] ? x : father[x]=findFather(father[x]);
}

下面给出一个简单使用并查集的题目

例题 好朋友

引用题目描述 有一个叫作“数码世界”的奇异空间，在数码世界里生活着许许多多的数码宝贝，其中有些数码宝贝之间可能是好朋友。并且数码世界有两条不成文的规...

题目描述

有一个叫作“数码世界”的奇异空间，在数码世界里生活着许许多多的数码宝贝，其中有些数码宝贝之间可能是好朋友。并且数码世界有两条不成文的规定:

第一，数码宝贝 A 和数码宝贝 B 是好朋友等价于数码宝贝 B 和数码宝贝 A 是好朋友。

第二，如果数码宝贝 A 和数码宝贝 C 是好朋友，而数码宝贝 B 和数码宝贝 C 也是好朋友，那么 A 和 B 也是好朋友。现在给出这些数码宝贝中所有好朋友的信息，问：可以把这些数码宝贝分成多少组，满足每组中的任意两只数码宝贝都是好朋友，且任意两组之间的数码宝贝都不是好朋友。

输入格式

输入的第一行有两个正整数 n(n<=100) 和 m(m<=100)，分别表示数码宝贝的个数和好朋友的组数，其中数码宝贝编号为 1~n。接下来有 m 行，每行两个正整数 a 和 b，表示数码宝贝 a 和数码宝贝 b 是好朋友。

样例输入

4 2
1 4
2 3

样例输出

2

本题是一个并查集模型，可以把题目中的“组”视为集合，而题目中给出的好朋友关系视为两个结点之间的边，那么在输入这些好朋友关系时就可以同时对它们进行并查集的合并操作。

对于集合个数的求解，需要用到这条规则：对于同一个集合来说只存在一个根结点，且将其作为所属集合的标识。因此开一个bool flag[n]来记录每个结点是否作为某个集合的根结点，这样在处理完输入数据之后就可以遍历所有元素，令它所在的集合的根结点的flag设置为true，最后累加flag中的元素即可。代码如下

代码CPP · 49 行

#include<bits/stdc++.h>
using namespace std;

const int maxn=110;
int father[maxn];
bool flag[maxn];

int findFather(int x){
    int a=x;
    while(x!=father[x]){
        x=father[x];
    }
    while(a!=father[a]){
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}
void Union(int a,int b){
    int faA=father[a];
    int faB=father[b];
    if(faA!=faB){
        father[faA]=faB;
    }
    return;
}

int main(){
    int n,m,a,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        father[i]=i;
        //flag[i]=false; 全局变量默认是 false
    }
    for(int i=0;i<m;i++){
        cin>>a>>b;
        Union(a,b);
    }
    for(int i=1;i<=n;i++){
        flag[findFather(i)]=true;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=(int)flag[i];
    }
    cout<<ans;
    return 0;
}

9.7 堆

9.7.1 堆的定义与基本操作

9.7.2 堆排序

9.8 哈夫曼树

9.8.1 哈夫曼树

9.8.2 哈夫曼编码

第 10 章 提高篇（4）——图算法专题

10.1 图的定义和相关术语

图由顶点和边组成。分为有向图和无向图。

顶点的度：与该顶点相连的边的条数。

对于有向图：顶点的出边条数称为出度，入边条数称为入度。

顶点和边的权值分别称为点权和边权。

10.2 图的存储

10.2.1 邻接矩阵

设图 G(V,E) 的顶点编号从 0 到 n-1，则可以令二维数组 G[n][n]的两维分别表示图的顶点标号。

若 G[i][j]==1 -> 顶点 i 和 j 之间有边，若为 0 则没有。另外如果存在边权则令 G[i][j]存放边权，而对于不存在的边就设边权为 0,-1，或 inf。

对于无向图来说，邻接矩阵是一个对称矩阵。

为了防止 MLE，邻接矩阵只适用于顶点数目不太大 (<=1000) 的题目。

10.2.2 邻接表

设图 G(V,E) 的顶点编号从 0 到 n-1，每个顶点都可能会有若干条出边，如果把同一个顶点的所有出边放到一个列表中，那么 n 个顶点就会有 n 个列表（没有出边则对应空表）。这 n 个列表被称为图 G 的邻接表，记作 Adj[n]，其中 Adj[i]存放顶点 i 的所有出边组成的列表。

这里我们使用 vector 来实现邻接表。

struct Node{
  int v; //边的终点编号
  int w; //边权
  Node(int _v,int _w):v(_v),w(_w){};
}
vector<Node> Adj[n];

然后如果我们这里想要添加从 1 号到达 3 号顶点的有向边，边权为 4，就可以这样：

Adj[1].emplace_back(3,4);

如果想要添加一条无向边，可以这样设计一个函数

// 添加无向边 (u, v, w)
void addEdge(int u, int v, int w) {
    Adj[u].emplace_back(v, w);  // 在 u 的邻接表中添加边 (u, v, w)
    Adj[v].emplace_back(u, w);  // 在 v 的邻接表中添加边 (v, u, w)
}

这样，当添加无向边时，不仅将 (v, w) 添加到 Adj[u] 中，也会将 (u, w) 添加到 Adj[v] 中，保证图的双向性质。

10.3 图的遍历

10.3.1 采用深度优先搜索（DFS）法遍历图

首先介绍两个概念：

1. 连通分量：在无向图中，如果两个顶点之间可以相互到达（可以是通过一定路径间接到达），那么就称这两个顶点连通。如果图 G(V,E) 的任意两个顶点均连通，则称图 G 为连通图，否则为非连通图，且称其中的极大连通子图为连通分量。
2. 强连通分量：在有向图中，如果两个顶点可以各自通过一条有向路径到达另一个顶点，就称这两个顶点强连通。如果图 G(V,E) 的任意两个顶点都强连通，则称图 G 为强连通图；否则称为非强连通图，且称其中的极大强连通子图为强连通分量。

为了叙述上的方便下面把连通分量和强连通分量统称为连通块。

所以要遍历整个图就是要对所有连通块进行遍历。DFS 遍历图的基本思路就是把以及访问过的顶点设置为已访问，在下次递归碰到这个顶点时就不再处理，直到整个图的顶点都被标记为已访问。

下面是一份 DFS 的伪代码

DFS(u){ //访问顶点 u
vis[u]=true;
    for(从u出发能到达的所有顶点v){
        if(!vis[v]) DFS(v);
    }
    DFSTraveG{ //遍历图 G
        for(G的所有顶点u){
            if(!vis[u]) DFS(u); //访问 u 所在的连通块
    }
}

在这份代码的基础上可以代入邻接矩阵和邻接表的代码，得到如下模板：

代码CPP · 25 行

//邻接矩阵版本
cosnt int maxv=1000; //最大顶点数
const int inf=0x3f3f3f3f;

int n,G[maxv][maxv];
bool vis[maxv]={false};

void dfs(int u,int depth){
    vis[u]=true;
    //如果需要对 u 进行一些操作可以在这里进行
    //下面对所有从 u 出发能到达的分支顶点进行枚举
    for(int v=0;v<n;v++){
        if(!vis[v]&&G[u][v]!=inf){
            dfs(v,depth+1); //访问 v，深度++
        }
    }
}

void DFSTrave(){ //遍历图 G
    for(int u=0;u<n;u++){
        if(!vis[u]){
            dfs(u+1);
        }
    }
}

代码CPP · 22 行

//邻接表版本
cosnt int maxv=1000; //最大顶点数
const int inf=0x3f3f3f3f;

vector<int> Adj[maxv];
int n; //顶点数
bool vis[maxv]={false};

void dfs(int u,int depth){
    vis[u]=true;
    //如果要对 u 进行一些操作可以在这里
    for(int i=0;i<(int)Adj[u].size();i++){
        int v=Adj[u][i];
        if(!vis[v]) dfs(v,depth+1);
    }
}

void DFSTrave(){
    for(int u=0;u<n;u++){
        if(!vis[u]) dfs(u,1);
    }
}

【PAT A1034】 Head of a gang

代码CPP · 69 行

#include<bits/stdc++.h>
using namespace std;

const int maxn=2010;
const int inf=0x3f3f3f3f;
int G[maxn][maxn];
int weight[maxn];
bool vis[maxn];
map<string,int> stringToInt;
map<int,string> intToString;
map<string,int> Gang;
int n,k;
int numPerson;

int change(string s){
    if(stringToInt.find(s)!=stringToInt.end()){
        return stringToInt[s];
    }
    else{
        stringToInt[s]=numPerson;
        intToString[numPerson]=s;
        return numPerson++;
    }
}

void dfs(int now,int &head,int &numMember,int &totalValue){
    vis[now]=true;
    numMember++;
    if(weight[now]>weight[head]) head=now;
    for(int v=0;v<numPerson;v++){
        if(!vis[v]&&G[now][v]!=0){
            totalValue+=G[now][v];
            dfs(v,head,numMember,totalValue);
        }
    }
}

void dfstrave(){
    for(int i=0;i<numPerson;i++){
        if(!vis[i]){
            int head=i,numMember=0,totalValue=0;
            dfs(i,head,numMember,totalValue);
            if(numMember>2&&totalValue>k){
                Gang[intToString[head]]=numMember;
            }
        }
    }
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        string s1,s2;
        int w;
        cin>>s1>>s2>>w;
        int id1=change(s1);
        int id2=change(s2);
        weight[id1]+=w;
        weight[id2]+=w;
        G[id1][id2]+=w;
        G[id2][id1]+=w;
    }
    dfstrave();
    cout<<Gang.size()<<"\n";
    for(auto &[x,y]:Gang){
        cout<<x<<" "<<y<<"\n";
    }
    return 0;
}

10.3.2 采用广度优先搜索（BFS）法遍历图

代码CPP · 28 行

//邻接矩阵版本
int n;
int G[maxv][maxv];
bool inq[maxv];

void bfs(int u){ //遍历顶点 u 所在的连通块
    queue<int> q;
    q.push(u);
    inq[u]=true;
    while(!q.empty()){
        int top=q.front();
        q.pop();
        for(int v=0;v<n;v++){
            if(!inq[v]&&G[top][v]!=0){
                q.push(v);
                inq[v]=true;
            }
        }
    }
}

void bfsTrave(){
    for(int i=0;i<n;i++){
        if(!inq[i]){
            bfs(i);
        }
    }
}

代码CPP · 28 行

//邻接表版本
vector<int> Adj[maxv];
int n;
bool inq[maxv];

void bfs(int u){
    queue<int> q;
    q.push(u);
    inq[u]=true;
    while(!q.empty()){
        int top=q.front();
        q.pop();
        for(int v:Adj[top]){
            if(!inq[v]){
                q.push(v);
                inq[v]=true;
            }
        }
    }
}

void bfsTrave(){
    for(int i=0;i<n;i++){
        if(!inq[i]){
            bfs(i);
        }
    }
}

如果需要记录每个结点的层次，可以使用结构体

代码CPP · 26 行

//邻接表版本
struct node{
    int v;
    int layer;
}Node;
vector<node> Adj[maxv];
int n;
bool inq[maxv];

void bfs(int s){ //s 为起始顶点编号
    queue<node> q;
    Node.v=s;Node.layer=0;
    q.push(Node);
    inq[Node.v]=true;
    while(!q.empty()){
        node top=q.front();
        q.pop();
        for(node next:Adj[top.v]){
            next.layer=top.layer+1;
            if(!inq[next.v]){
                q.push(next);
                inq[next.v]=true;
            }
        }
    }
}

10.4 最短路径

这是一个很经典的问题：给定图 G(V,E)，求一条从起点到终点的路径，使得这条路径上经过的所有边的边权之和最小。

10.4.1 Dijkstra 算法

10.4.2 Bellman-Ford 算法和 SPFA 算法

10.4.3 Floyd 算法

10.5 最小生成树

10.5.1 最小生成树及其性质

10.5.2 prim 算法

10.5.3 kruskal 算法

10.6 拓扑排序

代码CPP · 44 行

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int n,m;
    cin>>n>>m;
    vector<vector<int>> g(n+1);
    vector<int> ind(n+1,0);
    vector<int> outd(n+1,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        ind[b]++;
        outd[a]++;
    }

    queue<int> q;
    for(int i=1;i<=n;i++){
        if(ind[i]==0){
            q.push(i);
        }
    }
	int num=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:g[u]){
            ind[v]--;
            if(ind[v]==0){
                q.push(v);
            }
        }
        num++;
    }
	//num==m 则为 DAG，反之
    return 0;
}

10.6.1 有向无环图

10.6.2 拓扑排序

10.7 关键路径

10.7.1 AOV 网和 AOE 网

10.7.2 最长路径

10.7.3 关键路径

第 11 章 提高篇（5）——动态规划专题

11.1 动态规划的递归写法和递推写法

11.1.1 什么是动态规划

是用来解决一类最优化问题的算法思想。简单来说，动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。动态规划会将每个求解过的子问题的解记录下来。

一般可以使用递推或递归的写法来实现动态规划，其中递归写法又称记忆化搜索

11.1.2 动态规划的递归写法

使用记忆化搜索来计算斐波那契数列

int dp[maxn];
int F(int n){
    if(n<=1) return 1;
    if(dp[n]) return dp[n]; //已经计算过，直接返回结果
    else{
        dp[n]=F(n-1)+F(n-2);
        return dp[n];
    }
}

引出概念：如果一个问题可以被分解成若干子问题，而且这些子问题会重复出现，那么就称这个问题拥有重叠子问题

因此一个问题必须有重叠子问题才能用动态规划去解决

11.1.3 动态规划的递推写法

数塔问题

把一些数字排成数塔的形状，第 i 层有 i 个数字，现在要从第一层走到第 n 层，每次只能走向下一层连接的两个数字中的一个，问：最后将路径上所有数字相加后得到的和最大为多少？

按照题目的描述，使用一个二维数组 f 去存储存放在第 i 层的第 j 个数字，如果尝试去穷举所有路径，那么时间复杂度是$O(2^n)$,无法接受，这是因为会重复访问，解决方法是记录下来一个数字到底层所有路径可以产生的最大值，之后访问这个数的时候直接调用即可。不妨令 dp[i][j]表示从第 i 行第 j 个数字出发到达底层的所有路径中能得到的最大和，在定义这个数组之后，dp[1][1]就是最终想要的答案，现在我们来求它。

注意到一个细节，如果要求 dp[1][1]，就一定要先求出它的两个子问题 dp[2][1]和 dp[2][2]，即进行了一次决策，是走 f[2][1]还是 f[2][2]，于是 dp[1][1]可以写成这个式子 $$ \mathrm{dp}[1][1]=max(\mathrm{dp[2][1],dp[2][2]})+\mathrm{f[1][1]} $$ 由此可以归纳得到这么一个信息：如果要求出 d[i][j]，就一定要求出它的两个子问题 d[i+1][j]和 d[i+1][j+1]，即进行了一次决策，于是就有 $$ \mathrm{dp}[i][j]=max(\mathrm{dp[i+1][j],dp[i+1][j+1]})+\mathrm{f[i][j]} $$ 把 d[i][j]称之为问题的状态，上面的式子称之为状态转移方程，把各状态转移为 d[i+1][j]和 d[i+1][j+1]。可以注意到状态 d[i][j]只和第 i+1 层的状态有关，而与其他层的状态无关，这样层号为 i 的状态总是可以由层号为 i+1 的两个子状态得到。又注意到递归边界应该是数塔的最后一层的 dp 值总是等于元素本身，即 dp[n][j]==f[n][j]，把这种可以直接确定结果的部分称之为边界，而动态规划的递推写法总是从这种边界出发，又通过状态转移方程扩散到整个 dp 数组。

这样就可以从底层各位置的 dp 值开始不断向上求，最后就可以得到 dp[1][1]，即最后需要的答案。代码实现如下

代码CPP · 33 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int n,f[maxn][maxn],dp[maxn][maxn];

//状态转移方程的递归实现，调用时从初始状态调用
int P(int i,int j){
    if(dp[i][j]) return dp[i][j]; //记忆化存储
    if(i==n) return dp[i][j]=f[i][j];
    return dp[i][j]=max(P(i+1,j),P(i+1,j+1))+f[i][j];
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>f[i][j];
        }
    }
    //边界条件
    for(int i=1;i<=n;i++){
        dp[n][i]=f[n][i];
    }
    //从 n-1 层往上不断计算 dp[i][j]
    for(int i=n-1;i>=1;i--){
        for(int j=1;j<=i;j++){
            //状态转移方程
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
        }
    }
    cout<<dp[1][1]<<endl;
    return 0;
}

用递归也可以实现类似的效果

使用递归写法的计算方式是自底而上，即从边界开始不断向上解决问题，直到解决目标问题

而使用递归写法是自顶向下，从目标问题开始将它分解成子问题的组合，直至分解至边界

从上面的问题再引申出一个概念：如果一个问题的最优解可以由其子问题的最优解构造而来，那么称这个问题具有最优子结构。最优子结构保证了动态规划问题中原问题的最优解可以由子问题的最优解推导而来，因此一个问题必须拥有最优子结构才能用动态规划去解决。

需要指出，一个问题必须拥有重叠子问题和最优子结构才能使用动态规划去解决，指出两个概念的区别

1. 分治与动态规划。分治分解出的子问题是不重叠的，而动态规划解决的问题拥有重叠子问题。分治法解决的不一定是最优化问题，而动态规划解决的一定是最优化问题。
2. 贪心与动态规划。都要求原问题有最优子结构。贪心类似于自顶而下，但是并不是等待子问题求解完毕之后再去选择使用哪一个，而是选择一个策略去直接解决一个子问题。而动态规划总是从边界开始得到。

11.2 最大连续子序列和

给定一个数字序列$A_1,A_2, \cdots A_n$，求 i,j (1≤i≤j≤n)，使得$A_i+\cdots A_j$最大，输出这个最大和。

样例

-2 11 -4 13 -5 -2

如果暴力来做枚举 i 和 j 要$\mathrm{O(n^2)}$的复杂度，而计算 a[i]+...+a[j]需要 O(n) 的复杂度，因此总共复杂度为$\mathrm{O(n^3)}$。如果采用前缀和的方法令 s[i]=a[0]+a[1]+...+a[i]，这样 a[i]+...+a[j]=s[j]-s[i-1]使得计算时间为 O(1)，总复杂度还是$\mathrm{O(n^2)}$，无法接受。

下面介绍动态规划的做法，复杂度为 O(n)。

1. 令 dp[i]表示以 a[i]作为末尾的连续序列的最大和（这里说 a[i]必须要作为连续序列的末尾）。

   通过设置这么一个 dp 数组，那么我们无非就是要求从 dp[0]到 dp[n-1]中的最大值（因为以哪个元素作为结尾是未知的）。接下来想办法求解 dp 数组

2. 做如下考虑：因为 dp[i]必须是以 a[i]结尾的连续序列，那么只有两种情况

   1. 这个最大和的连续序列只有一个元素即以 a[i]开始又以 a[i]结束
   2. 这个最大和的连续序列有多个元素，即从某处 p 开始 (p<i)，一直到 a[i]结尾。

   第一种情况最大和就是 a[i]本身。

   第二种情况最大和是 dp[i-1]+a[i]，即 a[p]+...+a[i-1]+a[i]=dp[i-1]=a[i] (强行把 i 和 i-1 的情况拆开，得到状态方程的思路)

   由于只有这两种情况，得到状态转移方程 $$ \mathrm{dp[i]}=max (\mathrm{a[i],dp[i-1]+a[i]}) $$ 这个式子只和 i 与 i 之前的元素有关，且边界为 dp[0]=a[0]，于是枚举 i 即可解决问题。

无后效性

状态的无后效性指的是：当前状态记录了历史信息，一旦当前状态确定，就不会再改变，且未来的决策只能在已有的一个或若干个状态的基础上进行，历史信息只能通过已有的状态去影响未来的决策。

对于动态规划可解的问题来说，总会有很多设计状态的方式，但并不是所有状态都具有无后效性，因此必须要设计一个无后效性的状态以及相应的状态转移方程。

设计状态和状态转移方程是动态规划的核心。

11.3 最长不下降子序列（LIS）

在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个序列是不下降的。

暴力法：每个元素有取和不取两种情况，对之进行判断，直到枚举完成，时间复杂度$\mathrm{O(2^n)}$。下面介绍动态规划法。

令 dp[i]表示以 a[i]结尾的最长不下降子序列长度（与最大连续子序列和问题一样，以 a[i]结尾是强制的要求），这样对于 a[i]就有两种可能：

1. 如果存在 a[i]之前的元素 a[j] (j<i) 使得 a[j]≤a[i]且 dp[j]+1>dp[i]（即把 a[i]跟在以 a[j]结尾的 LIS 后面时能比当前以 a[i]结尾的 LIS 长度更长），那么就把 a[i]跟在以 a[j]结尾的 LIS 后面，形成一条更长的不下降子列（令 dp[i]=dp[j]+1）
2. 如果 a[i]之前的元素都比 a[i]大，那么 a[i]就只能自己形成一条长度为 1 的 LIS

最后以 a[i]结尾的 LIS 长度就是 1,2 中能形成的最大长度。

由此写出状态转移方程 $$ \mathrm{dp[i]}=max(\mathrm{1,dp[j]+1}) \ (j=1,2,\cdots.i-1&&a[j]<a[i]) \ 边界 dp[i]=1（先假设每个元素自成一个子序列） $$ 一个代码实现的案例

int ans=-1; //记录最大的 dp[i]
for(int i=1;i<=n;i++){
    dp[i]=1; //先假设每个元素自成一个子序列
    for(int j=1;j<i;j++){
        if(a[i]>=a[j]&&(dp[j]+1>dp[i])){
		dp[i]=dp[j]+1; //状态转移方程用以更新 dp[i]
            //也可以是 dp[i]=max(dp[i],dp[j]+1); 上面那个判断去掉
        }
    }
    ans=max(ans,dp[i]);
}

11.4 最长公共子序列（LCS）

给定两个字符串（或数字序列）a 和 b，求一个字符串，使得这个字符串是 A 和 B 的最长公共部分的长度（子序列可以不连续）

样例：

"sadstory"和"adminsorry"的最长公共子序列是"adsory"，长度为 6。

令 dp[i][j]表示字符串 a 的 i 号位和字符串 b 的 j 号位之前的 LCS 长度（下标从 1 开始），如 dp[4][5]表示"sads"和"admin"的 LCS 长度。那么可以根据 a[i]和 b[j]的情况分为两种决策。

1. 若 a[i]==b[j]，则字符串 a 和字符串 b 的 LCS 增加了一位，即有 dp[i][j]=dp[i-1][j-1]+1
2. 如果 a[i]!=b[j]，那么字符串 a 的 i 号位和字符串 b 的 j 号位之前的 LCS 无法延长，因此 dp[i][j]将会继承 dp[i-1][j]与 dp[i][j-1]中的较大值，即有 dp[i][j]=max{dp[i-1][j],dp[i][j-1]} （因为不相同，所以从这一位开始往前倒一位是不影响长度的，但是从哪一个维度倒一位就要分类，也就是取一个 max）

由此得到状态转移方程 $$ \mathrm{dp[i][j]}= \begin{cases} \mathrm{dp[i-1][j-1]+1,a[i]==b[j]} \ max(\mathrm{dp[i-1][j],dp[i][j-1]}), \mathrm{a[i]!=b[j]} \end{cases} \ 边界：\mathrm{dp[i][0]=dp[j][0]=0} \ \mathrm{i 和 j 从 1 遍历到各自字符串的长度} $$

11.5 最长回文子串

给出一个字符串 s，求 s 的最长回文子串的长度。

例：

"PATZJUJZTACCBCC"的最长回文子串为"ATZJUJZTA"，长度为 9

动态规划法，时间复杂度$\mathrm{O(n^2)}$

令bool dp[i][j]表示 s[i]至 s[j]所表示的子串是回文子串，这样根据 s[i]是否等于 s[j]可以把答案分成两类：

1. 若 s[i]==s[j]，则只要 s[i+1]至 s[j-1]是回文子串，s[i]至 s[j]就是回文子串；反之。
2. 如果 s[i]!=s[j]，那么 s[i]至 s[j]就一定不是回文子串。

由此可以写出状态转移方程 $$ \mathrm{dp[i][j]=} \begin{cases} \mathrm{dp[i+1][j-1] ,s[i]==s[j]} \ \mathrm{false, s[i]!=s[j]} \end{cases} \ \mathrm{边界 dp[i][i]=1， dp[i][i+1]=(s[i]==s[i+1]?true:false)} $$ 但是直接双重循环会无法保证计算过 dp[i+1][j-1]，从而无法计算出 dp[i+1][j-1]，解决方法如下：

根据递归写法从边界出发的原理：考虑按子串的长度和子串的初始位置进行枚举，即先枚举子串长度 L，再枚举左端点 i，这样右端点 i+L-1 也可以直接得到。

11.6 DAG 最长路

11.7 背包问题

11.7.1 多阶段动态规划问题

这一类问题的特征是：可以描述成若干个有序的阶段，且每个阶段的状态只和上一个阶段的状态有关。只需从第一个问题开始按照阶段的顺序解决每个阶段中状态的计算，就可以得到最后一个阶段中状态的解。

11.7.2 01 背包问题

有 n 件物品，每件物品的重量为 w[i]，价值为 c[i]。现有一个容量为 V 的背包，问如何选取物品放入背包使得背包内物品的总价值最大。每件物品都只有一件。

dfs 的方法时间复杂度为$O(2^n)$，显然不行，使用动态规划则为$O(nV)$

令 dp[i][v]表示前 i 件物品 (1≤i≤n,0≤v≤V)恰好（“恰好”指的是恰好把容量 v 填满）装入容量为 v 的背包所能获得的最大价值

考虑第 i 件物品的选择策略，有如下两种：

1. 不放第 i 件物品，那么问题转化为 dp[i-1][v]
2. 放第 i 件物品，那么问题转化为前 i-1 件物品恰好装入容量为 v-w[i]的背包所能获得的最大价值，也即 dp[i-1][v-w[i]]+c[i]

则有 $$ \mathrm{dp[i][v]}=max{\mathrm{dp[i-1][v],dp[i-1][v-w[i]]+c[i]}} \ 1≤i≤n,w[i]≤v≤V $$ 上面就是状态转移方程。又注意到 dp[i][v]只与之前的状态 dp[i-1][]有关，所以可以枚举 i 从 1 到 n，v 从 0 到 V，通过边界 dp[0][v]=0*(0 件物品价值当然是 0)*就可以把整个 dp 数组递推出来，而由于 dp[i][v]表示的是恰好为 v 的情况，所以需要枚举 dp[n][v]，取其最大值即可。

代码如下

int ans=0;
for(int i=0;i<n;i++){
    for(int v=w[i];v<=V;v++){
        dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);

    }
}
for(int v=1;v<=V;v++){
    ans=max(ans,dp[n][v]);
}
cout<<ans;

时间复杂度和空间复杂度均为$O(nV)$，但是空间复杂度还可以继续优化

注意到每次计算 dp[i][v]的时候只需要计算 dp[i-1][v]左侧部分的数据（即从 0 到 v 的部分的数据），且计算 dp[i+1][]的时候，dp[i-1][]部分的数据又没用了。所以开一个一维数组 dp[v]，枚举方向 i 从 1 到 n，v 从 V 到 0（逆序！），状态转移方程变为 $$ \mathrm{dp[v]}=max{\mathrm{dp[v],dp[v-w[i]]+c[i]}} \ 1≤i≤n,w[i]≤v≤V $$ 相当于每次计算出 dp[i][v]的时候，就覆盖掉 dp[i-1][v]，以节省空间

for(int i=0;i<n;i++){
    for(int v=V;v>=w[i];v--){
        dp[v]=max(dp[v],dp[v-w[i]+c[i]]);
    }
}
cout<<dp[V];

记得用一维数组存放时，v 的枚举必须是逆序！

对于能够划分阶段的问题来说，都可以尝试把阶段作为状态的一维，这样使得我们更方便地得到满足无后效性的状态。如果当前设计的状态不满足无后效性，不妨把状态进行升维，增加一维或者若干维来表示相应的信息。

11.7.3 完全背包问题

有 n 种物品，每件物品的重量为 w[i]，价值为 c[i]。现有一个容量为 V 的背包，问如何选取物品放入背包使得背包内物品的总价值最大。每件物品都有无穷件。

同样令 dp[i][v]表示前 i 件物品 (1≤i≤n,0≤v≤V)恰好（“恰好”指的是恰好把容量 v 填满）装入容量为 v 的背包所能获得的最大价值

对于第 i 件物品来说

1. 不放第 i 件物品则有 dp[i][v]=dp[i-1][v]
2. 放第 i 件物品转移到 dp[i][v-w[i]]+c[i]这个状态，这是因为每件物品可以放任意件，放了第 i 件物品之后还可以放第 i 件物品

状态转移方程为 $$ \mathrm{dp[i][v]}=max{\mathrm{dp[i-1][v],dp[i][v-w[i]]+c[i]}} \ 1≤i≤n,w[i]≤v≤V \ 边界\ d[0][v]=0 $$ 也可以改写成一维模式 $$ \mathrm{dp[v]}=max{\mathrm{dp[v],dp[v-w[i]]+c[i]}} \ 1≤i≤n,w[i]≤v≤V \ 边界\ d[v]=0 $$ 这就和 01 背包问题完全一致了，唯一的区别在于这里的 v 必须是正向枚举

因为 dp[i][v]可以直接覆盖 dp[i-1][v]

11.8 总结

总结过的模型列举如下：

1. 最大连续子序列和

   令 dp[i]表示以 a[i]作为结尾的连续序列的最大和。

2. 最长不下降子序列 (LIS)

   令 dp[i]表示以 a[i]结尾的最长不下降子序列长度

3. 最长公共子序列 (LCS)

   令 dp[i][j]表示字符串 a 的 i 号位和字符串 b 的 j 号位之前的 LCS 长度

4. 最长回文子串

   令 bool dp[i][j]表示 s[i]至 s[j]所表示的子串是否是回文子串

5. 数塔 DP

   令 dp[i][j]表示从第 i 行第 j 个数字出发的到达最底层的所有路径上所能得到的最大和

6. DAG 最长路

   令 dp[i]表示从 i 号顶点出发能获得的最长路径长度

7. 01 背包

   令 dp[i][v]表示前 i 件物品恰好装入容量为 v 的背包所能获得的最大价值

8. 完全背包

   令 dp[i][v]表示前 i 件物品恰好装入容量为 v 的背包所能获得的最大价值

特别说明：一般来说“子序列”可以不连续，“子串”必须连续。

当题目与序列或字符串 (记作 a) 有关时，可以考虑把状态设计成下面两种形式，然后根据端点特点去考虑状态转移方程。

1. 令 dp[i]表示以 a[i]结尾（或开头）的 xxx
2. 令 dp[i][j]表示 a[i]至 a[j]区间的 xxx

其中 xxx 均为原问题的表述。

当题目中的问题设计几个维度时候，分析题目中的状态需要几维来表示，然后对其中的每一维采取下面的某一个表述：

1. 恰好为 i
2. 前 i

在每一维的的含义设置完毕之后，dp 数组的含义就可以设置成"令 dp 数组表示恰好为 i（或前 i）、恰好为 j（或前 j）......的 XXX"，其中 xxx 为原问题的表述，接下来通过端点的特点去考虑状态转移方程。