wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共302篇）

hdu5306 Explosion

题目链接题意有n个房间，每个房间里面有若干把钥匙，每把钥匙可以打开对应的一扇门。如果手中没有钥匙，就要随机轰炸一个房间来打开这个房间。如果有钥匙，就要去打开这些房间。问期望轰炸次数是多少。思路根据期望的线性性质，总期望轰炸次数就是每个房间被轰炸的概率\(\times\) 1。所以就...

传递闭包 floyd bitset

2019-01-23

0 426

hdu5306 Explosion

题目链接题意有n个房间，每个房间里面有若干把钥匙，每把钥匙可以打开对应的一扇门。如果手中没有钥匙，就要随机轰炸一个房间来打开这个房间。如果有钥匙，就要去打开这些房间。问期望轰炸次数是多少。思路根据期望的线性性质，总期望轰炸次数就是每个房间被轰炸的概率\(\times\) 1。所以就...

传递闭包 floyd bitset

2019-01-23

0 496

bzoj2208 连通数(bitset优化传递闭包)

题目链接思路 floyd求一下传递闭包，然后统计每个点可以到达的点数。会tle，用bitset优化一下。将floyd的最后一层枚举变成bitset。代码 /* * @Author: wxyww * @Date: 2019-01-23 15:08:40 * @Last Modifie...

传递闭包 floyd bitset

2019-01-23

0 625

bzoj2208 连通数(bitset优化传递闭包)

题目链接思路 floyd求一下传递闭包，然后统计每个点可以到达的点数。会tle，用bitset优化一下。将floyd的最后一层枚举变成bitset。代码 /* * @Author: wxyww * @Date: 2019-01-23 15:08:40 * @Last Modifie...

传递闭包 floyd bitset

2019-01-23

0 503

bzoj3331 压力(圆方树)

题目链接圆方树圆方树就是对于联通无向图中的每一个点双新建一个方点，与点双中的每个点连一条边，然后将原来的边删去。将原来的点看作圆点，新建的点看作方点。所以叫做圆方树。性质 1.圆方树肯定是棵树(废话)。证明显然。 2.圆方树中与圆点相连的点肯定是方点。与方点相连的点肯定是圆点。算法...

圆方树

2019-01-22

0 442

bzoj3331 压力(圆方树)

题目链接圆方树圆方树就是对于联通无向图中的每一个点双新建一个方点，与点双中的每个点连一条边，然后将原来的边删去。将原来的点看作圆点，新建的点看作方点。所以叫做圆方树。性质 1.圆方树肯定是棵树(废话)。证明显然。 2.圆方树中与圆点相连的点肯定是方点。与方点相连的点肯定是圆点。算法...

圆方树

2019-01-22

0 553

UOJ176 新年的繁荣

题目链接 Boruvka生成树算法 \(Boruvka\)算法就是先把每个点看作一个联通块，然后不断在联通块之间找最优的边进行合并。因为每次联通块的数量最少缩小一半。所以合并次数是\(log\)的先把所有的点权挂到\(trie\)树上。然后对于每个联通块进行合并的时候。对于联通块中的每个点都去...

最小生成树

2019-01-21

0 639

博客简介

受限于博主水平，本博客可能会有一些错误。请勿轻信。欢迎指正。博主是一个正在OI路上摸爬滚打的现役OIER，我的个人博客申请友链请联系我 QQ 博客园消息自二月十五日之后的博客题目链接会尽量改为镶嵌页面(权限题和加载过慢的网站除外)，题解提交一条龙服务哦\(qwq\)

2018-12-26

0 424

[后缀数组][学习笔记]

定义——来自百度百科子串一个字符串中连续的一段成为这个字符串的子串。后缀后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串 r 的从第 i 个字符开始的后缀表示为 Suffix(i) ，也就是Suffix(i)=r[i,len(r)] 。子串的大小大小比较：关于字符串...

2018-12-20

0 453

[bzoj1717][Milk Patterns 产奶的模式]

题目链接思路先求出后缀数组，并且求出LCP。二分一下长度len。check的时候就是看有没有连续的k个后缀的LCP大于len。也就是判断是不是有连续的k-1个height大于len。代码 #include<cstdio> #include<iostream> u...

2018-12-19

0 520