爱悠闲 > 分类 >

BZOJ 第30页

BZOJ 3672 NOI2014 购票 树的点分治+斜率优化
题目大意:给定一棵以1为根的有根树,每条边有边权,每个点有三个值pi,qi,li 从一个点可以走到它的某个祖先处,前提是距离d不超过li,花销为pi*d+qi 求从每个点到达根节点的最小花销 这道题的上一份题解:链接地址 很不幸我作死去重写了一发233 之前的写法真是SB的1B。。。 为何要暴力- - 明明是分治结构直接排序不行么- - 简述一下做法: 0.先推出斜率优化的动归方程 1.找到当前分
BZOJ 2879 NOI2012 美食节 费用流
题目大意:给定n道菜和m个厨师,第i道菜需要p[i]份,第j个厨师做第i道菜需要时间t[i][j],求最长总等待时间 一个厨师做的倒数第一道菜对答案的贡献是时间的一倍,倒数第二道菜对答案的贡献是时间的两倍,以此类推 厨师们怒了!发动符卡·禁忌『p重存在』! 将每个厨师拆成Σp[i]个点,每道菜向每个厨师的第i个点连一条流量为1,费用为时间的i倍,每个点向汇点连一条流量为1费用为0的边,跑最小费用最
BZOJ 2786 Ural1142 Relation 递推
题目大意:用'='和'<'连接n个元素,等号之间看做一个整体,求方案数 令f[i][j]表示i个数划分成j个有序集合的方案数 如果将第i个数划分进原有的集合中,方案数为f[i-1][j]*j 如果将第i个数新建一个集合插进某个位置,方案数为f[i-1][j-1]*j 故f[i][j]=f[i-1][j-1]*j+f[i-1][j]*j ans = [0] * 60 f = [ ([0] * 60)
BZOJ 3834 Poi2014 Solar Panels 数论
题目大意:给定a,b,c,d,多次询问a<=x<=b,c<=x<=d时Gcd(x,y)的最大值ぽい 考虑枚举n=Gcd(x,y),那么[a,b]和[c,d]两个区间内存在n的倍数当且仅当floor(b/n)>floor((a-1)/n)且floor(d/n)>floor((c-1)/n)ぽい 由于后面的式子最多有O(√max(b,d))个取值,因此枚举商就可以了ぽい 1L和2L写了啥ぽい- - #
BZOJ 2553 BeiJing2011 禁忌 AC自动机+矩阵乘法
题目大意:给定n个模式串,定义一个字符串的伤害为所有子串的划分中最多包含的模式串数量,求长度为len的字符串的伤害期望值 小五prpr,恋恋prpr,大小姐prpr 首先建立AC自动机 令f[i][j]表示长度为i的字符串在AC自动机上的第j个节点的伤害期望值 如果要走到某个节点是危险节点或者fail指针指向危险节点,就ans++,然后回到根节点 这样构造出来的矩阵做快速幂= = 这么做都会把-
BZOJ 1213 HNOI2004 高精度开根 二分+高(Py)精(thon)度
题目大意:求n^(1/m) 一大早水个Python- - 直接开根尼玛过不去- - 需要二分- - m,n=int(raw_input()),int(raw_input()) l,r=0,1 while r**m<=n: l=r;r=r*2 while l+1<r: mid=(l+r)//2 if mid**m<=n: l=mid else: r=mid if r**m<=n:
BZOJ 3434 Wc2014 时空穿梭 莫比乌斯反演
题目大意:给定一个n维空间,需要在这n维空间内选取c个共线的点,要求这c个点每维坐标均单调递增,第i维坐标是整数且在[1,mi] 为了表述方便令||代表中间东西的方案数 顺便设第i维坐标为ai 但是这样不简洁因此用x表示第1维坐标,y表示第二维坐标,θ表示第n维坐标 貌似我的方法SB了?不管了总之自己能推出来真是太好了- - 尼玛BZOJ渣评测机卡常数- - 明明UOJ5s就全过了的说- - #i
BZOJ 2813 奇妙的Fibonacci 线性筛
题目大意:给定i,求斐波那契数列中有多少F[j]是F[i]的约数,以及这些j的平方和 定理:Gcd(F[i],F[j])=F[Gcd(i,j)] 证明见 http://hi.baidu.com/wyl8899/item/b4ed30e6b9f404acce2d4f68 那么当F[j]|F[i]时,必有Gcd(F[j],F[i])=F[j] 则此时F[Gcd(j,i)]=F[j] 若Gcd(j,i)
BZOJ 1408 NOI2002 Robot 数论
题目大意:- -我不行了自己看 逗比题- - 用了这么大篇幅来讲述什么是φ和μ- - 不过不是普通的φ和μ,有些变形- - 新定义的φ(1)=0,新定义的μ只计算奇质数,含有2为因子的数都按照μ值为零处理 我们首先求出第一问和第二问,即μ值不等于0的部分 由于μ的定义,μ值不等于0当且仅当每个质因数的次数都是1次 因此我们枚举每个奇质数 计算加上这个奇质数之后φ值之和多出来的部分 由于φ是积性函数
BZOJ 3601 一个人的数论 莫比乌斯反演+高斯消元
题目大意:求Σ[i|n]i^d 围观题解:http://www.cnblogs.com/jianglangcaijin/p/4033399.html 果然我还是太蒻了- - 此外Σ[1<=i<=n]i^m的零次项注定为0- - 所以常数项不用消了- - #include <cstdio> #include <cstring> #include <iostream> #include <algori