健康快乐最重要

分类

linux(1) 操作系统(3) 未归档(1) 机器人(2) 计算机机试(7) 计算机视觉(15) 递归(1) 题解(86)

/ 注册

全部文章（共115篇）

最大子序列和

思路用dp[i]，记录以i为末尾元素的子序列和。相对于之前的，只要增加end去记录最大子序列和的最后一个元素位置就可以，end确定后，从end往前找到一个小于0的位置，然后再+1，就是子序列开始，也就是begin的位置。 #include<iostream> #include<...

2020-02-25

3 1229

最大子序列和

a[i]表示以第i个元素为结尾的最大子序列和。通过一个例子我们可以推导出此递归产生式：a[i]=max(a[i],a[i-1]+a[i]); 比如1 5 -3 2 4a[0]=1;a[2]=1+5=6;a[3]=1+5+(-3)=3;a[4]=3+2=5;a[6]=5+4=9; 1 -2 3 4 -...

2020-02-25

15 1049

怎么判断图有环？

因为疫情在家，没事情干，脑子里突然迸发出了一个想法，图是程序员非常熟悉的数据结构，而且也被广泛地应用与生活日常，机器人，航天工程等各种领域。但是如果我们如果只是围着一个图去绕圈，那可能没什么意义。而且会陷入迷宫当中出不来。所以就想写一写，如何判断图到底有没有环呢？我们以有向图为例（假设图肯定是...

2020-02-24

1 1853

dijkstra变体

分析了半天题的情况，最后被大佬的一句话点醒了。大佬原话：没错，一开始我的分析是，因为1城市是1阵营，2城市是2阵营，所以只要保证连接1和2中间的城市阵营都相等就可以。比如1 2 2 2 2或者1 1 1 1 2，但是万万漏掉了一点就是可能有1 1 2 2 2这样的情况，即中间不是规律的，但是最...

2020-02-24

9 799

Dijkstra

Dijkstra算法的应用总是爱犯的一个错误就是在构建图的时候总是构建单个边。害，应该两个边都加进去（因为是无向图）。 #include<iostream> #include<queue> #include<algorithm> #include<vecto...

2020-02-23

6 1063

Kruskal 并查集

一遍过，本题运用的kruskal的思想，通过并查集实现。获得两个点以及两个点间的距离，然后从集合中找出距离的最小值。加入到图的集合中，当把所有边都遍历完后，由于这个题，图肯定是连通的。所以只要记录加进来的边的长度(也就是两点间的距离就行）。 #include<iostream> #inc...

2020-02-22

6 883

Kruskal继续畅通工程

几个题基本都是Kruskal算法 #include<iostream> #include<vector> #include<map> #include<algorithm> using namespace std; const int maxn=200...

2020-02-21

1 786

判断是否是一棵树(并查集)

这个题也太🐕了0 0空集是树(没好好读题)有环不是树(没想到)其他并查集判断是否是一个连通图，如果是的话且没环就是树 #include<iostream> #include<map> #include<vector> using namespace std; c...

2020-02-21

0 728

Head of Gang（并查集解决）

使用并查集和dfs都可以解决这个问题。如下是并查集解决的过程。相对于普通问题，主要是Union函数发生了变化 #include<iostream> #include<map> #include<string> using namespace std; //头是要点...

2020-02-21

3 885

并查集实现连通图的检测

并查集的板子，一开始不会做，后来多做了几道就差不多会了。普通并查集只是顺序的节点号。但是本题给出的节点号不是顺序的，所以这里没有采用数组的方式，而是采用了map散列表的方式。当然通过dfs也可以很好的解决这个题目。通过对所有节点进行dfs。只要没有全遍历到，那就sum++； #include<...

2020-02-21

12 835