爱悠闲 > 分类 >

BZOJ 第19页

BZOJ 3732 Network Kruskal重构树
题目大意:给定一个n个点m条边的无向连通图,k次询问两点之间所有路径中最长边的最小值 Kruskal+倍增LCA做法见http://blog.csdn.net/popoqqq/article/details/39755703 LCT做法见http://blog.csdn.net/popoqqq/article/details/39929277 Kruskal重构树真是强大……一不小心手滑就RANK
BZOJ 2438 中山市选2011 杀人游戏 Tarjan
题目大意:有n个人,其中一个是杀手,可以询问一些人,如果是杀手就会死,如果是平民,他会告诉你他认识的人中有谁是杀手有谁是平民 警告:数据有误,请谨慎提交! 易知如果我需要访问x个人,那么答案就是1-x/n 我们需要访问最少的人 如果我访问的人是平民,那么这个点所有的后继我都能知道 于是Tarjan缩点之后入度为零的点就是答案 但是还有一个问题 比如说这组样例 3 1 1 2 我访问了1,那么1和2
BZOJ 1935 SHOI2007 园丁的烦恼 树状数组
题目大意:给定平面上的一些点,多次询问某个矩形中有多少个点 将每个询问拆成4个 然后把所有询问和点都按照横坐标排序 对于每个询问,将所有x值小于等于这个询问的x的点的y值加入树状数组 然后在树状数组上查询小于等于这个询问的y值的点的数量 别被1000W吓到了 如果不爆内存的话1E也是能搞的 套个log就没多少了 #include <cstdio> #include <cstring> #inclu
BZOJ 3757 苹果树 树上莫队
题目大意:给定一棵树,每个节点有一个颜色,多次求两个节点的路径上有多少种不同的颜色 其中还有两个参数a和b,若苹果树上同时有这两种颜色,ans-- 传说中的树上莫队……颜色数既不满足区间加法也不满足区间减法,直接维护极其困难,这种东西就直接考虑莫队好了 但是怎么转移是个问题 首先树分块 然后以左端点所在块为第一键值,右端点在DFS序中的位置为第二键值排序 (优化:若左端点在DFS序中的位置大于右端
BZOJ 3720 Gty的妹子树 块状树
题目大意:维护一棵树,每个点有一个权值,提供下列操作: 1.询问某棵子树中有多少个节点的权值大于x 2.修改某个节点的权值 3.增加一个叶子节点 强制在线 传说中的树分块 首先DFS,对于每个节点,如果这个节点的父亲节点所在块未满,就塞进父节点所在块中,否则自成一块,然后与父节点所在的块连边 添加节点同理 然后就按照分块直接搞吧0.0 细节实在是太多了 所以写挂的地方看看本蒟蒻的代码就好了0.0
BZOJ 2464 中山市选2009 小明的游戏 SPFA
题目大意:给定一个由'#'和'@'构成的二维矩阵,走到不同的字符需要代价1,求s到t的最短路 签到题+1 这操作符重载要不要写的这么高大上…… #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 510 using namespace std; typedef pair<in
BZOJ 3727 PA2014 Final Zadanie 贪心
题目大意:给定n个数,多次询问选择k个数使和为奇数的最大和 首先将所有数排序 对于每个询问,如果最大的k个数之和是奇数,那么答案显然是这k个数的和 如果最大的k个数之和是偶数,那么我可以将后k个数中最小的偶数换成前n-k个数中最大的奇数,或者将后k个数中最小的奇数换成前n-k个数中最大的偶数 二者取最优即可 无法如此做则输出-1 #include <cstdio> #include <cstrin
BZOJ 3731 Gty的超级妹子树 块状树
题目大意:同3720 增加了一个操作 即删除一个点与父亲节点的连边 3720题解见 http://blog.csdn.net/popoqqq/article/details/41481439 断开一个节点与父节点的连边时 如果这个点是所在块的根节点,直接断掉就行 如果这个点不是所在块的根节点,那么就要把这个块分裂,这个点以及在块中的子树都分裂到新的块中,细节讨论较多不大好写0.0 然后是一些小问题
BZOJ 2434 NOI2011 阿狸的打字机 fail树+树状数组
题目大意:初始字串为空,首先给定一系列操作序列,有三种操作: 1.在结尾加一个字符 2.在结尾删除一个字符 3.打印当前字串 然后多次询问第x个打印的字串在第y个打印的字串中出现了几次 卡了很久……到底还是对AC自动机了解不是很深啊QAQ fail树不是很难想 至少在用AC自动机切掉3172之后不是很难想…… 首先构建AC自动机 注意由于这个字串的特殊构造 我们不必每打印一个字符串再插入Trie树
BZOJ 3759 Hungergame 博弈论+高斯消元
题目大意:给定一些箱子,每个箱子里有一些石子,两个人轮流操作,每个人可以进行以下操作之一: 1.打开任意多的箱子 2.从一个打开的箱子中拿走任意多的石子 不能操作者判负,求先手是否必胜 先手必胜的状态为:给出的数字集合存在一个异或和为零的非空子集,则先手必胜 证明: 首先我们有状态A:当前的所有打开的箱子中的石子数异或和为零,且所有关闭的箱子中的石子数的集合中不存在一个异或和为零的非空子集 易证A