爱悠闲 > 分类 >

BZOJ 第22页

BZOJ 1170 [Balkan2007]Cipher Hash
题目大意:给定一个二维矩阵,求出现次数最多的a*b的子矩阵 二维Hash,只要记住横纵的BASE不能相同就可以,爱怎么搞怎么搞 一开始写的自然溢出 结果OLE 以为是自然溢出被卡掉了于是写了双取模…… 结果还是OLE 最后发现尼玛这题读入坑爹……字符串里有空格不说,满满的不可见字符是咋回事…… 记住不要用scanf读入……可以用gets,或者fread,注意要把一开始的回车过滤掉 getchar读
BZOJ 1853 SCOI2010 幸运数字 容斥原理+DFS
题目大意:求[l,r]区间内有多少个数是只由6和8组成的数的倍数 同2393 链接:http://blog.csdn.net/popoqqq/article/details/41807333 此题数据强力了一些 由于r<=10^10 所以计算LCM的时候会爆long long 于是我们可以用double求出LCM的近似值与r进行比较 如果小于r再取精确值进行计算 此外就是搜索的时候要从大到小搜 从
BZOJ 1100 POI2007 对称轴osi 计算几何+KMP算法
题目大意:给定一个多边形,求对称轴数量 我X 这究竟是怎么想到KMP的…… 首先 将边字符化 即找到这个多边形的中心 然后用与中心构成的三角形的边-角-边的方式表示这条边 将边顺时针扫一遍 然后倍增至长度为2n-1 再逆时针扫一遍 逆时针扫的那遍在顺时针那遍中出现的次数就是对称轴数目 用KMP算法就能搞出来 证明自己YY吧 出题人卡精度丧心病狂。。。 #include <cmath> #inclu
BZOJ 1758 Wc2010 重建计划 树的点分治+二分+单调队列
题目大意:给定一棵树,询问长度在[l,u]范围内的路径中边权的平均值的最大值 01分数规划,首先想到二分答案 既然是统计路径肯定是点分治 每次统计时我们要找有没有大于0的路径存在 那么对于一棵子树的每一个深度i记录一个路径权值和的最大值 然后在这棵子树之前的所有子树的深度可选范围就是[l-i,u-i] 这个窗口是不停滑动的 因此用单调队列维护最大值即可 ↑上面这些网上的题解都说的还是蛮详细的 据说
BZOJ 3563 DZY Loves Chinese 并查集
题目大意:给定一个无向联通图,q次询问当图中某k条边消失时图是否联通 强制在线 逗比题233 不明白什么意思的去看DZY Loves Chinese II的红字就明白这题为何逗比了0.0 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 using names
BZOJ 3569 DZY Loves Chinese II 高斯消元
题目大意:给定一个【魞歄连通图】,多次询问当图中某k条边消失时这个图是否联通 强制在线 我们找到这个图的任意一棵生成树 然后对于每条非树边将其的权值赋为一个随机数 对于每条树边 我们将这条树边的权值设为所有覆盖这条树边的边权的异或和 那么图不连通当且仅当删除一条树边和覆盖这条树边的所有边集 而由于刚才的处理一条树边和覆盖这条边的所有边集的异或和为零 于是问题转化成了对于给定的k条边是否存在一个边权
BZOJ 3790 神奇项链 Hash+二分+树状数组
题目大意:给定一个串,问这个串最少可以由回文串拼接多少次而成(拼接可以重叠) 首先将每两个字符之间插入占位符,然后Hash+二分搞出所有极大回文串(可以用manacher,我不会) 问题转化成了给定一些区间,求最少的能覆盖整个数轴的区间 将所有区间按照某一端点排序 然后上树状数组即可 回头还是去学学manacher吧。。。 #include <cstdio> #include <cstring>
BZOJ 2618 CQOI2006 凸多边形 半平面交
题目大意:给定n个凸多边形,求交集的面积 时隔多年我终于把完整的半平面交搞出来了……真尼玛艰辛…… 曾经写了一发 RE到死 于是就搁置0.0 今天写一发又是WA到死的节奏…… 不多说直接上代码 其实刘汝佳同学写麻烦了 每次插入一个半平面之后不用两端都删的 只删一端 最后再处理两端的部分就行 300题留念……切了道模板题也不错 #include <cmath> #include <cstdio> #
BZOJ 3798 特殊的质数 分块打表
题目大意:求[l,r]区间内有多少个质数可以分解为两个正整数的平方和 考虑到对于一个数Check一下是O(√n)的 我们可以将3*10^8分成3000块 每块10W 对于整块的打表求出有多少个质数 块内暴力 令n为块的大小 则时间复杂度为O(n√n) 打表时忘加优化忘开O2 打了一下午 各种酸爽 #include <cmath> #include <cstdio> #include <cstrin
BZOJ 2802 Poi2012 Warehouse Store 堆+贪心
题目大意:有n天,早上进货中午卖,可以选择卖或者不卖,问最多可以卖出多少人 首先贪心的思想是如果当前能卖就卖 但是这样不一定是最优的 比如说我第一天来一个人把所有的库存都买走了 然后后面基本没有补给 后面的人都饿死了 因此我们维护一个大根堆来记录我们都卖出了多少份 如果有一个人买不到 我们去大根堆里寻找有没有买的比他多的 如果有 把之前的人取消 卖给这个人 这样虽然不能增加答案 但是可以增加库存