标签 仙人掌 下的文章:

ZJOI Day1 T1 仙人掌 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:59
考试的时候全程刚这题现在一看实在是有点亏啊………… 这题的仙人掌要求是没有重边的,那么我们可以在连完一种方案之后把剩下的没有被覆盖的边变成一个重边让他有覆盖 这样就变成了给定一棵树,找个方案使他的所有的边都被覆盖 树形dp即可 $f(x)$ 表示做完了 $x$ 的...

阅读全文>>

3899: 仙人掌树的同构 dp
发表于: | 分类:Oi | 评论:0 | 阅读:72
说好的字符串专题在我这直接变成dp了 23333333 这题求同构的仙人掌的方案数,我写了个 $n^2\log{n}$ 的做法【其实就是暴力 先随便找个点做跟,然后递归算儿子,$calc(x)$ 是计算 $x$ 子树的同构方案数。 如果 $x$ 是个链,有 $j$...

阅读全文>>

2125: 最短路 圆方树 仙人掌 倍增LCA
发表于: | 分类:Oi | 评论:0 | 阅读:61
犯了个智障错误调了半天 还是原来的套路,先把圆方树建出来,然后把每个点连到方点的距离设置成到环最上面的点的最短距离,然后正常倍增lca 注意最后的时候如果落在了一个圆点上就可以直接更新答案啦,如果落在方点上,就找到在lca方向上的最后一个点,然后把他们到lca的距...

阅读全文>>

1023: [SHOI2008]cactus仙人掌图 圆方树 单调队列 仙人掌
发表于: | 分类:Oi | 评论:0 | 阅读:46
开始刷仙人掌问题,主要依靠圆方树来解决问题 圆方树就是找一个环,然后把环上的边都拆掉,然后新建一个点连接所有的换上的点 实现的话依靠深搜,维护一下点在搜索树上的父亲以及深度,如果发现一个点连接的另外一个点的深度比自己的深度还小,那连接的点一定是一个环的上顶点,然后...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP