louhc

题解

未归档(78)

/ 注册

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

题解 | 信息学奥赛一本通 GT考试

思路先不考虑数据范围,我们设表示当前构造到第位,已经匹配了位的方案数.最终答案即为我们可以写出一个递推式,是我们要求的系数.我们可以使用KMP来求系数.只要求出前位(长度为)与相同,下一位的数字为时,与最大的匹配长度.对于每一个,,很明显不能承受.但是系数每次转移都不会变,因此直接用矩阵快速幂优化...

字符串矩阵乘法快速幂 KMP

2019-08-24

0 552

题解 | 信息学奥赛一本通迷路

思路首先,假设图中所有路径长度都为1.走步时从到的方案数,走步时从到的方案数.那么走步的方案数.矩阵快速幂就OK了.但是这里边权不为1.由于数据范围小,我们可以将边权为的边拆成条边权为1的边,然后矩阵快速幂即可.复杂度为代码 #include<bits/stdc++.h> using...

二进制拆分矩阵乘法快速幂

2019-08-24

0 594

题解 | 算法竞赛进阶指南 Cable TV Network

思路这是一个无源无汇的最小割问题.或者说叫"无向图全局最小割".一个很暴力的思想就是枚举任意两个点作为源点和汇点.复杂度大概是,但是由于跑不到上界,还是可以过的.如果对这个复杂度不满意,可以枚举源点,其他点向汇点连边,复杂度为,优秀得多.你还可以使用二进制思想,枚举每一位,将所有点分成两部分,源点...

最小割

2019-08-24

0 553

题解 | 算法竞赛进阶指南 K取方格数

思路费用流裸题.将每个点拆成入点和出点,入点与出点之间连边,容量为1,价值为该点的数.这样该点只能经过一次且经过会得到该数的代价.实际上每个格子能经过多次,但只能得到一次的代价,因此再连一条容量为,价值为0的边.然后源点向连边,向汇点连边,跑一遍最大费用最大流即可. 代码 #include<...

费用流 Floyd

2019-08-24

0 573

题解 | 算法竞赛进阶指南 Vani和cl2捉迷藏

思路事实上,此题等价于求最小路径可重覆盖.为什么呢?我们可以考虑构造出所有的藏身点.首先,跑一遍最小路径可重覆盖后,将所有路径的终点加入集合.假设表示.表示传递闭包后的边集.如果,选取,不断沿着路径向前移,直到为止.不断重复以上过程,直到停止.容易证明,这样肯定能找到一个合法的方案.这题不需要输出...

Floyd 最小路径覆盖

2019-08-24

0 645

题解 | 算法竞赛进阶指南 Muddy Fields

思路因为木板可以重叠,所以如果放置木板,木板两端肯定都顶到底(障碍或者边界)是最优的.这样就可以预处理出一些横向与纵向的联通块(宽度都为1).因为每一个方格必须被覆盖,所以该方格隶属的横向联通块与纵向联通块至少有一个被木板覆盖.这样就可以构建二分图,横向联通块为左部图,纵向联通块为右部图,每一个方...

二分图最小点覆盖

2019-08-24

0 597

题解 | 算法竞赛进阶指南 Machine Schedule

思路很裸的二分图最小点覆盖题.首先,因为最开始都处于0模式,那么或的边都可以删去.然后因为最优情况下每种模式最多只转换一次,可以把转换过这种模式看作选择这种模式所代表的的点,而可以看作一条边.的模式是左部图,的模式是右部图.很明显,题目转换成这样一个问题:选择最少的点,使所有边都能覆盖到.这就是经...

二分图最大匹配二分图最小点覆盖

2019-08-24

0 495

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

思路很明显,一对相斥的位置,横纵坐标之和的奇偶性肯定不同.所以可以构成一个二分图.源点向所有横纵坐标之和为奇数的点连边,为偶数的向汇点连边,边权都为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