louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共160篇）

题解 | 算法竞赛进阶指南骑士放置

思路很明显,一对相斥的位置,横纵坐标之和的奇偶性肯定不同.所以可以构成一个二分图.源点向所有横纵坐标之和为奇数的点连边,为偶数的向汇点连边,边权都为1.一对相斥的点之间连边,跑一遍最小割即可.或者如果你懒得写网络流,你可以套用最大独立点集的模型,跑匈牙利即可.虽然效率比网络流低得多. 代码 #in...

最大独立点集网络流最小割

2019-08-24

2 528

题解 | 算法竞赛进阶指南开车旅行

思路先预处理出,表示从开始,小A小B各走了步时,小A走的路程,小B走的路程,以及所到达的地方.这些东西可以预处理出来.2^1,然后对于第一问,我们可以枚举每一个出发点,从枚举到,能继续走就继续走,否则就停止,别忘了最后小A还可以走一步.然后就可以得到小A小B分别走的路程,取比值最小的即可.对于第二...

倍增

2019-08-24

0 759

题解 | 算法竞赛进阶指南银河

思路按照题意建边,若亮度大于等于的,连有向边,大于则为,相等则为.然后缩点,如果出现一个强连通子图内有大于0的边,说明存在正环,无解.然后拓扑排序,若有边,,直接DAG上DP即可.当然你想跑差分约束我也没办法qwq. 代码话说那时候脑子抽了还是怎么样,本地运行爆栈了,我还以为一定要手工栈什么的q...

tarjan 缩点

2019-08-24

0 551

题解 | 算法竞赛进阶指南 BLO

思路 I.设在搜索树T中以x为根的树包含的点集为SubTree(x)。 II.这里去除割点可以理解为删除与该点相连的所有边。 III.这里提到的连通块是指当某一割点去除时：1.其中任何两个点都能相互到达 2.没有更大的连通块包含该块当然，根据II，我们把单独的X也看做一个连通块 IV.为了方便，...

tarjan 割点

2019-08-24

0 573

题解 | 算法竞赛进阶指南棋盘覆盖

思路放置多米诺骨牌可以看作与或或或匹配的过程.因为与,奇偶性不同,可以分成一个二分图.这样就变成一个二分图匹配问题,能匹配且都不是障碍的两个点之间连边,直接跑匈牙利即可. 代码 #include<bits/stdc++.h> using namespace std; #define i...

二分图最大匹配

2019-08-24

0 561

题解 | 算法竞赛进阶指南关押罪犯

思路这题可以用并查集或二分+二分图染色解决.首先二分答案,然后只要判断是否能将罪犯分成两个图,图的内部边权都不超过答案. 并查集这样子可以直接使用并查集的边带权或者扩展域解决.对边从小到大排序.边带权的话,边权可以是两点是否相同,合并时如果有冲突判断就输出答案.扩展域的话也就是每个罪犯拆成两个点...

二分并查集二分图染色

2019-08-24

0 657

题解 | 算法竞赛进阶指南車的放置

思路因为每一行只能有一个車,每一列也只能有一个車.因此把每一行当做一个节点,每一列当做一个节点,若行列能放棋子,行节点向列节点连边,这样就是一个二分图最大匹配问题.跑一遍匈牙利算法即可. 代码 #include<bits/stdc++.h> using namespace std; #...

二分图最大匹配

2019-08-23

0 622

题解 | 算法竞赛进阶指南树网的核

思路通过大胆猜想与小心伪证,我们可以得到一个结论: 在任何一条直径求得的最小偏心距都是相等的. 有了这个结论,我们就可以乱搞啦.对于直径,若选取的核为,最小偏心距只有可能为,,或者是选取整条直径为核时的最小偏心距.(十分好证)那么先求出某条直径的最小偏心距,然后在直径两端分别为虎一个指针,不断...

树的直径

2019-08-23

0 733

题解 | 算法竞赛进阶指南雨天的尾巴

思路好恶心的卡常题(虽然一边颓废一边写,还是卡了一下午).如果空间和时间足够大,我们可以考虑对每一种粮食开一个大小的数组,若某条路径放类型的粮食,,树上前缀和,然后找出最大值即可.不过这样就算是离散化后,时空复杂度都是.不过这样直接把开的数组改成动态开点线段树就好了.求前缀和的过程可以看成线段树合...

线段树前缀和树上倍增

2019-08-22

0 618

题解 | 算法竞赛进阶指南异象石

思路我们需要把所求的东西转换一下.容易想象,取出所有节点建一棵虚树(放心,不用真的建,只要知道是什么就OK.也就是将所有节点以及两两之间的(以下称为关键点)取出来建树,若两个关键点之间的路径没有其他关键点,就将这两个关键点之间连边,长度为两个关键点的距离),虚树所有边长度和即为答案.想象遍历这颗虚...

树上倍增

2019-08-21

0 707