爱悠闲 > 分类 >

BZOJ 第56页

BZOJ 3684 大朋友和多叉树 FFT+拉格朗日反演
题目大意:给定 n 和集合 S ,求满足下列要求的多叉树的个数: 1.每个非叶节点的子节点数量在集合 S 中 2.每个叶节点的权值为 1 ,每个非叶节点的权值为子节点权值之和 3.根节点的权值为 n 注意每个节点的子节点有顺序 令 fi 表示根节点权值为 i 的神犇二叉树个数, F(x) 为 fi 的生成函数, C(x) 为 S 的生成函数,那么有: F(x)=∑i∈SFi(x)+x F(x)=C
BZOJ 2021 Usaco2010 Jan Cheese Towers 动态规划
题目大意:完全背包,如果最顶端的物品重量 ≥k ,那么下面的所有物品的重量变为原来的 45 考虑一些物品装进背包,显然我要把所有重量大于 ≥k 的物品中重量最小的那个放在最顶端,才能保证总重量最小 那么我们给物品排个序,第一键值为重量是否 ≥k ( ≥k 的放在前面),第二键值为重量(从小到大) 然后依次加入背包,令 fi 表示没有重量 ≥k 的物品放在最顶端时重量为 i 的最大价值, gi 表示
BZOJ 4059 Cerc2012 Non-boring sequences 线段树+扫描线
题目大意:定义一个序列为【不无聊的】当且仅当这个序列的任意一个区间都存在一个数只出现过一次,给定一个序列,要求判断这个序列是否是【不无聊的】 定义 lasti 表示第 i 个元素上一次出现的位置(第一次出现则为 0 ), nexti 表示第 i 个元素下一次出现的位置(最后一次出现则为 n+1 ),那么这个元素能成为某个区间仅出现一次的数,当且仅当这个区间的左端点在 [lasti+1,i] 之间,
BZOJ 2525 Poi2011 Dynamite 二分答案+树形贪心
题目大意:给定一棵树,有一些点是关键点,要求选择不超过 m 个点,使得所有关键点到最近的选择的点距离最大值最小 二分答案,问题转化为: 给定一棵树,有一些点是关键点,要求选择最少的点使得每个关键点到选择的点的距离不超过 limit 然后我们贪心DFS一遍 对于以一个节点为根的子树,有三种状态: 0.这棵子树中存在一个选择的点,这个选择的点的贡献还能继续向上传递 1.这棵子树中存在一个未被覆盖的关键
BZOJ 2792 Poi2012 Well 二分答案
题目大意:给定一个非负整数序列 A ,每次操作可以选择一个数然后减掉1,要求进行不超过 m 次操作使得存在一个 Ak=0 且 max{Ai−Ai+1} 最小,输出这个最小值以及此时最小的 k 二分答案,然后验证的时候首先让相邻的都不超过 x ,然后枚举哪个点应该改成 0 如果某个点需要改成 0 ,那么需要进行操作的位置是一段区间,左右端点都单调,扫两遍就行了 #include <cstdio> i
BZOJ 1122 POI2008 账本BBB 单调队列
题目大意:给定一个由 +1 和 −1 构成的长度为 n 的序列,提供两种操作: 1.将某一位取反,花销为 x 2.将最后一位移动到前一位,花销为 y 要求最终 p+sumn=q ,且 p+sumi≥0(1≤i≤n) ,求最小花销 枚举最终的序列以哪个点开始,那么从这个点往后的最小前缀和可以用单调队列预处理出来 然后贪心地把左边的 −1 改成 +1 ,右边的 +1 改成 −1 直到满足要求即可 #i
BZOJ 3233 Ahoi2013 找硬币 动态规划
题目大意:给定 n 个数,求一种混合进制使得每个数各个位之和之和最小 令 fi 表示表示最大硬币面值为 i 时零头部分(即 ak mod i 部分)的最小硬币数 那么有转移方程: fj=min{fi+∑nk=1⌊ak mod ji⌋}(i|j) 然后 ans=min{fi+∑nk=1⌊aki⌋} 时间复杂度 O(nmlogm) ,光荣TLE 优化: ji 一定是质数,否则我可以多添加一种硬币而不伤
BZOJ 4094 Usaco2013 Dec Optimal Milking 线段树
题目大意:给定n个点排成一排,每个点有一个点权,多次改变某个点的点权并将最大点独立集计入答案,输出最终的答案 开一个线段树,每个点记录四个信息: 区间左端点不选,右端点也不选的最大值 区间左端点选择,右端点不选的最大值 区间左端点不选,右端点选择的最大值 区间左端点选择,右端点也选择的最大值 然后合并时讨论一下就行了 #include <cstdio> #include <cstring> #in
BZOJ 3203 Sdoi2013 保护出题人 凸包+三分
题目大意:太长自己看 令 sumi 表示第 i 个僵尸以及之前的僵尸的体力总和, disi 表示第 i 个僵尸与房屋的初始距离 我们发现我们能消灭一个僵尸当且仅当 y>=sumidisi 那么我们要求的显然就是 max{sumidisi} 我们将一个僵尸抽象成一个点 sumidisi ,那么我们发现每个回合僵尸之间的相对位置是不变的 因此我们可以维护一个凸包,三分即可 #include <cstd
BZOJ 2069 POI2004 ZAW 堆优化Dijkstra
题目大意:给定一张无向图,每条边从两个方向走各有一个权值,求从点1往出走至少一步之后回到点1且不经过一条边多次的最短路 显然我们需要从点1出发走到某个和点1相邻的点上,然后沿最短路走到另一个和点1相邻的点上,然后回到点1 那么我们将与点1相邻的点都设为关键点,然后将点1从图中删除,题目转化成了给定图上的一些关键点求最近点对 枚举每个点显然会T 考虑每次将关键点划分为两个集合 A,B ,然后将 A