UOJ Logo zgjkt的博客

博客

各种K-D Tree

2016-05-25 13:54:15 By zgjkt

【bzoj2648】$SJY$摆棋子

题目大意

在一个很大的棋盘上,摆好了$n$个黑色棋子,现在执行$m$次操作,分为两种:

  1. 摆一个黑色棋子

  2. 摆一个白色棋子,同时输出距离这个棋子最近的一个黑色棋子与它的距离(曼哈顿距离)

值得注意的是,一个地方可以放两个棋子

数据范围

$n,m\leqslant 500000$


题解

对于这一个问题,有一个简单思路,每次新摆一个白色棋子然后枚举黑色棋子,计算曼哈顿距离

很好,但是$n$,$m$到了五十万[捂脸]

炸弹熊

这时候我们引入一个东西,叫做$K-D\ Tree$

Tree?这是二维的图哦

嗯,实际上这是引入$K-D\ Tree$,而不是别的什么玄学结构的原因之一

这个$Tree$是这样建树的:

  1. 选定一个维度

  2. 针对每个点在这个维度上的参数$a_1,a_2,a_3..a_n$,用$STL$中的$nth\_element()$排序,使得在中间值左边的值全都比它小,右边的值全都比它大,但不保证有序

  3. 把中间值取出,把这个点当成根节点

  4. 选定另一个维度,递归左边的值(左平面)作为左子树,再递归右边的值(右平面)作为右子树

  5. 递归完之后更新根节点记录的信息

当然如果只有一个维度,它的效率比别的数据结构较之一般,但是在多维度上,就显示出很强势的一面啦

坏笑熊

对于这道题,插入和查询怎么办?

插入一个新的节点,只要针对某一维度上的参数与节点作比较,然后递归到子树即可

查询就需要节点记录的信息了

例如这道题,节点记录平面上极值点的坐标参数,然后比较对于查询位置来说哪个平面上的极值点更近,就递归哪个平面(子树)

关于其他的东西,我在代码旁做了比较详细的注释,那么这道题的题解就结束了!

鼓掌熊

阅读更多……

各种分数规划

2016-04-20 14:04:31 By zgjkt

【poj2976】$Dropping\ tests$——初步接触分数规划

题目大意

给出两个有$n$个元素的序列$A,B$

分别选择$n-k$个元素,询问$\frac{\sum a_i}{\sum b_i}$的最大值

数据范围

$1\leqslant n\leqslant 1000,0\leqslant k< n$


题解——二分

入门题是一道裸题,就不会把人吓跑啦 捂脸熊

设,$x=\frac{\sum a_i}{\sum b_i}\ \rightarrow\ \sum a_i-x\times \sum b_i=0$

令,$f(x)=max(\sum a_i-x\times \sum b_i)$,可以得到$f(x)$是一个单调递减的函数

新函数是非分式的规划,有以下性质

设,原规划最优解为$x^{\prime}$

  1. $f(x)> 0\ \leftrightarrow\ x< x^{\prime}$

  2. $f(x)= 0\ \leftrightarrow\ x= x^{\prime}$

  3. $f(x)< 0\ \leftrightarrow\ x> x^{\prime}$

然后给出简略的证明 思考熊

$f(x)>0$,也就意味着存在$\sum a_i-x\times \sum b_i>0\ \rightarrow\ \frac{\sum a_i}{\sum b_i}>x$,则肯定有更优解,即$x< x^{\prime}$

另外两个,也是类似的证法,这里不详细给出

然后怎么来做这道题呢?

$f(x)$是单调递减的函数,因此可以每次二分$x$

然后处理得到$a_i-x\times b_i$,再排序得到最大的$n-k$个值,求和就是$f(x)$

最后利用性质判断,继续二分即可

阅读更多……

各种概率DP

2016-03-05 16:28:32 By zgjkt

初中课本知识已经有讲概率啦!应用在信息学里面可以这样↓

我们现在假装要从出生点出发去新日$♂$暮里,有两种方法

  1. 老司机开车带我们去,费用是一千软妹币,绝对不翻车

  2. 年轻司机开车带我们去,费用是一百软妹币,但是有$0.5$的概率会翻车被查。因此我们要回到出生点,此时只能让老司机带我们飞【捂眼

上谁的车呢?思考熊

权衡利弊之后,我们应当先上年轻司机的车试试看

此时年轻司机有$0.5$的概率成功,期望是$0.5 \times 100=50$

另外,$0.5$的概率是年轻司机被查之后我们去找老司机帮忙,期望是$0.5\times (100+1000)=550$

那么最终期望就是$550+50=600$



【bzoj4318】$OSU!$——初步接触期望$dp$

题目大意

给定一个数列$S$,长度为$n$

给出$a_i$,$S_i$有$a_i$的概率是$1$,否则是$0$

如果得分是数列$S$中所有连在一起的$1$的长度的立方和,询问得分的期望

数据范围

$n\leqslant 100000,0\leqslant a_i\leqslant 1$


题解

设转移到$S_i$时,$S_1,S_2...S_i-1$中连在一起的$1$的最长后缀长度为$x$

易证,如果$S_i=0$,则贡献为$0$,如果$S_i=1$,则贡献为$(x+1)^3-x^3=3x^2+3x+1$

只需要考虑对答案有所影响的情况

因此只要考虑,当$S_i=1$时,$x^2$和$x$的期望加起来,转移到$S_{i+1}$的期望即可

阅读更多……

【NOIP'2015'】运输计划

2016-03-02 14:08:18 By zgjkt

题目大意

给出一个$n$个节点的树,还有$m$条路径,并且保证边权$(t_i)$满足$0\leqslant t_i\leqslant 1000$

要求将任意一条边的边权变为$0$后,询问这$m$条路径上边权总和的最大值最小是多少

阅读更多……

【GDKOI'2016'】不稳定的传送门

2016-02-24 14:05:39 By zgjkt

题目大意

一共有$n$个城镇,第$i$个城镇到第$i+1$个城镇有一条收费$c_i$的单向道路

除此之外,再给出$m$个单向传送门,可以从传送门规定的起始地去往目的地,同样需要收费$w_j$

但它传送成功的概率只有$p_j$,失败会传送回起始地,并且无论成败,使用了传送门就需要花费$w_j$

现在若要从第$1$个城镇前往第$n$个城镇,询问最小期望花费

阅读更多……

【GDKOI'2016'】总结与反思

2016-02-22 14:04:44 By zgjkt

$Day1$

进考场之后领了题目,密码是“题目很简单”,然而…

做题顺序$2-1-3-4$

$T1$,因为上课的时候一直在说线段树,所以做题的时候一直套进线段树里做,发现并不会合并区间,也没有意识到换一个思路,比如拆位来做会好得多,拿走$30$分

$T2$,由于题面上有说整个都是单向往后,所以我直接就想到了$dp$来做,$dp[i]$表示从起点走到$i$点的最小期望,所以通过判断是不是通过某个传送门到的这个点来转移状态,但是可能细节写错了,一分没拿,好伤…

$T3$,一开始看到[条件式收益],就确定是最大权闭合子图。然后手画了一下,发现点上要记录两个值,伤害值和财富值。并没有意识到这就是建图的正负…反而困死在"&#%…两个值我怎么跑最小割!"的想法里。最后身手敏捷地避过了正解,暴力$10$分$get$

$T4$,不会做,暴力也不会写


$Day2$

做题顺序$2-4$

$T1$,看完题也不知道最优策略是啥,直接放弃

$T2$,看到这个数据范围就猜是不是数位$dp$啊!然后在纸上乱涂乱画写出了递推式,样例过了之后非常开心的以为今天好歹写得出一次正解,下午听讲评的时候发现正解也是数位$dp$,但是递推式和我写的相差甚远,然后知道自己写的三维可能写粗了,最后统计的时候会比标程麻烦得多,或许就是在那里写跪了,最后一分没拿

$T3$,似曾相识的题面 又是$m$算法,然而我不会做

$T4$,时间不够,草草打了个暴力,$10$分都不给我...


总结

这是初中最后一次koi了,年年都这么凄惨,不过可能年纪大了,会写几道题的正解了,但是两道都写粗了,真是拉低初三大老爷们的智商了,还是该整理代码风格多对拍…

【GDKOI'2014'】内存分配

2016-01-11 14:07:35 By zgjkt

题目大意

有$n$个程序$:p_1,p_2 \cdots p_n$,程序$p_i$已经占用了$a_i$个单位内存,还需要$b_i$个空闲内存就能结束运作,然后返还内存$a_i+b_i$

整台机子运作了$m$分钟,每分钟都有且只有一个程序改变了它的状态($a_i,b_i$),求在那一分钟至少需要多少空闲内存才能运作所有程序

阅读更多……

【GDOI'2014'】吃

2016-01-07 14:09:54 By zgjkt

题目大意

给出一个数列$A:a_1,a_2,a_3 \cdots a_n$

执行$m$次询问,每次给出区间$[l,r]$

在$[a_l,a_r]$中选一个数$x$

在$[a_1,a_{l-1}]$或者$[a_{r+1},a_n]$中选一个数$y$

求$gcd(x,y)$最大

阅读更多……

【bzoj3295】动态逆序对

2015-12-21 13:59:28 By zgjkt

题目大意

对于序列$A$,它的逆序对数定义为满足$i< j$,且$A_i> A_j$的数对$(i,j)$的个数

给$1$到$n$的一个排列,按照某种顺序依次删除$m$个元素,询问在每次删除一个元素之前统计整个序列的逆序对数

阅读更多……

【bzoj1875】HH去散步

2015-12-18 13:31:48 By zgjkt

题目大意

给定一个有$n$个点,$m$条边的无向图,每条边的长度都是$1$,没有自环,可能有重边

给定起点$A$与终点$B$,求从起点走$t$条边到达终点的边集个数

注意,每一条选取的边不能是刚刚加入边集的边

阅读更多……

共 62 篇博客