赞
踩
你是一名建筑工人,负责在一个城市中建造一座桥。你需要把这座桥连接的两个岸边的点连起来,并且要使得连接的边的权值和最小。
给定一张带权的无向图,求出其最小生成树。
第一行包含两个整数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算法是一种用于求解最小生成树的算法,它的核心思想是将图中所有边按照权值从小到大排序,然后依次加入边,如果加入后不会形成环,就加入这条为了判断一条边是否会形成环,我们可以使用并查集来维护连通性。每次加入一条边时,我们先将两个端点所在的集合合并,然后判断两个端点是否在同一个集合中,如果不是,就加入这条边。
#include <iostream> #include <algorithm> #include <cstring> 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]的值。
状态转移方程如下:
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])
#include <iostream> #include <cstring> 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])
#include <iostream> #include <cstring> 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。
#include <iostream> #include <cstring> 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; }
在一张带权无向图中,你需要选择一个最大的点双使得它的代价最小。
你的任务是计算出这个最小代价。
给定一张 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 的最小值即可。
#include <iostream> #include <cstring> #include <algorithm> 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 的矩形能够被覆盖。
#include <iostream> #include <cstring> #include <algorithm> 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; }
你有一个长度为 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 <iostream> #include <cstring> #include <algorithm> 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; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。