苟且的狮子
苟且的狮子
全部文章
题解
2020多校(6)
CF(27)
作业(3)
区域赛真题题解(提升思维!!!)(8)
寒假模拟赛(1)
未归档(1)
苏州大学排位赛(7)
随笔(1)
归档
标签
去牛客网
登录
/
注册
苟且的狮子的博客
人一我百、人百我万!
全部文章
/ 题解
(共179篇)
[HNOI2012]矿场搭建
tarjan、割点、分类讨论 题意: 分析: 这题很容易让我们想到割点。这并不难,但是细节上的处理于分类讨论才是这道题的难点。 我们想想如果一个连通块,他有一个割点。 那么,我们一定要在他被割点分开的两个连通块中放置救援出口。而放置的方案数就是两边的点数相乘,割点不算! 如果,他有两个以上的割点...
tarjan
割点
2020-08-29
4
559
[JSOI2010]连通数
bfs,bitset 题意: ##分析:题目没给数据范围,n<=2000考录到数据范围,这题我们可以直接bfs,或者dfs。暴力搜索。细节处理好也能过。但是,显然有些勉强。这里面考的是,bitset容器。 bitset的或运算代替了搜索。 看代码: bitset<max_n> a[...
bitset
bfs
2020-08-29
1
646
字符串的问题
kmp 题意: 分析: 我们看着一题,我们仔细想想。首先如果没有要求中间 子串 的话,就很简单了。我们直接输出前后缀相等的就好了。无论是 kmp 还是 暴力 都是线性时间。 但是麻烦就在于中间要有字串。 那我们想想,如何判断中间有没有子串呢? 假设,next[n] = k 意味着s0,s1,s...
kmp
2020-08-28
7
634
[HAOI2006]受欢迎的牛
tarjan,dfs 题意: 分析: 不知道怎么回事,这道题做的时候总是有点迷迷糊糊的,犯了好多低级错误。。。。。。 总之,如果接触到tarjan的话那么我们肯定能够反映过来:一定要缩点的。缩点后啊,这张图就是一张拓扑图。有向无环。每割点都有权值,就是此节点缩的点数那现在让我们从这张有向无环图中...
dfs
tarjan
map
2020-08-25
1
598
[AHOI2009]MINCUT 最小割
结论题,最小割,tarjan 题意: 分析: 题目看了,就是让我们对图中的每一条边都做判断:是否可以是最小割边?是否一定是最小割边?暴力做法:n*m对于每一条边我们都单独判断! 那么现在来看tarjan做法:首先让我们想想,传统如何判断一条边能不能在最小割集中。先跑最大流,得到其残余网络(此残余...
最小割唯一性判断
最小割
2020-08-19
1
636
团结就是力量
字符串同构,tarjan,hash 题意: 分析: 不难想到用tarjan算法,将互相愿意组队的人员划分出来。但是,稍微有困难把你的便是:如何计算这只队伍的团结系数呢? 这里牵扯到了一个知识点:字符串同构!!对于字符串a,和字符串b我们知道a经过一定的循环就会变成b。我们称a与b同构。那么倘若我...
同构字符串
tarjan
hash
2020-08-19
4
731
[CQOI2012]交换棋子
建图拆点,最小费用最大流 题意: 分析: 首先我们认识到,对于我所在的棋盘,如果我把所有的黑子都摆放在指定的位置上了的话,那么白子也一定被摆在了指定的位置。所以,这里我们不妨只看黑子,考虑让其摆放在规定的黑子位置上所消耗的步数最小。 不难想到,这是个匹配问题。我们要对所有的黑子对其归属位置进行匹...
最小费用最大流
思维
建图
2020-08-18
4
827
Coding Contest
最小费用最大流,对数乘法换加法,浮点数比较 题意: 这道题看上去很裸,似乎就是一道最小费用流的题目。需要注意的有三点:1.这里面最小费用的计算是乘法,所以我们要对其取对数将其变为加法。2.因为e(u,v)的cost为浮点数,所以再spfa算法中我们便不能再直接比较了。需要加上个eps否则会一直超...
最小费用最大流
对数乘法换加法
浮点数比较
2020-08-17
1
604
小Y写文章
网络流,二分、二分图最大匹配 题意: 分析: 这一题出的好啊!!!!正是我能力边缘的题目。有助于提升实力!!! 我们需要插入m段广告,有n+1个空位我们可以插入。当插入时,我们整体得不流畅度可能会改变。 当我们看到max() 时,我们就应该尝试用二分的思想取考虑一下,a1,a2,a3,a4当我们...
二分
最大流
网络流
二分图最大匹配
建图
2020-08-16
7
1244
[CQOI2014]危桥
最大流,反复跑流 题意: 分析: 这题我不会,是看人题解后做的。汗 这题有两个收获:1.网络流建无向图。 void add(int from, int to, int cap) { E[cnt].to = to; E[cnt].cap = cap; E[cnt].rev ...
反复跑图
网络流
2020-08-16
0
614
首页
上一页
7
8
9
10
11
12
13
14
15
16
下一页
末页