算法训练1

01背包问题

背包状态方程----动态规划

二维dp

使用 f[i][j] = max(f[i-1][j] ,f[i-1][j - w[i]] + v[i]);

 伪代码:

int dp[100][100];
void test6() {int n;  //装备数量int m;  //背包容量int v[105], w[105]; //前面空间,后面价值for (int i = 1; i <= n; i++) {for (int j = m; j >= 0; j--) {if (j >= v[i]) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);}else {dp[i][j] = dp[i - 1][j];}}}
}

 其中,dp中的横坐标i代表的是第i个装备,纵坐标 j 为背包容量,由于这里dp一直记录的是最大的,所以可以优化为一维dp

 同理的一道题:

 使用一维dp,注意的是:进行更新 f[ ]时,要从后面开始更新,这样可以使用的f[j - v[i]] 全是上次草药的值,如果从小往大进行更新,会导致后面更新,装两次一样的草药。导致错误。

void test3() {int timeAll, num;scanf("%d%d", &timeAll, &num);int v[105],w[105];int f[1005];for (int i = 1; i <= num; i++) {scanf("%d %d", &v[i], &w[i]);}for (int i = 0; i <= timeAll; i++) {f[i] = 0;}for (int i = 1; i <= num; i++) {for (int j = timeAll; j >= 0; j--) {if (j >= v[i]) {f[j] = max(f[j], f[j - v[i]] + w[i]);}else {f[j] = f[j];}}}printf("%d", f[timeAll]);
}

桶排序+暴力处理

 这里就不断处理最大值,最大湿度衣服进行烘干,然后暴力执行。

//堆排序
int f[500005];
void test5() {int n, a, b;scanf("%d%d%d", &n, &a, &b);int max = 0, sum = 0,time = 0;for (int i = 1; i <= n; i++) {int k;scanf("%d", &k);f[k]++;if (k > max) {max = k;}}while (1) {if (max <= sum) {break;}f[max]--;if (max > b) {f[max - b] += 1;}while(f[max] == 0) {max--;}sum += a;time += 1;}printf("%d", time);}

二分答案:

题解 P2678 【跳石头】 - 洛谷专栏 (luogu.com.cn)icon-default.png?t=N7T8https://www.luogu.com.cn/article/08mxthsv

运用二分答案,进行枚举判断答案是否正确

比如:

 使用check函数检查答案是否正确,运用二分答案:两个要素

单调性,有界性。答案可以枚举出来

#define _CRT_SECURE_NO_WARNINGS 
#include<cstdio> 
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;
int H[1000005];
int N, M;
bool check2(int l) {int count = 0;for (int i = 1; i <= N; i++) {if (H[i] > l) {count += H[i] - l;if (count >= M) {return true;}}}return false;
}int max(int a, int b) {return a > b ? a : b;
}void test8() {scanf("%d%d", &N, &M);for (int i = 1; i <= N; i++) {scanf("%d", &H[i]);}sort(H + 1, H + 1 + N);int left = 1, right = H[N], ans = 0;while (left <= right) {int mid = (left + right) / 2;if (check2(mid)) {ans = max(ans, mid);left = mid + 1;}else {right = mid - 1;}}cout << ans;}
int main() {test8();
}

 还有这题:P1824 进击的奶牛 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 同理:使用二分答案,解决


 

#define _CRT_SECURE_NO_WARNINGS 
#include<cstdio> 
#include<cstring>
#include<iostream>
#include<algorithm>
int V[200005];
int N, C, H;
using namespace std;
int check(int k) {int last = V[1], count = 0;for (int i = 2; i <= N; i++) {if (V[i] - last < k) {count++;if (H < count)return 1;}else {last = V[i];}}return 0;
}int max(int a, int b) {return a > b ? a : b;
}void swap(int* a, int* b) {int t = *a;*a = *b;*b = t;
}void test7() {scanf("%d %d", &N, &C);for (int i = 1; i <= N; i++) {scanf("%d", &V[i]);}H = N - C;sort(V+1,V+N+1);int left = 1, right = V[N], ans = 0;while (left <= right) {int mid = (left + right) / 2;if (check(mid) == 0) {ans = max(mid, ans);left = mid + 1;}else {right = mid - 1;}}printf("%d", ans);}
int main() {test7();
}

并查集

比如:

P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

找祖先,就一直找到最初的组件,判断是否相等,如果相等,就说明这两个是在同一个集合中。

int find(int x) {while (x != f[x]) {x = f[x];}return x;
}//路径压缩,循环实现
int find(int x){while (x != f[x]){f[x] = f[f[x]];x = f[x]}return x;
}//路径压缩,递归实现
int find(int x){if(x == f[x])return x;return f[x] = find[f[x]];
}

 路径压缩后会可以使查询祖先时,快不少。

并查集还有一个重要的出来查询之外,还有合并了

这里可以直接把一个元素的祖先赋值给一个元素的祖先

void merge(int a,int b){int a1 = find(a);int a2 = find(b);f[a1] = a2;
}

 

#define _CRT_SECURE_NO_WARNINGS 
#include<cstdio> 
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;
int N, M;
int f[10005];
void init() {for (int i = 1; i <= N; i++) {f[i] = i;}
}int find(int x) {while (x != f[x]) {f[x] = f[f[x]];x = f[x];}return x;
}void test8() {cin >> N >> M;init();for (int i = 1; i <= M; i++) {int z, x, y;cin >> z >> x >> y;if (z == 1) {f[find(x)] = find(y);}else if (z == 2) {if (find(x) == find(y)) {cout << "Y\n";}else {cout << "N\n";}}}}
int main() {test8();
}

最小生成树

算法:prim,kruskal算法

主要学习了kruskal算法

运用到了并查集。P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

顺便学习了c++中sort函数,自定义排序方式,

图中的边权值,进行排序。

kruskal:先找出最小没有连接的边,然后判断如果连接后有没有回路,如果有回路,就舍弃这条边,没有就把这条边加入,然后再进行判断下一条边。

P1195 口袋的天空 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

类似的,这个是需要把n个点构造成k棵最小生成树,所以只要加入的边等于n-k就行了

附上代码

#define _CRT_SECURE_NO_WARNINGS 
#include<cstdio> 
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int N, M, K;
int f[1005];struct edge {int v, u, w;
}edges[10005];int find(int x) {while (f[x] != x) {f[x] = f[f[x]];x = f[x];}return x;
}
bool cmp(edge a, edge b) {return a.w < b.w;
}void kruskal() {int ans = 0, cnt = 0;sort(edges + 1, edges + M + 1, cmp);for (int i = 1; i <= M; i++) {int a1 = find(edges[i].u);int a2 = find(edges[i].v);if (a1 == a2) {continue;}ans += edges[i].w;f[a1] = a2;    //连接两个顶点cnt++;if (cnt == N - K) {cout << ans;return;}}cout << "No Answer";
}void test() {cin >> N >> M >> K;for (int i = 1; i <= N; i++) {f[i] = i;}for (int i = 1; i <= M; i++) {cin >> edges[i].u >> edges[i].v >> edges[i].w;}kruskal();
}
int main() {test();
}

 

最短路径

dijkstra算法+链式前向星存边,

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include <algorithm>
#include<cstring>
#define inf 2147483647
using namespace std;
long long dis[10005];
bool vis[10005];
int head[10005];
int n, m, s,cnt = 0;
//在这里head数组储存i点的一条边的编号,edge中的next表示的是起点相同的边的编号,
//可以从加边那里深刻理解
//链式前向星存边
struct edge {int next;int to;int val;
}edges[500005];void dijkstra() {dis[s] = 0;int cur = s;while (!vis[cur]) {vis[cur] = true;for (int i = head[cur]; i != 0; i = edges[i].next) {if (!vis[edges[i].to] && dis[edges[i].to] > dis[cur] + edges[i].val) {dis[edges[i].to] = dis[cur] + edges[i].val;}}int min = inf;for (int i = 1; i <= n; i++) {if (!vis[i] && min > dis[i]) {min = dis[i];cur = i;}}}for (int i = 1; i <= n; i++) {cout << dis[i] <<" ";}
}//加边
void add(int a,int b,int c) {edges[++cnt].next = head[a];edges[cnt].to = b;edges[cnt].val = c;head[a] = cnt;            //记录编号
}void test() {cin >> n >> m >> s;for (int i = 1; i <= m; i++) {int a, b, c;cin >> a >> b >> c;add(a, b, c);}for (int i = 1; i <= n; i++) {dis[i] = inf;}dijkstra();
}int main() {test();
}

训练总结:昨天晚上加今天一天完成了这所有的训练,确实收获不少。

靠思维,暴力解决:A,,K,L

动态规划还是不太熟练, B

二分答案,能够理解。  C,D,E,F

 并查集:G,H

最小生成树:H,I

最短路径:J

思路有个大概,但是完全自己想出来,还是有点难度

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ONLYOFFICE文档:为企业和开发者带来强大的文档编辑功能

本文给大家介绍一个开源项目&#xff1a;ONLYOFFICE文档&#xff0c;它能够为文档编辑、多人协作提供强大支持。无论你是个人使用&#xff0c;还是企业、商业开发&#xff0c;都能找到适合你的版本。 关于 ONLYOFFICE 文档 ONLYOFFICE 文档是一套功能强大的文档编辑器&#x…

微信小程序获取AppSecret的步骤

文章目录 微信小程序获取AppSecret的步骤&#xff1a;注意&#xff1a; 微信公众平台 小程序的密钥&#xff08;或称为AppSecret&#xff09;是用于加密解密、验证服务器身份等安全操作的敏感信息。不同的平台&#xff08;如微信小程序、支付宝小程序、百度智能小程序等&am…

vulhub:Apache解析漏洞apache_parsing

在Apache1.x/2.x中Apache 解析文件的规则是从右到左开始判断解析&#xff0c;如果后缀名为不可识别文件解析&#xff0c;就再往左判断。如 1.php.xxxxx 漏洞原理 Apache HTTPD 支持一个文件拥有多个后缀&#xff0c;并为不同后缀执行不同的指令。比如如下配置文件 AddType te…

【C#】.net core 6.0 webapi 使用core版本的NPOI的Excel读取数据以及保存数据

欢迎来到《小5讲堂》 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 目录 背景读取并保存NPOI信息NPOI 插件介绍基本功能示例代码写入 Excel 文件…

算法小白的进阶之路(力扣1~5)

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小…

花几千上万学习Java,真没必要!(三十九)

1、BufferedReader的使用&#xff1a; 测试代码&#xff1a; package test.com; import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.List; public class FileReadToList { pu…

使用 openai 和 langchain 调用自定义工具完成提问需求

我们提供了一个函数&#xff0c;接受传入运算的字符串&#xff0c;返回运算的结果。 现在的需求是&#xff0c;我们问 gpt 模型&#xff0c;由于模型计算能力并不好&#xff0c;他要调用计算函数&#xff0c;根据计算结果&#xff0c;回答我们的问题。 使用 openai 实现&#…

发布NPM包详细流程

制作 首先需要制作一个npm包。 按照以下步骤依次执行。 mkdir my-npm-package cd my-npm-package npm init 相信这一步不需要过多的解释&#xff0c;就是创建了一个文件夹&#xff0c;然后初始化了一下文件夹。 然后在生成的package.json文件夹中更改一下自己的配置&…

优化冗余代码:提升前端项目开发效率的实用方法

目录 前言代码复用与组件化模块化开发与代码分割工具辅助与自动化结束语 前言 在前端开发中&#xff0c;我们常常会遇到代码冗余的问题&#xff0c;这不仅增加了代码量&#xff0c;还影响了项目的可维护性和开发效率。还有就是有时候会接到紧急业务需求&#xff0c;要求立马完…

这两个大龄程序员,打算搞垮一个世界软件巨头!

大家都知道&#xff0c;Adobe是多媒体和数字内容创作者的绝对王者&#xff0c;它的旗下有众多大家耳熟能详的软件&#xff1a;Photoshop、Illustrator、Premiere Pro、After Effects、InDegign、Acrobat、Animate等等。 这些软件使用门槛很高&#xff0c;价格昂贵&#xff0c;安…

遗传算法与深度学习实战——生命模拟及其应用

遗传算法与深度学习实战——生命模拟及其应用 0. 前言1. 康威生命游戏1.1 康威生命游戏的规则1.2 实现康威生命游戏1.3 空间生命和智能体模拟 2. 实现生命模拟3. 生命模拟应用小结系列链接 0. 前言 生命模拟是进化计算的一个特定子集&#xff0c;模拟了自然界中所观察到的自然…

大模型之多模态大模型技术

本文作为大模型综述第三篇,介绍语言大模型多模态技术。 不同于语言大模型只对文本进行处理,多模态大模型将文本、语音、图像、视频等多模态数据联合起来进行学习。多模态大模型融合了多种感知途径与表达形态, 能够同时处理和理解来自不同感知通道(例如视觉、听觉、语言和触…

麒麟系统查看和修改ip

查看ip ifconfig ifconfig enp0s3 192.168.1.110

使用Echarts来实现数据可视化

目录 一.什么是ECharts? 二.如何使用Springboot来从后端给Echarts返回响应的数据&#xff1f; eg:折线图&#xff1a; ①Controller层&#xff1a; ②service层&#xff1a; 一.什么是ECharts? ECharts是一款基于JavaScript的数据可视化图标库&#xff0c;提供直观&…

javaScript中的对象

创建 this指向 命名规则 不符合变量名的命名规则和规范使用数组关联语法获取 遍历对象 使用for&#xff08;var key in 对象&#xff09; 删除属性 对象引用关系

Flutter大型项目架构:私有组件包管理

随着项目功能模块越来越多&#xff0c;怎么去管理这些私有组件包是一个不得不面对的问题&#xff0c;特别对于团队开发来讲&#xff0c;一些通用的公共组件往往会在多个项目间使用&#xff0c;多的有几十个&#xff0c;每个组件包都有有自己的版本&#xff0c;组件包之间还有依…

一篇文章带你入门爬虫并编写自己的第一个爬虫程序

一、引言 目前我们处在一个信息快速迭代更新的时代&#xff0c;海量的数据以大爆炸的形式出现在网络之中&#xff0c;相比起过去那个通过广播无线电、书籍报刊等传统媒介获取信息的方式&#xff0c;我们现在通过网络使用搜索引擎几乎可以获得任何我们需要的信息资源。 但与此同…

Vue前端工程

创建一个工程化的vue项目 npm init vuelatest 全默认回车就好了 登录注册校验 //定义数据模型 const registerDataref({username:,password:,rePassword: }) //校验密码的函数 const checkRePassword(rule,value,callback)>{if (value){callback(new Error(请再次输入密…

python基础知识点

最近系统温习了一遍python基础语法&#xff0c;把自己不熟知的知识点罗列一遍&#xff0c;便于查阅~~ python教程 Python 基础教程 | 菜鸟教程 1、python标识符 以单下划线开头 _foo 的代表不能直接访问的类属性&#xff0c;需通过类提供的接口进行访问&#xff0c;不能用 f…

c++STL容器中vector的使用,模拟实现及迭代器使用注意事项和迭代器失效问题

目录 前言&#xff1a; 1.vector的介绍及使用 1.2 vector的使用 1.2 1 vector的定义 1.2 2 vector iterator&#xff08;迭代器&#xff09;的使用 1.2.3 vector 空间增长问题 1.2.4 vector 增删查改 1.2.5vector 迭代器失效问题。 2.vector模拟实现 2.1 std::vect…