爱悠闲 > 分类 >

BZOJ 第28页

BZOJ 1930 Shoi2003 pacman 吃豆豆 费用流
题目大意:给定一个平面上的一些点,吃豆先生从原点出发,只能向右或向上走,求两个吃豆先生最多吃到多少豆 每个点拆成两个,之间连一条流量为1,费用为1的边; 如果从一个点出发可以到达另一个点,就将前一个点的出点连向后一个点的入点 跑费用流。但是这样显然是会TLE的 如果i能到j,j能到k,那么显然无需连i->k这条边 这是一个剪枝 加了这个剪枝之后可能会WA 因此还要考虑一个点经过多次的情况 即每个点
BZOJ 2877 NOI2012 魔幻棋盘 二维线段树
题目大意:给定一个矩阵,支持两种操作: 1.将某个子矩阵中的每个值增加一个数 2.询问某个子矩阵中的所有数的GCD 已知所有询问恒过定点(x,y) 算了BZOJ没有原题我还是把原题发上来吧- - 《论代码长度与注释长度以及题目简单程度的比例失调关系以及日本饮用水资源的解决方案》 《10K+代码是怎样炼成的》 《GCD与修改标记的正确用法》 《出题人我*你吗系列》 《懒惰即美德》 咳咳。 首先我们可
BZOJ 2286 SDOI2011 消耗战 倍增LCA+单调栈
题目大意:给定一棵树,边上有边权,m次询问,每次选定一些关键点,求将1号节点与所有关键点都切断所需的最小花销 关键点的总数<=50W 首先我们考虑暴力想法 令f[x]表示切断以x为根的子树中所有关键点的最小花销 g[x]表示x是不是关键点 那么对于x的每个子节点y有f[x]=Σmin(g[y]?INF:f[y],Distance(x,y) ) 这样每次暴力做一遍树形DP,时间复杂度是O(n*m)的
BZOJ 3611 HEOI2014 大工程 倍增LCA+单调栈+树形DP
题目大意:给定一棵树,m次询问,每次给出k个关键点,询问这k个点之间的两两距离和、最小距离和最大距离 n<=100W,m<=50000,Σk<=2*n 处理方法同2286 消耗战 地址见 http://blog.csdn.net/popoqqq/article/details/42493725 这个题的DP有些麻烦 因此我把要处理的节点单独拎出来做的DP 具体状态和转移见代码 #include <
BZOJ 2595 Wc2008 游览计划 斯坦纳树
题目大意:给定一个矩阵,有一些关键点,每个格子有权值,选择一些格子使所有关键点连通,求最小权值和 传说中的斯坦纳树- - 感觉不是很难理解的样子 枚举连通的状态,对于每个状态先对每个位置枚举子集进行合并,然后对这个状态的分层图进行SPFA 看了几分代码还是ZKY写的比较简洁- - 此外就是终于能通过操作符重载访问结构体里的三维数组了- - 我真是太丧病了233 #include <cstdio>
BZOJ 3205 Apio2013 机器人 斯坦纳树
题目大意:给定一张地图,一些地方有障碍物,有k<=9个机器人,可以一推到底,遇到转向器会转向,两个编号相邻的机器人可以合并,求最少推多少次可以全部合并 令f[l][r][i][j]表示在点(i,j)将编号在[l,r]区间内的机器人全部合并的最小推动次数 则有动规方程组: f[l][r][i][j]=min{f[l][r][_i][_j]+1} ( (_i,_j)->(i,j) ) f[l][r][
BZOJ 3858 Number Transformation 数论
题目大意:给定n,k,i从1到k循环一遍,每次将n更新成i的倍数中第一个大于等于n的 求最终的n 逗比题。。。 我们会发现当i>=sqrt(n)时,ceil(n/i)每次都是一样的- - ↑不能理解这句话的注意n是变化的 于是当i>=sqrt(n)时只需要输出ceil(n/i)*k即可 别的做法基本都卡了- - #include <cstdio> #include <cstring> #inclu
BZOJ 1197 HNOI2006 花仙子的魔法 递推
题目大意:求n维空间下的m个球最多可以将空间分为多少个区域 VFK的题解: http://vfleaking.blog.163.com/blog/static/174807634201321193348312/ 自己看吧。。。。 我还在纠结零维空间内放入一个零维的球之后空间到底会被分成几份。。。。。 #include <cstdio> #include <cstring> #include <io
BZOJ 3612 HEOI2014 平衡 递推
题目大意:给定一个杠杆,一共2n+1个位置,每个上面有一个质点,求拿走k个质点后使杠杆仍然保持平衡的方案数 mod p的值 n<=1W k<=10 令f[n][m]表示n个数划分为m个互不相同的数且最大不超过k的数的方案数 如果最小的数是1 等价于将最下方一排砍掉的方案数 即f[n-m][m-1] 如果最小的数不是1 等价于将最下方一排砍掉的方案数 即f[n-m][m] 但是这样求出的是最大不超过
BZOJ 3288 Mato矩阵 线性筛
题目大意:给定一个n阶行列式,第i行第j列为GCD(i,j),求这个行列式的值 高斯消元之后发现对角线上的东西是phi 于是线性筛出所有的欧拉函数即可 /* #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 110 using namesp