爱悠闲 > 分类 >

BZOJ 第42页

BZOJ 2054 疯狂的馒头 并查集
题目大意:给定一个序列,多次将某个区间染成某种颜色,求最后每个点是什么颜色 m<=1000W,线段树肯定T 由于对每个点起作用的染色只有最后一次,因此倒着做,如果一个点已经被染色,就在并查集中将这个点连向右面那个 这样每个点只会被染色一次,时间复杂度O(n+m) #include <cstdio> #include <cstring> #include <iostream> #include <a
BZOJ 3904 最长上升子序列 lkids 线段树
题目大意:给定一个序列,求以较小数开始的锯齿子序列,使相邻两项之间差值不小于k 令f[i][0]表示第i个数为序列中的较大值的最长子序列 f[i][1]表示第i个数为序列中的较小值的最长子序列 暴力转移是O(n^2)的 我们发现决策点的值都是连续的一段区间 因此用线段树维护一下就行了 (真简略) #include <cstdio> #include <cstring> #include <iost
BZOJ 3901 Magic 最小割
题目大意:给定一张有向图,每个点有一个权值,你可以付出b[i]的代价将第i个点的权值变成0,一个点的代价为所有出边指向的点的代价的最大值,要求代价之和最小 萌哒哒的zxr曾经给我们讲过这个建图方式~ 还记得真是太好了poi~ 将每个点的所有出边指向的点按照权值从大到小建成从源点出发的一条链,一个点与之前的点的边流量为这个点的权值 然后把一个点所有分出去的点全都连到一起,然后向汇点连一条流量为这个点
BZOJ 2938 Poi2000 病毒 AC自动机+拓扑排序
题目大意:给定n个01串,问是否存在一个无限长的01串,不包含这n个01串中的任何一个 建出Trie图之后判环即可 我这傻逼一开始居然跑了一个DFS去判环23333 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 30300 using namespace std; in
BZOJ 1149 CTSC2007 风玲Mobiles DFS
题目大意:给定一棵完全二叉树,可以交换某个节点的左右儿子,求最少交换多少次可以使所有的叶节点深度相差不超过1,且深度较大的叶节点都在深度较小的叶节点左侧 铃抄千 这水题居然还WA了两次- - 脑残害死人啊QAQ 首先DFS一次处理出深度最大和最小的叶节点 如果深度相差>=2则无解 然后再DFS一遍,对于每个节点首先向子节点递归,然后记录左右两棵子树中深度较大叶节点的存在性和深度较小叶节点的存在性
BZOJ 2072 POI2004 MOS 动态规划+贪心
题目大意:过桥问题 我们考虑利用时间最小的两个人倒运,把时间大的人依次送过去 有两种方式: 1.时间最小的人和时间最大的人过去,然后时间最小的人把火把拿回来 2.时间最小和第二小的两个人过去,然后时间最小的人把火把拿回来;接着时间最大和第二大的两个人过去,时间第二小的人把火把拿回来 为了保证最优 运输应该不外乎这两种形式 那么令f[i]表示当前没有过桥的人还剩i个时的最短时间 DP即可 #incl
BZOJ 2946 Poi2000 公共串 后缀自动机
题目大意:求n个串的最长公共子串 太久没写SAM了真是…… 将第一个串建成后缀自动机,用其它的串进去匹配 每个节点记录每个串在上面匹配的最大长度 那么这个节点对答案的贡献就是所有最大长度的最小值 对所有贡献取最大就行了= = 这最大最小看着真是别扭 #include <cstdio> #include <cstring> #include <iostream> #include <algorith
BZOJ 1102 POI2007 山峰和山谷Grz Floodfill
题目大意:给定一张地势图,求山峰和山谷的数量 直接Floodfill……注意DFS会爆栈,用BFS才能过 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 1010 using namespace std; int n,ans1,ans2,a[M][M]; bool fla
BZOJ 1104 POI2007 洪水pow 并查集
题目大意:给定一张地势图,所有的点都被水淹没,现在有一些关键点,要求放最少的水泵使所有关键点的水都被抽干 前排感谢VFK 首先可以证明一定存在一种最优解使所有的水泵都在关键点上 那么我们将所有关键点按照高度排序,从小到大枚举每个关键点 对于每个关键点x,我们将所有高度小于等于x点的点都加入并查集并将相邻的合并 由于x是并查集中最高的点,因此并查集中任意一个点放置水泵都会导致点x被抽干 故如果x所在
BZOJ 1106 POI2007 立方体大作战tet 模拟
题目大意:给定一个长度为2n的序列,1~n各出现两次,可以交换相邻两项,两个同样的数放在一起会对消,求把所有数对消的最小交换次数 如果有一对在另一对中间 那么这一对肯定要先于另一对交换 除掉这个因素之外答案是确定的 由于保证交换次数<=100W,因此可以从左向右扫,维护一个栈,按顺序记录还没有被消掉的元素 如果新来的元素在栈里出现过,就直接去栈中查找,删除后直接维护就可以了 #include <c