爱悠闲 > 分类 >

BZOJ 第37页

BZOJ 2314 士兵的放置(play) 树形DP
题目大意:给定一棵树,求最小支配集以及最小支配集数量 首先我们需要会求最小支配集- - 其实支配集的求法很优雅的= = 那些第一问就写了一大坨的第二问还怎么写- - 可以自己YY一下简单的支配集求法= = 实在不懂看代码吧我懒得解释了= = 然后第二问就直接把方案数顺便统计下就行了 大半夜胡乱写了发居然也过了= = #include <cstdio> #include <cstring> #inc
BZOJ 1907 树的路径覆盖 树形DP
题目大意:给定一棵树,求最小路径覆盖 数据范围1W,看到还想跑网络流来着= = 不过算了明明树形DP这么水还是不要用网络流这种大杀器为好 首先将所有的链都考虑成以链上所有点的LCA为转折点的V字形 那么点有两种:转折点和非转折点 因此我们选择两种状态进行转移:还会和父亲组成链的状态和成为转折点的状态 转移就自己YY算了 时间复杂度是线性的 #include <cstdio> #include <c
BZOJ 1644 Usaco2007 Oct Obstacle Course 障碍训练课 SPFA
题目大意:给定一个有坏点的网格图,从A点走到B点,要求拐弯最少 裸SPFA……在状态那里记录下方向就好了 水水更健康~~ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 10100 #define P(x,y) ((x)*n-n+(y)) using namespace
BZOJ 2146 Construct 计算几何
题目大意:给定曼哈顿空间下的一个多边形,求这个多边形的凸包的周长和面积 注意是曼哈顿空间 第一问直接用个最小的矩形框一下就好 第二问就要求曼哈顿空间内的凸包了 容易YY出来曼哈顿空间下的凸包一定是这种东西 我们将这个凸包分成左上 右上 左下 右下四部分 那么每部分都是一个单调增的点序列 扫一遍就行 求出凸包上的关键点之后(图中所有凸出来的点)计算下面积即可 此外应某人不想这么快看到题解的要求就让它
BZOJ 1967 Ahoi2005 CROSS 穿越磁场 FloodFill+BFS
题目大意:给定平面上的n个正方形,求某个点到另一个点至少穿过多少个边界 一开始想对于每个正方形判断一下起点和终点是否在同一侧= = 但是反例显然 考虑到n<=100,可以离散化一下,然后用Floodfill标记每块区域 然后跑最短路就行了……由于边权都是1,所以用BFS就能搞出最短路了 连边连挂了调了半宿…… #include <cstdio> #include <cstring> #includ
BZOJ 2565 最长双回文串 Hash+二分
题目大意:给定一个字符串,求一个最长的子串,该字串可以分解为两个回文子串 傻逼的我又忘了Manacher怎么写了= = 无奈Hash+二分吧 首先将字符串用分隔符倍增,然后求出以每个点为中心的最长回文半径 然后考虑两个回文串怎么合并成一个 我们发现图中以i为中心的回文串和以j为中心的回文串合并后长度恰好为(j-i)*2 能合并的前提是以两个点为中心的回文串有交点 那么对于每个j我们要求出有交点的最
BZOJ 3544 ONTAK2010 Creative Accounting 平衡树
题目大意:给定一个序列,求一个区间之和mod m的值最大 维护一个前缀和,每次利用set寻找第一个比当前值大的数,如果找不到就去找整个set中最小的数,然后将当前前缀和加入set 注意set中upper_bound的写法 upper_bound(s.begin(),s.end(),a[i])是O(n)的 s.upper_bound(a[i])才是O(logn)的 好坑。。。。。 #include
BZOJ 2306 Ctsc2011 幸福路径 倍增Floyd
题目大意:给定一张有向图,每个点有权值,蚂蚁从某个节点出发,初始体力值为1,每走一条边体力值*=p,每经过一个点会获得幸福值为点权*体力值,求最大幸福值 令f[i][j][t]为从点i走到点j花2^t步的最大幸福值 那么有f[i][j][t]=max{f[i][k][t-1]+f[k][j][t-1]*p^(2^t)} 迭代多次即可得到答案的近似值 注意蚂蚁可能卡死在某个点不动,因此初始要将邻接矩
BZOJ 3043 IncDec Sequence 差分
题目大意:给定一个序列,提供一个操作:将某个区间内所有数+1或-1 求将所有数变成一样最少多少次操作,以及最终可以有多少种数 考虑差分后的序列 每次对[l,r]进行+1/-1,相当于在差分后的数组上对l进行+1/-1,然后对r+1进行-1/+1 特殊的,如果r=n,那么就相当于对l进行了+1/-1 我们最终的目标是将差分数组变成第一个位置是最终的数字,2~n都是0 那么我们统计差分后的数组的2~n
BZOJ 2430 Poi2003 Chocolate 贪心
题目大意:给定一个巧克力,怎么切看题目吧我实在写不动了= = 首先每条线被切至少一次 在此基础上一条线每被切一次就多付出一份代价 故每个交叉点上用权值较大的线切权值较小的线比较优 说白了就是大的先切然后小的后切 贪心的证明我说不明白了大家意会吧QAQ 一天之内写了整整十道题也是够受的了QAQ #include <cstdio> #include <cstring> #include <iostre