苟且的狮子

分类

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

/ 注册

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

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

9篇文章 596人学习

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

10篇文章 524人学习

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

14篇文章 594人学习

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

8篇文章 449人学习

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

8篇文章 615人学习

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

9篇文章 687人学习

Kuangbin刷题详解(AC自动机)

4篇文章 506人学习

Kuangbin题单详解(kmpManacher)

20篇文章 831人学习

Kuangbin题单详解(区间dp)

6篇文章 670人学习

全部文章（共8篇）

F. False God

思维+建图首先，万物起源：对于这种两个变动的题目，我们相对的看可以给金的每次移动向前增加一位然后我们在草稿上画出一个金可以走到的所有格点会发现，正好以斜线为界限的范围是这个金可以走到的地方但是，还有一个问题，这里是一轮过后，即金和步都走一步后但是还有可能步还没走就让金吞了因此，为了避免这种情...

思维建图

2021-03-25

1 481

点阵

最大流，建图题意：分析：难点就在建图。我们不难这样想：将每一条边视作一个点，将每一个格子视作一个点。格子点拆成两个。然后这样建造：但是，这很明显不能满足约束条件。对于相邻的两个格点，如果他们相邻的边被选中时，两个格点的s-s1或者s2-ed都要减一，并且该边所代表的点再也不能走了！很明显我...

最大流网络流建图

2020-08-30

1 448

[CQOI2012]交换棋子

建图拆点，最小费用最大流题意：分析：首先我们认识到，对于我所在的棋盘，如果我把所有的黑子都摆放在指定的位置上了的话，那么白子也一定被摆在了指定的位置。所以，这里我们不妨只看黑子，考虑让其摆放在规定的黑子位置上所消耗的步数最小。不难想到，这是个匹配问题。我们要对所有的黑子对其归属位置进行匹...

最小费用最大流思维建图

2020-08-18

4 675

小Y写文章

网络流，二分、二分图最大匹配题意：分析：这一题出的好啊！！！！正是我能力边缘的题目。有助于提升实力！！！我们需要插入m段广告，有n+1个空位我们可以插入。当插入时，我们整体得不流畅度可能会改变。当我们看到max() 时，我们就应该尝试用二分的思想取考虑一下，a1,a2,a3,a4当我们...

二分最大流网络流二分图最大匹配建图

2020-08-16

7 1107

[SDOI2010]星际竞速

建图，网络流，最小费用最大流题意：分析：雨神说过，图论题难就难在建图上。这题我觉得建图还是蛮难的。我们捕捉一下重要信息：从一个额外的点出发，恰好经过每一个点一次，可以进行跳跃，永远是小点连大点。我们不难明白，所谓额外的点其实就是时空跳跃的中介点，也同时是起点。同时，我们也很本能的想将所...

最小费用最大流建图

2020-08-15

2 823

Deliver the Cake

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

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

2020-07-31

1 452

Car的旅行路线

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

最短路建图

2020-07-29

1 480

小雨坐地铁

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

最短路分层图建图

2020-07-27

7 592