爱悠闲 > 分类 >

BZOJ 第26页

BZOJ 2823 AHOI2012 信号塔 计算几何
题目大意:给定n个点(n<=50W),求最小圆覆盖 逗我?n<=50W?最小圆覆盖?O(n^3)? 其实数据是随机生成的 经过验证 随机生成50w的点集 平均在凸包上的点在50~60个左右 于是求凸包之后就可以随便乱搞了- - 不会写O(n^3)的最小圆覆盖 写了O(n^4)的照过 注意最小圆覆盖时要讨论有两点在圆上和有三点在圆上两种情况 --------------------以上是题解----
BZOJ 3160 万径人踪灭 Manacher算法+快速傅里叶变换
题目大意:给定一个由'a'和'b'构成的字符串,求不连续回文子序列的个数 首先回文一定是将字符串倍增 由于求的是不连续回文子序列的个数 因此我们可以求出总回文子序列的个数,然后减掉连续的 连续的就是回文子串 用Manacher算法可以O(n)求解 不连续的就有些难搞了 首先我们令f[i]表示以i为中心的对称字符对个数 比如s[]=$#a#b#a 那么s[4]='b' f[4]=2 那么对于每个中心
BZOJ 3823 定情信物 递推
题目大意:定义点为零维元素,线为一维元素,面为二维元素,空间为三维元素,以此类推,求n维立方体中各维元素都有多少 令f[i][j]为i维立方体内j维元素的个数 考虑n维立方体中的i维元素,将n维立方体拓展至n+1维空间时(觉得抽象的可以想象平面扩展成立方体) 原先的i维元素增加了一倍,同时原先的i-1维元素变为了i维元素 故有f[i][j]=f[i-1][j]*2+f[i-1][j-1] 经过一系
BZOJ 2337 HNOI2011 XOR和路径 期望DP+高斯消元
题目大意:给定一个无向连通图,从1出发,每次等概率沿着任意一条出边走到n为止,求路径上的边权的异或和的期望值 首先既然是位运算的问题我们的一般处理办法就是拆位,按位处理 对于每一位 令f[i]为从i节点出发到n的期望值 对于每条出边,如果这条边边权为1,那么f[x]+=f[y]/d[x] 否则f[x]+=(1-f[y])/d[x] 其中d[x]表示x的度数 特殊地,f[n]=1 由于这个图不是拓扑
BZOJ 3143 HNOI2013 游走 期望DP+高斯消元
题目大意:给定一个无向连通图,我们需要给每条边附一个1~m的不重复的权值,使1到n的期望权值和最小 首先贪心思想是求出每条边的期望经过次数 然后对期望值最小的边附加m的权值,第二小的边附加m-1的权值,以此类推。 令f[i]为第i个点的期望经过次数 那么每条边的期望经过次数就是f[x]/d[x]+f[y]/d[y] 其中d[x]表示x的度数 那么显然有: f[1]=1+Σ[1->j]f[j]/d[
BZOJ 3217 ALOEXT 替罪羊树套Trie树
题目大意:维护一个序列,支持以下操作: 1.在某个位置插入一个数 2.删除某个位置上的数 3.修改某个位置上的数 4.求某段区间中的次大值与区间中另一个数的异或值的最大值 强制在线 替罪羊树套Trie树。。。终于尼玛A了。。。7.4KB的大代码啊- - 插入和修改同带插入区间k小值 删除要打标记不能直接删 删除的时候注意 删除导致的不平衡不要重建 否则复杂度无法保证 因此每个节点维护一个max_s
BZOJ 1706 usaco2007 Nov relays 奶牛接力跑 倍增Floyd
题目大意:给定一张无向图,求从s出发恰好经过n条边到达e的最短路 倍增Floyd……为何大家都管这个叫做矩阵乘法- - 算了为何要纠结这种事- - 令f[p][i][j]表示走2^p步从i到达j的最短路 有f[p][i][j]=min{f[p-1][i][k]+f[p-1][k][j]} 将n进行二进制拆分 用矩阵g记录答案矩阵 对于每一位p 用f[p]和g两个矩阵搞出h 再将h的值赋给g 切忌直
BZOJ 1965 AHOI2005 SHUFFLE 洗牌 数论
题目大意:给定偶数张牌,问m次洗牌之后第l张牌是多少 x*2^m==l (mod n+1) x=(n/2+1)^m*l mod n+1 快速幂+快速乘233 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MOD (n+1) using namespace std; type
BZOJ 2527 Poi2011 Meteors 整体二分+线段树 / 可持久化线段树(MLE)
题目大意:给定一个环,每个节点有一个所属国家,k次事件,每次对[l,r]区间上的每个点点权加上一个值,求每个国家最早多少次操作之后所有点的点权和能达到一个值 首先我们考虑暴力想法 对于每个国家分开讨论 二分操作次数 但是这样每次Judge的时候我们要模拟1~mid所有的操作 浪费在这里的复杂度实在太大 这样做每个国家需要模拟O(klogk)次操作 时间复杂度O(nklogk) TLE 我们需要对浪
BZOJ 2738 矩阵乘法 整体二分+二维树状数组
题目大意:给定一个矩阵,多次求某个子矩阵中的第k小 分块解法见 http://blog.csdn.net/popoqqq/article/details/41356899 《论除最小割外题目解法从来与题目名称无关系列》 整体二分 Solve(x,y,S)表示处理答案在[x,y]区间内的询问集合S 预先将所有数按照大小排序 每次将[1,mid]之间的数插入树状数组 然后对于分治内部的每一个询问 去树