爱悠闲 > 分类 >

BZOJ 第35页

BZOJ 1443 JSOI2009 游戏Game 二分图博弈
题目大意:给定一个矩阵,一些位置有障碍,先手放置在某个位置,后手移动,先手再移动,一个格子只能经过一次,问是否先手必胜 二分图博弈= = 将矩阵建成二分图,考虑二分图博弈的模型: 给定一个二分图,每个点只能走一次,先手选定位置后手走,问是否先手必胜 那么对于任意一个点,如果存在一个最大匹配中这个点没有被匹配,那么先手从这个点开始存在必胜策略 先手放置后,后手无论走到哪个点,先手一定能沿着匹配边走回
BZOJ 3585 mex 莫队算法+分块
题目大意:给定一个长度为n的数组,m次询问某个区间内的mex值 怒写莫队233 将权值分成√n块,记录每个权值的出现次数以及每块内有多少权值出现过 修改O(1)即可完成 查询时首先扫一遍找到第一个块内有没有覆盖的点的块 然后在块内暴力查找 时间复杂度O(√n) 套个莫队 总时间复杂度O(m√n) #include <cmath> #include <cstdio> #include <cstrin
BZOJ 1419 Red is good 期望DP
题目大意:有R张红牌和B张黑牌打乱扣在桌子上,一张一张翻,可以随时停止翻牌,翻到红牌收益+1,翻到黑牌收益-1,求最优策略下的最大期望收益 OTZ wfycyx= =  http://wyfcyx.is-programmer.com/posts/74629.html #include <cstdio> #include <cstring> #include <iostream> #include
BZOJ 3566 SHOI2014 概率充电器 树形期望DP
题目大意:给定一棵树,每个点初始有一个概率为1,为1的节点会沿着边以边权上的概率向四周扩散,求最终期望有多少个点是1 OTZ 不想写题解了贴个代码吧= = 如果有不明白做法的直接问我就好了= = #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 500500 #define
BZOJ 1406 AHOI2007 密码箱 数论
题目大意:给定n,求[1,n)内所有满足x^2≡1(mod n)的x x^2=kn+1 x^2-1=kn (x+1)(x-1)=kn 令x+1=k1n1,x-1=k2n2,其中k1k2=k,n1n2=n 因此我们可以枚举n的约数中所有大于等于√n的,分别作为n1和n2代入验证 最后排序去重输出即可(我偷懒用了map #include <set> #include <cstdio> #include
BZOJ 3011 Usaco2012 Dec Running Away From the Barn 可并堆
题目大意:给定一棵有根树,求以每个点为根的子树中有多少点到它的距离不超过l 第一眼是可并堆- - 于是怒写- - 管它正解是啥- - 从下到上维护可并大根堆 键值是该点到当前根节点的距离 一旦堆顶剪枝大于l就弹顶 时间复杂度O(nlogn) 什么?你说将整个堆都加上一个值? 打标记不就好了- - 毫无疑问可并堆是可以打标记的- - 此外我的随机堆写if(flag^=1)就T写if(rand()&1
BZOJ 2079 Poi2010 Guilds 并查集
题目大意:给定一个无向图,要求将一些点红黑染色,使每个点及其相连的点中至少有一个黑色的点和一个红色的点 逗比题ぽい~ 对于任意一个大小>=2的连通图,我们只需要搞出这个图的任意一棵生成树,将这棵生成树撸成二分图再染色就一定能满足要求的ぽい~ 因此无法满足要求当且仅当存在一个大小为1的联通块ぽい~ 并查集即可ぽい~ #include <cstdio> #include <cstring> #incl
BZOJ 3450 Tyvj1952 Easy 期望DP
题目大意:给定一个OX序列,一些点未确定,连续len长度的O会得到len^2的收益,求期望收益值 令f[i]为第i个点的期望收益值,l[i]为第i个点的期望长度 如果一个点是'O' 那么l[i]=l[i-1]+1 f[i]=f[i-1]+(l[i]*2-1) 如果一个点是'X' 那么l[i]=0 f[i]=f[i-1] 如果一个点是'?' 那么l[i]=(l[i-1]+1)/2 f[i]=f[i-
BZOJ 3165 Heoi2013 Segment 线段树
题目大意:给定一个平面,多次插入一条线段,以及询问某个x值能截到的最大纵坐标 OTZ 一份详细的网址:http://hi.baidu.com/wyl8899/item/2deafd3a376ef2d46d15e998 注意细节 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <al
BZOJ 1076 SCOI2008 奖励关 期望状压DP
题目大意:给定k次弹出宝物的机会,每次随机弹出n种宝物的机会,如果吃过这种宝物的所有前提宝物就可以吃这种宝物,求最优策略的期望得分 看到数据范围果断状压DP- - 不看数据范围害死人- - 至于吃还是不吃 这是个问题 对于这种最优策略的期望DP 我们一般都是从后往前推 枚举每次出现宝物 枚举此时的状态 枚举宝物是哪种 如果当前的宝物可以吃 就在吃与不吃的后继状态中选择最大值加到当前状态上 如果当前