文章目录

• Kruskal算法：最小生成树
• • 题目背景故事
  • 题目描述
  • 输入描述
  • 输出描述
  • 输入样例
  • 输出样例
  • 解题思路
  • C++代码
• 动态规划：最长公共子序列
• • 题目背景故事
  • 题目描述
  • 输入描述
  • 输出描述
  • 输入样例
  • 输出样例
  • 解题思路
  • C++代码
• 动态规划+二分：最小表示法
• • 题目背景故事
  • 题目描述
  • 输入描述
  • 输出描述
  • 输入样例
  • 输出样例
  • 解题思路
  • C++代码
• 动态规划+二分：最小表示法
• • 题目背景
  • 题目描述
  • 输入描述
  • 输出描述
  • 输入样例
  • 输出样例
  • 解题思路
  • C++代码
• 动态规划+贪心：最小代价带权图的最大点双
• • 题目背景
  • 题目描述
  • 输入描述
  • 输出描述
  • 输入样例
  • 输出样例
  • 解题思路
  • C++代码
• 贪心+二分：最大子矩形
• • 题目背景
  • 题目描述
  • 输入描述
  • 输出描述
  • 输入样例
  • 输出样例
  • 解题思路
  • C++代码
• 贪心+二分：滑动窗口最大值
• • 题目背景
  • 题目描述
  • 输入描述
  • 输出描述
  • 输入样例
  • 输出样例
  • 解题思路

Kruskal算法：最小生成树

题目背景故事

你是一名建筑工人，负责在一个城市中建造一座桥。你需要把这座桥连接的两个岸边的点连起来，并且要使得连接的边的权值和最小。

题目描述

给定一张带权的无向图，求出其最小生成树。

输入描述

第一行包含两个整数n和m，分别表示点数和边数。

接下来m行，每行包含三个整数u, v, w，表示一条从点u到点v的有向边，权值为w。

输出描述

输出最小生成树的权值和。

输入样例

4 5
1 2 3
1 3 4
4 2 6
4 3 5
2 3 7

输出样例

14

解题思路

这道题我们可以使用Kruskal算法来解决。Kruskal算法是一种用于求解最小生成树的算法，它的核心思想是将图中所有边按照权值从小到大排序，然后依次加入边，如果加入后不会形成环，就加入这条为了判断一条边是否会形成环，我们可以使用并查集来维护连通性。每次加入一条边时，我们先将两个端点所在的集合合并，然后判断两个端点是否在同一个集合中，如果不是，就加入这条边。

C++代码

#include 
#include 
#include using namespace std;const int N = 1010;struct Edge
{int u, v, w;
} edges[N];int p[N];int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{int n, m;cin >> n >> m;for (int i = 0; i < m; i ++ )cin >> edges[i].u >> edges[i].v >> edges[i].w;for (int i = 1; i <= n; i ++ ) p[i] = i;sort(edges, edges + m, [](Edge a, Edge b){ return a.w < b.w; });int res = 0;for (int i = 0; i < m; i ++ ){int u = edges[i].u, v = edges[i].v;int t1 = find(u), t2 = find(v);if (t1 != t2){p[t1] = t2;res += edges[i].w;}}cout << res << endl;return 0;
}

动态规划：最长公共子序列

题目背景故事

你是一名研究生，正在研究两个DNA序列的相似性。你需要找出这两个DNA序列的最长公共子序列，并确定它们的相似度。

题目描述

给定两个字符串A和B，求出它们的最长公共子序列的长度。

输入描述

第一行包含两个字符串A和B。

输出描述

输出最长公共子序列的长度。

输入样例

abcde
abcdf

输出样例

4

解题思路

这道题我们可以使用动态规划来解决。我们可以定义一个二维数组dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列的长度。

对于每一个dp[i][j]，我们可以由dp[i-1][j]和dp[i][j-1]转移而来，但是如果A[i]==B[j]，我们就可以加上dp[i-1][j-1]的值。

状态转移方程如下：

dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])dp[i][j]=\max(dp[i-1][j],dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i][j−1])

dp[i][j]=dp[i−1][j−1]+1(A[i]==B[j])dp[i][j]=dp[i-1][j-1]+1(A[i]==B[j])dp[i][j]=dp[i−1][j−1]+1(A[i]==B[j])

C++代码

#include 
#include using namespace std;const int N = 1010;char A[N], B[N];int dp[N][N];int main()
{cin >> A + 1 >> B + 1;int n = strlen(A + 1), m = strlen(B + 1);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ ){dp[i][j] = max(dp[i-1][j], dp[i][j-1]);if (A[i] == B[j]) dp[i][j] = dp[i-1][j-1] + 1;}cout << dp[n][m] << endl;return 0;
}

动态规划+二分：最小表示法

题目背景故事

你是一名研究生，正在研究两个DNA序列的相似性。你需要找出这两个DNA序列的最长公共子序列，并确定它们的相似度。

题目描述

给定两个字符串A和B，求出它们的最长公共子序列的长度。

输入描述

第一行包含两个字符串A和B。

输出描述

输出最长公共子序列的长度。

输入样例

abcde
abcdf

输出样例

4

解题思路

这道题我们可以使用动态规划来解决。我们可以定义一个二维数组dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列的长度。

对于每一个dp[i][j]，我们可以由dp[i-1][j]和dp[i][j-1]转移而来，但是如果A[i]==B[j]，我们就可以加上dp[i-1][j-1]的值。

状态转移方程如下：

dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])dp[i][j]=\max(dp[i-1][j],dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i][j−1])

dp[i][j]=dp[i−1][j−1]+1(A[i]==B[j])dp[i][j]=dp[i-1][j-1]+1(A[i]==B[j])dp[i][j]=dp[i−1][j−1]+1(A[i]==B[j])

C++代码

#include 
#include using namespace std;const int N = 1010;char A[N], B[N];int dp[N][N];int main()
{cin >> A + 1 >> B + 1;int n = strlen(A + 1), m = strlen(B + 1);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ ){dp[i][j] = max(dp[i-1][j], dp[i][j-1]);if (A[i] == B[j]) dp[i][j] = dp[i-1][j-1] + 1;}cout << dp[n][m] << endl;return 0;
}

动态规划+二分：最小表示法

题目背景

有一种古老的文字，是由一些简单的符号构成的。每个符号有一个价值，从左到右依次给出。你的任务是将这些符号解码成一个数字，其中任意两个相邻的符号的价值的最小值不超过9。

题目描述

给定一个由 nnn 个符号组成的序列，每个符号的价值为 aia_iai​，你的任务是将这些符号解码成一个数字。其中任意两个相邻的符号的价值的最小值不超过 999。

输入描述

第一行包含一个整数 nnn，表示符号的个数。

第二行包含 nnn 个整数 a1,a2,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​，表示每个符号的价值。

输出描述

输出一个数字，表示解码后的数字。

输入样例

5
1 2 3 4 5

输出样例

12345

解题思路

可以使用动态规划来解决这个问题。定义状态 dpidp_idpi​ 表示前 iii 个符号的最小表示法。

使用二分的方法来枚举任意两个相邻的符号的价值的最小值的范围。对于每一个符号 aia_iai​，我们可以在 [1,9][1,9][1,9] 之间二分查找最小的 kkk，使得 k+dpi−1k+dp_{i-1}k+dpi−1​ 能够表示 aia_iai​。

C++代码

#include 
#include using namespace std;const int N = 100010;int n;
int a[N];
int dp[N];int main()
{cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];memset(dp, 0x3f, sizeof dp);dp[0] = 0;for (int i = 1; i <= n; i ++ ){int l = 1, r = 9;while (l < r){int mid = l + r >> 1;if (a[i] - dp[i-1] < mid) r = mid;else l = mid + 1;}dp[i] = min(dp[i], dp[i-1] + l);}cout << dp[n] << endl;return 0;
}

动态规划+贪心：最小代价带权图的最大点双

题目背景

在一张带权无向图中，你需要选择一个最大的点双使得它的代价最小。

你的任务是计算出这个最小代价。

题目描述

给定一张 nnn 个节点、mmm 条边的带权无向图，边权为正整数。

你的任务是选择一个最大的点双使得它的代价最小。

输入描述

第一行包含两个整数 n,mn, mn,m，表示节点数和边数。

接下来 mmm 行，每行包含三个整数 u,v,wu, v, wu,v,w，表示一条从节点 uuu 到节点 vvv，权值为 www 的有向边。

输出描述

输出一个整数，表示选择一个最大的点双使得它的代价最小的最小代价。

输入样例

4 5
1 2 3
2 3 4
3 4 5
4 1 6
1 3 7

输出样例

7

解题思路

定义状态 dpi,Sdp_{i,S}dpi,S​ 表示当前已经选择了集合 SSS 中的节点，且最后一个选择的节点为 iii 时的最小代价。

我们可以使用贪心的思想来枚举下一个要选择的节点。

对于每一个点 iii，我们可以遍历所有与之相连的点 jjj，更新状态 dpj,S∪j=min⁡(dpj,S∪j,dpi,S+wi,j)dp_{j,S\cup{j}}=\min(dp_{j,S\cup{j}},dp_{i,S}+w_{i,j})dpj,S∪j​=min(dpj,S∪j​,dpi,S​+wi,j​)

最终，我们只需要枚举所有的点 iii，找出 dpi,1,2,...,ndp_{i,{1,2,...,n}}dpi,1,2,...,n​ 的最小值即可。

C++代码

#include 
#include 
#include using namespace std;const int N = 210;
const int M = N * N;
const int INF = 0x3f3f3f3f;int h[N], e[M], ne[M], w[M], idx;
int n, m;
int f[N][N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}void floyd()
{memset(f, 0x3f, sizeof f);for (int i = 1; i <= n; i ++ ) f[i][i] = 0;for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}int main()
{cin >> n >> m;while (m -- ){int a, b, c;cin >> a >> b >> c;add(a, b, c);f[a][b] = min(f[a][b], c);}floyd();int res = INF;for (int i = 1; i <= n; i ++ )res = min(res, f[i][i]);cout << res << endl;return 0;
}

贪心+二分：最大子矩形

题目背景

你有一个矩形，你需要找到最大的子矩形使得它的面积最小。

你的任务是计算出这个最小的面积。

题目描述

给定一个 nnn 行 mmm 列的矩阵，每个位置的值为 000 或 111。

你的任务是找到一个最大的子矩形使得它的面积最小。

输入描述

第一行包含两个整数 n,mn, mn,m，表示矩阵的行数和列数。

接下来 nnn 行，每行包含 mmm 个整数，表示矩阵的值。

输出描述

输出一个整数，表示找到一个最大的子矩形使得它的面积最小的最小面积。

输入样例

4 5
1 0 1 1 0
1 0 1 1 0
1 1 1 1 1
0 0 1 1 1

输出样例

4

解题思路

定义状态 dpi,jdp_{i,j}dpi,j​ 表示当前位置在 (i,j)(i,j)(i,j)，最大子矩形的最小面积。

使用二分的方法来枚举当前的矩形的高度 hhh。对于每一个位置 (i,j)(i,j)(i,j)，在 [0,n][0,n][0,n] 之间二分查找最小的 hhh，使得以 (i,j)(i,j)(i,j) 为左上角，高度为 hhh 的矩形能够被覆盖。

C++代码

#include 
#include 
#include using namespace std;const int N = 110;int n, m;
int a[N][N];
int h[N][N];
int l[N], r[N];
int st[N], top;int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )cin >> a[i][j];for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ ){if (!a[i][j]) h[i][j] = 0;else h[i][j] = h[i-1][j] + 1;}int res = 0;for (int i = 1; i <= n; i ++ ){top = 0;for (int j = 1; j <= m; j ++ ){while (top && h[i][st[top]] >= h[i][j]) top -- ;l[j] = st[top];st[ ++ top] = j;}top = 0;for (int j = m; j; j -- ){while (top && h[i][st[top]] >= h[i][j]) top -- ;r[j] = st[top];st[ ++ top] = j;}for (int j = 1; j <= m; j ++ )res = max(res, (r[j] - l[j] + 1) * h[i][j]);}cout<< res << endl;return 0;
}

贪心+二分：滑动窗口最大值

题目背景

你有一个长度为 nnn 的数组，你需要找到长度为 kkk 的滑动窗口中的最大值。

你的任务是在给定的数组中找到所有的滑动窗口的最大值。

题目描述

给定一个数组 aaa 和一个整数 kkk，你的任务是找到所有长度为 kkk 的滑动窗口中的最大值。

输入描述

第一行包含两个整数 n,kn, kn,k，表示数组的长度和滑动窗口的长度。

第二行包含 nnn 个整数，表示数组的值。

输出描述

输出一个整数，表示找到的所有滑动窗口的最大值。

输入样例

10 3
2 3 4 2 5 6 7 8 1 2

输出样例

4 4 4 5 5 6 7 8 8 8

解题思路

用贪心的思想来解决这个问题。

定义状态 dpidp_idpi​ 表示当前位置在 iii，滑动窗口的最大值。

我们可以使用二分的方法来枚举当前的滑动窗口的左端点 lll。对于每一个位置 iii，我们可以在 [i−k+1,i][i-k+1,i][i−k+1,i] 之间二分查找最小的 lll，使得 [l,i][l,i][l,i] 之间的所有数的最大值是 aia_iai​。

#include 
#include 
#include using namespace std;const int N = 1e5 + 10;int n, k;
int a[N];int main()
{cin >> n >> k;for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= n; i ++ ){int l = i - k + 1, r = i;while (l < r){int mid = l + r >> 1;if (a[mid] < a[i]) l = mid + 1;else r = mid;}cout << a[l] << " ";}return 0;
}