爱悠闲 > 分类 >

BZOJ 第32页

BZOJ 1057 ZJOI2007 棋盘制作 单调栈
题目大意:给定一个黑白两色的矩阵,求最大的黑白相间的子正方形和子矩阵 将奇数位置的点反色,然后就是求纯色的最大子正方形和子矩阵 将矩阵一层层剖分,每层上方是一段类似于▆▃▇▂▉的东西,用单调栈跑出每个点向左向右能拓展到的最大距离,更新答案即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm>
BZOJ 3239 Discrete Logging Baby-Step-Giant-Step
题目大意:给定P,B,N,求最小的L使B^L≡N (mod P) (P是质数) 裸的BSGS。。。 练练手吧- - #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 #define INF 0x3f3f3f3f using n
BZOJ 2795 Poi2012 A Horrible Poem Hash
题目大意:给定一个字符串,多次询问某一子串的循环节 首先循环次数一定是子串长度的约数 因此我们可以枚举子串长度的约数进行验证 验证时选择Hash,验证[x,y-len]和[x+len,y]这两段是否相等,O(1)即可出解 但是这样做总复杂度是O(q√n)的,会T 考虑一个优化,设某个字母在子串中出现了k次,那么循环次数一定是k的约数 因此我们取每个字母在子串中出现次数的Gcd,枚举这个值的约数即可
BZOJ 2096 Poi2010 Pilots 单调队列
题目大意:给定一个序列,求一个最长的子串,使最大值与最小值之差不超过k 从左到右枚举右端点,利用单调队列维护当前区间中的最大值和最小值 如果某一时刻当前区间的最大值和最小值之差超过了k,就向右调整左端点直到差小于等于k为止 时间复杂度O(n) #include <cstdio> #include <cstring> #include <iostream> #include <algorithm>
BZOJ 1097 POI2007 旅游景点atr SPFA+状压DP
题目大意:给定一张图,要求从第一个点出发,按照某个拓扑序遍历2~k+1的所有节点,然后到达n,求最短路径 首先将所有关键点之间的最短路用SPFA求出来 然后状压DP 令f[state][p]表示已经走过的点集为state,将要走到p点的最短路 记忆化搜索就行了- - 标准卡时过- - #include <cstdio> #include <cstring> #include <iostream>
BZOJ 1370 Baltic2003 Gang团伙 并查集
题目大意:给定n个人,朋友的朋友是朋友,敌人的敌人是朋友,朋友之间组成一个团伙,求团伙数 将每个点x拆成两个:x和x+n 如果x和y是朋友,就将x和y合并 如果x和y是敌人,就将x和y+n合并,将y和x+n合并 注意敌人的朋友不一定是敌人,因此如果x和y是朋友,不能将x+n和y+n合并 #include <cstdio> #include <cstring> #include <iostream>
BZOJ 2729 HNOI2012 排队 组合数学
题目大意:给定n个男生m个女生两个老师,求有多少种排列满足任意两个女生不相邻,任意两个老师也不相邻 def A(n): re=1 for i in range(1,n+1): re*=i return re def C(n,m): if n<m: return 0 return A(n)//A(m)//A(n-m) n,m=[int(i) for i in raw_input()
BZOJ 1811 IOI2005 mea
题目大意:有一个单调不降整数序列,定义平均值数列为这个数列的相邻两项的平均值组成的序列,现在给定这个平均值序列,问原序列有多少种 这相当于给定了相邻两项之间的对称轴 那么我将这个数轴沿着这个对称轴折叠 相邻两项在数轴上就重合了 如果将整个数轴沿着所有的对称轴各折叠一次,所有的点就会重合于一点 此时所有对称轴组成的区间的交集大小就是解的数量 注意无解情况 500W的读入还真有人敢传。。。 #incl
BZOJ 2600 IOI2011 ricehub 中位数
题目大意:给定一条道路上的n个稻田,要求建一个粮仓,并且选定一些稻田进行运输,这些稻田到粮仓的距离之和不能超过B,求最多能选择多少个稻田 维护一个队列,头指针从前到后扫一遍 如果发现尾指针到头指针这段稻田的中位数上建一个粮仓时距离之和超过了B,就调整尾指针 对距离维护一个前缀和 每次取中位数之后可以O(1)计算距离和 #include <cstdio> #include <cstring> #in
BZOJ 2258 pku2758 Checking the Text 文本校对 Splay+Hash
题目大意:给定一个字符串,多次插入一个字符和询问某两个后缀的LCP Splay+Hash。同1014 这逗比的询问。。。。。。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 50500 #define BASE 151 using namespace std; type