louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共81篇）

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

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

tarjan 割点

2019-08-24

0 580

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

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

二分图最大匹配

2019-08-24

0 566

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

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

二分并查集二分图染色

2019-08-24

0 663

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

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

二分图最大匹配

2019-08-23

0 628

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

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

树的直径

2019-08-23

0 739

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

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

线段树前缀和树上倍增

2019-08-22

0 630

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

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

树上倍增

2019-08-21

0 719

题解 | 算法竞赛进阶指南闇の連鎖

思路删去一条树边能把树断成两个联通块.未删去的非树边不能把两个连通块再连回去(否则不是白搭了2333).如果一条非树边与树上的边构成一个环,删去这个环的树边的同时,必须将这两条边同时删去.如果某条树边同时在好几个环中,肯定不能删去这条树边,因为只能删一条非树边,删了条非树边,剩下的还是连通.对于一...

树上倍增前缀和

2019-08-21

0 518

题解 | 算法竞赛进阶指南次小生成树

思路先建出最小生成树,然后考虑删去树上一条边,加入一条非树边.枚举一条非树边加入,然后需要选出树上节点,之间的路径的一条边删去.很明显,删去的边应该越大越好,但是不能与边相等,否则就不是严格次小了,因此需要求出树上路径边权的最大值和最小值,可以使用倍增LCA解决qwq.最生成树复杂度为,寻找替换边...

树上倍增

2019-08-21

0 659

题解 | 算法竞赛进阶指南巡逻

思路当时,答案显然是树的直径减去新增的那条边.因为加上这条边,可以变成一棵基环树,那个环上的每条边只要走一编,其他边仍然要走两遍.当时,因为是两个环,要考虑这两个环是否相交.如果不相交,这两个环上的边都可以少走一遍.如果相交,这两个环共有的边仍然要走两遍(可以自行画图理解).这样就有一种做法,先找...

树的直径

2019-08-21

0 665