【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. 递归完之后更新根节点记录的信息

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

对于这道题，插入和查询怎么办？

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

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

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

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

阅读更多……

【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)$

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

阅读更多……

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

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

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}$的期望即可

阅读更多……

题目大意

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

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

阅读更多……

题目大意

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

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

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

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

阅读更多……

$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了，年年都这么凄惨，不过可能年纪大了，会写几道题的正解了，但是两道都写粗了，真是拉低初三大老爷们的智商了，还是该整理代码风格多对拍…

题目大意

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

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

阅读更多……

题目大意

给出一个数列$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)$最大

阅读更多……

题目大意

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

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

阅读更多……

题目大意

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

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

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

阅读更多……