每日一练c++题目日刊 | 第十一期
文章目录
- 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 > 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]的值。
状态转移方程如下：
d
p
[
i
]
[
j
]
=
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
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])
d
p
[
i
]
[
j
]
=
d
p
[
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]的值。
状态转移方程如下：
d
p
[
i
]
[
j
]
=
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
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])
d
p
[
i
]
[
j
]
=
d
p
[
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。
题目描述
给定一个由
n
n
n 个符号组成的序列，每个符号的价值为
a
i
a_i
ai，你的任务是将这些符号解码成一个数字。其中任意两个相邻的符号的价值的最小值不超过
9
9
9。
输入描述
第一行包含一个整数
n
n
n，表示符号的个数。
第二行包含
n
n
n 个整数
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \dots, a_n
a1,a2,…,an，表示每个符号的价值。
输出描述
输出一个数字，表示解码后的数字。
输入样例
5
1 2 3 4 5
输出样例
12345
解题思路
可以使用动态规划来解决这个问题。定义状态
d
p
i
dp_i
dpi 表示前
i
i
i 个符号的最小表示法。
使用二分的方法来枚举任意两个相邻的符号的价值的最小值的范围。对于每一个符号
a
i
a_i
ai，我们可以在
[
1
,
9
]
[1,9]
[1,9] 之间二分查找最小的
k
k
k，使得
k
+
d
p
i
−
1
k+dp_{i-1}
k+dpi−1 能够表示
a
i
a_i
ai。
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 > 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;
}
动态规划+贪心：最小代价带权图的最大点双
题目背景
在一张带权无向图中，你需要选择一个最大的点双使得它的代价最小。
你的任务是计算出这个最小代价。
题目描述
给定一张
n
n
n 个节点、
m
m
m 条边的带权无向图，边权为正整数。
你的任务是选择一个最大的点双使得它的代价最小。
输入描述
第一行包含两个整数
n
,
m
n, m
n,m，表示节点数和边数。
接下来
m
m
m 行，每行包含三个整数
u
,
v
,
w
u, v, w
u,v,w，表示一条从节点
u
u
u 到节点
v
v
v，权值为
w
w
w 的有向边。
输出描述
输出一个整数，表示选择一个最大的点双使得它的代价最小的最小代价。
输入样例
4 5
1 2 3
2 3 4
3 4 5
4 1 6
1 3 7
输出样例
7
解题思路
定义状态
d
p
i
,
S
dp_{i,S}
dpi,S 表示当前已经选择了集合
S
S
S 中的节点，且最后一个选择的节点为
i
i
i 时的最小代价。
我们可以使用贪心的思想来枚举下一个要选择的节点。
对于每一个点
i
i
i，我们可以遍历所有与之相连的点
j
j
j，更新状态
d
p
j
,
S
∪
j
=
min
(
d
p
j
,
S
∪
j
,
d
p
i
,
S
+
w
i
,
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)
最终，我们只需要枚举所有的点
i
i
i，找出
d
p
i
,
1
,
2
,
.
.
.
,
n
dp_{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;
}
贪心+二分：最大子矩形
题目背景
你有一个矩形，你需要找到最大的子矩形使得它的面积最小。
你的任务是计算出这个最小的面积。
题目描述
给定一个
n
n
n 行
m
m
m 列的矩阵，每个位置的值为
0
0
0 或
1
1
1。
你的任务是找到一个最大的子矩形使得它的面积最小。
输入描述
第一行包含两个整数
n
,
m
n, m
n,m，表示矩阵的行数和列数。
接下来
n
n
n 行，每行包含
m
m
m 个整数，表示矩阵的值。
输出描述
输出一个整数，表示找到一个最大的子矩形使得它的面积最小的最小面积。
输入样例
4 5
1 0 1 1 0
1 0 1 1 0
1 1 1 1 1
0 0 1 1 1
输出样例
4
解题思路
定义状态
d
p
i
,
j
dp_{i,j}
dpi,j 表示当前位置在
(
i
,
j
)
(i,j)
(i,j)，最大子矩形的最小面积。
使用二分的方法来枚举当前的矩形的高度
h
h
h。对于每一个位置
(
i
,
j
)
(i,j)
(i,j)，在
[
0
,
n
]
[0,n]
[0,n] 之间二分查找最小的
h
h
h，使得以
(
i
,
j
)
(i,j)
(i,j) 为左上角，高度为
h
h
h 的矩形能够被覆盖。
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 > 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;
}
贪心+二分：滑动窗口最大值
题目背景
你有一个长度为
n
n
n 的数组，你需要找到长度为
k
k
k 的滑动窗口中的最大值。
你的任务是在给定的数组中找到所有的滑动窗口的最大值。
题目描述
给定一个数组
a
a
a 和一个整数
k
k
k，你的任务是找到所有长度为
k
k
k 的滑动窗口中的最大值。
输入描述
第一行包含两个整数
n
,
k
n, k
n,k，表示数组的长度和滑动窗口的长度。
第二行包含
n
n
n 个整数，表示数组的值。
输出描述
输出一个整数，表示找到的所有滑动窗口的最大值。
输入样例
10 3
2 3 4 2 5 6 7 8 1 2
输出样例
4 4 4 5 5 6 7 8 8 8
解题思路
用贪心的思想来解决这个问题。
定义状态
d
p
i
dp_i
dpi 表示当前位置在
i
i
i，滑动窗口的最大值。
我们可以使用二分的方法来枚举当前的滑动窗口的左端点
l
l
l。对于每一个位置
i
i
i，我们可以在
[
i
−
k
+
1
,
i
]
[i-k+1,i]
[i−k+1,i] 之间二分查找最小的
l
l
l，使得
[
l
,
i
]
[l,i]
[l,i] 之间的所有数的最大值是
a
i
a_i
ai。
#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 > 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;
}
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/75fa41bf24.html
相关推荐
-
如何通过Java的Apache PDFBox库制作一个PDF表格模板并填充数据
要使用Java的Apache PDFBox库制作一个PDF表格模板并填充数据，你需要遵循以下步骤： 添加依赖：首先，确保你的项目中包含了Apache PDFBox的依赖。如果你使用…
-
利用Python中selenium库爬虫实现中国裁判文书网自动登录批量下载功能——最新版详细教程！！
目录 工具准备 Chrome浏览器 ChromeDriver驱动 什么是ChromeDriver 下载安装 首先，需要检查Chrome浏览器的版本。请按照以下步骤进行： 请记下这个…
-
【Java】快速排序
文章目录 一、什么是快速排序 二、基准元素的选择 1、选择第一个元素 2、随机选择 三、元素的交换 1、双边循环法 2、单边循环法 一、什么是快速排序 快速排序是由冒泡排序演变而来…
-
2、在vscode上创建第一个C++多文件编译工程（即如何添加task.json和launch.json文件到工程里面）
文章目录 1、新建一个工程目录 2、在vscode打开刚建立的工程目录，建立cpp文件 3、设置C/C++编译的选项:c_cpp_properties.json （1）鼠标点在.c…
-
低版本jdk运行高版本编译jar包失败(class file version 61.0), this version of the Java Runtime class file 52.0
省流：使用jdk1.8执行17编译的包，启动报错。 背景： 项目运行中难免出现服务器环节集成其它jar包的情况，而其它jar包的jdk版本可能和我们业务项目的jdk…
-
Pytorch实现GCN(基于PyTorch实现)
文章目录 前言 一、导入相关库 二、加载Cora数据集 三、定义GCN网络 3.1 定义GCN层 3.1.1 邻接矩阵A 3.1.2 度矩阵D 3.1.3 获取矩阵 D − 1 /…
-
【Java 进阶篇】JDBC插入数据详解
在Java应用程序中，与数据库交互是一项常见的任务。其中，插入数据操作是一种基本的数据库操作之一。本文将详细介绍如何使用Java JDBC（Java Database Connec…
-
Python利用pip安装tar.gz格式的离线资源包
Python利用pip安装tar.gz格式的离线资源包 2023年5月14日 下午7:52 • python 下面是Python利用pip安装tar.gz格式的离线资源包的完整攻略…
-
pytorch实战7：手把手教你基于pytorch实现VGG16
手把手教你基于pytorch实现VGG16（长文） 前言 最近在看经典的卷积网络架构，打算自己尝试复现一下，在此系列文章中，会参考很多文章，有些已经忘记了出处，所以就不贴链接了…
-
eclipse安装和配置环境教程（详细步骤）
一、下载与安装 1. 下载 我们可以在eclipse的官网上直接进行下载，地址如下：https://www.eclipse.org/downloads/ 大家可以选择一个适合自…
