算法刷题day36

2024-03-27 22:44
文章标签 算法 刷题 day36

本文主要是介绍算法刷题day36，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  • 引言
  • 一、道路与航线
  • 二、最优贸易
  • 三、选择最佳路线

引言

今天先是把之前还不熟的模板都写了一遍，写了才能体会到，其实模板写了背了其实还是不顶用，还是要有大量的刷题积累，才能把模板发挥出来，不然真的你都看不出来模型，你怎么去做。所以得大量的刷题啊，加油吧！

一、道路与航线

标签：图论、SPFA、Dijkstra、最短路

思路：这道题一看边权有负数，所以第一时间就想着用 S P F A SPFA SPFA 算法了，几乎就是模板，然后过了 14 16 \frac{14}{16} 1614​ 的数据，如果要是放在蓝桥杯里其实已经很不错了，但要是为 A C M ACM ACM 赛制的话，就等于没做，所以我们就要对其优化。这里采用的是 S P F A + S L E SPFA + SLE SPFA+SLE 优化，核心就是判断 d i s t [ j ] dist[j] dist[j] 和队头：如果 d i s t [ j ] < d i s t [ q . f r o n t ( ) ] dist[j]<dist[q.front()] dist[j]<dist[q.front()] ，那就入队头，否则入队尾。加这么点变化，常数就会变小，就刚好能过了。

题目描述：

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 T 个城镇，编号为 1∼T。这些城镇之间通过 R 条道路 (编号为 1 到 R) 和 P 条航线 (编号为 1 到 P) 连接。每条道路 i 或者航线 i 连接城镇 Ai 到 Bi，花费为 Ci。对于道路，0≤Ci≤10,000;然而航线的花费很神奇，花费 Ci 可能是负数(−10,000≤Ci≤10,000)。道路是双向的，可以从 Ai 到 Bi，也可以从 Bi 到 Ai，花费都是 Ci。然而航线与之不同，只可以从 Ai 到 Bi。事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从 Ai 到 Bi，那么保证不可能通
过一些道路和航线从 Bi 回到 Ai。由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇 S 把奶牛送到每个城镇的最便宜的方案。输入格式
第一行包含四个整数 T,R,P,S。接下来 R 行，每行包含三个整数（表示一个道路）Ai,Bi,Ci。接下来 P 行，每行包含三个整数（表示一条航线）Ai,Bi,Ci。输出格式
第 1..T 行：第 i 行输出从 S 到达城镇 i 的最小花费，如果不存在，则输出 NO PATH。数据范围
1≤T≤25000,1≤R,P≤50000,1≤Ai,Bi,S≤T
输入样例：
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
输出样例：
NO PATH
NO PATH
5
0
-95
-100

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 3e4+10, M = 5e4*3+10, INF = 0x3f3f3f3f;int n, R, P, S;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void spfa()
{memset(dist, 0x3f, sizeof dist);dist[S] = 0; st[S] = true;deque<int> q; q.push_front(S);while(q.size()){int t = q.front(); q.pop_front();st[t] = false;for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];if(dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if(!st[j]) {if(q.size() && dist[j] < dist[q.front()]) q.push_front(j);else q.push_back(j);st[j] = true;}}}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1 , sizeof h);cin >> n >> R >> P >> S;while(R--){int a,b,c; cin >> a >> b >> c;add(a,b,c), add(b,a,c);}while(P--){int a, b, c; cin >> a >> b >> c;add(a,b,c);}spfa();for(int i = 1; i <= n; ++i){if(dist[i] == INF) cout << "NO PATH" << endl;else cout << dist[i] << endl;}return 0;
}

二、最优贸易

标签：图论SPFA

思路：这道题刚开始我觉得就是找最大值和最小值一减就行了，虽然过了几个样例但明显不对，因为这是有路程顺序的，并且不是所有的路都是双向的，所以得模拟。我们可以用两个数组来记录当前结点及之前的点的最大值和最小值，然后分别一正一反搜两次，用 S P F A SPFA SPFA 算法，因为有可能第一次走到的点不是最优的，因为有可能退回来，所以得用 S P F A SPFA SPFA，剩余细节见代码。

题目描述：

C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到 C 国旅游。当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点
旅费。设 C 国 n 个城市的标号从 1∼n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出
这个水晶球，用赚取的差价当做旅费。因为阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。注意：本题数据有加强。输入格式
第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。接下来 m 行，每行有 3 个正整数，x，y，z，每两个整数之间用一个空格隔开。如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市 y 之间的双向道路。输出格式
一个整数，表示答案。数据范围
1≤n≤100000,1≤m≤500000,1≤各城市水晶球价格≤100
输入样例：
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
输出样例：
5

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5+10, M = 5e5*3+10, INF = 0x3f3f3f3f;int n, m;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dmin[N], dmax[N];
bool st[N];void add(int h[], int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void spfa(int h[], int dist[], int S, bool type)  //true为min 
{memset(st, 0, sizeof st);if(type) memset(dist, 0x3f, sizeof dmax);else memset(dist, 0xcf, sizeof dmin);queue<int> q;dist[S] = w[S], q.push(S), st[S] = true;while(q.size()){int t = q.front(); q.pop();st[t] = false;for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];if((type && dist[j] > min(dist[t], w[j])) || (!type && dist[j] < max(dist[t], w[j]))){if(type){dist[j] = min(dist[t], w[j]);}else{dist[j] = max(dist[t], w[j]);}if(!st[j]) {q.push(j);}}}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1, sizeof h);memset(rh, -1, sizeof rh);cin >> n >> m;for(int i = 1; i <= n; ++i) cin >> w[i];while(m--){int u,v,t; cin >> u >> v >> t;add(h,u,v), add(rh,v,u);if(t == 2) add(h,v,u), add(rh,u,v);}spfa(h, dmin, 1, true);spfa(rh, dmax, n, false);int res = 0;for(int i = 1; i <= n; ++i) {// cout << dmax[i] << " " << dmin[i] << endl;res = max(res, dmax[i] - dmin[i]);}cout << res << endl;return 0;
}

三、选择最佳路线

标签：最短路

思路：相当于给了一个图，然后求任意多个点到一个点的最短路，这里直接把边建成反向的，然后从终点做一遍最短路，然后在这多个起点中找最小值就行了。这里我把 S P F A SPFA SPFA 和 D i j k s t r a Dijkstra Dijkstra 算法都写了，见代码自行查看。

题目描述：

有一天，琪琪想乘坐公交车去拜访她的一位朋友。由于琪琪非常容易晕车，所以她想尽快到达朋友家。现在给定你一张城市交通路线图，上面包含城市的公交站台以及公交线路的具体分布。已知城市中共包含 n 个车站（编号1~n）以及 m 条公交线路。每条公交线路都是 单向的，从一个车站出发直接到达另一个车站，两个车站之间可能存在多条公交线路。琪琪的朋友住在 s 号车站附近。琪琪可以在任何车站选择换乘其它公共汽车。请找出琪琪到达她的朋友家（附近的公交车站）需要花费的最少时间。输入格式
输入包含多组测试数据。每组测试数据第一行包含三个整数 n,m,s，分别表示车站数量，公交线路数量以及朋友家附近车站的编号。接下来 m 行，每行包含三个整数 p,q,t，表示存在一条线路从车站 p 到达车站 q，用时为 t。接下来一行，包含一个整数 w，表示琪琪家附近共有 w 个车站，她可以在这 w 个车站中选择一个车站作为始发站。再一行，包含 w 个整数，表示琪琪家附近的 w 个车站的编号。输出格式
每个测试数据输出一个整数作为结果，表示所需花费的最少时间。如果无法达到朋友家的车站，则输出 -1。每个结果占一行。数据范围
n≤1000,m≤20000,1≤s≤n,0<w<n,0<t≤1000
输入样例：
5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1
输出样例：
1
-1

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1010, M = 2e5+10, INF = 0x3f3f3f3f;int n, m, S, k;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
int E[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}// void spfa()
// {
// 	memset(st, 0, sizeof st);
// 	memset(dist, 0x3f, sizeof dist);
// 	dist[S] = 0; st[S] = true;// 	queue<int> q; q.push(S);
// 	while(q.size())
// 	{
// 		int t = q.front(); q.pop();
// 		st[t] = false;// 		for(int i = h[t]; i != -1; i = ne[i])
// 		{
// 			int j = e[i];
// 			if(dist[j] > dist[t] + w[i])
// 			{
// 				dist[j] = dist[t] + w[i];
// 				if(!st[j]) st[j] = true, q.push(j);
// 			}
// 		}
// 	}
// }void dijkstra()
{memset(st, 0, sizeof st);memset(dist, 0x3f, sizeof dist);dist[S] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0,S});while(heap.size()){auto t = heap.top(); heap.pop();int v = t.x, p = t.y;if(st[p]) continue;st[p] = true;for(int i = h[p]; i != -1; i = ne[i]){int j = e[i];if(dist[j] > dist[p] + w[i]){dist[j] = dist[p] + w[i];heap.push({dist[j],j});}}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);while(cin >> n >> m >> S){memset(h, -1, sizeof h);while(m--){int a, b, c; cin >> a >> b >> c;add(b,a,c);}cin >> k;for(int i = 0; i < k; ++i){cin >> E[i];}dijkstra();
// 		spfa();int res = INF;for(int i = 0; i < k; ++i){int j = E[i];
// 			cout << dist[j] << " ";res = min(res, dist[j]);}if(res == INF) cout << -1 << endl;else cout << res << endl;}return 0;
}

这篇关于算法刷题day36的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/853637。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
最大公因数：欧几里得算法

最大公因数：欧几里得算法

简述         求两个数字 m和n 的最大公因数，假设r是m%n的余数，只要n不等于0，就一直执行 m=n，n=r 举例 以18和12为例 m n r18 % 12 = 612 % 6 = 06 0所以最大公因数为：6 代码实现 #include<iostream>using namespace std;/
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2