louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共160篇）

题解 | 算法竞赛进阶指南清理班次

思路先将所有左边界-1,也就是将所有"块"变成"点",从"第l块到第r块"到"坐标之间的块",方便离散化.先对所有区间按右边界排序,枚举每个区间,更新答案大家可能发现我的转移方程与算法竞赛进阶指南上不太一样,因为我的表示方式不同,书上表示覆盖第1块到第i块都被覆盖过的最优答案,而我是坐标从到之间所...

线段树动态规划

2019-08-25

0 570

题解 | 算法竞赛进阶指南杰拉尔德和巨型象棋

思路因为较大,不能直接用和设计状态.将染成黑色,题目变成求从开始,第一个经过的黑色格子是的路径有多少.先将所有点排序,第一关键字为所在行,第二关键字为所在列.设为从开始,第一个经过的黑色格子为的路径条数.首先,.假设之前不经过任何黑格子,那么.然后减去之前经过黑色格子的路径.枚举这些路径经过的第二...

计数类动态规划动态规划排列组合

2019-08-25

0 603

题解 | 信息学奥赛一本通网格

思路首先所有的路径数为,也就是选出个时间点向上,其他时候向右.然后只要减去越过的路径即可.先上图:将上移,变成,也就是路径不能碰到.将路径最后一个碰到的点与以为对称轴翻折.也就是粉色点路径翻折成紫色点路径.这样的路径一定是一一对应的,因为从到的路径一定可以唯一地翻折回来,而且这样的路径肯定是碰到的...

高境地卡特兰数

2019-08-24

0 695

题解 | 信息学奥赛一本通 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