爱悠闲 > 分类 >

BZOJ 第53页

BZOJ 4026 dC Loves Number Theory 分块+十字链表/可持久化线段树
题目大意:给定一个序列,多次询问某段区间乘积的 φ 值对 1000777 的模 我竟然卡过去了233333 将序列分块,记录 fi,j 表示第 i 块左端点到第 j 个点中出现的所有质数 p 的 p−1p 之积 每次询问 [x,y] ,首先取出 [x,y] 区间内所有数的积,然后乘上 fst,y (其中 st 是 x 后面第一个块端点所在块) 现在还剩 [x,l[st]] 部分没有统计 由于 10
BZOJ 4031 HEOI2015 小Z的房间 Matrix-Tree定理
题目大意:给定一张地图,求生成树个数 Matrix-Tree定理直接上 不过模数是 109 ,不能直接求逆元 因此消元的时候辗转相除一下就好了 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 110 #define MOD 1000000000 using namespa
BZOJ 1742 Usaco2005 nov Grazing on the Run 边跑边吃草 动态规划
题目大意:给定一个数轴,初始在位置 p ,有 n 坨草( n≤3000 ),约瑟芬需要吃掉所有的草,定义一坨草的腐败值为吃掉的时间,求最小腐败值之和 容易证明任何时刻约瑟芬吃掉的草都是一个区间。(废话,难道还能路过草不吃?) 因此令 fi,j,k 表示已经吃掉了以i开头的j坨草,当前在左端点/右端点的最小腐败值之和(包括被吃掉的和未被吃掉的,当然被吃掉的腐败值就不会再涨了) DP方程自己YY吧 注
BZOJ 1600 Usaco2008 Oct 建造栅栏
题目大意:给定一个长度为 n ( n≤2500 )的木板,要求分成4部分拼成一个面积为正的四边形,求方案数 能拼成一个面积为正的四边形等价于任意一个木板的长度 <n2 切割点有3个,前两个枚举,第三个O(1)计算即可 时间复杂度 O(n2) #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> u
BZOJ 1603 Usaco2008 Oct 打谷机 DFS
题目大意:给定一棵树,每个点是一个齿轮,1号齿轮顺时针旋转,每条边有同向和反向两种连接方式,求n号齿轮的旋转方向 DFS一遍即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 1010 using namespace std; struct abcd{ int
BZOJ 4034 HAOI2015 T2 DFS序+线段树
题目大意:给定一棵树,每个点有点权,支持下列操作: 1.某个点的点权+a 2.某棵子树所有点权+a 3.查询某个点到根路径上的点权和 这个用入栈出栈序就可以了 入栈为正,出栈为负,那么一个点到根路径上的权值和就是入栈出栈序中[1,入栈位置]的和 而子树在入栈出栈序中是连续的,因此用线段树维护一下就可以了 (似乎只要无脑链剖就可以了? #include <cstdio> #include <cstr
BZOJ 4052 Cerc2013 Magical GCD
题目大意:给定一个序列,求一个连续子序列,使得序列长度* Gcd 最大 考虑以某个位置结尾的所有连续子序列,我们会发现不同的 Gcd 不会超过 log2n 个 于是暴力即可= = #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 using namespace
BZOJ 4027 HEOI2015 兔子与樱花 树形贪心
题目大意:给定一棵有根树,每个点上有一些樱花,现在要求删除一些节点,删除节点的樱花和子节点都会连到父节点上,要求每个节点的樱花数+子节点数不超过 m ,求最多删多少个节点 这数据范围也只能贪心了吧= = 令 fi 为以节点 i 为根的子树中能删除的最多节点( i 节点不删), gi 为删除最多节点的情况下 i 号节点的最小负重 那么首先对于每个节点我们对于所有的子节点为根的子树尽量删,然后考虑如何
BZOJ 4025 二分图 分治+并查集
题目大意:给定一张 n 个点的图,有 m 条边, T 个时间段,每条边只存在于 (st,ed] 这些时间段,求每个时间段内这个图是否是二分图 分治并查集大法好 定义 Solve(x,y,E) 为当前处理的区间为 [x,y] , E 为所有存在时间为 [x,y] 的子集的边的集合 那么对于 E 中的每一条边 (u,v) ,讨论: 若当前边的存在时间为 [x,y] ,则在并查集上判断是否出现奇环 如果
BZOJ 3307 雨天的尾巴 线段树
题目大意:给定一棵树,有 m 个操作,每次给一条路径上的每个点分发一个颜色为 z 的物品,所有操作结束后输出每个点上数量最多的是哪种物品 对于每个操作,我们在 x 和 y 上各打上一个插入 z 的标记,然后在 LCA(x,y) 和 Fa(LCA(x,y)) 上各打上一个删除 z 的标记 然后我们对 z 维护线段树 DFS一遍,对于每个节点进行如下操作: 1.将所有子节点的线段树合并过来 2.处理标