louhc

题解

未归档(78)

/ 注册

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

题解 | 算法竞赛进阶指南学校网络

思路因为对于一个环,给其中任何一点支援都是等效的,因此先对原图进行缩点.对于缩点后的图,入度为0的点不能被其他学校支援,其他入读不为0的都能被其他学校支援,因此第一问答案就是入度为0的点.而要满足第二问的条件,必须使都在一个强连通分量才行.这样答案就是max(入度为0的点个数,出度为0的点个数)....

tarjan 缩点

2019-08-26

1 531

题解 | 算法竞赛进阶指南赤壁之战

思路设计状态表示最后一个数为,长度为的严格递增子序列个数.我们可以轻松地推出转移方程: 注意到这两个限制是二维的,第一维直接按顺序枚举不断加入状态即可解决,第二维套一个树状数组即可解决.因为可能很大需要离散化.复杂度为看起来有点大,但是因为树状数组常数小,还是可以过的.实现中为了减小内存使用了滚动...

树状数组计数类动态规划动态规划

2019-08-26

0 780

题解 | 算法竞赛进阶指南蒙德里安的梦想

思路都这么小可以考虑考虑状态压缩.表示填了前行,只有第行还有一些位置没有填过(满足). 可以从上一种状态转移过来需要满足以下条件: 每段连续的都是偶数个. 因为数据范围比较小,并且你也不知道询问有多少,可以预处理出所有可能输入的答案(当然也可以打表,虽然好像不太厚道),然后每次询问直接输出答...

状态压缩动态规划

2019-08-26

0 1028

题解 | 算法竞赛进阶指南炮兵阵地

思路 ,这么小的数据范围当然要想到状态压缩.我们把放置炮兵的位置变成,不放炮兵为.这题比较猥琐的一点就是会影响到能否放炮兵的有前两行.这样至少需要三维,记录当前到哪行以及前两行的状态.这样不能承受.由于这特殊的"十字",每行两个炮兵之间至少要两个格子.打个表可以发现满足条件的状态大概只有六十几个,这...

状态压缩动态规划

2019-08-26

1 637

题解 | 算法竞赛进阶指南积蓄程度

思路假设源点已经确定为1,那么直接跑树形DP即可.表示到叶子节点的最大流量(不考虑父亲节点的限制,也就是说看成父亲流到的流量为无穷),但是现在源点不一定为1,考虑怎么快速地"换根".设为为根时真正的答案.首先,它流到以为根时就是其儿子节点的流量是(注意是叶子节点时要赋为0).流到以为根时为父亲,而...

树形动态规划动态规划

2019-08-26

0 639

题解 | 算法竞赛进阶指南环路运输

思路将数组复制一倍衔接在最后,那么答案就是用单调队列维护一下的最大值即可.注意及时排除已经不满足的状态.复杂度为,常数也比较优秀. 代码 using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b),...

单调队列

2019-08-26

0 623

题解 | 算法竞赛进阶指南金字塔

思路设为字符串中从到部分为一整棵树时的方案数.我们可以枚举第一棵子树,也就是为一棵子树,其它子树在为剩余的子树(与为根节点,同时也是的根节点,也就是说这两个点是同一个点).然后乘法原理与加法原理计算出答案即可.可以发现,一般情况下,很多状态是无用的.所以用记忆化搜索效率更高. 代码 #includ...

动态规划区间动态规划

2019-08-25

1 617

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

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

线段树动态规划

2019-08-25

0 570

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

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

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

2019-08-25

0 603

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

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

高境地卡特兰数

2019-08-24

0 695