爱悠闲 > 分类 >

BZOJ 第20页

BZOJ 3052 WC2013 糖果公园 带修改树上莫队
题目大意:给定一棵树,每个点有一个颜色,提供两种操作: 1.询问两点间路径上的Σv[a[i]]*w[k],其中a[i]代表这个点的颜色,k表示这个点是这种颜色第k次出现 2.修改某个点的颜色 VfleaKing的题解见 http://vfleaking.blog.163.com/blog/static/174807634201311011201627/ 带修改莫队上树……如果不带修改就正常搞就好了
BZOJ 1854 SCOI2010 游戏 二分图最大匹配/并查集
题目大意:给定n个武器,每个武器有两个属性,只能使用其中一个,要求选择一些武器 可以造成形如1 2 3 4的伤害 求最大伤害 题目大意我没写明白还是去看原题把QAQ 做法1: 同 1191 每个武器向两个属性连边 然后从1~10000枚举属性 跑二分图最大匹配 无法匹配则输出答案 #include<cstdio> #include<cstring> #include<iostream> #incl
BZOJ 3769 spoj 8549 BST again 记忆化搜索
题目大意:求深度为h,大小为n个BST的数量对1000000007取模的值 令f[i][j]为大小为i,深度为j以下的BST的数量 设根节点为k,那么两个儿子一定分别是两个BST 有递推式f[i][j]=(1<=k<=i)Σf[k-1][j-1]*f[i-k][j-1] 记忆化搜索即可 卡常数可以过 #include <cstdio> #include <cstring> #include <io
BZOJ 3781 小B的询问 莫队算法
题目大意:给定一个序列,多次询问某个区间中所有数字出现次数的平方和 莫队算法 不解释 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 50500 using namespace std; struct query{ int l,r
BZOJ 3758 数数 分块打表
题目大意:定义一个数是完美的,当且仅当这个数的每一位可以分成两个集合,使这两个集合之和相等,求[a,b]区间内有多少个数是完美的 数位DP?……不大好搞 分块打表大法好! 首先考虑验证一个数是不是完美的怎么搞 求出数字和 如果是奇数肯定不是 如果是偶数就跑一下背包 背包很慢?没关系,由于最大的和只能有9*8/2=36 所以我们直接状压 令f=1 然后对于每一位x有 f|=f<<x 最后返回f&(1
BZOJ 3738 Ontak2013 Kapitał 数论
题目大意:求C(n+m,n)去掉末尾所有的0之后的后k位 组合数取模问题……首先k<=9,所以我们考虑直接mod 10^9 将10^9分解质因数,可以得到10^9=2^9*5^9=512*1953125 这两个数都不是很大 所以直接套用组合数取模的模板 具体细节参见 2142 礼物 http://blog.csdn.net/popoqqq/article/details/39891263 消0的时
BZOJ 1189 HNOI2007 紧急疏散evacuate 二分答案+最大流
题目大意:给定一个m*n的地图,每个点有可能是空地、墙或者出口,每个空地初始站着一个人,每一时刻可以向周围走1格,门每一时刻只能通过一个人,求最短多少时间后所有人可以撤离 首先从每个出口出发开始广搜,得到每个空地到所有出口的距离 然后二分答案,每次建图如下: 从源点向每个空地一条流量为1的边 如果一个空地能在规定时间到达某个出口,就从这个空地出发向该出口链接一条流量为1的边 每个出口向汇点连接一条
BZOJ 2219 数论之神 数论
题目大意:求在[0,p)范围内的解的个数 鏼爷的题解:http://jcvb.is-programmer.com/posts/42036 我只是来粘代码的QAQ 指标啥的原根啥的中国剩余定理啥的真的完全不知道QAQ #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorith
BZOJ 1132 POI2008 Tro 计算几何
题目大意:给定平面上的一些点,求这些点能组成的所有三角形的面积之和 首先我们枚举每一个点 以这个点为原点建立平面直角坐标系 然后将第一、四象限和x、y轴正半轴上的点按照斜率排序 枚举第二个和第三个点 这样做是O(n^3)的 肯定超时 但是我们发现了什么? 对于每个点k 它对答案的贡献为: (x1*yk-y1*xk)+(x2*yk-y2*xk)+...+(x_(k-1)*yk-y_(k-1)*xk)
BZOJ 3786 星系探索 DFS序+Splay
题目大意:给定一棵有根树,提供下列操作: 1.询问某个点到根路径上的点权和 2.修改某个点的父亲,保证修改之后仍然是一棵树 3.将某个点所在子树的所有点权加上一个值 子树修改,LCT明显是搞不了了,在想究竟会不会有人去写自适应Top-Tree…… 首先我们DFS搞出这棵树的入栈出栈序 然后入栈为正出栈为负 那么一个点到根的路径上的点权和就是从根节点的入栈位置到这个点的入栈位置的和 子树修改就记录某