苟且的狮子

分类

2020多校(6) CF(27) 作业(3) 区域赛真题题解(提升思维！！！)(8) 寒假模拟赛(1) 未归档(1) 苏州大学排位赛(7) 随笔(1) 题解(180)

/ 注册

TA的专栏 88篇文章 0人订阅

kuangbin题单刷题详解(最短路篇)

9篇文章 696人学习

kuangbin题单刷题详解(网络流)

10篇文章 648人学习

kuangbin题单刷题详解(匹配问题)

14篇文章 724人学习

kuangbin刷题题单详解(后缀数组)

8篇文章 588人学习

kuangbin刷题题单详解(博弈论)

8篇文章 736人学习

kuangbin刷题题单详解(连通图)

9篇文章 814人学习

Kuangbin刷题详解(AC自动机)

4篇文章 613人学习

Kuangbin题单详解(kmpManacher)

20篇文章 950人学习

Kuangbin题单详解(区间dp)

6篇文章 791人学习

全部文章（共229篇）

Equal Sentences

dp，斐波那契数列题意：分析：我们现列举简单的例子：对第一个例子，he he zhou is watching you我们简写为： a a b c d e那么一共有几种呢？首先自己是一个然后我们两两交换：a (b a) c d e a a (c b) d e a a b ...

斐波那契数列 dp

2020-07-31

1 622

Deliver the Cake

最短路，链式向前星，循环dp，分层图题意：分析：这题不难，循环dp问题而已(分层图)正好最近我认真研究过，所以当时在赛场上的时候我还是很有自信能做出来的。思路如下，我们添加一维构造循环dp。d[i][j]为节点i在j状态下距离s的最短距离！！！我们很容易能推出其动态转移方程：d[i][j...

最短路 Dijstra 分层图循环dp Bellman-Ford 建图

2020-07-31

1 568

[HNOI2006]公路修建问题

最小生成树、kruskai算法题意：废话：做了些题单的题后，我发现题目考察点基本上围绕着建图、算法本身理解、dp 三点展开。本题考察的是对kruskai算法的理解分析：我们首先抓住重要信息：公路1是一定比公路2开销大的！至少要有k条公路1.那么很明显我们就只铺设k条公路1好了，剩下的都...

最小生成树 kruskai

2020-07-29

1 633

追债之旅

松弛操作，循环dp 题意：分析：又是这种题，很好，对于已经明白松弛操作与循环dp的我来说已经不成问题了。给出dp状态dp[i][j] 指在第j步到达节点i的最短路径d[i][j] = min(d[k][j-1] + edge(i,k) + cost[j] k为i相邻节点)这是个无限...

Dijstra 循环dp Bellman-Ford

2020-07-29

2 683

Car的旅行路线

建图，最短路题意：分析：没有什么难以思考的地方，关键就是建图，我们以每个机场为节点建图。成功建图后跑4次dijstra算法取得城市a到城市b的最小路径就行了。但是，在此题中建图这件事还真是挺大工程的。代码量巨大，烦死我了。代码如下： #include<iostream> #i...

最短路建图

2020-07-29

1 649

Rinne Loves Graph

dp松弛问题(循环特性) 题意：分析： dp松弛问题。这是我的总结。所谓的最短路，不过是dp只不过该dp无法借由循环和记忆化搜索实现(因为有环使其左右横跳)详细见我的另一篇题解，正好是题单中的下一题：https://blog.nowcoder.net/n/8316b13c345d49b08b2...

Dijstra dp Bellman-Ford 循环dp

2020-07-28

6 658

Rinne Loves Dynamic Graph

Bellman-Ford算法，dijstra算法，循环dp问题这题很好，让我重新认识到了最短路到底是为解决了一个什么样的问题！！！！题意：分析：首先，我不会分层图！！！！所以，这题我主要是围绕dp展开。我们必须要知道题中所给函数1/(1-x)是个周期为三的周期函数那么边权就为x,1/(x...

Dijstra dp Bellman-Ford

2020-07-28

3 992

小雨坐地铁

分层图，建图，最短路题意：分析：首先来看看我当时的思路吧！我们很容易发现这是个最短路问题，但线路的存在很棘手。雨神说过，图论的难点在于建图！如果成功建图接下来就只是套板子了。那来看看我们如何建图。我上来也没有思路，后是从实际生活入手的。想象一下，我们在站点i我们可以坐1,2,3三路高铁，...

最短路分层图建图

2020-07-27

7 745

Forsaken喜欢独一无二的树

题意：分析：正如“jxnu-19-软技一班-刘晟”所说的，按照kruskai算法的想法来看的话，出现多条最短路径的原因只可能是存在复数的最小权值边连接着两个集合以供选择。那我们其实只要在kruskai算法进行的同时动手脚就行了。我们先对权值进行从小到大的排序，然后将其分为一个个的相等权值的集...

最小生成树 kruskai

2020-07-27

3 618

B-旅行

最小路、枚举题意： ##分析：版子题，枚举中间点，选两个最大的。注意图并不是连通图，选择的时候不能选自己。代码： #include<iostream> #include<algorithm> #include<vector> #include<queue...

最短路暴力枚举

2020-07-27

2 650