爱悠闲 > 分类 >

BZOJ 第54页

BZOJ 3774 最优选择 最小割
题目大意:给定一张网格图,每个点有一个代价和一个收益,如果选择了某个点将会付出这个代价,如果一个点被选择或周围的4个点都被选择那么就会获得这个收益,求最大收益 乍一看这个关系中既有【且】又有【或】,没有办法直接建图 但是我们有一个结论: 如果一个点周围的4个点都被选择,那么这个点一定不会被选择 这个结论几乎是显然的,因为如果周围的4个点都选择了的话,选择这个点一定不会产生任何贡献,不如不选 然后就
BZOJ 3004 吊灯 树形DP
题目大意:给定一棵树,要求将这棵树分成 nk 个连通块,每块大小为 k ,求所有可行的 k 首先 k 一定是 n 的约数。(废话 然后我们有一个结论:某个 k 满足条件当且仅当存在 nk 个节点满足以每个节点为根的子树大小都是 k 的倍数 证明: 首先不可能存在超过 nk 个节点满足以每个节点为根的子树大小都是 k 的倍数,这是废话 首先证明必要性: 假设我们已经有了一组合法的方案,那么对于每一个
BZOJ 3308 九月的咖啡店 费用流
题目大意:在 [1,n] 区间内选择一些数,使得这些数两两互质,求这些数的和的最大值 容易发现对于一个最优解,每个质数存在且仅存在于一个数中。(废话。 但是有可能一个数中存在多个质数 下面是两个结论: 1.一个数中最多存在两个不同的质数 2.这两个质数一个 <n√ ,一个 >n√ 我完全不会证明这两个结论,这两个结论都是官方题解里的 然后就好办了,我们对于 <n√ 的质数和 >n√ 的质数建立二分
BZOJ 2959 长跑 Link-Cut-Tree+并查集
题目大意:给定n个点,支持以下操作: 1.在某两个点之间连接一条无向边 2.改变某个点的权值 3.将每条边设定一个方向,然后从 x 走到 y ,求能经过的所有点的权值和 首先如果这个图是静态的,我们把边双都缩点,那么每次询问显然就是两个点所在边双路径上的点权和 现在图是动态的,因此我们用动态树维护一下就行了 如果连边的两个点不连通,就在LCT中连接这两个点 如果连边的两个点已经连通,就将这个两个点
BZOJ 2276 Poi2011 Temperature 单调队列
题目大意:给定一个序列,每个元素的大小有一个取值范围,求一段区间满足区间内元素可能单调不降 对 L 维护一个单调不增的单调队列,一旦新插入的 R 值比队头的 L 值小就把队头弹掉 这样可以保证单调队列中的元素是合法的极大子区间 然后更新答案就行了 乱写读入优化害死人啊QwQ #include <cstdio> #include <cstring> #include <iostream> #incl
BZOJ 4033 HAOI2015 T1 树形DP
题目大意:给定一棵树,你需要把其中的 k 个点染成黑色,使得黑色点两两之间的距离和+白色点两两之间的距离和最大,求最大值 题解戳这里 Orz ydcydc 看来我对于非线性的树形DP还是做得太少了QwQ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 2020 using
BZOJ 1138 POI2009 Baj 最短回文路 BFS
+题目大意:给定一张有向图,每个点有一个字符,多次求两点的最短回文路 据说这道题第一次做的人都会T? 一开始的思路是这样的:令 fx,y 表示从点 x 走到点 y 的最短回文路径,转移 fx,y=min{fz,w+2|x−c−>z,w−c−>y} 然后广搜,果断T了= = 冗余的转移太多了…… 正解是这样的: 令 gx,y,c 表示从点 x 走到点 y ,除了最后一条边之外是回文路径且最后一条边的
BZOJ 1137 POI2009 Wsp 岛屿 半平面交
题目大意:给定一个凸 n 边形,从点 1 走到点 n ,有一些边不能走,若两条边相交可以变道,求最短路 MD这水题看错题困扰了我多年= = 一直以为是补图的最短路…… 最短路显然是半平面交 从一个点出发的所有边中只有最后一条可能在半平面交上 然后就完事了啊= = #include <cmath> #include <vector> #include <cstdio> #include <cstri
BZOJ 1140 POI2009 KOD 编码 DFS
题目大意:给定一棵二进制编码树,保证每个节点要么有2个儿子,要么没有儿子,每个叶节点代表一个字符,求有多少字符满足即使前面被删掉一个前缀,只要这个字符的编码没有被破坏,就可以保证后面的编码都解读正确 先说下这个做法是可以被卡的…… 首先我们可以发现这样的字符满足【编码树上根节点+任意一个后缀+一些完整的子串+这个字符的转移都能到达一个叶节点】 然后打几个标记爆搜就行了…… 然而这样做的复杂度是 ∑
BZOJ 4082 Wf2014 Surveillance 树上倍增
题目大意:给定一个 n 个点的环,有 k 个区间,要求选择最少的区间覆盖所有点 首先我们考虑链上版本,显然我们有一个贪心的做法: 从1号节点开始,每次选择能向后走的最远的区间,直到走完所有节点为止 正确性显然 但是到了环上版本我们却不能直接套用这个算法,因为环上不存在所谓的“1号节点” 因此我们这样做: 拆环后将序列倍增,把所有区间按照右端点从小到大排序 每个区间向这个区间右端点向后能走的最远的区