爱悠闲 > 分类 >

BZOJ 第49页

BZOJ 2401 陶陶的难题I 数论
题目大意:求 ∑Ni=1∑Nj=1Lcm(i,j) 一开始写了个莫比乌斯反演结果T到死。。。 ∑Ni=1∑Nj=1Lcm(i,j)=∑Ni=1i+2∑Ni=1∑i−1j=1Lcm(i,j)=∑Ni=1i+2∑Ni=1∑i−1j=1i∗jGcd(i,j)=∑Ni=1i+2∑Nd=1∑⌊Nd⌋i=2∑i−1j=1[gcd(i,j)=1]d∗i∗j=∑Ni=1i+2∑Nd=1∑⌊Nd⌋i=2d∗i∗i∗
BZOJ 3942 Usaco2015 Feb Censoring KMP算法
题目大意:给定两个串A和B,要求将A中删掉所有的B后输出 为何BC群刚有人问完我这题的【C++语法基础题】版之后就出了个KMP版的= = 维护一个栈,将A中的字符依次加进去,一旦A的栈顶出现了B就弹栈 用KMP算法来加速这个过程即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #defi
BZOJ 3943 Usaco2015 Feb SuperBull Prim
题目大意:给定n个数,每次选择两个数,将两数的异或值计入答案,并删掉其中一个,反复如此直到只剩一个数为止,求答案的最大值 每次将选择的两个数连边,那么显然会得到一棵树 用Prim算法求最大生成树即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 2020 using n
BZOJ 3940 Usaco2015 Feb Censoring AC自动机
题目大意:给定一个字符串A和一些模板串,要求删除A中所有的模板串后输出 同3942,由于是多串所以把KMP换成AC自动机即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 using namespace std; int n; char s[M],_s[M
BZOJ 2244 SDOI2011 拦截导弹 CDQ分治/二维树状数组
题目大意:给定一个序列,每个元素是一个二元组,等概率选择一LIS,求LIS长度以及每个元素被选中的概率 第一问CDQ分治裸上 第二问用每个元素所在的LIS个数/总LIS个数就是答案 每个元素所在的LIS自己必选,然后统计前面的方案数和后面的方案数 以前面的方案数为例,令f[x]为以x结尾的LIS长度,那么有DP方程: g[i]=Σg[j] (f[j]+1=f[i],j<i,a[j].x<a[i].
BZOJ 1094 ZJOI2007 粒子运动 计算几何
题目大意:给定一个圆,一堆粒子在里面反射,每个粒子只能撞墙k次,求全程粒子间距离的最小值 每两个粒子之间计算一遍 反射就是把射线沿着切线作镜像变换 随便搞搞咯…… #include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #def
BZOJ 2701&&BZOJ 1319 Discrete Roots 数论
题目大意:求方程 xk≡a(mod p) 在 [0,p) 区间内的全部解 取 p 的一个原根 g ,两侧取指标得到: k∗indgx≡indga(mod p−1) 上EXGCD即可 注意 a=0 要特判 (EXGCD已死系列…… #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <a
BZOJ 3944 Sum 数论
题目大意:求 ∑ni=1φ(i) 和 ∑ni=1μ(i) 。 n≤231−1 令 F(n) 为 f(n) 的前缀和, G(n) 为 g(n) 的前缀和,且满足 g(n)=∑i|nf(i) ,则有: G(n)=∑ni=1g(i)         =∑ni=1∑j|if(j)         =∑nj=1∑j|if(j)         =∑nj=1⌊nj⌋f(j)         =∑nj=1F(⌊
BZOJ 2960 跨平面 对偶图+朱刘算法
题目大意:给定一张平面图,求对偶图的最小树形图 这题TM考了我两遍!!两遍!!我拿了两遍MST的60分! 世界你赢了 你逼着我学了朱刘算法233 #include <cmath> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 3030
BZOJ 3128 Usaco2013 Open Figure Eight
题目大意:给定一个有坏点的矩阵,求能画出来的最大的“8”字形 “8”字形满足: *数字8由上下两个矩形构成。 *数字8的上下两个矩形都满足至少有一个单元格在矩形内部。 *数字8顶部的矩形的底边必须为底部矩形顶边的子集。 *数字8只能刻在大理石完美无瑕的部分。 *规定数字8的得分为上矩形和下矩形的面积的乘积,它们希望得分能达到最大。 枚举顶部矩形的底边,可以用上一行的底边O(1)转移得到,然后每行O