😀大家好，我是白晨，一个不是很能熬夜😫，但是也想日更的人✈。如果喜欢这篇文章，点个赞👍，关注一下👀白晨吧！你的支持就是我最大的动力！💪💪💪

前言

---

本文适合有一定算法基础，但是由于各种原因已经很久没有敲代码的同学。本文以复习+练习为主，旨在通过练习算法题快速复习已经遗忘的算法。即使不是参加蓝桥杯的同学，如果符合上面的条件，依然可以参考本文进行复习。

如果你是新手，可以参考白晨的算法专栏进行学习。

如果你想系统性进行复习，可关注白晨的蓝桥杯专栏进行学习。

---

蓝桥杯复习（三）

---

一、并查集

---

复习

并查集 （英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构 ，用于处理一些不交集 （Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：

• 查询：查询某个元素属于哪个集合，通常是返回集合内的一个"代表元素"。这个操作是为了判断两个元素是否在同一个集合之中。

• 合并：将两个集合合并为一个。

本篇文章只复习并查集的模拟实现，想具体了解并查集的同学可以参考这篇文章——【数据结构与算法】并查集。

举个例子，有小明、小亮、小虎、小李、小王、小孙六个学生，已知小明和小孙是同学，小王和小明是同学，小亮和小李是同学，小虎和小孙是同学。

• 问：小虎和小王是什么关系，小李和小王是什么关系？

按照常识，我们可以把互为同学的学生划入同一个集合，如果两个同学的名字在同一个集合中出现，那么这两个人互为同学。反之，两个人不是同学。

观察上图，小虎和小王是同学关系，小李和小王不是同学关系。

上面就是并查集的简单应用，并查集能够快速合并两个集合以及快速查询两个元素是否在一个集合中，时间复杂度在大量查询的情况下可以达到O(1)。

• 逻辑结构

• 物理结构

数组模拟实现并查集。

• 具体实现

1. 初始化

• 存储结构：数组
• 初始化：数组元素全部初始化为-1。
• 下标i：从1号下标开始使用。
• 存储数据p[i]：孩子结点中存放父节点的下标，并查集的元素初始化为自身下标。

const int N = 100010;

int p[N]; 

for (int i = 1; i <= n; ++i) p[i] = i;

2. 根结点查找

并查集最核心的操作就是查询元素集合的根，如果两个元素集合的根相同，说明两个元素在同一个集合中。子节点存放的是父节点的下标，只需要向上查找就能找到根。

1. 如果当前节点不是根节点，就递归地找到它的父节点，然后将它的父节点指向根节点。这样可以压缩路径，使得每个节点都直接指向根节点，从而提高了查找效率。
2. 如果当前节点是根节点，直接返回自己的下标。

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

3. 合并

将两个集合合并：

1. 查找两个要合并元素的根节点，根节点相同则不用合并；
2. 如果两个根节点不同，则将随便将其中一个集合的根节点连接到另一个集合根节点下。

void merge(int x, int y)
{
    p[find(x)] = find(y);
}

练习：奶酪

🍬题目链接：奶酪

🍎算法思想：

这个题目就是并查集的一个变体题目，可以这样思考：

1. 创造两个虚拟节点，一个是和奶酪底部相连的集合A，一个是和奶酪顶部相连的集合B。
2. 开始时，先将所有直接和奶酪底部/顶部相连的空洞分别加入上面的两个集合A、B。
3. 两两遍历所有的空洞，如果两个相连，则加入同一个集合。

一开始有两个集合A、B，如果这个奶酪可以走通，则A、B必可以通过上面的方式合为一个集合。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1010;

int T, n, h, r;

struct Node {
    int x, y, z;
}g[N];
int p[N];

int find(int x) 
{
    if (p[x] != x) p[x] = find(p[x]);
    
    return p[x];
}


int main()
{
    scanf("%d", &T);
    
    while (T--) 
    {
        scanf("%d%d%d", &n, &h, &r);
        
        for (int i = 0; i <= n + 1; ++i) p[i] = i;
        
        for (int i = 1; i <= n; ++i) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            g[i] = {x, y, z};
            
            if (z - r <= 0 && z + r >= 0) p[find(0)] = find(i);
            if (z - r <= h && z + r >= h) p[find(n + 1)] = find(i);
        }
        
        
        for (int i = 1; i <= n; ++i) 
        {
            for (int j = i + 1; j <= n; ++j)
            {
                LL dx = g[i].x - g[j].x, dy = g[i].y - g[j].y, dz = g[i].z - g[j].z;
                
                if (dx * dx + dy * dy + dz * dz <= 4 * (LL)r * r) p[find(i)] = find(j);
            }
        }
        
        if (find(0) == find(n + 1)) puts("Yes");
        else puts("No");
    }
    return 0;
}

---

二、哈希

---

复习

先来复习一下字符串哈希：

字符串前缀哈希是针对一个字符串的哈希，将字符串的字母视为 131 或者 13331 进制的数。如abcd，就是 $a\ast 131^3+b\ast 131^2+c\ast 131^1+d\ast 131^0$。
这样将一个字符串从左到右的哈希值都存到一个数组h[]中，$h[0]=0，h[1]=a\ast 131^0，h[2]=a\ast 131^1+b\ast 131^0，h[3]=a\ast 131^2+b\ast 131^1+c\ast 131^0$，依次类推就是字符串前缀哈希数组

• 那么这个哈希有什么用呢？

如果要求一个字符串和另一个字符串是否相等，一般做法就是逐个比较字符，时间复杂度为O(N)，如果使用两个字符串的哈希值比较，那么时间复杂度就能降低为O(1)。

但是这样有一个问题，字符串长度如果很大到达10w位左右，那么哈希值就是 $131^{10w}$ 的大小，非常夸张，这样的值如何保存呢？ 我们这里选择只保留 2^64 大小的值，相当于一个unsigned long long 的大小，但是这样保存的话就无法保证哈希值的唯一性，如果发生哈希冲突就无法比较两个字符串是否真的相等。

所以，这样的做法并不能保证完全正确，所以我们必须尽量避免冲突，做法就是 将字符串的字母视为 131 或者 13331 进制的数，而不是其他进制的数，有数学证明这个进制产生的冲突是最少的。

即使这种方法有瑕疵，但是并不能掩盖其优秀的能力，如 求一个字符串中 l1~r1 和 l2~r2 这两段子串是否相等
l1~r1 和 l2~r2 这两段子串的哈希值可以从字符串前缀哈希数组中求得：$h[l\sim r]=h[r]-h[l-1]\ast 131^{(r-l+1)}$​
比较两段哈希值，相等即可认为字符串相等

本次题目中同样使用了哈希的思想，但是哈希的方式不一样，并且十分难想，因为下面题目要求如果一个图形可以通过另一个对称和旋转得到，那么就将这两个图形视为相同的图形。所以，这个哈希函数必须要无视朝向和对称的差别，所有满足旋转和对称可以相互得到的图形必须要是一个哈希值。

下面题目中使用的哈希算法是一种简单但有效的方法，用于将连通块内的点集映射成一个唯一的标识符。以下是对这种哈希算法的详细解释：

1. 计算连通块内点的哈希值：
   • 让连通块内的所有点与其他点进行两两组合，并计算它们之间的欧几里得距离，将它们的欧几里得距离求和。
2. 正确性保证：
   • 即使两个连通块内的点集具有不同的朝向，只要每个点的相对距离不变，得到的哈希值就是相同的。

练习：星空之夜

🍬题目链接：星空之夜

🍎算法思想：

本题目其实分为两个部分：

1. 找连通块，注意星群的定义是只要有公共点，就是联通的，也就是平常说的八联通块。还记得扫雷这道题中我们是怎么寻找八联通块的吗？与那道题相同，我们直接使用Flood Fill算法，使用DFS实现，找到连通块中所有点的坐标。

2. 对连通块进行哈希，并根据哈希值进行字符映射。

   此哈希算法是一种简单但有效的方法，用于将连通块内的点集映射成一个唯一的标识符。以下是对这种哈希算法的详细解释：

   1. 计算连通块内点的哈希值：
      • 让连通块内的所有点与其他点进行两两组合，并计算它们之间的欧几里得距离，将它们的欧几里得距离求和。
   2. 正确性保证：
      • 即使两个连通块内的点集具有不同的朝向，只要每个点的相对距离不变，得到的哈希值就是相同的。

以下是函数分析：

1. 找八连通块：
   • 使用深度优先搜索（DFS）算法遍历输入的矩阵，找到所有连通块，并将连通块中的所有点的坐标保存在数组 q[] 中。
   • 在 DFS 函数中，以当前点为中心，遍历周围八个方向，将连通块内的所有点标记为已访问。
2. 哈希函数计算哈希值：
   • 定义了 get_distance() 函数用于计算两个点之间的欧几里得距离。
   • 在 get_hash() 函数中，对连通块内的所有点两两组合，计算它们之间的距离之和作为哈希值。
   • 这个哈希值的计算保证了不同连通块将具有不同的哈希值，即使它们的形状相同也是如此。
3. 哈希值映射为字符：
   • 使用 get_id() 函数将哈希值映射为一个字符，以便用于表示连通块。
   • 如果计算得到的哈希值已经存在于 tb[] 数组中，就返回相应的字符；否则，将该哈希值添加到 tb[] 数组中，并返回一个新的字符。
4. 主程序逻辑：
   • 主函数首先读取输入的矩阵的行数和列数。
   • 然后通过两个嵌套循环遍历整个矩阵，寻找所有的 ‘1’，即连通块的起始点。
   • 对于每个连通块，先使用 DFS 找到连通块内所有的点，然后计算哈希值，并将哈希值映射为一个字符。
   • 最后将矩阵中所有属于同一个连通块的点替换为相同的字符，表示该连通块。

🍊具体实现：

// 找八连通块 + 哈希
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef pair<int, int> PII;

#define x first
#define y second

const int N = 110;
const double eps = 1e-6;

int m, n;

char g[N][N];
PII q[N * N];
int cnt;

double get_distance(PII a, PII b)
{
    double dx = a.x - b.x, dy = a.y - b.y;
    
    return sqrt(dx * dx + dy * dy);
}

double get_hash()
{
    double res = 0;
    // 连通块中两两节点组合求距离
    for (int i = 0; i < cnt; ++i) 
        for (int j = i + 1; j < cnt; ++j)
            res += get_distance(q[i], q[j]);
    
    return res;
}

char get_id(double val)
{
    static double tb[30];
    static int asc = 0;
    
    for (int i = 0; i < asc; ++i)
        if (fabs(tb[i] - val) < eps)
            return 'a' + i;
    
    tb[asc++] = val;
    return 'a' + asc - 1;
}

void dfs(int x, int y) 
{
    if (g[x][y] == '0') return;
    
    g[x][y] = '0';
    q[cnt++] = {x, y};
    
    for (int i = x - 1; i <= x + 1; ++i) 
        for (int j = y - 1; j <= y + 1; ++j)
        {
            if (i < 0 || i >= n || j < 0 || j >= m) continue;
            dfs(i, j);
        }
}

int main()
{
    cin >> m >> n;
    
    for (int i = 0; i < n; ++i) cin >> g[i];
    
    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < m; ++j) 
        {
            if (g[i][j] == '1') 
            {
                cnt = 0;
                dfs(i, j); // 获取此连通块各点的坐标
                char c = get_id(get_hash()); // 获取要渲染的字符
                
                for (int k = 0; k < cnt; ++k) 
                {
                    int x = q[k].x, y = q[k].y;
                    g[x][y] = c;
                }
            }
        }
    }
    
    for (int i = 0; i < n; ++i) cout << g[i] << endl;
    return 0;
}

---

三、单调栈

---

复习

**单调栈是指栈内元素单调递增或单调递减。**具体来说，如果是单调递增栈，那么栈底到栈顶的元素就是从小到大排列的；如果是单调递减栈，那么栈底到栈顶的元素就是从大到小排列的。在使用单调栈时，我们可以利用这个特点来解决一些问题。

单调栈是一种和单调队列类似的数据结构。单调队列主要用于O(n)解决滑动窗口问题，单调栈则主要用于O(n)解决NGE问题（Next Greater Element），也就是，对序列中每个元素，找到下一个比它大的元素。

• 逻辑结构

上图为一个单调递增的栈。

• 物理结构

数组模拟栈。

• 具体实现

1. 初始化

st 为栈，top为栈顶下标。

const int N = 100010;

int st[N], top = 0; // 定义一个数组st和一个变量top，表示栈

2. 插入

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

1. 如果栈不为空且栈顶元素大于等于插入元素，那么就弹出栈顶元素，直到栈为空或者栈顶元素小于插入元素为止
2. 将插入元素入栈

例如，栈中自底向上的元素为 { 0, 11, 45, 81 } 。插入元素 14 时为了保证单调性需要依次弹出元素 45, 81 ，操作后栈变为 { 0, 11, 14 } 。

while (top > 0 && st[top] >= num) top--; // 如果栈不为空且栈顶元素大于等于num，那么就弹出栈顶元素，直到栈为空或者栈顶元素小于num为止
st[++top] = num; // 将num压入栈中

单调栈一般只用插入这个操作，出栈一般在插入的过程中就已经完成。

练习：矩形牛棚

🍬题目链接：矩形牛棚

🍎算法思想：

这道题是一个经典的问题，通常被称为"最大矩形面积"问题。它的目标是在一个由0和1组成的矩形网格中找到最大的全为0的矩形的面积。这个问题可以通过不同的方法来解决，其中一个比较高效的方法就是使用动态规划和单调栈。

思路概括如下：

1. 首先，我们读取输入，得到矩形的大小以及有1的格子的位置。
2. 我们需要计算出每个格子上方连续0的个数，这可以通过遍历矩形网格来完成。我们用一个数组来记录每个格子上方连续0的个数，这样我们就可以在O(1)的时间内得到任意格子上方连续0的个数。
3. 接下来，我们对于每一行，以当前行为底边，计算最大矩形面积。这可以通过单调栈来实现。对于每一行，我们维护一个单调递增的栈，栈中存放列的编号。遍历每个格子，如果当前格子的高度小于栈顶的格子高度，说明当前格子可以将栈中的部分格子弹出，并计算以这些弹出的格子为高度形成的矩形的面积。同时更新最大面积值。这样，我们可以在O(m)的时间内得到以当前行为底边的最大矩形面积。
4. 最后，我们输出得到的最大矩形面积即可。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3010;

int n, m, t;
int g[N][N], h[N][N];
int l[N], r[N], st[N];
int top;

int work(int k)
{
    int res = 0;
    top = 0;
    // 统计每个格子左边第一个比自己低的列
    for (int i = 1; i <= m; ++i) 
    {
        while (top && h[k][st[top]] >= h[k][i]) top--;
        
        if (!top) l[i] = 0;
        else l[i] = st[top];
        st[++top] = i;
    }
    
    top = 0;
    // 统计每个格子右边第一个比自己低的列
    for (int i = m; i > 0 ; --i) 
    {
        while (top && h[k][st[top]] >= h[k][i]) top--;
        
        if (!top) r[i] = m + 1;
        else r[i] = st[top];
        st[++top] = i;
    }
    
    // 矩形面积 = 高(h[k][i]) * 宽(r[i] - l[i] - 1)
    for (int i = 1; i <= m; ++i) res = max(res, h[k][i] * (r[i] - l[i] - 1));
    
    return res;
}

int main()
{
    scanf("%d%d%d", &n, &m, &t);
    
    for (int i = 0; i < t; ++i) 
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x][y] = 1;
    }
    
    // 统计每一个格子上面有多少个完好的格子
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) 
            if (!g[i][j]) 
            {
                h[i][j] = h[i - 1][j] + 1;
            }
        
    
    int res = 0;
    // 按每一行计算面积最大值（每行只关注自己及以上的行）
    for (int i = 1; i <= n; ++i) res = max(res, work(i));
    
    printf("%d", res);
    return 0;
}

---

四、树状数组

---

复习

树状数组（Binary Indexed Tree，BIT），又称为Fenwick树，是一种用于高效处理动态序列的数据结构，通常用于解决一些数值处理问题，比如累加和、区间修改和查询等。它能够在O(logN)的时间内完成单点更新和区间查询，其中N是序列的长度。

结构与原理：

树状数组的基本思想是通过将序列以一种特定的方式编码，使得每个元素能够“代表”一段区间的信息，从而在实现单点更新和区间查询时，能够通过简单的计算得到结果。

1. 数据结构： 树状数组是一个数组，通常称为BIT或fenwick，其长度为N+1，其中N是原始序列的长度。数组的下标从1开始，这样做是为了方便计算。
2. 编码： 对于每个元素i，其保存的是原始序列中一段区间的信息。具体来说，对于元素i，其代表的区间为[i - lowbit(i) + 1, i]，其中lowbit(i)表示i的最低位1所代表的值。例如，lowbit(6) = 2，因为6的二进制表示为110，最低位1所代表的值是2。
3. 更新操作： 单点更新操作是树状数组的核心。对于要更新的位置pos，我们需要更新的是代表该位置的所有区间。具体操作是，从pos开始，不断向右移动lowbit(pos)个单位，并将相应的值进行更新。这样做的目的是，使得在查询某个区间的时候，可以通过一系列的区间累加得到结果。
4. 查询操作： 区间查询操作也是树状数组的重要功能。对于查询区间[1, k]的累加和，我们需要从k开始，不断向左移动lowbit(k)个单位，将相应的区间累加和起来。这样做的原因是，在更新的过程中，每个元素保存的都是某个区间的累加和。

向右移动：

在树状数组中，向右移动意味着我们将当前位置pos加上lowbit(pos)，以转移到下一个代表不同区间的位置。

例如，假设我们在位置pos = 6，其二进制表示为110，那么lowbit(6) = 2。向右移动2个单位意味着将当前位置加上2，即pos = pos + lowbit(pos) = 6 + 2 = 8。此时，位置8代表的区间是[1, 8]。

这种向右移动的操作是为了确保我们能够覆盖到所有包含当前位置的区间。

向左移动：

在树状数组中，向左移动意味着我们将当前位置pos减去lowbit(pos)，以转移到前一个代表不同区间的位置。

例如，假设我们在位置pos = 8，其二进制表示为1000，那么lowbit(8) = 8。向左移动8个单位意味着将当前位置减去8，即pos = pos - lowbit(pos) = 8 - 8 = 0。此时，位置0代表的区间是空区间，我们已经到达了序列的起始位置。

向左移动的操作是为了逐步向前覆盖所有包含当前位置的区间，直到覆盖整个需要查询或更新的区间。

这种向左向右移动的操作保证了在更新或查询时，我们能够正确地覆盖到所有相关的区间，从而实现了树状数组的功能。

int tr[N];

// 返回x二进制的最后一个1
int lowbit(int x)
{
    return x & -x;
}

int query(int x) 
{
    int res = 0;
    // 查询就是将x末尾的1所形成的区间中的数加和
    for (int i = x; i; i -= lowbit(i)) 
        res += tr[i];
        
    return res;
}

void add(int x, int v) 
{
    // 修改一个数也就是将x节点和其祖先节点全部加上这个数
    for (int i = x; i < M; i += lowbit(i)) 
        tr[i] += v;
}

练习：数星星

🍬题目链接：数星星

🍎算法思想：

注意：本题使用的平面直角坐标系，而不是二维数组坐标系，所以在点1判断左下点的时候要注意 $x_2<=x_1$ && $y_2<=y_1$。

注意到题目中描述，坐标是按(y, x)的升序输入的，所以当一个点被输入时，它的所有左下点就已经被输入了，所以可以直接求解了。

如果要求解坐标为(x1, y1)的点左下有多少个点，如果使用暴力做法，时间复杂度就为$O(n^2)$了，会TL。所以，必须有一种能快速求出左下点数量的方法。

注意到，在输入到(x1, y1)求左下点数量，其实就是求前x1列所有点的总数，因为此时前x1列都是y小于等于y1的坐标，由于输入为升序，大于y1的点还没有被输入。

所以要一种可以快速计算出前x1列点数量，并且在后续增加点时也要能快速增加的数据结构，这也就轮到了树状数组登场了。树状数组查询前缀和以及修改一个数的时间复杂度均是$O(lo{g}_{2}n)$，正好符合我们的要求。只要能反应出这道题是树状数组可解的，这道题就很简单，具体实现见下。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15010, M = 32010;

int n;
// 树状数组中存储前i列中有多少个星星
int tr[M], level[N];

// 返回x二进制的最后一个1
int lowbit(int x)
{
    return x & -x;
}

int query(int x) 
{
    int res = 0;
    // 查询就是将x末尾的1所形成的区间中的数加和
    for (int i = x; i; i -= lowbit(i)) 
        res += tr[i];
        
    return res;
}

void add(int x, int v) 
{
    // 修改一个数也就是将x节点和其祖先节点全部加上这个数
    for (int i = x; i < M; i += lowbit(i)) 
        tr[i] += v;
}

int main()
{
    scanf("%d", &n);
    
    for (int i = 0; i < n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        x++; // 树状数组不能从0开始
        int ret = query(x);
        level[ret]++;
        // 修改第x列的星星数，一个星星加1
        add(x, 1);
    }
    
    for (int i = 0; i < n; ++i) 
        printf("%d\n", level[i]);
    return 0;
}

---

五、状态压缩DP

---

复习

状态压缩动态规划（State Compression Dynamic Programming）是一种优化动态规划算法的技术，通常用于处理状态空间较大的问题。在动态规划中，状态的数量可能随着问题规模的增长而指数级增加，这会导致算法的时间和空间复杂度变得不可接受。状态压缩动态规划通过巧妙地设计状态表示方式，将原本需要的大量状态信息压缩成较少的信息，从而减小算法的复杂度。

一般来说，状态压缩动态规划适用于以下情况：

1. 状态之间存在重叠子问题：即某个状态的计算可能依赖于前面某些状态的计算结果。
2. 状态之间存在子集关系：即某些状态的计算可以通过已计算的子集状态得到。
3. 状态空间较大但是状态之间存在某种性质，使得可以通过某种方式进行压缩。

常见的状态压缩技巧包括：

1. 位压缩（Bitmasking）：将状态用二进制位表示，每一位代表一个状态。这种方法适用于状态之间没有重叠的情况，例如旅行商问题（TSP）中的状态表示某个城市是否已经访问过。
2. 状态压缩数组：如果状态之间存在子集关系，可以用一个一维数组表示状态，通过状态转移方程逐步更新数组的值。
3. 状压DP + 集合划分：将状态按照某种特定的规则划分成若干个集合，通过集合的状态转移来实现状态压缩。

总的来说，状态压缩动态规划是一种高效处理动态规划问题的技术，在处理状态空间较大的问题时能够有效地降低算法的时间和空间复杂度。

🍬原题链接：最短Hamilton路径

🪅算法思想：

• 状态定义：f(i, j) —— 所有从0走到j，中间经历的所有结点为i(二进制状态表示)的路径的最小权值，例如i = 0b1101，代表走过0、2、3结点，没走过1号结点，k号结点在i中由i的从右到左第k位表示（k从0开始计）。

• 状态划分：将f(i,j)按照倒数第二个结点k来划分，可以表示为f(i-{j},k)+w[k][j]，k为i中除了j的其他结点。i-{j}是从二进制状态表示把j这个结点去掉，比如，i = 0b101，j是第二个结点，i-{j} 就意味着 101 - {100} = 001，也就是将第二个结点从状态i中去掉了。

• 状态转移：f(i, j) = min(f(i-{j}, k) + w[k][j]) 。

🪆代码实现：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 21, M = 1 << N;

int n;
int g[N][N];
int dp[M][N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &g[i][j]);
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0; // 从0到0，只经历了0这个路径
    for (int i = 1; i < 1 << n; ++i)
        for (int j = 0; j < n; ++j)
            if ((i >> j) & 1) // i路径中有j
            {
                int t = i - (1 << j); // 去掉j的二进制表示
                // 按照倒数第二个结点k来划分
                for (int k = 0; k < n; ++k)
                    if ((t >> k) & 1) dp[i][j] = min(dp[t][k] + g[k][j], dp[i][j]);
            }
    printf("%d\n", dp[(1 << n) - 1][n - 1]);
    return 0;
}

练习：毕业旅行问题

🍬题目链接：毕业旅行问题

🍎算法思想：

本题与最短Hamilton路径几乎一模一样，唯一区别是最后要加上回北京的费用。本题是状态压缩DP，状态划分参考最短Hamilton路径。

• 状态定义：f(i, j) —— 所有从0走到j，中间经历的所有结点为i(二进制状态表示)的路径的最小权值，例如i = 0b1101，代表走过0、2、3结点，没走过1号结点，k号结点在i中由i的从右到左第k位表示（k从0开始计）。

• 状态划分：将f(i,j)按照倒数第二个结点k来划分，可以表示为f(i-{j},k)+w[k][j]，k为i中除了j的其他结点。i-{j}是从二进制状态表示把j这个结点去掉，比如，i = 0b101，j是第二个结点，i-{j} 就意味着 101 - {100} = 001，也就是将第二个结点从状态i中去掉了。

• 状态转移：f(i, j) = min(f(i-{j}, k) + w[k][j]) 。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20, M = 1 << N, INF = 0x3f3f3f3f;

int n;
int g[N][N], f[M][N];

int main()
{
    // 北京这里我们将其设为0号点，其余节点也相应-1
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &g[i][j]);
    
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    
    // 因为从0号节点出发的，所以0号节点一定被遍历，所以路径状态i一定是奇数（要保证最低位为1，因为0号节点已经走过了）
    for (int i = 1; i < 1 << n; i += 2)
        for (int j = 0; j < n; ++j)
            if ((i >> j) & 1) // 如果路径i经过j，说明这个状态是合法的，求出这个状态的值
                for (int k = 0; k < n; ++k) // 枚举倒数第二个走过的节点
                    if ((i - (1 << j) >> k) & 1) // 如果此路径包含k节点，进行状态转移
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + g[k][j]);
    
    int res = INF;
    // 由于最后要回北京，所以遍历一遍f[(1 << n) - 1][i] + g[i][0]，让结果加上回北京的费用，选出最小值
    for (int i = 1; i < n; ++i) res = min(res, f[(1 << n) - 1][i] + g[i][0]);
    printf("%d", res);
    return 0;
}

---

六、线性DP

---

复习

线性动态规划（Linear Dynamic Programming，简称线性DP）是动态规划（Dynamic Programming，DP）的一种变体，通常用于解决一些特定类型的问题，其中状态之间存在某种线性关系。

在线性动态规划中，状态转移方程具有特殊的形式，通常是线性的，即状态之间的转移可以表示为一个线性方程或线性组合。这种特殊的形式使得问题的求解更加高效，因为可以利用线性代数的技巧进行优化。

线性动态规划通常用于解决一些经典的优化问题，如最长递增子序列（Longest Increasing Subsequence，LIS）、最长公共子序列（Longest Common Subsequence，LCS）等。在这些问题中，状态之间的转移可以通过线性关系来表示，从而可以利用线性动态规划的方法进行求解。

总的来说，线性动态规划是动态规划方法的一个重要变体，适用于特定类型的问题，通过利用状态之间的线性关系，可以更加高效地求解问题。

练习：乌龟棋

🍬题目链接：乌龟棋

🍎算法思想：

• 状态定义：f(a, b, c, d)——使用了a张1格爬行卡，b张2格爬行卡，c张3格爬行卡，d张4格爬行卡后所得分数的最大值。
• 状态划分：f(a, b, c, d)可以按最后一个使用的爬行卡种类进行划分，分为f(a - 1, b, c, d) + w、f(a, b - 1, c, d) + w、f(a, b, c - 1, d) + w、f(a-1, b, c, d - 1) + w，w为使用了a张1格爬行卡，b张2格爬行卡，c张3格爬行卡，d张4格爬行卡到达格子的分数。
• 状态转移：f(a, b, c, d) = max(f(a - 1, b, c, d) + w, f(a, b - 1, c, d) + w, f(a, b, c - 1, d) + w, f(a-1, b, c, d - 1) + w,)。

由于每种爬行卡的张数不会超过40，所以最多计算$40^4=2,560,000$次，所以是完全不会超时的。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 41, M = 360;

int n, m;
int w[M], s[5];
int f[N][N][N][N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    for (int i = 1; i <= m; ++i) {
        int x;
        scanf("%d", &x);
        s[x]++;
    }
    
    for (int A = 0; A <= s[1]; ++A) 
        for (int B = 0; B <= s[2]; ++B)
            for (int C = 0; C <= s[3]; ++C)
                for (int D = 0; D <= s[4]; ++D)
                {
                    int& x = f[A][B][C][D];
                    int sc = w[1 + A * 1 + B * 2 + C * 3 + D * 4];
                    x = sc;
                    
                    if (A) x = max(x, f[A - 1][B][C][D] + sc);
                    if (B) x = max(x, f[A][B - 1][C][D] + sc);
                    if (C) x = max(x, f[A][B][C - 1][D] + sc);
                    if (D) x = max(x, f[A][B][C][D - 1] + sc);
                }
                
    printf("%d", f[s[1]][s[2]][s[3]][s[4]]);
    return 0;
}

---

七、背包问题

---

复习

背包问题（Knapsack Problem）是一个经典的组合优化问题，通常有两个变种：0-1背包问题和分数背包问题。其基本思想是在给定的一组物品中选择一些物品放入一个容量有限的背包，以使得选入背包的物品价值之和最大化（或者在满足背包容量限制的前提下，使得选入背包的物品总重量最大化）。

动态规划方法：

• 这是解决背包问题最常用的方法之一。它通常通过构建一个二维的动态规划表来解决问题。
• 在0-1背包问题中，状态转移方程通常为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])，其中dp[i][j]表示在前i个物品中，容量为j的背包可以装的最大价值，weight[i]表示第i个物品的重量，value[i]表示第i个物品的价值。
• 在分数背包问题中，状态转移方程稍有不同，但基本思想相同。

由于今天的练习题是一个完全背包问题，所以我们来复习一下完全背包的思想。

🍬原题链接：完全背包问题

🪅算法思想：

1. 状态表示：

   • dp[i][j]：表示在前i个物品中，容量为j的背包可以装的最大价值。

2. 状态划分：

   • 对于每个物品i，可以选择装入背包或不装入背包。
   • 当选择装入第i个物品时，背包容量减少v[i]，价值增加w[i]；当选择不装入第i个物品时，背包容量不变，价值不变。

3. 状态转移：

   • 状态转移方程为：

     dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])
     

     • 第一项 dp[i-1][j] 表示不选择第i个物品时的最大价值。
     • 第二项 dp[i][j-v[i]] + w[i] 表示选择第i个物品时的最大价值，其中 dp[i][j-v[i]] 表示在容量为 j-v[i] 时能获得的最大价值，加上当前物品的价值 w[i]。

   • 通过比较两种情况的价值，选择价值更大的方案作为状态转移的结果。

对于完全背包问题，我们可以观察到状态转移方程中，当前行的状态只与上一行的状态有关。因此，我们可以仅使用一个一维数组来表示状态。

具体思路如下：

1. 我们定义一个一维数组 dp[]，其中 dp[j] 表示在容量为j的背包下可以获得的最大价值。
2. 在状态转移时，我们需要确保每个物品可以被选择多次，因此我们需要从小到大更新背包容量 j。
3. 对于每个物品 i，我们遍历背包容量 j，根据状态转移方程 dp[j] = max(dp[j], dp[j-v[i]] + w[i]) 更新 dp[j]。
4. 在更新 dp[j] 时，由于我们以前使用的是dp[i][j-v[i]] + w[i]，所以需要先把本行前面的值计算出来，所以需要顺序更新。

🪆代码实现：

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;

int v[N], w[N];
int dp[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; ++i)
        for (int j = v[i]; j <= m; ++j)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    printf("%d\n", dp[m]);
    return 0;
}

---

练习：货币系统

🍬题目链接：货币系统

🍎算法思想：

本道题就是完全背包的变式，所以下面就是完全背包的讲解：

1. 状态表示：

   • dp[i][j]：表示在前i个物品中，容量为j的背包可以装的最大价值。

2. 状态划分：

   • 对于每个物品i，可以选择装入背包或不装入背包。
   • 当选择装入第i个物品时，背包容量减少v[i]，价值增加w[i]；当选择不装入第i个物品时，背包容量不变，价值不变。

3. 状态转移：

   • 状态转移方程为：

     dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])
     

     • 第一项 dp[i-1][j] 表示不选择第i个物品时的最大价值。
     • 第二项 dp[i][j-v[i]] + w[i] 表示选择第i个物品时的最大价值，其中 dp[i][j-v[i]] 表示在容量为 j-v[i] 时能获得的最大价值，加上当前物品的价值 w[i]。

   • 通过比较两种情况的价值，选择价值更大的方案作为状态转移的结果。

对于完全背包问题，我们可以观察到状态转移方程中，当前行的状态只与上一行的状态有关。因此，我们可以仅使用一个一维数组来表示状态。

具体思路如下：

1. 我们定义一个一维数组 dp[]，其中 dp[j] 表示在容量为j的背包下可以获得的最大价值。
2. 在状态转移时，我们需要确保每个物品可以被选择多次，因此我们需要从小到大更新背包容量 j。
3. 对于每个物品 i，我们遍历背包容量 j，根据状态转移方程 dp[j] = max(dp[j], dp[j-v[i]] + w[i]) 更新 dp[j]。
4. 在更新 dp[j] 时，由于我们以前使用的是dp[i][j-v[i]] + w[i]，所以需要先把本行前面的值计算出来，所以需要顺序更新。

🍊具体实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010, M = 30;

int v, n;
long long f[N];

int main()
{
    cin >> v >> n;
    f[0] = 1;
    for (int i = 1; i <= v; ++i) 
    {
        int w;
        cin >> w;
        for (int j = w; j <= n; ++j) 
            f[j] += f[j - w];
    }
    
    cout << f[n] << endl;
    
    return 0;
}

---

总结

---

本周我们复习了：

• 并查集
• 哈希
• 单调栈
• 树状数组
• 状态压缩DP
• 线性DP
• 背包问题

如果解析有不对之处还请指正，我会尽快修改，多谢大家的包容。

如果大家喜欢这个系列，还请大家多多支持啦😋！

如果这篇文章有帮到你，还请给我一个大拇指 👍和小星星 ⭐️支持一下白晨吧！喜欢白晨【蓝桥杯】系列的话，不如关注👀白晨，以便看到最新更新哟！！！

我是不太能熬夜的白晨，我们下篇文章见。

---