算法竞赛模板———上（常规优化，排序，搜索，动态规划）

算法竞赛模板一、主函数与重命名模板#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>#include <vector>#include <algorithm>#include <set>#include <unordered_map>#include <string>#in

怠惰的弈方

1917人浏览 · 2023-11-26 17:51:04

怠惰的弈方 · 2023-11-26 17:51:04 发布

算法竞赛模板

一、主函数与重命名模板

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <bitset>
#include <cmath>

#define fi first
#define se second
#define endl '\n'

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<string, int> psi;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pss> vpss;
typedef vector<vi> vvi;

typedef queue <int> qi;
typedef queue <ll> ql;
typedef queue <pii> qpii;
typedef queue <psi> qpsi;

typedef map<int, int> mii;
typedef map<string, int> msi;

typedef priority_queue<int> pqi;
typedef priority_queue<string> pqs;
typedef priority_queue<pii> pqpii;
typedef priority_queue<psi> pqpsi;

typedef unordered_map<int, int> umapii;
typedef unordered_map<string, int> umapsi;

const int N = 1e5 + 5;

void solve()
{

}

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

二、读写与输出的优化

在C++编程中，对输入输出进行优化可以提高程序的执行效率。以下是一些常见的优化技巧：

1. 优化 `cin` 与 `cout`

关闭 C++ 的 cin 与 cout 与 C 的 stdio 的同步，以提高输入输出效率。

通过 cin.tie(nullptr) 和 cout.tie(nullptr) 解除了 cin 和 cout 的绑定。

绑定主要是指，每次调用 cin 之后，会自动调用 cout 进行刷新。解除绑定后，它们的刷新可以手动控制，避免不必要的刷新操作，提高性能。

#include <iostream>

int main()
{
    // 关闭输入输出同步，提高输入输出效率
    std::ios::sync_with_stdio(false);

    // 解除 cin 与 cout 的绑定，防止混用时的性能损失
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    // 此处是程序的主体部分

    return 0;
}

2. 快速读入

通过 getchar() 逐个读取字符，并根据 ASCII 码将字符转换成对应的数字。

支持读取负数，通过记录符号位 y 来实现。

#include <cstdio>

inline int read()
{
    register int x = 0, y = 1;
    register char ch = getchar();
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            y = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * y;
}

3. 快速输出

通过递归将整数按位输出，避免了多次调用 putchar 的开销，从而提高了输出效率。

#include <cstdio>

inline void write(int x) 
{
    if (x < 0) 
    {
        putchar('-');
        x = -x;
    }
    if (x >= 10) 
    {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

三、排序

1. 选择排序

时间复杂度： $O(n^2)$ ，其中 $n$ 为数组长度。

空间复杂度： $O (1)$ 。

功能： 选择排序是一种简单直观的排序算法，它的工作原理是每次从待排序的数据元素中选择最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）的元素，依次类推。

#include <iostream>
#include <vector>

using namespace std;

void selectionSort(vector<int>& arr)
{
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) 
    {
        // 找到最小元素的索引
        int minIndex = i;
        for (int j = i + 1; j < n; j++) 
        {
            if (arr[j] < arr[minIndex]) 
            {
                minIndex = j;
            }
        }

        // 交换最小元素和当前元素
        swap(arr[i], arr[minIndex]);
    }
}

2. 冒泡排序

时间复杂度： $O(n^2)$ ，其中 $n$ 为数组长度。

空间复杂度： $O (1)$ 。

功能： 冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

#include <iostream>
#include <vector>

using namespace std;

void bubbleSort(vector<int>& arr) 
{
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) 
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            // 如果相邻元素逆序，则交换它们
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

3. 插入排序

时间复杂度： $O(n^2)$ ，其中 $n$ 为数组长度。

空间复杂度： $O (1)$ 。

功能： 插入排序是一种简单直观的排序算法，其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

#include <iostream>
#include <vector>

using namespace std;

void insertionSort(vector<int>& arr)
{
    int n = arr.size();

    for (int i = 1; i < n; i++) 
    {
        // 从当前元素往前比较，找到合适的插入位置
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) 
        {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // 插入当前元素到合适的位置
        arr[j + 1] = key;
    }
}

4. 快速排序

时间复杂度： 平均情况 $\log n)$ ，最坏情况 $O(n^2)$ ，其中 $n$ 为数组长度。

空间复杂度： 平均情况 $O(\log n)$ 。

功能： 快速排序是一种高效的排序算法，采用分治法来实现。它选择一个基准元素，将序列分割成两个子序列，然后对子序列进行递归排序。

#include <iostream>
#include <vector>

using namespace std;

// 分割函数
int partition(vector<int>& arr, int low, int high) 
{
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) 
    {
        if (arr[j] < pivot) 
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 快速排序递归函数
void quickSort(vector<int>& arr, int low, int high) 
{
    if (low < high) 
    {
        // 找到分割点
        int pivotIndex = partition(arr, low, high);
        // 分别对左右子序列进行排序
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

5. 归并排序

时间复杂度： 平均情况 $\log n)$ ，最坏情况 $\log n)$ ，其中 $n$ 为数组长度。

空间复杂度： $O (n)$ 。

功能： 归并排序是一种稳定的排序算法，采用分治法来实现。它将待排序的序列分成两个子序列，分别进行递归排序，然后将两个有序的子序列合并成一个有序序列。

#include <iostream>
#include <vector>

using namespace std;

// 归并函数
void merge(vector<int>& arr, int low, int mid, int high) 
{
    int n1 = mid - low + 1;
    int n2 = high - mid;

    // 创建临时数组
    vector<int> left(n1), right(n2);

    // 将数据复制到临时数组 left[] 和 right[] 中
    for (int i = 0; i < n1; i++) 
    {
        left[i] = arr[low + i];
    }
    for (int j = 0; j < n2; j++) 
    {
        right[j] = arr[mid + 1 + j];
    }

    // 归并临时数组到 arr[low..high]
    int i = 0, j = 0, k = low;
    while (i < n1 && j < n2) 
    {
        if (left[i] <= right[j]) 
        {
            arr[k] = left[i];
            i++;
        } 
        else 
        {
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    // 复制 left[] 的剩余元素
    while (i < n1) 
    {
        arr[k] = left[i];
        i++;
        k++;
    }

    // 复制 right[] 的剩余元素
    while (j < n2) 
    {
        arr[k] = right[j];
        j++;
        k++;
    }
}

// 归并排序递归函数
void mergeSort(vector<int>& arr, int low, int high) 
{
    if (low < high) 
    {
        // 计算中间点
        int mid = low + (high - low) / 2;

        // 递归排序左右两部分
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);

        // 合并排序好的两部分
        merge(arr, low, mid, high);
    }
}

6. 堆排序

时间复杂度： 平均情况 $\log n)$ ，最坏情况 $\log n)$ ，其中 $n$ 为数组长度。

空间复杂度： $O (1)$ 。

功能： 堆排序是一种高效的排序算法，它利用了堆这一数据结构的特性。它将待排序的序列构建成一个最大堆（或最小堆），然后逐步取出堆顶元素，得到排序结果。

#include <iostream>
#include <vector>

using namespace std;

// 堆调整函数，保持最大堆性质
void heapify(vector<int>& arr, int n, int i) 
{
    int largest = i;    // 初始化最大值的索引
    int left = 2 * i + 1;  // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 如果左子节点大于根节点，更新最大值索引
    if (left < n && arr[left] > arr[largest]) 
    {
        largest = left;
    }

    // 如果右子节点大于根节点，更新最大值索引
    if (right < n && arr[right] > arr[largest])
    {
        largest = right;
    }

    // 如果最大值索引不等于根节点，交换它们，并递归调整堆
    if (largest != i) 
    {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// 堆排序函数
void heapSort(vector<int>& arr) 
{
    int n = arr.size();

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        heapify(arr, n, i);
    }

    // 逐步取出堆顶元素，得到排序结果
    for (int i = n - 1; i > 0; i--) 
    {
        swap(arr[0], arr[i]);   // 将堆顶元素移动到末尾
        heapify(arr, i, 0);     // 重新调整堆
    }
}

7. 计数排序

时间复杂度： 平均情况 $O (n + k)$ ，最坏情况 $O (n + k)$ ，其中 $n$ 为数组长度， $k$ 为数据范围。

空间复杂度： $O (n + k)$ 。

功能： 计数排序是一种非比较排序算法，它通过统计每个元素在序列中出现的次数，然后根据元素的计数位置来排序。

#include <iostream>
#include <vector>

using namespace std;

// 计数排序函数
void countingSort(vector<int>& arr) 
{
    int n = arr.size();

    // 找到数组中的最大值
    int maxVal = *max_element(arr.begin(), arr.end());

    // 创建计数数组，并初始化为0
    vector<int> count(maxVal + 1, 0);

    // 统计每个元素的出现次数
    for (int i = 0; i < n; i++) 
    {
        count[arr[i]]++;
    }

    // 根据计数数组重构原数组
    int index = 0;  // 初始化原数组索引

    // 遍历计数数组，重构原数组
    for (int i = 0; i <= maxVal; i++)
    {
        while (count[i] > 0) 
        {
            arr[index] = i;
            index++;
            count[i]--;
        }
    }
}

8. 基数排序

时间复杂度： 平均情况 $\cdot (n + k))$ ，最坏情况 $\cdot (n + k))$ ，其中 $n$ 为数组长度， $k$ 为数据范围， $d$ 为最大数字的位数。

空间复杂度： $O (n + k)$ 。

功能： 基数排序是一种非比较排序算法，它按照数字的每个位数进行排序。它首先按照最低有效位（个位）排序，然后按照次低有效位排序，直到按照最高有效位排序。

#include <iostream>
#include <vector>

using namespace std;

// 获取数字的指定位数的值
int getDigit(int num, int place) 
{
    int result = 1;
    for (int i = 0; i < place; i++) 
    {
        result *= 10;
    }
    return (num / result) % 10;
}

// 获取数字的位数
int getNumDigits(int num)
{
    int digits = 0;
    while (num > 0) 
    {
        num /= 10;
        digits++;
    }
    return digits;
}

// 基数排序函数
void radixSort(vector<int>& arr)
{
    int n = arr.size();

    // 找到数组中的最大值
    int maxVal = *max_element(arr.begin(), arr.end());

    // 计算最大值的位数
    int numDigits = getNumDigits(maxVal);

    // 根据每个位数进行计数排序
    for (int place = 0; place < numDigits; place++)
    {
        // 创建计数数组，并初始化为0
        vector<int> count(10, 0);

        // 统计每个元素的出现次数
        for (int i = 0; i < n; i++) 
        {
            count[getDigit(arr[i], place)]++;
        }

        // 根据计数数组重构原数组
        int index = 0;
        for (int i = 0; i < 10; i++) 
        {
            while (count[i] > 0) 
            {
                arr[index] = i;
                index++;
                count[i]--;
            }
        }
    }
}

9. 桶排序

时间复杂度： 平均情况 $O(n + n^2/k + k)$ ，其中 $n$ 为数组长度， $k$ 为桶的数量。

空间复杂度： $O (n + k)$ 。

功能： 桶排序是一种排序算法，它通过将待排序元素分到有限数量的桶中，每个桶再单独进行排序，最后将所有桶中的元素合并得到最终排序结果。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 桶排序函数
void bucketSort(vector<int>& arr, int numBuckets) 
{
    int n = arr.size();

    // 创建桶
    vector<vector<int>> buckets(numBuckets);

    // 将元素分配到桶中
    for (int i = 0; i < n; i++) 
    {
        int bucketIndex = arr[i] * numBuckets / (INT_MAX + 1LL);
        buckets[bucketIndex].push_back(arr[i]);
    }

    // 对每个桶进行排序，并合并结果
    int index = 0;
    for (int i = 0; i < numBuckets; i++) 
    {
        sort(buckets[i].begin(), buckets[i].end());
        for (int j = 0; j < buckets[i].size(); j++) 
        {
            arr[index++] = buckets[i][j];
        }
    }
}

10. 希尔排序

时间复杂度： 平均情况 $\log n)$ ，最坏情况 $O(n^2)$ ，其中 $n$ 为数组长度。

空间复杂度： $O (1)$ 。

功能： 希尔排序是插入排序的一种改进版本，它通过将数组分割成若干个子序列，并对子序列进行插入排序，最后再对整个数组进行一次插入排序。

#include <iostream>
#include <vector>

using namespace std;

// 希尔排序函数
void shellSort(vector<int>& arr) 
{
    int n = arr.size();

    // 逐步缩小增量
    for (int gap = n / 2; gap > 0; gap /= 2) 
    {
        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++)
        {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
            {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

11. 锦标赛排序

时间复杂度： 平均情况 $\log n)$ ，最坏情况 $\log n)$ ，其中 $n$ 为数组长度。

空间复杂度： $O (n)$ 。

功能： 锦标赛排序是一种排序算法，它通过构建一棵二叉树，每个非叶子节点存储两个叶子节点的最小值，最后根节点存储整个序列的最小值。

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// 锦标赛排序辅助函数：构建树
void buildTree(vector<int>& arr, vector<int>& tree, int node, int start, int end) 
{
    if (start == end) 
    {
        tree[node] = arr[start];
    } 
    else 
    {
        int mid = (start + end) / 2;
        buildTree(arr, tree, 2 * node, start, mid);
        buildTree(arr, tree, 2 * node + 1, mid + 1, end);
        tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    }
}

// 锦标赛排序辅助函数：查询区间最小值
int queryTree(vector<int>& tree, int node, int start, int end, int left, int right) 
{
    if (start > right || end < left)
    {
        return INT_MAX;
    }
    if (start >= left && end <= right) 
    {
        return tree[node];
    }

    int mid = (start + end) / 2;
    int leftMin = queryTree(tree, 2 * node, start, mid, left, right);
    int rightMin = queryTree(tree, 2 * node + 1, mid + 1, end, left, right);

    return min(leftMin, rightMin);
}

// 锦标赛排序函数
void tournamentSort(vector<int>& arr) 
{
    int n = arr.size();

    // 构建树
    int treeSize = 2 * n;
    vector<int> tree(treeSize, 0);
    buildTree(arr, tree, 1, 0, n - 1);

    // 查询树并排序
    for (int i = 0; i < n; i++) 
    {
        arr[i] = queryTree(tree, 1, 0, n - 1, i, n - 1);
    }
}

12. tim排序

时间复杂度： 平均情况 $\log n)$ ，最坏情况 $\log n)$ ，其中 $n$ 为数组长度。

空间复杂度： $O (n)$ 。

功能： tim排序是一种融合了归并排序和插入排序的稳定排序算法，它在归并排序的基础上对小规模子数组使用插入排序进行优化。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MIN_MERGE = 32;

// 插入排序函数
void insertionSort(vector<int>& arr, int left, int right) 
{
    for (int i = left + 1; i <= right; i++) 
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// 归并排序辅助函数：合并两个有序数组
void merge(vector<int>& arr, int left, int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    vector<int> leftArr(n1), rightArr(n2);

    // 将数据复制到临时数组 leftArr[] 和 rightArr[] 中
    for (int i = 0; i < n1; i++) 
    {
        leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) 
    {
        rightArr[j] = arr[mid + 1 + j];
    }

    // 归并临时数组到 arr[left..right]
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) 
    {
        if (leftArr[i] <= rightArr[j]) 
        {
            arr[k] = leftArr[i];
            i++;
        } 
        else 
        {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 复制 leftArr[] 的剩余元素
    while (i < n1) 
    {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    // 复制 rightArr[] 的剩余元素
    while (j < n2) 
    {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// 归并排序函数
void timSort(vector<int>& arr)
{
    int n = arr.size();

    // 对数组进行插入排序，形成长度为 MIN_MERGE 的块
    for (int i = 0; i < n; i += MIN_MERGE) 
    {
        insertionSort(arr, i, min((i + MIN_MERGE - 1), (n - 1)));
    }

    // 对块进行归并排序
    for (int size = MIN_MERGE; size < n; size = 2 * size) 
    {
        for (int left = 0; left < n; left += 2 * size) 
        {
            int mid = left + size - 1;
            int right = min((left + 2 * size - 1), (n - 1));
            if (mid < right) 
            {
                merge(arr, left, mid, right);
            }
        }
    }
}

13. 排序相关 STL

C++标准库提供了丰富的排序相关的函数和容器，以下是一些常用的排序相关 STL：

13.1. sort函数

功能： 对指定范围内的元素进行升序排序。

头文件： <algorithm>

用法：

#include <algorithm>
#include <vector>
#include <iostream>

int main() 
{
    std::vector<int> vec = {5, 2, 9, 1, 5, 6};
    
    std::sort(vec.begin(), vec.end());  // 对整个向量进行排序
    
    std::cout << "Sorted array: ";
    for (int num : vec) 
    {
        std::cout << num << " ";
    }
    
    return 0;
}

13.2. stable_sort函数

功能： 对指定范围内的元素进行升序排序，保持相等元素的相对顺序。

头文件： <algorithm>

用法：

#include <algorithm>
#include <vector>
#include <iostream>

int main() 
{
    std::vector<int> vec = {5, 2, 9, 1, 5, 6};
    
    std::stable_sort(vec.begin(), vec.end());  // 对整个向量进行稳定排序
    
    std::cout << "Stably Sorted array: ";
    for (int num : vec) 
    {
        std::cout << num << " ";
    }
    
    return 0;
}

13.3. partial_sort 函数

功能： 对指定范围内的元素进行部分排序，保证指定数量的最小元素在指定位置，无序的。

头文件： <algorithm>

用法：

#include <algorithm>
#include <vector>
#include <iostream>

int main() 
{
    std::vector<int> vec = {5, 2, 9, 1, 5, 6};
    
    int k = 3; // 希望找到最小的3个元素
    std::partial_sort(vec.begin(), vec.begin() + k, vec.end());  
    
    std::cout << "Partially Sorted array: ";
    for (int num : vec) 
    {
        std::cout << num << " ";
    }
    
    return 0;
}

13.4. nth_element 函数

功能： 对指定范围内的元素进行部分排序，保证指定位置的元素是排序后的。

头文件： <algorithm>

用法：

#include <algorithm>
#include <vector>
#include <iostream>

int main() 
{
    std::vector<int> vec = {5, 2, 9, 1, 5, 6};
    
    int k = 3; // 希望找到排在第3位的元素
    std::nth_element(vec.begin(), vec.begin() + k, vec.end());  
    
    std::cout << "Element at position " << k << ": " << vec[k] << std::endl;
    
    return 0;
}

13.5. 堆操作

功能： 构建堆、将元素推入堆、从堆中弹出元素、堆排序等。

头文件： <algorithm>

用法：

#include <algorithm>
#include <vector>
#include <iostream>

int main() 
{
    std::vector<int> vec = {5, 2, 9, 1, 5, 6};
    
    std::make_heap(vec.begin(), vec.end());  // 构建最大堆
    
    // 将新元素推入堆
    vec.push_back(10);
    std::push_heap(vec.begin(), vec.end());  // 推入新元素后调整堆
    
    // 弹出堆顶元素
    std::pop_heap(vec.begin(), vec.end());  // 将最大元素移到末尾
    int maxElement = vec.back();
    vec.pop_back();  // 移除末尾元素
    
    // 对剩余元素排序（堆排序）
    std::sort_heap(vec.begin(), vec.end());  
    
    std::cout << "Sorted array after heap operations: ";
    for (int num : vec) 
    {
        std::cout << num << " ";
    }
    
    return 0;
}

四、搜索

1、深度优先搜索

时间复杂度： $O (V + E)$ ，其中 $V$ 为节点数， $E$ 为边数。

空间复杂度： $O (V)$ ，存储节点的访问状态。

**功能：**深度优先搜索（DFS）是一种用于遍历图或树的算法。通过从起始节点开始，递归地访问节点的邻居节点，直到无法继续深入为止。深度优先搜索常用于找到图中的连通分量、拓扑排序等应用场景。

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 5;
bool visited[N];

// 深度优先搜索
void dfs(int u, vector<vector<int>>& graph) 
{
    // 访问节点u
    cout << u << " ";
    visited[u] = true;

    // 遍历u的邻居节点
    for (int v : graph[u]) 
    {
        if (!visited[v]) 
        {
            dfs(v, graph);
        }
    }
}

2、广度优先搜索

时间复杂度： $O (V + E)$ ，其中 $V$ 为节点数， $E$ 为边数。

空间复杂度： $O (V)$ ，存储节点的访问状态和队列。

功能： 广度优先搜索（BFS）是一种用于遍历图或树的算法。通过从起始节点开始，逐层访问节点的邻居节点，实现对整个图的广度优先遍历。广度优先搜索常用于最短路径、最小生成树等应用场景。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int N = 1e5 + 5;
bool visited[N];

// 广度优先搜索
void bfs(int start, vector<vector<int>>& graph)
{
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) 
    {
        int u = q.front();
        q.pop();
        cout << u << " ";

        // 遍历u的邻居节点
        for (int v : graph[u]) 
        {
            if (!visited[v]) 
            {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

3. 双向搜索

时间复杂度： $O(\text{max}(B, D^{\frac{1}{2}}))$ ，其中 $B$ 为每层的分支数， $D$ 为搜索树的深度。

空间复杂度： $O(\text{max}(B, D^{\frac{1}{2}}))$

功能： 通过从起点和终点同时进行搜索，缩小搜索空间，提高搜索效率。适用于无向图的最短路径问题等。

#include <iostream>
#include <unordered_set>
#include <queue>

using namespace std;

/**
 * 双向搜索算法
 * @param start 起点
 * @param end 终点
 * @param graph 图的邻接矩阵表示
 * @return 共同搜索到的节点，表示路径的交汇点，如果没有找到连接，返回-1
 */
int bidirectionalSearch(int start, int end, vector<vector<int>>& graph) 
{
    // 记录从起点出发的已访问节点
    unordered_set<int> visitedStart;
    // 记录从终点出发的已访问节点
    unordered_set<int> visitedEnd;
    // 从起点出发的广度优先搜索队列
    queue<int> qStart;
    // 从终点出发的广度优先搜索队列
    queue<int> qEnd;

    // 初始化起点搜索
    qStart.push(start);
    visitedStart.insert(start);

    // 初始化终点搜索
    qEnd.push(end);
    visitedEnd.insert(end);

    // 双向搜索主循环
    while (!qStart.empty() && !qEnd.empty()) 
    {
        // 从起点扩展
        int uStart = qStart.front();
        qStart.pop();

        // 从起点扩展的逻辑
        for (int v : graph[uStart]) 
        {
            if (!visitedStart.count(v)) 
            {
                // 访问节点的逻辑
                visitedStart.insert(v);
                qStart.push(v);
            }
        }

        // 检查是否有交汇点
        if (visitedEnd.count(uStart))
            return uStart;

        // 从终点扩展
        int uEnd = qEnd.front();
        qEnd.pop();

        // 从终点扩展的逻辑
        for (int v : graph[uEnd]) 
        {
            if (!visitedEnd.count(v)) 
            {
                // 访问节点的逻辑
                visitedEnd.insert(v);
                qEnd.push(v);
            }
        }

        // 检查是否有交汇点
        if (visitedStart.count(uEnd))
            return uEnd;
    }

    return -1;  // 没有找到连接
}

4. 启发式搜索 (A*算法)

时间复杂度： $O(b^d)$ ，其中 $b$ 为每个节点的平均分支数， $d$ 为目标节点的深度。

空间复杂度： $O(b^d)$

功能： 利用启发式函数估计每个节点到目标节点的代价，以优先探索最有可能导致解的节点。适用于最短路径、游戏搜索等。

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

struct Node 
{
    int state;        // 节点状态
    int cost;         // 起始节点到当前节点的路径成本
    int heuristic;    // 启发式函数估计的代价（到目标的估计代价）

    // 优先队列中比较节点的 ">" 操作符重载
    bool operator>(const Node& other) const 
    {
        return cost + heuristic > other.cost + other.heuristic;
    }
};

/**
 * A*搜索算法
 * @param start 起始节点
 * @param target 目标节点
 * @param graph 图的邻接表表示
 * @param heuristic 启发式函数的映射，存储每个节点到目标的估计代价
 * @return 若存在路径，则返回起始节点到目标节点的最小代价，否则返回-1
 */
int astarSearch(int start, int target, vector<vector<pair<int, int>>>& graph, unordered_map<int, int>& heuristic) 
{
    // 优先队列，按照节点的总代价（cost + heuristic）升序排列
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({start, 0, heuristic[start]});

    // 记录每个节点的路径成本
    unordered_map<int, int> cost;

    while (!pq.empty()) 
    {
        // 弹出当前总代价最小的节点
        Node node = pq.top();
        pq.pop();

        int u = node.state;

        // 到达目标节点，返回路径成本
        if (u == target) 
        {
            return node.cost;
        }

        // 遍历当前节点的邻居
        for (auto& neighbor : graph[u]) 
        {
            int v = neighbor.first;
            int edgeCost = neighbor.second;

            // 计算新的路径成本
            int newCost = node.cost + edgeCost;

            // 如果新的路径成本更小，更新并加入队列
            if (!cost.count(v) || newCost < cost[v]) 
            {
                cost[v] = newCost;
                pq.push({v, newCost, heuristic[v]});
            }
        }
    }

    return -1;  // 未找到路径
}

5. 迭代加深搜索

时间复杂度： 取决于深度限制 $D$ ，通常介于 $O(b^d)$ 和 $O(b^{\frac{D}{2}})$ 之间。

空间复杂度： $O (D)$

功能： 迭代加深搜索是一种结合了深度优先搜索和逐层递增深度的搜索方法。它通过逐渐增加搜索深度，以便在较小的深度限制内进行搜索。该算法在一些问题中能够有效地找到解。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 深度受限的深度优先搜索
 * @param u 当前节点
 * @param depth 剩余深度
 * @param target 目标节点
 * @param graph 图的邻接表表示
 * @return 若在指定深度内找到目标节点，返回true，否则返回false
 */
bool depthLimitedDFS(int u, int depth, int target, vector<vector<int>>& graph) 
{
    // 在指定深度内找到目标节点
    if (depth == 0 && u == target) 
    {
        return true;
    }

    // 仍有深度可用
    if (depth > 0) 
    {
        // 遍历当前节点的邻居
        for (int v : graph[u]) 
        {
            // 递归调用深度受限DFS
            if (depthLimitedDFS(v, depth - 1, target, graph)) 
            {
                return true;
            }
        }
    }

    return false;  // 未找到目标节点
}

/**
 * 迭代加深搜索算法
 * @param start 起始节点
 * @param target 目标节点
 * @param graph 图的邻接表表示
 * @return 若找到目标节点，返回最小深度，否则返回-1
 */
int iterativeDeepeningDFS(int start, int target, vector<vector<int>>& graph) 
{
    int depth = 0;

    // 逐渐增加深度
    while (true) 
    {
        // 在当前深度限制内进行深度受限DFS
        if (depthLimitedDFS(start, depth, target, graph)) 
        {
            return depth;  // 找到目标节点，返回深度
        }

        depth++;  // 增加深度限制
    }
}

6. IDA* 算法

时间复杂度： 取决于深度限制 $D$ ，通常介于 $O(b^d)$ 和 $O(b^{\frac{D}{2}})$ 之间。

空间复杂度： $O (D)$

功能： 结合深度优先搜索和A*算法，用于在较小的深度限制内进行搜索，提高效率。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 启发式函数，估计从当前状态到目标状态的代价
 * @param state 当前状态
 * @param target 目标状态
 * @return 启发式估计的代价
 */
int heuristic(int state, int target) 
{
    // 启发式函数
}

/**
 * 深度受限的深度优先搜索
 * @param state 当前状态
 * @param target 目标状态
 * @param depth 剩余深度
 * @param graph 图的邻接表表示
 * @return 若在指定深度内找到目标状态，返回true，否则返回false
 */
bool depthLimitedSearch(int state, int target, int depth, vector<vector<int>>& graph) 
{
    // 在指定深度内找到目标状态
    if (depth == 0 && state == target) 
    {
        return true;
    }

    // 仍有深度可用
    if (depth > 0) 
    {
        // 遍历当前状态的邻居
        for (int neighbor : graph[state]) 
        {
            // 递归调用深度受限DFS
            if (depthLimitedSearch(neighbor, target, depth - 1, graph)) 
            {
                return true;
            }
        }
    }

    return false;  // 未找到目标状态
}

/**
 * IDA*搜索算法
 * @param start 起始状态
 * @param target 目标状态
 * @param graph 图的邻接表表示
 * @return 若找到目标状态，返回最小深度，否则返回-1
 */
int idaStarSearch(int start, int target, vector<vector<int>>& graph) 
{
    // 启发式函数的初始深度限制
    int depth = heuristic(start, target);

    while (true) 
    {
        // 在当前深度限制内进行深度受限DFS
        if (depthLimitedSearch(start, target, depth, graph)) 
        {
            return depth;  // 找到目标状态，返回深度
        }

        depth++;  // 增加深度限制
    }
}

7. 回溯法

时间复杂度： 取决于问题规模和解的个数。

空间复杂度： $O(\text{max depth of recursion})$

功能： 通过尝试所有可能的解，找到问题的解。适用于组合优化问题、八皇后问题等。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 安全性检查函数，检查在当前位置放置皇后是否安全
 * @param row 当前行
 * @param col 当前列
 * @param board 棋盘
 * @return 若安全返回true，否则返回false
 */
bool isSafe(int row, int col, vector<vector<int>>& board) 
{
    // 你的安全性检查逻辑
}

/**
 * N皇后问题求解函数
 * @param row 当前行
 * @param board 棋盘
 * @return 若找到解返回true，否则返回false
 */
bool solveNQueens(int row, vector<vector<int>>& board) 
{
    // 已经找到了一种解决方案
    if (row == board.size()) 
    {
        // 打印或存储解决方案
        return true;
    }

    // 在当前行尝试每一列
    for (int col = 0; col < board.size(); col++) 
    {
        // 如果在当前位置放置皇后是安全的
        if (isSafe(row, col, board)) 
        {
            // 放置皇后
            board[row][col] = 1;

            // 递归调用解决下一行
            if (solveNQueens(row + 1, board)) 
            {
                return true;
            }

            // 回溯，撤销当前位置的皇后
            board[row][col] = 0;
        }
    }

    return false;  // 未找到解
}

8. Dancing Links (DLX)

时间复杂度： 取决于问题规模和解的个数。

空间复杂度： $O (NM)$ ，其中 $N$ 为行数， $M$ 为列数。

**功能：**Dancing Links (DLX) 是一种用于求解精确覆盖问题的算法，如数独、精确覆盖等。它通过精妙的数据结构和回溯算法实现高效的解空间搜索。

#include <iostream>
#include <vector>

using namespace std;

struct Node 
{
    int row, col;
    Node* left, *right, *up, *down;
};

// 你的 Dancing Links 实现

9. Alpha-Beta 剪枝

时间复杂度： 取决于树的分支因子和深度。

空间复杂度： $O(\text{max depth of recursion})$

**功能：**Alpha-Beta剪枝是一种用于优化极小极大搜索算法的技术，通过排除一些不可能成为最优解的分支，从而削减搜索空间，提高搜索效率。

#include <iostream>
#include <vector>

using namespace std;

/**
 * Alpha-Beta剪枝搜索
 * @param depth 当前搜索深度
 * @param node 当前节点
 * @param alpha 当前最好的最大值
 * @param beta 当前最好的最小值
 * @param isMaximizingPlayer 当前轮到的玩家是极大化还是极小化
 * @return 当前节点的估值
 */
int alphaBeta(int depth, int node, int alpha, int beta, bool isMaximizingPlayer) 
{
    // 到达叶节点或者终止节点
    if (depth == 0 || /*terminal node*/) 
    {
        return /*evaluate node*/;
    }

    if (isMaximizingPlayer) 
    {
        int value = INT_MIN;
        for (/* each child node */) 
        {
            value = max(value, alphaBeta(depth - 1, child, alpha, beta, false));
            alpha = max(alpha, value);
            if (beta <= alpha) 
                break;  // Beta剪枝
        }
        return value;
    } 
    else 
    {
        int value = INT_MAX;
        for (/* each child node */) 
        {
            value = min(value, alphaBeta(depth - 1, child, alpha, beta, true));
            beta = min(beta, value);
            if (beta <= alpha) 
                break;  // Alpha剪枝
        }
        return value;
    }
}

10. 优化

优化通常包括一系列技巧，如记忆化搜索、状态压缩等，具体应用取决于问题的性质。以下是一个简单的例子：

10.1. 记忆化搜索

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

// 用于存储已经计算过的斐波那契数值
unordered_map<int, int> memo;

/**
 * 记忆化搜索斐波那契数列
 * @param n 斐波那契数列的索引
 * @return 第n个斐波那契数值
 */
int fibonacci(int n) 
{
    // 基本情况
    if (n <= 1) 
    {
        return n;
    }

    // 如果已经计算过，直接返回结果
    if (memo.count(n)) 
    {
        return memo[n];
    }

    // 递归计算并存储结果
    int result = fibonacci(n - 1) + fibonacci(n - 2);
    memo[n] = result;

    return result;
}

五、字符串

1. 字符串部分简介

字符串是由字符组成的序列。在计算机科学中，字符串是一种基本的数据结构，其操作涵盖了多个领域，包括文本处理、模式匹配、数据压缩等。字符串的算法涉及到字符串的匹配、查找、排序、编辑距离等问题。

2. 字符串基础

字符串表示

在 C++ 中，字符串可以用 std::string 类型表示。C 语言中通常使用字符数组（char array）表示字符串。

#include <iostream>
#include <string>

int main()
{
    // C++ 中的字符串表示
    std::string str1 = "Hello, ";
    std::string str2 = "World!";
    std::string combined = str1 + str2;

    std::cout << "Combined String: " << combined << std::endl;

    // C 中的字符串表示
    const char* cstr1 = "Hello, ";
    const char* cstr2 = "World!";
    char buffer[20];
    snprintf(buffer, sizeof(buffer), "%s%s", cstr1, cstr2);

    printf("Combined String: %s\n", buffer);

    return 0;
}

字符串长度

在 C++ 中，可以使用 size() 或 length() 成员函数获取字符串的长度。在 C 语言中，可以使用 strlen 函数。

#include <iostream>
#include <cstring>

int main()
{
    // C++ 中获取字符串长度
    std::string str = "Hello, World!";
    std::cout << "Length of String: " << str.size() << std::endl;

    // C 中获取字符串长度
    const char* cstr = "Hello, World!";
    printf("Length of String: %zu\n", strlen(cstr));

    return 0;
}

字符串遍历

字符串的遍历可以使用循环结构，逐个访问字符串中的字符。

#include <iostream>

int main()
{
    // C++ 中字符串遍历
    std::string str = "Hello, World!";
    for (char c : str) 
    {
        std::cout << c << " ";
    }
    std::cout << std::endl;

    // C 中字符串遍历
    const char* cstr = "Hello, World!";
    while (*cstr) 
    {
        putchar(*cstr);
        cstr++;
    }
    putchar('\n');

    return 0;
}

3. 标准库

C++ 标准库提供了丰富的字符串处理函数和算法。以下是一些常用的函数：

std::stoi：将字符串转换为整数。
std::stod：将字符串转换为双精度浮点数。
std::to_string：将基本数据类型转换为字符串。
std::find：在字符串中查找子串。
std::replace：替换字符串中的指定字符。
std::substr：提取字符串的子串。

#include <iostream>
#include <string>
#include <algorithm>

int main()
{
    // 字符串转换
    std::string numStr = "123";
    int num = std::stoi(numStr);
    std::cout << "Converted Integer: " << num << std::endl;

    // 查找子串
    std::string text = "Hello, World!";
    std::string pattern = "World";
    size_t found = text.find(pattern);
    if (found != std::string::npos) 
    {
        std::cout << "Pattern found at position: " << found << std::endl;
    } 
    else 
    {
        std::cout << "Pattern not found." << std::endl;
    }

    // 替换字符
    std::replace(text.begin(), text.end(), ',', ' ');
    std::cout << "String after replacement: " << text << std::endl;

    // 提取子串
    std::string subStr = text.substr(7, 5);  // 从位置 7 开始，提取长度为 5 的子串
    std::cout << "Substring: " << subStr << std::endl;

    return 0;
}

4. 字符串匹配

4.1. KMP 算法

时间复杂度： $O (N + M)$ ，其中 $N$ 为文本串的长度， $M$ 为模式串的长度。

空间复杂度： $O (M)$

功能： KMP 算法用于在文本串中查找是否包含特定的子串，并返回匹配的起始位置。

#include <iostream>
#include <vector>

/**
 * 构建部分匹配表（Longest Prefix which is also Suffix，简称 LPS）
 * @param pattern 模式串
 * @return 部分匹配表
 */
std::vector<int> buildPartialMatchTable(const std::string& pattern) 
{
    int m = pattern.size();
    std::vector<int> lps(m, 0);

    int len = 0;
    for (int i = 1; i < m; ) 
    {
        if (pattern[i] == pattern[len]) 
        {
            len++;
            lps[i] = len;
            i++;
        } 
        else 
        {
            if (len != 0) 
            {
                len = lps[len - 1];
            } 
            else 
            {
                lps[i] = 0;
                i++;
            }
        }
    }

    return lps;
}

/**
 * KMP 算法
 * @param text 文本串
 * @param pattern 模式串
 * @return 若找到匹配，返回匹配的起始位置，否则返回 -1
 */
int kmpSearch(const std::string& text, const std::string& pattern) 
{
    int n = text.size();
    int m = pattern.size();
    std::vector<int> lps = buildPartialMatchTable(pattern);

    int i = 0, j = 0;
    while (i < n) 
    {
        if (pattern[j] == text[i]) 
        {
            i++;
            j++;
        }

        if (j == m) 
        {
            return i - j;  // 匹配成功，返回匹配的起始位置
        }

        // 不匹配时，更新 j
        if (i < n && pattern[j] != text[i]) 
        {
            if (j != 0) 
            {
                j = lps[j - 1];
            } 
            else 
            {
                i++;
            }
        }
    }

    return -1;  // 匹配失败
}

int main() 
{
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";

    int position = kmpSearch(text, pattern);
    if (position != -1) 
    {
        std::cout << "Pattern found at position: " << position << std::endl;
    } 
    else 
    {
        std::cout << "Pattern not found." << std::endl;
    }

    return 0;
}

4.2. Boyer-Moore 算法

时间负责度： $O (n / m)$ - 最佳情况， $O (nm)$ - 最坏情况

空间负责度： $O (m)$

**功能：**Boyer-Moore 算法是一种字符串匹配算法，其核心思想是从右向左比较模式串和文本串，以尽量减少比较次数。

#include <string>
#include <vector>

/**
 * Boyer-Moore 算法
 * @param text 文本串
 * @param pattern 模式串
 * @return 若找到匹配，返回匹配的起始位置，否则返回 -1
 */
int boyerMooreSearch(const std::string& text, const std::string& pattern)
{
    const int n = text.size();
    const int m = pattern.size();

    // 计算字符的最大移动距离
    std::vector<int> badCharShift(256, 0);
    for (int i = 0; i < m; ++i)
    {
        badCharShift[static_cast<int>(pattern[i])] = i;
    }

    // 计算好后缀的最大移动距离
    std::vector<int> goodSuffixShift(m + 1, 0);
    std::vector<int> suffix(m, 0);
    std::vector<bool> prefix(m, false);
    calculateGoodSuffixShift(pattern, goodSuffixShift, suffix, prefix);

    int i = 0;  // i 表示在文本中匹配的位置

    while (i <= n - m)
    {
        int j = m - 1;  // j 表示在模式串中匹配的位置

        while (j >= 0 && pattern[j] == text[i + j])
        {
            j--;
        }

        if (j < 0)  // 匹配成功
        {
            return i;
        }
        else
        {
            i += std::max(goodSuffixShift[j + 1], j - badCharShift[static_cast<int>(text[i + j])]);
        }
    }

    return -1;  // 匹配失败
}

/**
 * 计算字符的最大移动距离
 *
 * @param pattern 模式串
 * @param badCharShift 记录字符的最大移动距离的数组
 */
void calculateBadCharacterShift(const std::string& pattern, std::vector<int>& badCharShift)
{
    const int m = pattern.size();

    for (int i = 0; i < 256; i++)
    {
        badCharShift[i] = -1;
    }

    for (int i = 0; i < m; i++)
    {
        badCharShift[static_cast<int>(pattern[i])] = i;
    }
}

/**
 * 计算好后缀的最大移动距离
 *
 * @param pattern 模式串
 * @param goodSuffixShift 记录好后缀的最大移动距离的数组
 * @param suffix 后缀数组
 * @param prefix 前缀数组
 */
void calculateGoodSuffixShift(const std::string& pattern, std::vector<int>& goodSuffixShift, std::vector<int>& suffix, std::vector<bool>& prefix)
{
    const int m = pattern.size();
    int j = 0;

    // 初始化数组
    std::fill(suffix.begin(), suffix.end(), 0);
    std::fill(prefix.begin(), prefix.end(), false);

    // 计算后缀数组
    for (int i = m - 1; i >= 0; i--)
    {
        while (j > 0 && pattern[i] != pattern[j])
        {
            j = suffix[j - 1];
        }

        if (pattern[i] == pattern[j])
        {
            j++;
        }

        suffix[i] = j;
    }

    // 计算前缀数组
    for (int i = 0; i < m - 1; i++)
    {
        prefix[suffix[i]] = true;
    }

    // 计算好后缀数组
    for (int i = 0; i < m; i++)
    {
        goodSuffixShift[i] = m;
    }

    j = 0;
    for (int i = m - 1; i >= 0; i--)
    {
        if (suffix[i] == i + 1)
        {
            for (; j < m - 1 - i; j++)
            {
                if (goodSuffixShift[j] == m)
                {
                    goodSuffixShift[j] = m - 1 - i;
                }
            }
        }
    }

    for (int i = 0; i <= m - 2; i++)
    {
        goodSuffixShift[m - 1 - suffix[i]] = m - 1 - i;
    }
}

5. 字符串哈希

时间负责度： $O (n)$

空间负责度： $O (n)$

功能： 字符串哈希是一种将字符串映射为整数的技术，通过哈希可以快速比较两个字符串是否相同。

#include <iostream>
#include <vector>

const int BASE = 256;
const int MOD = 1e9 + 7;

/**
 * 计算字符串的哈希值
 * @param str 输入字符串
 * @return 字符串的哈希值
 */
int calculateHash(const std::string& str) 
{
    int hashValue = 0;
    for (char ch : str) 
    {
        hashValue = (1LL * hashValue * BASE + ch) % MOD;
    }

    return hashValue;
}

/**
 * 计算字符串的前缀哈希值
 * @param str 输入字符串
 * @return 字符串的前缀哈希值数组
 */
std::vector<int> calculatePrefixHash(const std::string& str) 
{
    int n = str.size();
    std::vector<int> prefixHash(n + 1, 0);

    for (int i = 0; i < n; i++) 
    {
        prefixHash[i + 1] = (1LL * prefixHash[i] * BASE + str[i]) % MOD;
    }

    return prefixHash;
}

/**
 * 计算子串的哈希值
 * @param prefixHash 字符串的前缀哈希值数组
 * @param left 子串的左边界
 * @param right 子串的右边界
 * @return 子串的哈希值
 */
int calculateSubstringHash(const std::vector<int>& prefixHash, int left, int right) 
{
    int hashValue = (prefixHash[right] - 1LL * prefixHash[left] * power(BASE, right - left) % MOD + MOD) % MOD;
    return hashValue;
}

/**
 * 计算 x 的 n 次方
 * @param x 底数
 * @param n 指数
 * @return x 的 n 次方
 */
int power(int x, int n) 
{
    int result = 1;
    while (n > 0) 
    {
        if (n % 2 == 1) 
        {
            result = (1LL * result * x) % MOD;
        }
        x = (1LL * x * x) % MOD;
        n /= 2;
    }
    return result;
}

int main() 
{
    std::string str = "abcde";
    std::vector<int> prefixHash = calculatePrefixHash(str);

    // 计算整个字符串的哈希值
    int hashValue = calculateHash(str);
    std::cout << "Hash Value of the entire string: " << hashValue << std::endl;

    // 计算子串的哈希值（示例：从位置 1 到位置 3 的子串）
    int left = 1, right = 4;
    int substringHash = calculateSubstringHash(prefixHash, left, right);
    std::cout << "Hash Value of the substring [" << left << ", " << right << "): " << substringHash << std::endl;

    return 0;
}

6. 字典树 (Trie)

时间负责度： 插入、搜索、判断前缀操作均为 $O (m)$ ，其中 $m$ 为键长。

空间负责度： $\cdot m)$ ，其中 $n$ 为键的数量， $m$ 为键长。

功能： 字典树，又称为 Trie 树，是一种树形数据结构，用于高效地存储和检索集合中的键（通常是字符串）。每个节点表示一个字符，从根节点到叶子节点的路径构成一个键。字典树常用于搜索引擎、拼写检查等应用中。

#include <iostream>
#include <unordered_map>

class TrieNode 
{
public:
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode() : isEndOfWord(false) {}
};

class Trie 
{
private:
    TrieNode* root;

public:
    Trie() 
    {
        root = new TrieNode();
    }

    /**
     * 插入一个单词到 Trie 中
     * @param word 要插入的单词
     */
    void insert(const std::string& word) 
    {
        TrieNode* node = root;
        for (char ch : word) 
        {
            if (node->children.find(ch) == node->children.end()) 
            {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }

    /**
     * 搜索一个单词是否存在于 Trie 中
     * @param word 要搜索的单词
     * @return 若存在，返回 true，否则返回 false
     */
    bool search(const std::string& word) 
    {
        TrieNode* node = root;
        for (char ch : word) 
        {
            if (node->children.find(ch) == node->children.end()) 
            {
                return false;
            }
            node = node->children[ch];
        }
        return node->isEndOfWord;
    }

    /**
     * 判断 Trie 中是否存在以指定前缀开头的单词
     * @param prefix 指定前缀
     * @return 若存在，返回 true，否则返回 false
     */
    bool startsWith(const std::string& prefix) 
    {
        TrieNode* node = root;
        for (char ch : prefix) 
        {
            if (node->children.find(ch) == node->children.end()) 
            {
                return false;
            }
            node = node->children[ch];
        }
        return true;
    }
};

int main() 
{
    Trie trie;

    // 插入单词
    trie.insert("apple");
    trie.insert("app");
    trie.insert("banana");

    // 搜索单词
    std::cout << "Search 'apple': " << (trie.search("apple") ? "Found" : "Not found") << std::endl;
    std::cout << "Search 'app': " << (trie.search("app") ? "Found" : "Not found") << std::endl;
    std::cout << "Search 'orange': " << (trie.search("orange") ? "Found" : "Not found") << std::endl;

    // 判断前缀
    std::cout << "Starts with 'app': " << (trie.startsWith("app") ? "Yes" : "No") << std::endl;
    std::cout << "Starts with 'ban': " << (trie.startsWith("ban") ? "Yes" : "No") << std::endl;
    std::cout << "Starts with 'ora': " << (trie.startsWith("ora") ? "Yes" : "No") << std::endl;

    return 0;
}

7. 前缀函数与 KMP 算法

7.1. 前缀函数

时间负责度： $O (n)$ ，其中 $n$ 为字符串的长度。

空间负责度： $O (n)$ 。

功能： 前缀函数是一种用于字符串匹配的辅助函数。给定一个字符串 s，前缀函数 pi 的第 i 个元素 pi[i] 表示 s[0...i] 的最长真前缀（不包括自身）与后缀相等的长度。前缀函数的计算可以使用 KMP 算法的一部分。

#include <iostream>
#include <vector>

// 计算字符串的前缀函数
std::vector<int> calculatePrefixFunction(const std::string& str) 
{
    int n = str.size();
    std::vector<int> pi(n, 0);

    for (int i = 1; i < n; i++) 
    {
        int j = pi[i - 1];
        while (j > 0 && str[i] != str[j]) 
        {
            j = pi[j - 1];
        }
        if (str[i] == str[j]) 
        {
            j++;
        }
        pi[i] = j;
    }

    return pi;
}

int main() 
{
    std::string str = "ababaca";
    std::vector<int> prefixFunction = calculatePrefixFunction(str);

    // 输出前缀函数的值
    std::cout << "Prefix Function Values: ";
    for (int value : prefixFunction) 
    {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

7.2. KMP 算法

时间负责度： $O (n + m)$ ，其中 $n$ 为文本串的长度， $m$ 为模式串的长度。

空间负责度： $O (m)$ 。

功能： KMP 算法中的前缀函数用于避免在不匹配时进行不必要的回溯。具体而言，如果在匹配的过程中某一位置不匹配，KMP 算法利用前缀函数找到一个可以跳跃的位置。

#include <iostream>
#include <vector>

// 计算字符串的前缀函数
std::vector<int> calculatePrefixFunction(const std::string& str) 
{
    int n = str.size();
    std::vector<int> pi(n, 0);

    for (int i = 1; i < n; i++) 
    {
        int j = pi[i - 1];
        while (j > 0 && str[i] != str[j]) 
        {
            j = pi[j - 1];
        }
        if (str[i] == str[j]) 
        {
            j++;
        }
        pi[i] = j;
    }

    return pi;
}

// KMP 算法
int kmpSearch(const std::string& text, const std::string& pattern) 
{
    int n = text.size();
    int m = pattern.size();
    std::vector<int> pi = calculatePrefixFunction(pattern);

    int i = 0, j = 0;
    while (i < n) 
    {
        if (pattern[j] == text[i]) 
        {
            i++;
            j++;
        }

        if (j == m) 
        {
            return i - j;  // 匹配成功，返回匹配的起始位置
        }

        // 不匹配时，更新 j
        if (i < n && pattern[j] != text[i]) 
        {
            if (j != 0) 
            {
                j = pi[j - 1];
            } 
            else 
            {
                i++;
            }
        }
    }

    return -1;  // 匹配失败
}

int main() 
{
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";

    int position = kmpSearch(text, pattern);
    if (position != -1) 
    {
        std::cout << "Pattern found at position: " << position << std::endl;
    } 
    else 
    {
        std::cout << "Pattern not found." << std::endl;
    }

    return 0;
}

8. Z 函数（扩展 KMP）

时间负责度： $O (n)$ ，其中 $n$ 为字符串的长度。

空间负责度： $O (n)$ 。

功能： Z 函数是一种字符串匹配的辅助函数，与 KMP 算法相似。给定一个字符串 s，Z 函数的第 i 个元素 z[i] 表示 s[0...i] 与 s 的最长公共前缀的长度。

#include <iostream>
#include <vector>

/**
 * 计算字符串的 Z 函数
 * @param str 输入字符串
 * @return Z 函数值数组
 */
std::vector<int> calculateZFunction(const std::string& str) 
{
    int n = str.size();
    std::vector<int> z(n, 0);

    int left = 0, right = 0;
    for (int i = 1; i < n; i++) 
    {
        // 如果当前位置在 right 的范围内，可以利用之前计算的值进行初始化
        if (i <= right) 
        {
            z[i] = std::min(right - i + 1, z[i - left]);
        }

        // 尝试继续匹配
        while (i + z[i] < n && str[z[i]] == str[i + z[i]]) 
        {
            z[i]++;
        }

        // 更新 right 和 left
        if (i + z[i] - 1 > right) 
        {
            left = i;
            right = i + z[i] - 1;
        }
    }

    return z;
}

int main() 
{
    std::string str = "abacabadabacaba";
    std::vector<int> zFunction = calculateZFunction(str);

    // 输出 Z 函数的值
    std::cout << "Z Function Values: ";
    for (int value : zFunction) 
    {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

9. 自动机

9.1. AC 自动机

时间复杂度：

插入模式串： $O (m * n)$ ，其中 $m$ 为模式串的平均长度， $n$ 为模式串的数量。
构建失败指针： $O (m * n)$ ，其中 $m$ 为模式串的平均长度， $n$ 为模式串的数量。
在文本中搜索模式串： $O (k + z)$ ，其中 $k$ 为文本长度， $z$ 为匹配的总次数。

**空间复杂度：**AC 自动机的空间复杂度主要由节点数量决定，取决于插入的模式串的数量和长度。在最坏情况下，空间复杂度为 $O (m * n)$ ，其中$ m$ 为模式串的平均长度， $n$ 为模式串的数量。

功能：

插入模式串：将模式串插入 AC 自动机。
构建失败指针：构建 AC 自动机中每个节点的失败指针，以便在搜索时进行跳跃。
在文本中搜索模式串：在给定文本中搜索所有插入的模式串，并返回匹配的位置。

#include <iostream>
#include <queue>
#include <unordered_map>

/**
 * AC 自动机节点
 */
class ACNode 
{
public:
    std::unordered_map<char, ACNode*> children;
    ACNode* fail;
    bool isEndOfWord;

    ACNode() : fail(nullptr), isEndOfWord(false) {}
};

/**
 * AC 自动机
 */
class ACAutomaton 
{
private:
    ACNode* root;

public:
    ACAutomaton() 
    {
        root = new ACNode();
    }

    /**
     * 插入一个模式串到 AC 自动机中
     * @param pattern 要插入的模式串
     */
    void insert(const std::string& pattern) 
    {
        ACNode* node = root;
        for (char ch : pattern) 
        {
            if (node->children.find(ch) == node->children.end()) 
            {
                node->children[ch] = new ACNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }

    /**
     * 构建 AC 自动机的失败指针
     */
    void buildFailurePointer() 
    {
        std::queue<ACNode*> q;
        for (auto& it : root->children) 
        {
            it.second->fail = root;
            q.push(it.second);
        }

        while (!q.empty()) 
        {
            ACNode* current = q.front();
            q.pop();

            for (auto& it : current->children) 
            {
                char ch = it.first;
                ACNode* child = it.second;
                q.push(child);

                ACNode* failNode = current->fail;
                while (failNode != nullptr && failNode->children.find(ch) == failNode->children.end()) 
                {
                    failNode = failNode->fail;
                }

                child->fail = (failNode != nullptr) ? failNode->children[ch] : root;
            }
        }
    }

    /**
     * 在文本中搜索模式串并返回匹配的位置
     * @param text 要搜索的文本
     * @return 匹配的位置
     */
    std::vector<int> search(const std::string& text) 
    {
        std::vector<int> positions;
        ACNode* current = root;

        for (int i = 0; i < text.size(); i++) 
        {
            char ch = text[i];

            while (current != nullptr && current->children.find(ch) == current->children.end()) 
            {
                current = current->fail;
            }

            if (current != nullptr) 
            {
                current = current->children[ch];
                if (current->isEndOfWord) 
                {
                    positions.push_back(i - pattern.size() + 1);
                }
            } 
            else 
            {
                current = root;
            }
        }

        return positions;
    }
};

int main() 
{
    ACAutomaton acAutomaton;

    // 插入模式串
    acAutomaton.insert("he");
    acAutomaton.insert("she");
    acAutomaton.insert("his");
    acAutomaton.insert("hers");

    // 构建 AC 自动机的失败指针
    acAutomaton.buildFailurePointer();

    // 在文本中搜索模式串
    std::string text = "ushers";
    std::vector<int> positions = acAutomaton.search(text);

    // 输出匹配的位置
    std::cout << "Pattern found at positions: ";
    for (int position : positions) 
    {
        std::cout << position << " ";
    }
    std::cout << std::endl;

    return 0;
}

9.2. 后缀数组 (SA)

**时间复杂度：**构建后缀数组： $O(n \log^2 n)$ ，其中 $n$ 为文本长度。

**空间复杂度：**后缀数组的空间复杂度为 $O (n)$ ，其中 $n$ 为文本长度。

**功能：**构建后缀数组：生成文本的后缀数组，用于高效解决多种字符串相关问题，如最长公共子串、最长重复子串等。

#include <iostream>
#include <vector>
#include <algorithm>

/**
 * 后缀数组节点
 */
struct Suffix 
{
    int index;
    int rank[2];
};

/**
 * 后缀数组比较器
 */
bool suffixComparator(const Suffix& a, const Suffix& b) 
{
    return (a.rank[0] == b.rank[0]) ? (a.rank[1] < b.rank[1]) : (a.rank[0] < b.rank[0]);
}

/**
 * 构建后缀数组
 */
std::vector<int> buildSuffixArray(const std::string& text) 
{
    int n = text.size();
    std::vector<Suffix> suffixes(n);

    for (int i = 0; i < n; i++) 
    {
        suffixes[i].index = i;
        suffixes[i].rank[0] = text[i] - 'a';
        suffixes[i].rank[1] = (i + 1 < n) ? (text[i + 1] - 'a') : -1;
    }

    std::sort(suffixes.begin(), suffixes.end(), suffixComparator);

    std::vector<int> indices(n, 0);

    for (int k = 4; k < 2 * n; k *= 2) 
    {
        int rank = 0;
        int prevRank = suffixes[0].rank[0];
        suffixes[0].rank[0] = rank;
        indices[suffixes[0].index] = 0;

        for (int i = 1; i < n; i++) 
        {
            if (suffixes[i].rank[0] == prevRank && suffixes[i].rank[1] == suffixes[i - 1].rank[1]) 
            {
                prevRank = suffixes[i].rank[0];
                suffixes[i].rank[0] = rank;
            } 
            else 
            {
                prevRank = suffixes[i].rank[0];
                suffixes[i].rank[0] = ++rank;
            }

            indices[suffixes[i].index] = i;
        }

        for (int i = 0; i < n; i++) 
        {
            int nextIndex = suffixes[i].index + k / 2;
            suffixes[i].rank[1] = (nextIndex < n) ? suffixes[indices[nextIndex]].rank[0] : -1;
        }

        std::sort(suffixes.begin(), suffixes.end(), suffixComparator);
    }

    std::vector<int> suffixArray(n);
    for (int i = 0; i < n; i++) 
    {
        suffixArray[i] = suffixes[i].index;
    }

    return suffixArray;
}

int main() 
{
    std::string text = "banana";
    std::vector<int> suffixArray = buildSuffixArray(text);

    // 输出后缀数组
    std::cout << "Suffix Array: ";
    for (int index : suffixArray) 
    {
        std::cout << index << " ";
    }
    std::cout << std::endl;

    return 0;
}

9.3. 后缀自动机 (SAM)

**时间复杂度：**向 SAM 中添加字符： $O (1)$ （均摊复杂度）。

**空间复杂度：**后缀自动机的空间复杂度主要由节点数量决定，取决于插入的字符串的长度。在最坏情况下，空间复杂度为 $O (n)$ ，其中 $n$ 为插入字符串的总长度。

**功能：**向 SAM 中添加字符：将字符逐个添加到后缀自动机中，维护有效状态。

#include <iostream>
#include <vector>
#include <unordered_map>

/**
 * 后缀自动机节点
 */
class SAMNode 
{
public:
    std::unordered_map<char, SAMNode*> children;
    SAMNode* suffixLink;
    int length;

    SAMNode() : suffixLink(nullptr), length(0) {}
};

/**
 * 后缀自动机
 */
class SAMAutomaton 
{
private:
    SAMNode* root;
    SAMNode* last;

public:
    SAMAutomaton() 
    {
        root = new SAMNode();
        last = root;
    }

    /**
     * 向 SAM 中添加一个字符
     * @param ch 要添加的字符
     */
    void addCharacter(char ch) 
    {
        SAMNode* newLast = new SAMNode();
        newLast->length = last->length + 1;

        SAMNode* current = last;
        while (current != nullptr && current->children.find(ch) == current->children.end()) 
        {
            current->children[ch] = newLast;
            current = current->suffixLink;
        }

        if (current == nullptr) 
        {
            newLast->suffixLink = root;
        } 
        else 
        {
            SAMNode* next = current->children[ch];
            if (current->length + 1 == next->length) 
            {
                newLast->suffixLink = next;
            } 
            else 
            {
                SAMNode* split = new SAMNode();
                split->length = current->length + 1;
                split->children = next->children;
                split->suffixLink = next->suffixLink;

                while (current != nullptr && current->children[ch] == next) 
                {
                    current->children[ch] = split;
                    current = current->suffixLink;
                }

                next->suffixLink = split;
                newLast->suffixLink = split;
            }
        }

        last = newLast;
    }
};

int main() 
{
    SAMAutomaton samAutomaton;

    // 向 SAM 中添加字符串 "abab"
    std::string str = "abab";
    for (char ch : str) 
    {
        samAutomaton.addCharacter(ch);
    }

    return 0;
}

9.4. 后缀平衡树

时间复杂度：

插入元素到平衡树： $O(\log n)$ ，其中 $n$ 为平衡树的节点数。
获取小于等于给定值的元素数量： $O(\log n)$ ，其中 $n$ 为平衡树的节点数。

**空间复杂度：**后缀平衡树的空间复杂度主要由节点数量决定，取决于插入的元素数量。在最坏情况下，空间复杂度为 $O (n)$ ，其中 $n$ 为插入的元素数量。

功能：

插入元素到平衡树：将元素插入到后缀平衡树中。
获取小于等于给定值的元素数量：统计平衡树中小于等于给定值的元素数量。

#include <iostream>
#include <vector>

/**
 * 后缀平衡树
 */
class SuffixBalancedTree 
{
private:
    struct Node 
    {
        int count;
        Node* left;
        Node* right;

        Node() : count(0), left(nullptr), right(nullptr) {}
    };

    Node* root;

    // 获取节点的计数
    int getCount(Node* node) 
    {
        return (node != nullptr) ? node->count : 0;
    }

    // 更新节点的计数
    void updateCount(Node* node) 
    {
        if (node != nullptr) 
        {
            node->count = getCount(node->left) + getCount(node->right) + 1;
        }
    }

    // 将一个元素插入到平衡树中
    Node* insert(Node* node, int value) 
    {
        if (node == nullptr) 
        {
            return new Node();
        }

        if (value < node->count) 
        {
            node->left = insert(node->left, value);
        } 
        else 
        {
            node->right = insert(node->right, value - node->count);
        }

        updateCount(node);
        return node;
    }

    // 在平衡树中查找小于等于给定值的元素的数量
    int rank(Node* node, int value) 
    {
        if (node == nullptr || value <= 0) 
        {
            return 0;
        }

        if (value >= node->count) 
        {
            return getCount(node->left) + getCount(node->right) + 1;
        }

        return rank(node->left, value);
    }

public:
    SuffixBalancedTree() : root(nullptr) {}

    /**
     * 插入一个元素到平衡树中
     * @param value 要插入的元素值
     */
    void insert(int value) 
    {
        root = insert(root, value);
    }

    /**
     * 获取小于等于给定值的元素的数量
     * @param value 给定值
     * @return 小于等于给定值的元素的数量
     */
    int rank(int value) 
    {
        return rank(root, value);
    }
};

int main() 
{
    SuffixBalancedTree suffixBalancedTree;

    // 向平衡树中插入一些元素
    suffixBalancedTree.insert(3);
    suffixBalancedTree.insert(1);
    suffixBalancedTree.insert(4);
    suffixBalancedTree.insert(1);
    suffixBalancedTree.insert(5);

    // 获取小于等于给定值的元素的数量
    int result1 = suffixBalancedTree.rank(2);
    int result2 = suffixBalancedTree.rank(5);

    std::cout << "Elements less than or equal to 2: " << result1 << std::endl;
    std::cout << "Elements less than or equal to 5: " << result2 << std::endl;

    return 0;
}

10. 广义后缀自动机

**时间复杂度：**添加字符操作的时间复杂度为 $O (n)$ ，其中 $n$ 为添加的字符总数。

**空间复杂度：**广义后缀自动机的空间复杂度主要由节点数量决定，取决于添加的字符总数和长度。在最坏情况下，空间复杂度为 $O (n)$ 。

功能：

向广义 SAM 中添加一个字符：将给定字符添加到广义后缀自动机中，更新其状态。
广义 SAM 主要用于处理多个字符串的后缀问题。

#include <iostream>
#include <vector>
#include <unordered_map>

/**
 * 广义后缀自动机节点
 */
class GSuffixAutomaton 
{
private:
    struct Node 
    {
        std::unordered_map<char, Node*> children;
        Node* suffixLink;
        int length;

        Node() : suffixLink(nullptr), length(0) {}
    };

    Node* root;
    Node* last;

public:
    GSuffixAutomaton() 
    {
        root = new Node();
        last = root;
    }

    /**
     * 向广义 SAM 中添加一个字符
     * @param ch 要添加的字符
     */
    void addCharacter(char ch) 
    {
        Node* newLast = new Node();
        newLast->length = last->length + 1;

        Node* current = last;
        while (current != nullptr && current->children.find(ch) == current->children.end()) 
        {
            current->children[ch] = newLast;
            current = current->suffixLink;
        }

        if (current == nullptr) 
        {
            newLast->suffixLink = root;
        } 
        else 
        {
            Node* next = current->children[ch];
            if (current->length + 1 == next->length) 
            {
                newLast->suffixLink = next;
            } 
            else 
            {
                Node* split = new Node();
                split->length = current->length + 1;
                split->children = next->children;
                split->suffixLink = next->suffixLink;

                while (current != nullptr && current->children[ch] == next) 
                {
                    current->children[ch] = split;
                    current = current->suffixLink;
                }

                next->suffixLink = split;
                newLast->suffixLink = split;
            }
        }

        last = newLast;
    }
};

int main() 
{
    GSuffixAutomaton gSuffixAutomaton;

    // 向广义 SAM 中添加字符串 "abab"
    std::string str = "abab";
    for (char ch : str) 
    {
        gSuffixAutomaton.addCharacter(ch);
    }

    return 0;
}

11. 后缀树

**时间复杂度：**创建后缀树： $O(n^2)$ ，其中 $n$ 为字符串的长度。

**空间复杂度：**后缀树的空间复杂度主要由节点数量决定，取决于字符串的长度。在最坏情况下，空间复杂度为 $O(n^2)$ 。

**功能：**创建后缀树：高效地存储一个字符串的所有后缀。

#include <iostream>
#include <unordered_map>
#include <vector>

class SuffixTree 
{
private:
    struct Node 
    {
        int start;
        int* end;
        std::unordered_map<char, Node*> children;

        Node(int start, int* end = nullptr) : start(start), end(end) {}
    };

    Node* root;
    Node* lastNewNode;
    int* lastEnd;
    int activeLength;
    int activeNode;
    int remainder;

    // 创建一个新节点
    Node* createNode(int start, int* end = nullptr) 
    {
        return new Node(start, end);
    }

    // 扩展当前活跃点的子节点
    void extendSuffixTree(int index) 
    {
        lastNewNode = nullptr;
        remainder++;

        while (remainder > 0) 
        {
            if (activeLength == 0) 
            {
                activeNode = index;
            }

            if (root->children.find(text[index]) == root->children.end()) 
            {
                root->children[text[index]] = createNode(index, &leafEnd);
                addSuffixLink(activeNode);
            } 
            else 
            {
                Node* next = root->children[text[index]];
                if (walkDown(next)) 
                {
                    continue;
                }

                if (text[next->start + activeLength] == text[index]) 
                {
                    if (lastNewNode != nullptr && activeNode != root) 
                    {
                        addSuffixLink(activeNode);
                        lastNewNode = nullptr;
                    }

                    activeLength++;
                    break;
                }

                splitNode(next);
            }

            remainder--;
            if (activeNode == root && activeLength > 0) 
            {
                activeLength--;
                activeEdge = index - remainder + 1;
            } 
            else if (activeNode != root) 
            {
                activeNode = suffixLink[activeNode];
            }
        }
    }

    // 检查当前节点是否包含给定的边
    bool walkDown(Node* node) 
    {
        if (activeLength >= edgeLength(node)) 
        {
            activeEdge += edgeLength(node);
            activeLength -= edgeLength(node);
            activeNode = node->children[text[activeEdge]]->start;
            return true;
        }
        return false;
    }

    // 获取当前节点的边的长度
    int edgeLength(Node* node) 
    {
        return *(node->end) - node->start + 1;
    }

    // 添加一个后缀链接
    void addSuffixLink(int node) 
    {
        if (lastNewNode != nullptr) 
        {
            lastNewNode->suffixLink = node;
        }
        lastNewNode = node;
    }

    // 分割节点
    void splitNode(Node* node) 
    {
        int nextIndex = node->start + activeLength - 1;
        char nextChar = text[nextIndex];

        Node* split = createNode(node->start, &nextIndex);
        root->children[text[node->start]] = split;

        Node* leaf = createNode(index, &leafEnd);
        split->children[nextChar] = leaf;

        node->start += activeLength;
        split->children[text[node->start]] = node;

        addSuffixLink(split);
    }

public:
    SuffixTree(const std::string& str) 
    {
        root = createNode(0);
        lastNewNode = nullptr;
        lastEnd = nullptr;
        activeNode = 0;
        activeEdge = -1;
        activeLength = 0;
        remainder = 0;
        leafEnd = -1;
        text = str;
        leafEnd = text.size() - 1;

        for (int i = 0; i < text.size(); i++) 
        {
            extendSuffixTree(i);
        }
    }

    // 其他操作（例如搜索特定模式等）可在此添加
};

int main() 
{
    std::string text = "banana";
    SuffixTree suffixTree(text);

    // 在这里可以进行其他后缀树相关的操作

    return 0;
}

12. Manacher 算法

时间复杂度： $O (n)$ ，其中 $n$ 为字符串的长度。

空间复杂度： $O (n)$ 。

**功能：**找到一个字符串中的最长回文子串。

#include <iostream>
#include <vector>

// 预处理字符串，插入特殊字符 '#'
std::string preprocessString(const std::string& s) 
{
    std::string processed = "#";
    for (char ch : s) 
    {
        processed += ch;
        processed += '#';
    }
    return processed;
}

// Manacher 算法
std::string findLongestPalindrome(const std::string& s) 
{
    std::string processed = preprocessString(s);
    int n = processed.size();

    std::vector<int> p(n, 0);  // 记录每个位置的回文半径
    int center = 0;  // 当前最长回文串的中心位置
    int rightmost = 0;  // 最长回文串的右边界

    for (int i = 0; i < n; i++) 
    {
        // 根据对称性找到 i 关于 center 的对称位置
        int mirror = 2 * center - i;

        // 如果 i 在当前最长回文串的右边界内，可以利用对称性得到一个初始值
        if (i < rightmost) 
        {
            p[i] = std::min(rightmost - i, p[mirror]);
        }

        // 尝试扩展以 i 为中心的回文串
        while (i - p[i] > 0 && i + p[i] < n - 1 && processed[i - p[i] - 1] == processed[i + p[i] + 1]) 
        {
            p[i]++;
        }

        // 如果新的回文串的右边界超过当前最长回文串的右边界，更新 center 和 rightmost
        if (i + p[i] > rightmost) 
        {
            center = i;
            rightmost = i + p[i];
        }
    }

    // 找到 p 中的最大值和对应的位置
    int maxRadius = 0;
    int centerIndex = 0;
    for (int i = 0; i < n; i++) 
    {
        if (p[i] > maxRadius) 
        {
            maxRadius = p[i];
            centerIndex = i;
        }
    }

    // 提取原始字符串中的最长回文子串
    int start = (centerIndex - maxRadius) / 2;
    return s.substr(start, maxRadius);
}

int main() 
{
    std::string str = "babad";
    std::string longestPalindrome = findLongestPalindrome(str);
    std::cout << "Longest Palindrome: " << longestPalindrome << std::endl;

    return 0;
}

13. 回文树

**时间复杂度：**构建回文树的时间复杂度为 $O (n)$ ，其中 $n$ 为字符串的长度。

**空间复杂度：**回文树的空间复杂度为 $O (n)$ 。

**功能：**回文树是一种专门用于处理回文串的数据结构，用于高效解决多种回文串相关的问题。

#include <iostream>
#include <vector>
#include <unordered_map>

class PalindromeTree 
{
private:
    struct Node 
    {
        std::unordered_map<char, Node*> children;
        int length;  // 长度
        int suffixLink;  // 后缀链接
        int occurrence;  // 出现次数

        Node() : length(0), suffixLink(0), occurrence(0) {}
    };

    std::string text;
    std::vector<Node> tree;
    int last;  // 最后一个添加的节点

    // 添加一个字符到回文树中
    void addCharacter(int position) 
    {
        int current = last;
        while (true) 
        {
            int left = position - tree[current].length - 1;
            if (left >= 0 && text[left] == text[position]) 
            {
                break;
            }
            current = tree[current].suffixLink;
        }

        if (tree[current].children.find(text[position]) != tree[current].children.end()) 
        {
            last = tree[current].children[text[position]]->suffixLink;
            return;
        }

        int newNode = tree.size();
        last = newNode;
        tree.emplace_back();
        tree[newNode].length = tree[current].length + 2;
        tree[current].children[text[position]] = newNode;

        if (tree[newNode].length == 1) 
        {
            tree[newNode].suffixLink = 1;  // 根节点的 suffixLink 是空节点
            tree[newNode].occurrence = 1;  // 新节点是一个长度为 1 的回文串
            return;
        }

        while (true) 
        {
            current = tree[current].suffixLink;
            int left = position - tree[current].length - 1;
            if (left >= 0 && text[left] == text[position]) 
            {
                tree[newNode].suffixLink = tree[current].children[text[position]];
                break;
            }
        }

        tree[newNode].occurrence = 1 + tree[tree[newNode].suffixLink].occurrence;
    }

public:
    PalindromeTree(const std::string& str) : text(str), last(0) 
    {
        // 初始化根节点和空节点
        tree.emplace_back();  // 根节点
        tree.emplace_back();  // 空节点

        // 设置初始状态
        last = 1;  // 根节点的 suffixLink 是空节点
        tree[0].suffixLink = 1;  // 空节点的 suffixLink 也是空节点

        for (int i = 0; i < text.size(); i++) 
        {
            addCharacter(i);
        }
    }

    // 其他操作（例如计算不同回文串的个数等）可在此添加
};

int main() 
{
    std::string text = "abbaaccbba";
    PalindromeTree palindromeTree(text);

    // 在这里可以进行其他回文树相关的操作

    return 0;
}

六、动态规划

1. 动态规划基础

关键思想： 将问题划分成子问题，并找到它们之间的关系，通过解决子问题来解决原问题。

经典问题： Fibonacci数列、最长上升子序列等。

状态转移方程： $d p [i] = f (d p [i - 1], d p [i - 2], ..., d p [0])$

动态规划基础包括定义状态、找到状态转移方程以及确定初始状态。通常， $d p [i]$ 表示问题规模为 $i$ 时的状态。

#include <iostream>
#include <vector>

using namespace std;

/**
 * Fibonacci数列的动态规划实现
 * @param n 输入的正整数
 * @return Fibonacci数列第n项的值
 */
int fibonacciDP(int n) 
{
    vector<int> dp(n + 1, 0);
    dp[1] = 1;

    for (int i = 2; i <= n; ++i) 
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

2. 记忆化搜索

记忆化搜索（Memoization） 是动态规划的一种实现方式，通过存储中间计算结果，避免重复计算。

状态转移方程： $\text{max}(dp[i], \text{dfs}(i-1) + \text{dfs}(i-2) + ... + \text{dfs}(0))$

记忆化搜索是在递归算法基础上引入缓存，防止重复计算。通过递归深度优先搜索，将中间结果保存在缓存中，避免重复计算。

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<int, int> memo;

/**
 * 记忆化搜索的斐波那契数列实现
 * @param n 输入的正整数
 * @return Fibonacci数列第n项的值
 */
int fibonacciMemo(int n) 
{
    if (n <= 1) 
        return n;

    if (memo.find(n) != memo.end()) 
        return memo[n];

    memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
    return memo[n];
}

3. 背包 DP

背包问题 是动态规划中的经典问题，包括 0/1 背包问题和完全背包问题。

3.1. 0/1背包

状态转移方程： $\text{max}(dp[i-1][j], dp[i-1][j-w[i]] + v[i])$

背包 DP 通常用于解决组合优化问题，其中 $d p [i] [j]$ 表示在前 $i$ 个物品中选择，背包容量为 $j$ 时的最优解。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 0/1背包问题的动态规划实现
 * @param weights 物品重量数组
 * @param values 物品价值数组
 * @param capacity 背包容量
 * @return 背包能够装载的最大价值
 */
int knapsack01DP(vector<int>& weights, vector<int>& values, int capacity) 
{
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; ++i) 
    {
        for (int w = 0; w <= capacity; ++w) 
        {
            if (weights[i - 1] <= w) 
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
            else 
                dp[i][w] = dp[i - 1][w];
        }
    }

    return dp[n][capacity];
}

3.2. 完全背包

状态转移方程： $d p [i] [j] = ma x (d p [i - 1] [j], d p [i] [j - w [i]] + v [i])$

每种物品都有无限件可用，其中 $d p [i] [j]$ 表示前 $i$ 种物品，背包容量为 $j$ 时的最大价值，$w[i] $表示第 $i$ 种物品的重量，$v[i] $表示第 $i$ 种物品的价值。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 完全背包问题求解函数
 * @param n 物品数量
 * @param capacity 背包容量
 * @param weights 物品重量数组
 * @param values 物品价值数组
 * @return 最大总价值
 */
int knapsackComplete(int n, int capacity, vector<int>& weights, vector<int>& values) 
{
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; ++i) 
    {
        for (int j = 0; j <= capacity; ++j) 
        {
            dp[i][j] = dp[i - 1][j];  // 不选第i件物品

            // 选第i件物品，状态转移
            for (int k = 1; k * weights[i - 1] <= j; ++k) 
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weights[i - 1]] + k * values[i - 1]);
            }
        }
    }

    return dp[n][capacity];
}

3.3. 分数背包

状态转移方程： $d p [i] [j] = ma x (d p [i - 1] [j], d p [i] [j - w [i]] + v [i])$

可以选取物品的一部分。，其中 $d p [i] [j]$ 表示前 $i$ 种物品，背包容量为 $j$ 时的最大价值，$w[i] $表示第 $i$ 种物品的重量，$v[i] $表示第 $i$ 种物品的价值。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Item 
{
    int weight;
    int value;
    double unitValue;

    Item(int w, int v) : weight(w), value(v), unitValue((double)v / w) {}
};

/**
 * 分数背包问题求解函数
 * @param n 物品数量
 * @param capacity 背包容量
 * @param items 物品数组
 * @return 最大总价值
 */
double knapsackFractional(int n, int capacity, vector<Item>& items) 
{
    // 按照单位价值降序排序
    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.unitValue > b.unitValue;
    });

    double maxValue = 0.0;
    for (int i = 0; i < n && capacity > 0; ++i) 
    {
        if (items[i].weight <= capacity) 
        {
            // 可以完全装入背包
            maxValue += items[i].value;
            capacity -= items[i].weight;
        } 
        else 
        {
            // 不能完全装入，按比例装入
            double fraction = (double)capacity / items[i].weight;
            maxValue += fraction * items[i].value;
            capacity = 0;  // 背包装满
        }
    }

    return maxValue;
}

4. 区间 DP

区间 DP 通常涉及在一个序列或数组的区间上进行状态转移，求解问题的最优解。

状态转移方程： $\text{min/max}(dp[i][k] \text{操作} dp[k+1][j])$

区间 DP 用于解决涉及区间操作的问题，其中 $d p [i] [j]$ 表示在区间 $[i, j]$ 上的最优解。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 区间 DP 的示例问题：石子合并问题
 * @param stones 石子序列
 * @return 合并石子的最小代价
 */
int minCostMergeStones(vector<int>& stones) 
{
    int n = stones.size();
    vector<int> prefixSum(n + 1, 0);
    for (int i = 0; i < n; ++i) 
    {
        prefixSum[i + 1] = prefixSum[i] + stones[i];
    }

    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int len = 2; len <= n; ++len) 
    {
        for (int i = 0; i + len <= n; ++i) 
        {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;

            for (int k = i; k < j; ++k) 
            {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j + 1] - prefixSum[i]);
            }
        }
    }

    return dp[0][n - 1];
}

5. DAG 上的 DP

DAG（有向无环图）上的 DP 解决的问题涉及到在有向无环图上的节点上进行状态转移，通常是通过拓扑排序确定计算顺序。

状态转移方程： $\text{max/min}(dp[j] \text{操作} \text{边权值})$

DAG 上的 DP 通常用于解决有向无环图上的问题。通过拓扑排序确定计算顺序，进行动态规划。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/**
 * DAG 上的 DP 的示例问题：最长路径问题
 * @param graph 有向无环图的邻接表表示
 * @param source 起点
 * @return 最长路径长度
 */
int longestPathDAG(vector<vector<pair<int, int>>>& graph, int source) 
{
    int n = graph.size();
    vector<int> inDegree(n, 0);
    vector<int> dp(n, 0);

    // 计算入度
    for (int u = 0; u < n; ++u) 
    {
        for (auto& edge : graph[u]) 
        {
            int v = edge.first;
            inDegree[v]++;
        }
    }

    // 拓扑排序
    queue<int> q;
    for (int u = 0; u < n; ++u) 
    {
        if (inDegree[u] == 0) 
            q.push(u);
    }

    while (!q.empty()) 
    {
        int u = q.front();
        q.pop();

        for (auto& edge : graph[u]) 
        {
            int v = edge.first;
            int weight = edge.second;

            // 更新最长路径
            dp[v] = max(dp[v], dp[u] + weight);

            // 减小入度
            if (--inDegree[v] == 0) 
                q.push(v);
        }
    }

    // 找到最长路径
    int maxPath = 0;
    for (int i = 0; i < n; ++i) 
    {
        maxPath = max(maxPath, dp[i]);
    }

    return maxPath;
}

6. 树形 DP

树形 DP 解决的问题通常是在树上进行状态转移，例如在树上求解最长路径、最大权重独立集等。

状态转移方程： $\text{max/min}(dp[v] \text{操作} \text{边权值})$

树形 DP 用于解决树结构上的问题，通过在树上进行动态规划转移。

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode 
{
    int val;
    vector<TreeNode*> children;
};

/**
 * 树形 DP 的示例问题：树上最大独立集
 * @param root 树的根节点
 * @return 最大独立集的大小
 */
int maxIndependentSet(TreeNode* root) 
{
    if (root == nullptr) 
        return 0;

    // 选择根节点
    int chooseRoot = 1;  // 根节点被选择，计数为1
    for (TreeNode* child : root->children) 
    {
        chooseRoot += maxIndependentSet(child->children);
    }

    // 不选择根节点
    int notChooseRoot = 0;
    for (TreeNode* child : root->children) 
    {
        notChooseRoot += maxIndependentSet(child);
    }

    return max(chooseRoot, notChooseRoot);
}

7. 状压 DP

状压 DP 通常用于处理集合的状态，将集合的状态用二进制表示，通过位运算进行状态转移。

状态转移方程： $\text{max/min}(dp[mask \text{去掉一位}][k] \text{操作} dp[当前状态][j])$

状压 DP 通常用于处理集合的状态，通过二进制位表示集合，进行状态转移。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 状压 DP 的示例问题：旅行商问题（Traveling Salesman Problem, TSP）
 * @param n 城市数量
 * @param graph 城市之间的距离矩阵
 * @return 最短路径长度
 */
int tsp(int n, vector<vector<int>>& graph) 
{
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    dp[1][0] = 0;  // 起点是0号城市

    for (int mask = 1; mask < (1 << n); ++mask) 
    {
        for (int u = 0; u < n; ++u) 
        {
            if ((mask & (1 << u)) == 0) 
                continue;

            for (int v = 0; v < n; ++v) 
            {
                if (u != v && (mask & (1 << v)) != 0) 
                {
                    dp[mask][v] = min(dp[mask][v], dp[mask ^ (1 << v)][u] + graph[u][v]);
                }
            }
        }
    }

    int minPath = INT_MAX;
    for (int v = 1; v < n; ++v) 
    {
        minPath = min(minPath, dp[(1 << n) - 1][v] + graph[v][0]);
    }

    return minPath;
}

8. 数位 DP

数位 DP 解决的问题通常涉及在数字的各个位上进行状态转移，例如计算某一范围内满足某一条件的数字个数。

状态转移方程： $\text{max/min}(dp[i-1][j'][k'] \text{操作} dp[i][j][k])$

数位 DP 用于处理数字的位上的状态转移，通常用于计算满足某种条件的数字。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 数位 DP 的示例问题：计算某一范围内满足某一条件的数字个数
 * @param limit 上界
 * @return 满足条件的数字个数
 */
int countNumbers(int limit) 
{
    vector<vector<int>> dp(2, vector<int>(2, 0));  // dp[i][j]表示在第i位，j=0表示是否达到上界，j=1表示是否已经有前导零

    // 初始化
    dp[0][0] = 1;

    // 动态规划
    for (int i = 1; i <= limit; ++i) 
    {
        vector<vector<int>> nextDp(2, vector<int>(2, 0));

        for (int j = 0; j < 2; ++j) 
        {
            for (int k = 0; k < 2; ++k) 
            {
                for (int d = 0; d <= 9; ++d) 
                {
                    if (j == 0 && d > i % 10) 
                        break;

                    int newJ = (j == 1 || d < i % 10) ? 1 : 0;
                    int newK = (d > 0) ? 1 : k;

                    nextDp[newJ][newK] += dp[j][k];
                }
            }
        }

        dp = move(nextDp);
    }

    return dp[0][0] + dp[1][0];
}

9. 插头 DP

插头 DP 解决的问题通常是在某个状态下通过插头的方式进行状态转移，例如排列组合问题。

状态转移方程： $\text{sum}(dp[i-1][k] \text{操作} dp[i][j-k])$

插头 DP 通常用于处理组合问题，通过插头的方式进行状态转移。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 插头 DP 的示例问题：插头排列组合问题
 * @param n 插头数量
 * @param m 插座数量
 * @return 排列组合的数量
 */
int plugDP(int n, int m) 
{
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    // 初始化
    for (int i = 0; i <= m; ++i) 
    {
        dp[0][i] = 1;
    }

    // 动态规划
    for (int i = 1; i <= n; ++i) 
    {
        for (int j = 1; j <= m; ++j) 
        {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
        }
    }

    return dp[n][m];
}

10. 计数 DP

计数 DP 解决的问题通常是在某个状态下计算满足条件的方案数。

状态转移方程： $d p [i] [j] = d p [i - 1] [j] + d p [i - 1] [j - 1]$

计数 DP 通常用于计算满足条件的方案数。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 计数 DP 的示例问题：数字组合问题
 * @param n 目标数字
 * @param k 组合数字个数
 * @return 满足条件的组合数
 */
int countCombination(int n, int k) 
{
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));

    // 初始化
    for (int i = 0; i <= n; ++i) 
    {
        dp[i][0] = 1;
    }

    // 动态规划
    for (int i = 1; i <= n; ++i) 
    {
        for (int j = 1; j <= k; ++j) 
        {
            // 选择当前数字或不选择当前数字
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }

    return dp[n][k];
}

11. 动态 DP

动态 DP 通常是指在不断变化的环境中进行状态转移，例如根据当前情况调整策略。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 动态 DP 的示例问题：股票买卖问题
 * @param prices 股票价格序列
 * @return 最大利润
 */
int maxProfit(vector<int>& prices) 
{
    int n = prices.size();
    if (n <= 1) 
        return 0;

    // 定义状态数组
    vector<int> dp(n, 0);

    // 动态规划
    for (int i = 1; i < n; ++i) 
    {
        dp[i] = max(dp[i - 1], dp[i - 1] + prices[i] - prices[i - 1]);
    }

    return dp[n - 1];
}

12. 概率 DP

概率 DP 解决的问题通常是在考虑不同概率情况下的状态转移，例如在游戏中考虑随机事件。

状态转移方程： $\text{max/min}(dp[i-1] \text{操作} \text{当前状态})$

动态 DP 通常指的是在不断变化的环境中进行状态转移，例如根据当前情况调整策略。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 概率 DP 的示例问题：骰子游戏
 * @param n 骰子数量
 * @param faces 骰子面数
 * @param target 目标点数
 * @return 达到目标点数的概率
 */
double diceGame(int n, int faces, int target) 
{
    vector<vector<double>> dp(n + 1, vector<double>(target + 1, 0));

    // 初始化
    dp[0][0] = 1.0;

    // 动态规划
    for (int i = 1; i <= n; ++i) 
    {
        for (int j = 1; j <= target; ++j) 
        {
            for (int k = 1; k <= faces && k <= j; ++k) 
            {
                dp[i][j] += dp[i - 1][j - k] * (1.0 / faces);
            }
        }
    }

    return dp[n][target];
}

13. DP 优化

DP 优化 包括一些技巧和优化策略，例如滚动数组、状态压缩等，用于降低空间复杂度或提高计算效率。

#include <iostream>
#include <vector>

using namespace std;

/**
 * DP 优化的示例问题：斐波那契数列
 * @param n 输入的正整数
 * @return Fibonacci数列第n项的值
 */
int fibonacciDPOptimized(int n) 
{
    if (n <= 1) 
        return n;

    int a = 0, b = 1;

    for (int i = 2; i <= n; ++i) 
    {
        int next = a + b;
        a = b;
        b = next;
    }

    return b;
}

本来还有数据结构和数论和图论的，但是CSDN上放不下

西安城市开发者社区

欢迎加入西安开发者社区！我们致力于为西安地区的开发者提供学习、合作和成长的机会。参与我们的活动，与专家分享最新技术趋势，解决挑战，探索创新。加入我们，共同打造技术社区！

更多推荐

猫头虎分享：小米大模型升级第二代MiLM2：从一代到二代，能力飞跃提升

西安城市开发者社区

猫头虎分享：Qwen2.5-Coder 系列模型运行与使用教程

西安城市开发者社区

猫头虎分享：2024年微信小程序注册和备案详细教程

西安城市开发者社区

所有评论(0)

查看更多评论

怠惰的弈方

@Lazy_ChessPlayer

已为社区贡献1条内容

算法竞赛模板———上（常规优化，排序，搜索，动态规划）

怠惰的弈方

算法竞赛模板

一、主函数与重命名模板

二、读写与输出的优化

1. 优化 cin 与 cout

2. 快速读入

3. 快速输出

三、排序

1. 选择排序

2. 冒泡排序

3. 插入排序

4. 快速排序

5. 归并排序

6. 堆排序

7. 计数排序

8. 基数排序

9. 桶排序

10. 希尔排序

11. 锦标赛排序

12. tim排序

13. 排序相关 STL

13.1. sort函数

13.2. stable_sort函数

13.3. partial_sort 函数

13.4. nth_element 函数

13.5. 堆操作

四、搜索

1、深度优先搜索

2、广度优先搜索

3. 双向搜索

4. 启发式搜索 (A*算法)

5. 迭代加深搜索

6. IDA* 算法

7. 回溯法

8. Dancing Links (DLX)

9. Alpha-Beta 剪枝

10. 优化

10.1. 记忆化搜索

五、字符串

1. 字符串部分简介

2. 字符串基础

字符串表示

字符串长度

字符串遍历

3. 标准库

4. 字符串匹配

4.1. KMP 算法

4.2. Boyer-Moore 算法

5. 字符串哈希

6. 字典树 (Trie)

7. 前缀函数与 KMP 算法

7.1. 前缀函数

7.2. KMP 算法

8. Z 函数（扩展 KMP）

9. 自动机

9.1. AC 自动机

9.2. 后缀数组 (SA)

9.3. 后缀自动机 (SAM)

9.4. 后缀平衡树

10. 广义后缀自动机

11. 后缀树

12. Manacher 算法

13. 回文树

六、动态规划

1. 动态规划基础

2. 记忆化搜索

3. 背包 DP

3.1. 0/1背包

3.2. 完全背包

3.3. 分数背包

4. 区间 DP

5. DAG 上的 DP

6. 树形 DP

7. 状压 DP

8. 数位 DP

9. 插头 DP

10. 计数 DP

11. 动态 DP

12. 概率 DP

1. 优化 `cin` 与 `cout`