爱悠闲 > 分类 >

BZOJ 第25页

BZOJ 2656 ZJOI2012 数列(sequence) 高精度+记忆化搜索
题目大意:给定一个数列的通项公式,求数列的某一项 高精度+记忆化搜索没说的 其实不用记忆化搜索的但是既然写完了就写完了吧 顺便学习了一下友元函数之类的东西- - #include <map> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; class
BZOJ 3170 Tjoi 2013 松鼠聚会 计算几何
题目大意:给定平面上的n个点,求这n个点中的一个点到这n个点的切比雪夫距离之和最小 切比雪夫距离,即各坐标差绝对值的最大值 首先我们如果想把曼哈顿距离转化成切比雪夫距离 那么就要把点(x,y)变成(x+y,x-y) 这样新点之间的切比雪夫距离就是原点之间的曼哈顿距离 同理,我们可以把切比雪夫距离转化成曼哈顿距离 即把点(x,y)变成((x+y)/2,(x-y)/2) 然后将横纵坐标排序 维护前缀和
BZOJ 3210 花神的浇花集会 计算几何- -?
题目大意:给定平面上的n个点,求一个点到这n个点的切比雪夫距离之和最小 与3170不同的是这次选择的点无需是n个点中的一个 首先将每个点(x,y)变为(x+y,x-y) 这样新点之间的曼哈顿距离的一半就是原点之间的切比雪夫距离 由于曼哈顿距离中横纵坐标不互相干扰,因此我们可以将横纵坐标分开处理 每一维要选一个坐标 到其他所有坐标的绝对值之和相等 很容易想到中位数 但是直接选择中位数得到的点可能横纵
BZOJ 3489 A simple rmq problem 可持久化树套树
题目大意:给定一个序列,多次询问某一区间中出现且仅出现一次的最大的数 令第i个数左侧第一个与这个数相同的数为last[i] 右侧第一个与这个相同的数为next[i] 那么一个数a[i]在区间内出现一次当且仅当last[i]<l&&next[i]>r&&l<=i<=r 于是我们将元素按照last[i]排序并构建可持久化线段树 令pos为满足last[i]<l的最大的i 每次查询我要查询的是第pos个
BZOJ 3309 DZY Loves Math 莫比乌斯反演
题目大意: 枚举d=gcd(i,j),得到 现在我们只需要知道Σ[d|T]f(d)μ(T/d)的前缀和就行了 设这个函数为g(x) 观察这个函数 由于含平方因子数的μ值都为零,因此我们只考虑μ(T/d)!=0的数 令T=p1^a1*p2^a2*...*pk^ak,d=p1^b1*p2^b2*...*pk^bk 那么0<=(ai-bi)<=1 如果存在ai≠aj(i≠j),那么我们可以将所有的a分为
BZOJ 3813 奇数国 线段树+数论
题目大意:给定一个序列,每个数都由60个最小的素数的乘积构成,求某段的乘积的欧拉函数值对19961993取模后的值,支持单点修改 19961993是个质数 出题人还是满贴心的 利用线段树维护乘积取模后的值以及哪些素数出现过 后者用bitset维护 得到的值根据bitset里出现过的素数来计算欧拉函数值 时间复杂度O(nlog10W+60n) #include <bitset> #include <
BZOJ 2179 FFT快速傅立叶 快速傅里叶变换
题目大意:给定两个高精度整数,求两个数的乘积 FFT大法好 系统的complex比手写慢了2.5倍 简直吓死人- - #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 131080 #define PI 3.1415926535897932
BZOJ 2194 快速傅立叶之二 快速傅里叶变换
题目大意:给定两个长度为n的序列a和b,求c[k]=Σa[i]*b[i-k] 这东西不是卷积的形式,因此我们将b数组反转,之后就是卷积的形式了 然后就愉♂悦地上FFT吧 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 263000 #de
BZOJ 3257 ZJOI2014 力 快速傅里叶变换
题目大意:给定n个点,第i个点和第j个点之间的库仑力为(qi*qj)/(i-j)^2,定义左侧为正方向,求每个点受的合力与电荷量的比值 题解详见 http://eolv.farbox.com/post/shui-yu-zheng-feng/2014-12-07 我懒得打了- - #include <cmath> #include <cstdio> #include <cstring> #inclu
BZOJ 2165 大楼 倍增Floyd
题目大意:给定一张图,求从1开始到达m的权值至少需要遍历多少条边 n<=100,果断倍增Floyd f[temp][i][j]表示经过2^temp条边从i走到j的最大权值 更新时f[temp[i][j]=max{f[temp-1][i][k]+f[temp-1][k][j]} 然后用矩阵g[i][j]记录当前走的权值,初始主对角线为0,其余为-∞ 从大到小枚举temp,利用f[temp]和g得到矩