爱悠闲 > 分类 >

BZOJ 第31页

BZOJ 3560 DZY Loves Math V 数论
题目大意:给定a1,a2,...,an,求 由于φ是积性函数,我们可以将i1i2...in分解质因数,对于每个质因数分开讨论,求积即可 将每个a分解质因数,假设分解后某个质数p在每个ai中的次数分别是bi,那么p对答案的贡献就是 于是对p^j维护一个前缀和,直接计算即可 #include <cstdio> #include <cstring> #include <iostream> #includ
BZOJ 1086 SCOI2005 王室联邦 块状树
题目大意:给定一棵树,要求将这棵树分成一些块,使每块大小在[B,3B]之间 《手把手教你块状树系列》 - -终于搞懂这题怎么做了 - -去网上扒了个代码居然是错的 坑死我了 - -还好题解的思想是对的 朴素的分块方式是贪心 能加就加 这种方法存在着严重的效率问题 可以被菊花卡成O(n)块 因此我们可以为其它的块预留位置 如果一块大小刚好>=b 就将这坨东西分成一块 首先任选一点开始深搜 维护一个栈
BZOJ 2589 Spoj 10707 Count on a tree II 强制在线莫队算法(TLE)
题目大意:给定一棵树,每个节点有一个颜色,多次询问某条路径上颜色数量,强制在线 正解是块状数组,强制在线莫队会TLE到死,想AC这道题的不用看了 如果朴素的跑树上莫队其实并不难- - 但是强制在线 因此我们可以考虑强制在线莫队算法 将树分成O(n^1/3)块,每块大小O(n^2/3) 记录每两块之间的答案、每种颜色的出现次数和哪些点被记录到了答案中 每次查询先找到两端点所在块的端点的答案,然后暴力
BZOJ 3028 食物 组合数学
题目大意:简单易懂自己看- - 去学了下母函数相关的东西- - 其实不难理解嘛- - 的说- - #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 510 #define MOD 10007 using namespace std; int n; char s[M]; in
BZOJ 1342 Baltic2007 Sound静音问题 单调队列
题目大意:给定一个长度为n的序列,求哪些长度为m的区间满足区间内最大值与最小值之差小于等于c 利用单调队列维护区间内的最大值和最小值- - 硬搞就可以了- - 刷刷水题真爽- - #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 1001001 using namespac
BZOJ 1093 ZJOI2007 最大半连通子图 Tarjan+动态规划
题目大意:定义半连通子图为一个诱导子图,其中任意两点(x,y)中x可到达y或y可到达x,求最大半连通子图的大小以及方案数 不就是个缩点之后拓扑序DP求最长链么 这题意逗不逗233333 注意缩点后连边不要连重复了 判重边那里我用了set。。。 #include <set> #include <cstdio> #include <cstring> #include <iostream> #inclu
BZOJ 3856 Monster 不公平博弈
题目大意:给定一只喵,初始h点HP,每回合先手砍一刀a点伤害,喵后手回b点血,先手k回合攻击之后休息一次,问先手能否砍死喵 C++语法基础题23333333 很容易WA- - 能砍死的三个充分条件: 1.OTK 2.第k回合砍死 3.休息之后喵的血量比初始低 #include <cstdio> #include <cstring> #include <iostream> #include <alg
BZOJ 2134 单选错位 期望DP
题目大意:给定一张n道选择题的试卷,所有答案都是正确的,但是第i个题的答案被答到了第i%n+1个位置上,求期望得分 第i道题的答案被填到了第i%n+1个位置上 期望得分是1/max(a[x],a[i%n+1]) 然后就水了233 #include <cstdio> #include <cstring> #include <iostream> #define M 10001000 #include
BZOJ 3208 花神的秒题计划Ⅰ 记忆化搜索
题目大意:给定一个矩阵,多次改变某个点的权值,设定某个子矩阵内的所有点可用/禁用,求滑雪的最大长度 再也不敢不看数据范围就做题了233333 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 710 using namespace std; const int dx[]={
BZOJ 1202 HNOI2005 狡猾的商人 并查集
题目大意:给定一个序列,m次给出一段区间的和,求这个序列是否合法 第一眼看还以为是差分约束- - [x,y]区间内和为z等价于sum[y]-sum[x-1]=z 用并查集来维护这个关系即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 110 using namespa