爱悠闲 > 分类 >

BZOJ 第48页

BZOJ 1529 POI2005 ska Piggy banks 并查集
题目大意:有n个储钱罐,每个的钥匙都在另一个里面,求取出所有储钱罐中的钱最少要砸开几个 容易发现每个联通块都是一棵外向树,我们只需要砸开环上的任意一个节点就可以打开这个联通块中的所有储钱罐 问题转化成了求一个图的联通块个数 上并查集即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #de
BZOJ 3926 Zjoi2015 诸神眷顾的幻想乡 后缀自动机
题目大意:给定一棵树,每个节点有一个字符,求从一个节点出发沿最短路径走到另一个节点所构成的字符串一共有多少种 此生无悔入东方,来世愿生幻想乡 题目戳这里 注意一句话:太阳花田的结构比较特殊,只与一个空地相邻的空地的数量不超过20个 有奖问答:↑你看到这句话的第一反应是啥? 1.度数<=20 2.叶节点数<=20 仔细看几遍就能找到答案~ [捂脸熊]陈老师真是语文高手。。。。 叶节点数<=20还做啥
BZOJ 3925 Zjoi2015 地震后的幻想乡 期望状压DP
题目大意:给定一张点数不超过10的无向连通图,每条边有一个[0,1]之间的随机权值,求最小生成树上最大边的期望值 此生无悔入东方,来世愿生幻想乡 OTZ 首先既然权值在[0,1]之间均匀分布那么两条边权值相同的概率为0 于是我们只考虑所有边边权都不同的情况 如果最小生成树上的最大边为x,那么权值小于x的边一定不能将这个图连通,而权值<=x的边就可以 因此对于一个x,如果我们求出【只有边权小于x的边
BZOJ 3924 Zjoi2015 幻想乡战略游戏 动态树分治
题目大意:给定一棵树,每个点有一个点权,多次改变某个点的点权,多次查询带权重心到所有点的带权距离之和 此生无悔入东方,来世愿生幻想乡 首先我们考虑如何计算一个点到所有点的带权距离之和且支持修改 用动态树分治就好了嘛。。。 每个点记录子树中带权距离之和,以及权值之和,再在每个子树中记录一个需要减掉的版本 然后一直向上扫到根就能统计了 ↑这段话面对会写动态树分治的人,不会的先去切捉迷藏吧 然后就好搞了
BZOJ 3930 CQOI2015 选数 莫比乌斯反演
题目见 http://pan.baidu.com/s/1o6zajc2 此外不知道H-L<=10^5这个条件是干嘛的。。。。 #include <map> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 10001000 #define INF 0x3f3f3f3f #d
BZOJ 3931 CQOI2015 网络吞吐量 Dijkstra+网络流
题目大意见http://pan.baidu.com/s/1o6zajc2 用Dijkstra跑出最短路图,然后拆点跑网络流即可 这水题我TM还WA了两次是不是省选要滚粗了 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 1010 #define S 0 #define T
BZOJ 3932 CQOI2015 任务查询系统 可持久化线段树
题目大意见http://pan.baidu.com/s/1o6zajc2 主席树裸上就好了。。。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 using namespace std; struct Segtree{ Segtree *ls,*rs;
BZOJ 3933 CQOI2015 多项式 高精度
题目大意戳这里 用x替换式子中的x-t得到: ∑nk=0ak(x+t)k=∑nk=0bkxk 于是可以得到: bm=∑nk=mCk−mktk−mak=∑n−mi=0Cim+itiam+i 其中 ai=(209∗1234i mod 3388+3181) mod 3389 然后。。。出题人我*尼玛。。。 #include <cstdio> #include <cstring> #include <io
BZOJ 3938 Robot 线段树
题目大意:给定n个点,每个点沿数轴匀速直线运动,多次改变某个点的速度和询问当前离数轴最远的点 标解见http://pan.baidu.com/share/link?shareid=4093182173&uk=2587171485#path=%252F%25E9%259B%2586%25E8%25AE%25AD%25E9%2598%259F%25E4%25BA%2592%25E6%25B5%258B
BZOJ 2331 SCOI2011 地板 插头DP
题目大意:给定一张有坏点的地图,要求用L型地毯将整个图覆盖,求方案数 插头DP。。。 首先由于R*C<=100,故min(R,C)<=10 然后插头状态为:0-无插头 1-有一个没有拐过的插头 2-有一个拐过的插头 然后就自己YY吧。。。。 珍爱生命,远离memset #include <cstdio> #include <cstring> #include <iostream> #include