爱悠闲 > 分类 >

BZOJ 第1页

BZOJ 3626 LCA 树链剖分
题目大意: 给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。 设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。 有q次询问,每次询问给出l r z,求sigma_{l<=i<=r}dep[LCA(i,z)]。 (即,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和) 这题看见了直接卡壳。。。然后看了题解才搞懂要
BZOJ 1501 NOI2005 智慧珠游戏 Dancing-Links(DLX)
题目大意:给定一个10*10的三角形棋盘和12种零件,每种零件只能放一次,可以旋转和翻转,一些零件已经放在了上面,求一种方案,使12个零件无重叠地放在棋盘上 首先这题目一看就是DLX 但是建图真心恶心 需要枚举每一个零件的最多八个朝向的所有位置 我一开始想要全部代码处理 但是后来发现真做不了 于是我选择了打表录入12个零件的所有60种朝向,选择第一排最左面的点作为基点,依次得出每个点关于基点的相对
BZOJ 2875 NOI2012 随机数生成器 矩阵乘法
题目大意:令Xi+1=(a*Xi+c)%m,求Xn%g 水题。。。我们令x矩阵为 a 0 c 1 自乘n次,然后计算(aX0+c)%m%g即可 此题要写快速乘 不然会挂 我这个沙茶居然把矩阵开成了int 早知道多磕点脑残片了 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespa
BZOJ 3680 吊打XXX 模拟退火
首先这题应该改名叫吊打出题人 题目大意:给定n个质点,求重心 这n个质点的重心满足Σ(重心到点i的距离)*g[i]最小 模拟退火的裸题 尼玛交了两篇 死活过不去 各种改参数 最后发现是我的INF不够大 尼玛! 这题INF开0x3f妥妥过不去。。。起码要max_of _long_long附近才可以 最后写了10188MS,BZOJ倒数第一……这也是种艺术啊0.0 #include<cmath> #i
BZOJ 1038 ZJOI2008 瞭望塔 模拟退火+二分答案
题目大意:给定一条折线,要求选择一个点建立高度为h的瞭望塔,要求瞭望塔塔顶可以看到折线上的每一个点,求h的最小值 正解:半平面交 不会! 于是我们选择模拟退火来寻找瞭望塔的横坐标 确定瞭望塔的高度的时候我们选择二分处理 对于二分的每一个值 我们把折线上的端点从左到右枚举 瞭望塔的塔尖到每个端点的连线必须从左到右逆时针顺序 否则就会被遮挡 如图,塔尖到点2的连线在到点1的连线的顺时针方向,故点1被遮
BZOJ 1565 NOI2009 植物大战僵尸 最大权闭合图+拓扑排序
题目大意:给定一个m*n的草坪,每块草坪上的植物有两个属性: 1.啃掉这个植物,获得收益x(可正可负) 2.保护(r,c)点的植物不被啃掉 任何一个点的植物存活时,它左侧的所有植物都无法被攻击 求最大收益 首先这个保护和被保护的关系就是最大权闭合图的连边关系 然后直接跑就行 然后我们就会发现没过样例0.0 原因当图出现环时,根据题意,环上的所有点都不能取(想象一个无冷却的食人花前面放一个坚果) 所
BZOJ 1564 NOI2009 二叉查找树 动态规划
题目大意:给定一棵完全性质的treap,定义代价为每个点的访问频率*深度之和 我们可以花K的代价改变一些点的权值 求最小总代价 改变后的权值不能相同 但是由于可以改成任意实数 而且代价与更改的大小无关 所以其实相同与否无所谓了 首先键值是不能更改的 而一棵平衡树的中序遍历保证键值递增 故中序遍历一定 我们先按照键值排序得到中序遍历 w很大 但是保证不重复 所以我们将w离散化 然后就是DP的问题了。
BZOJ 1858 SCOI2010 序列操作 线段树
题目大意:给定一个01序列,提供三种操作: 0:把一段区间的所有元素都变成0 1:把一段区间的所有元素都变成1 2:把一段区间内的所有元素全都取反 3:查询一段区间内1的个数 4:查询一段区间内最长的一段连续的1 首先如果没有操作4这就是bitset的水题。。。多了这个,我们考虑线段树 线段树的每一个节点存修改标记和翻转标记,以及该区间的信息 虽然查询的信息都是1 但是我们要连0一起保存 因为翻转
BZOJ 1500 NOI2005 维修数列 Splay
我尽力了。。。从之前的递归版Splay变成非递归,然后各种删除冗余的操作,除了蛋疼的读入优化基本已经精简到底了,连传参都省了-0- 刚交上去是10956MS,差4MS就是BZOJ倒数第一,改完了是9244MS,快了一秒。。。单点测还是死活过不去,等加上读入优化再说吧 题目大意:维护一个序列,支持六种操作: 1.在某个数后面插入一些数字 2.删除从某个数开始的一些数字 3.把从某个数开始的一些数字都
BZOJ 2329 HNOI2011 括号修复 Splay
ああああああああああああああ——散弾铳とテレキャスター 言叶の整列、アンハッピー  単身、都会の町并み 撃ち込んだ音、嫌いですか?  题目大意:给定一个括号序列,提供四种操作: 1.将一段区间内的所有括号的变成'('或者')' 2.将一段区间反转 3.将一段区间内的所有括号翻转,即'('变成‘)',')'变成'(' 4.查询一段区间内要将至少多少个括号翻转才能变成一个合法的括号序列 5.没有5了我