wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

bzoj3900 交换茸角

题目链接思路看到n比较小，可以状压。可以先考虑什么情况下会无法平衡。显然就是排完序之后两两相邻的不能满足小于等于c的限制。状态。用f[i]来表示i集合中的鹿完成交换所需要的次数。预处理。无法平衡的肯定就是INF。已经平衡的是0。其他的先暂设为k-1(k是i集合中鹿的个数)。然后转移。...

动态规划dp 状态压缩

2019-01-24

0 491

bzoj3900 交换茸角

题目链接思路看到n比较小，可以状压。可以先考虑什么情况下会无法平衡。显然就是排完序之后两两相邻的不能满足小于等于c的限制。状态。用f[i]来表示i集合中的鹿完成交换所需要的次数。预处理。无法平衡的肯定就是INF。已经平衡的是0。其他的先暂设为k-1(k是i集合中鹿的个数)。然后转移。...

动态规划dp 状态压缩

2019-01-24

0 472

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

位运算小结

听attack学长讲完课，整理一波基本运算按位或 \(1|1 = 1，1 | 0 = 1，0|0 = 0\) 按位与 \(1\&1=1 ,1 \& 0 = 0,0 \& 0 = 0\) 异或 \(1 \bigoplus 1 =...

位运算

2019-01-23

0 606

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