爱悠闲 > 分类 >

BZOJ 第23页

BZOJ 1528 POI2005 sam-Toy Cars 堆+贪心
题目大意:有n个玩具,都放在架子上,地板上能放k个,要玩p次玩具,如果不在地板上就要去架子上拿,地板满了要放回去,求最少操作次数 贪心思想:每次放回玩具时选择下次玩的时间最靠后的玩具放回去 可以用堆来模拟这一贪心过程 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 500
BZOJ 2555 Substring 后缀自动机+Link-Cut-Tree
题目大意:给定一个初始字符串,提供两种操作: 1.在这个字符串的后面连接一个字符串 2.询问某个字符串在当前串中出现了多少次 SAM大叔的自动机~~ 对于每个询问就是在后缀自动机上找到该子串所对应的节点 找不到返回0 然后这个节点的Right集合的大小就是这个子串的出现次数 每次Extend的时候将新建节点沿着parent指针到根的路径上所有点的Right集合大小+1即可 分裂节点的时候要将Rig
BZOJ 3275 Number 最小割
题目大意:给定n个数,如果两个数互质且平方和为完全平方数则不能同时被选,求选出一些数的最大和 首先这肯定是网络流无误 但是建图十分巧妙 很容易发现两个奇数不满足条件一 两个偶数不满足条件2 于是这是一个二分图 跑最小割即可 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algo
BZOJ 3000 Big Number 数学算法
题目大意:求n!在k进制下的位数 即 Stirling公式: 数据范围小就暴力,数据范围大套用Stirling公式 注意先利用log来避免数字过大而失精 最后答案要开long long #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namesp
BZOJ 2348 Baltic 2011 Plagiarism 排序
题目大意:求n个数中有多少无序点对(i,j)满足0.9a[j]<=a[i]<=a[j] 《论排序算法的高效性和合理利用以及能否记得使用排序算法》 忘写sort贡献了个WA 2333333 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 #define EPS
BZOJ 2597 楼房重建 分块
题目大意:给定n座楼,初始高度为0,每次可以改变某栋楼的高度,求每次改变高度之后从原点可以看到几栋楼 记录每栋楼楼顶与原点连线的斜率 那么一栋楼可见当且仅当前面所有楼的斜率都小于这栋楼 将n栋楼分为√(0.5*n*logn)块 每一块内维护一个单调上升子序列(注意不是LCS) 比如说4 1 2 3 5 那么维护的序列就是4 5 修改的时候块内暴力重建 然后查询顺着块撸一遍 每次记录当前的最大值 然
BZOJ 2301 HAOI2011 Problem b 容斥原理+莫比乌斯反演
题目大意:多次询问有多少个数对(x,y)满足a<=x<=b,c<=y<=d,且GCD(x,y)=k 首先利用容斥原理将询问分解 问题转化为求有多少个数对(x,y)满足x<=m,y<=n,且GCD(x,y)=k 这里就可以利用到莫比乌斯反演: 我们令F(d)为GCD(x,y)=d且x<=m,y<=n的数对数 f(d)为d|GCD(x,y)且x<=m,y<=n的数对数 那么显然有F(d)=(n/d)*
BZOJ 2820 YY的GCD 莫比乌斯反演
题目大意:求有多少个数对(x,y),使得x<=m,y<=n且GCD(x,y)为质数 具体去见ACdream的博客 里面讲的还是很详细的 地址 http://blog.csdn.net/acdreamers/article/details/8542292 其实求的时候只需要枚举每个素数暴力就行了 由于有1/1+1/2+1/3+...+1/n=O(logn)这个结论 因此每个质数枚举时是均摊O(log
BZOJ 2882 工艺 后缀自动机
题目大意:最小表示法模板题 不会最小表示法,拿后缀自动机水了一发~~ 一开始还写挂了MLE…… 权当练习一下SAM的熟练度了0.0 #include <map> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 300300 using namespace std; int
BZOJ 3329 Xorequ 数位DP+矩阵乘法
题目大意:给定n,求[1,n]以内以及[1,2^n]以内有多少x满足x^3x=2x x^3x=2x等价于x^2x = 3x 而3x=x+2x 且2x=x<<1 故x满足条件当且仅当x&(x<<1)=0 故x的二进制拆分中任意两个1不相邻 令f[i]为i位数中最高位为0的满足条件的数的数量 g[i]为i位数中最高位为1的满足条件的数的数量 则显然有 f[i+1]=f[i]+g[i] g[i+1]=f