【蓝桥杯】蓝桥杯算法复习(三)

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

在这里插入图片描述

文章目录

  • 前言
  • 蓝桥杯复习(三)
    • 一、并查集
      • 复习
      • 练习:奶酪
    • 二、哈希
      • 复习
      • 练习:星空之夜
    • 三、单调栈
      • 复习
      • 练习:矩形牛棚
    • 四、树状数组
      • 复习
      • 结构与原理:
      • 向右移动:
      • 向左移动:
      • 练习:数星星
    • 五、状态压缩DP
      • 复习
      • 练习:毕业旅行问题
    • 六、线性DP
      • 复习
      • 练习:乌龟棋
    • 七、背包问题
      • 复习
      • 练习:货币系统
  • 总结

前言


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

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

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


蓝桥杯复习(三)


一、并查集


复习

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

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

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

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

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

  • 问:小虎小王是什么关系,小李小王是什么关系?

image-20230130203524181

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

image-20230130203119960

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

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

  • 逻辑结构

image-20230130210320997

  • 物理结构

数组模拟实现并查集。

  • 具体实现
  1. 初始化
  • 存储结构:数组
  • 初始化:数组元素全部初始化为-1
  • 下标i:从1号下标开始使用。
  • 存储数据p[i]孩子结点中存放父节点的下标,并查集的元素初始化为自身下标。
const int N = 100010;

int p[N]; 

for (int i = 1; i <= n; ++i) p[i] = i;
  1. 根结点查找

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

  1. 如果当前节点不是根节点,就递归地找到它的父节点,然后将它的父节点指向根节点。这样可以压缩路径,使得每个节点都直接指向根节点,从而提高了查找效率。
  2. 如果当前节点是根节点,直接返回自己的下标。
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
  1. 合并

将两个集合合并:

  1. 查找两个要合并元素的根节点,根节点相同则不用合并;
  2. 如果两个根节点不同,则将随便将其中一个集合的根节点连接到另一个集合根节点下。
void merge(int x, int y)
{
    p[find(x)] = find(y);
}

练习:奶酪

image-20240320095029950

🍬题目链接:奶酪

🍎算法思想

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

  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 ∗ 13 1 3 + b ∗ 13 1 2 + c ∗ 13 1 1 + d ∗ 13 1 0 a * 131^3 + b * 131^2 + c * 131^1 + d * 131^0 a1313+b1312+c1311+d1310
这样将一个字符串从左到右的哈希值都存到一个数组h[]中, h [ 0 ] = 0 , h [ 1 ] = a ∗ 13 1 0 , h [ 2 ] = a ∗ 13 1 1 + b ∗ 13 1 0 , h [ 3 ] = a ∗ 13 1 2 + b ∗ 13 1 1 + c ∗ 13 1 0 h[0] = 0,h[1] = a * 131^0,h[2] = a * 131^1 + b * 131^0,h[3] = a * 131^2 + b * 131^1 + c * 131^0 h[0]=0h[1]=a1310h[2]=a1311+b1310h[3]=a1312+b1311+c1310,依次类推就是字符串前缀哈希数组

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

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

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

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

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

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

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

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

练习:星空之夜

image-20240321105111256

🍬题目链接:星空之夜

🍎算法思想

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

  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),也就是,对序列中每个元素,找到下一个比它大的元素。

  • 逻辑结构

febfb1db746d4ac5838975f5fb19cdb2

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

  • 物理结构

数组模拟栈。

image-20230503215659185

  • 具体实现
  1. 初始化

st 为栈,top为栈顶下标。

image-20230503215659185

const int N = 100010;

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

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

  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压入栈中

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

练习:矩形牛棚

image-20240321235202086

🍬题目链接:矩形牛棚

🍎算法思想

这道题是一个经典的问题,通常被称为"最大矩形面积"问题。它的目标是在一个由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. 数据结构: 树状数组是一个数组,通常称为BITfenwick,其长度为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;
}

练习:数星星

image-20240326094608225

🍬题目链接:数星星

🍎算法思想

注意:本题使用的平面直角坐标系,而不是二维数组坐标系,所以在点1判断左下点的时候要注意 x 2 < = x 1 x_2 <= x_1 x2<=x1 && y 2 < = y 1 y_2 <= y_1 y2<=y1

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

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

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

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

🍊具体实现

#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 + 集合划分:将状态按照某种特定的规则划分成若干个集合,通过集合的状态转移来实现状态压缩。

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

image-20230220172836383

🍬原题链接:最短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]ki中除了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;
}

练习:毕业旅行问题

image-20240326235223353

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

🍎算法思想

本题与最短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]ki中除了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)等。在这些问题中,状态之间的转移可以通过线性关系来表示,从而可以利用线性动态规划的方法进行求解。

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

练习:乌龟棋

image-20240327144419594

🍬题目链接:乌龟棋

🍎算法思想

  • 状态定义:f(a, b, c, d)——使用了a张1格爬行卡,b张2格爬行卡,c张3格爬行卡,d张4格爬行卡后所得分数的最大值。
  • 状态划分:f(a, b, c, d)可以按最后一个使用的爬行卡种类进行划分,分为f(a - 1, b, c, d) + wf(a, b - 1, c, d) + wf(a, b, c - 1, d) + wf(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,所以最多计算 4 0 4 = 2 , 560 , 000 40^4=2,560,000 404=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个物品的价值。
  • 在分数背包问题中,状态转移方程稍有不同,但基本思想相同。

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

image-20230215211434903

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

🪅算法思想

  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;
}

练习:货币系统

image-20240327231139771

🍬题目链接:货币系统

🍎算法思想

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

  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
  • 背包问题

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

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

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

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


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/495271.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Elasticsearch:虚拟形象辅助和对话驱动的语音到 RAG 搜索

作者&#xff1a;来自 Elastic Sunile Manjee 搜索的演变 搜索已经从产生简单结果的简单文本查询发展成为容纳文本、图像、视频和问题等各种格式的复杂系统。 如今的搜索结果通过生成式人工智能、机器学习和交互式聊天功能得到增强&#xff0c;提供更丰富、更动态且与上下文相…

Linux 注入依赖环境

文章目录 配置依赖程序安装 JDK安装 Tomcat安装 mysql 配置依赖程序 下面配置依赖程序都以CentOS为例。 安装 JDK 可以直接使用 yum(CentOS) 直接进行安装。 先搜索&#xff0c;确定软件包的完整名称。 yum list | grep jdk再进行安装 进行安装的时候一定要先确保处在“管理…

循环神经网络之语言模型和数据集

总结重要知识点 在给定这样的文本序列时&#xff0c;语言模型&#xff08;language model&#xff09;的目标是估计序列的联合概率 语言模型是自然语言处理的关键。 元语法通过截断相关性&#xff0c;为处理长序列提供了一种实用的模型。 长序列存在一个问题&#xff1a;它们…

JS new Array.fill(new Array()) 创建二维数组 fill方法的坑

我们通常会通过如下方式来创建一个二维数据&#xff1a; const arr new Array(5).fill(new Array(2).fill(0))我们如果想要修改其中一个元素的值 arr[0][0] 1输出&#xff1a;   我们只想给arr[0][0]赋值&#xff0c;但是每一行数组为0的下标元素的值全部改变了&#xf…

循序渐进丨MogDB 对 Oracle DBLink兼容性增强

本特性自 MogDB 5.0.0版本开始引入&#xff0c;支持 Oracle DBLink语法&#xff0c;可以使用符号访问 Oracle 数据库中的表。 示 例 01 环境准备 MogDB 环境 已安装 MogDB 数据库。已安装oracle_fdw插件&#xff0c;具体安装方法参见oracle_fdw安装文档https://docs.mogdb.io/…

[Linux_IMX6ULL驱动开发]-基础驱动

驱动的含义 如何理解嵌入式的驱动呢&#xff0c;我个人认为&#xff0c;驱动就是嵌入式上层应用操控底层硬件的桥梁。因为上层应用是在用户态&#xff0c;是无法直接操控底层的硬件的。我们需要利用系统调用&#xff08;open、read、write等&#xff09;&#xff0c;进入内核态…

好看又好用,这 10 个宝藏 App 免费拿走不谢!

目录 1. 综合AI工具箱——HuluAI 2. 文本视频生成工具——Jujilu 3.翻译软件 —— TTime 4.专业录屏和直播软件 —— OBS Studio 5.开源跨平台轻量计时软件 —— wnr 6.开源跨平台绘图 —— Drawio 7.开源三维建模动画渲染 —— Blender 8.跨平台的多功能软件 —— Pear…

小满CRM怎么样,多少外贸公司在用?

我们在20年用过小满CRM&#xff0c;产品很明显是围绕着外贸业务场景设计的&#xff0c;功能很多&#xff0c;但价格相对来说也算贵的了&#xff0c;看了其他用户的使用感受发现小满的数据安全和服务器方面可能也有点问题。 我们最后选择了零代码平台自主搭建了一个CRM系统&…

4.Python数据分析—数据分析入门知识图谱索引(知识体系下篇)

4.Python数据分析—数据分析入门知识图谱&索引-知识体系下篇 一个人简介二机器学习基础2.1 监督学习与无监督学习2.1.1 监督学习&#xff1a;2.1.2 无监督学习&#xff1a; 2.2 特征工程2.3 常用机器学习算法概述2.3.1 监督学习算法&#xff1a;2.3.2 无监督学习算法&#…

拿下阿里面试:揭秘JVM对象引用的奥秘!

如有疑问或者更多的技术分享,欢迎关注我的微信公众号“知其然亦知其所以然”! 大家好,我是小米!今天我要和大家一起探讨的是JVM中的对象引用,这也是阿里巴巴面试中经常被问到的热门话题哦!在Java开发中,我们经常需要管理对象的引用,了解不同类型的引用对于优化内存、避…

【一】TensorFlow神经网络模型构建之神经元函数及优化方法

TensorFlow神经网络模型构建主要涉及如下几块&#xff1a;神经元函数、卷积函数、池化函数、分类函数、优化方法。下面分别对这几块进行展开说明&#xff1a; 神经元函数及优化方法 神经网络之所以能解决非线性问题&#xff08;如语音、图像识别等&#xff09;&#xff0c;本…

web学习笔记(四十七)

目录 1. node.js中的三个全局变量 1.1 global 1.2 __dirname 文件夹的绝对路径 1.3 __filename 文件名的绝对路径 2.模块化 2.1 什么是模块化 2.2 模块化的好处 3. Node.js 中模块化 3.1 Node.js 中的模块化规范 4. Node.js 中的模块作用域 4.1module 对象 4.2 mod…

自定义你的商店 – 设计WooCommerce商店的新方法

WooCommerce 8.8即将推出&#xff0c;带来了一种无需代码即可创建精美商店的新方法。向“自定义你的商店”问好&#xff0c;这是一项全新功能&#xff0c;将取代“个性化你的商店”入门步骤。 自定义你的商店将利用最新的WordPress站点编辑工具以及酷炫的新Pattern Assembler …

深兰科技陈海波:生成式AI,新一轮知识生产力革命

3月26日&#xff0c;AIoT创新技术赋能工业数字化高峰论坛在上海市宝山区临港南大数智中心隆重举行。活动吸引了诸多行业内的专家学者、企业家及金融投资机构、政府园区、用户等多位业界精英出席&#xff0c;共同探讨该领域面临的挑战与机遇&#xff0c;分享最新的科研成果和技术…

【信号处理】基于DGGAN的单通道脑电信号增强和情绪检测(tensorflow)

关于 情绪检测&#xff0c;是脑科学研究中的一个常见和热门的方向。在进行情绪检测的分类中&#xff0c;真实数据不足&#xff0c;经常导致情绪检测模型的性能不佳。因此&#xff0c;对数据进行增强&#xff0c;成为了一个提升下游任务的重要的手段。本项目通过DCGAN模型实现脑…

【动手学深度学习】深入浅出深度学习之线性神经网络

目录 &#x1f31e;一、实验目的 &#x1f31e;二、实验准备 &#x1f31e;三、实验内容 &#x1f33c;1. 线性回归 &#x1f33b;1.1 矢量化加速 &#x1f33b;1.2 正态分布与平方损失 &#x1f33c;2. 线性回归的从零开始实现 &#x1f33b;2.1. 生成数据集 &#x…

泛微表单添加自定义按钮

页面效果&#xff1a; 点击按钮&#xff0c;将参数字段对应的值传入链接中。 表单配置如下&#xff1a; 然后插入js代码块&#xff0c;代码如下&#xff1a; <script> jQuery(document).ready(function(){ //在表单的按钮单元格插入自定义属性&#xff1a;ID&#xff1…

三级等保建设技术方案-Word

1信息系统详细设计方案 1.1安全建设需求分析 1.1.1网络结构安全 1.1.2边界安全风险与需求分析 1.1.3运维风险需求分析 1.1.4关键服务器管理风险分析 1.1.5关键服务器用户操作管理风险分析 1.1.6数据库敏感数据运维风险分析 1.1.7“人机”运维操作行为风险综合分析 1.2…

云能耗管理系统在某高校建筑系统平台的开发与应用

摘要&#xff1a;依据本项目依托某学院的电能计量管理系统、给水计量监管系统以及供热计量管理系统等基础平台&#xff0c;制订了高等学校建筑能耗综合管理系统平台应用的总体框架和方案&#xff0c;该系统可以对校园建筑的各种用能情况进行实时监测、统计能耗、进行能效分析&a…

DVWA-CSRF通关教程-完结

DVWA-CSRF通关教程-完结 文章目录 DVWA-CSRF通关教程-完结Low页面使用源码分析漏洞利用 Medium源码分析漏洞利用 High源码分析漏洞利用 impossible源码分析 Low 页面使用 当前页面上&#xff0c;是一个修改admin密码的页面&#xff0c;只需要输入新密码和重复新密码&#xff…