【bzoj1877】晨跑

题目大意

给出有$n$个点$m$条边的带权图

要求找到最多的(起点到终点)路径数且使总费用尽量少

路径与路径之间不能相交

建图

每个点只能经过一次

拆点，容量为$1$，费用为$0$

每条边有边权，且使得边权和最小

容量为$+∞$,费用为边权

源点和汇点

点$1$和点$n$可以经过多次，因此不用开超级源和超级汇，直接取点$1$和点$n$分别作为源点和汇点

阅读更多……

[bzoj2648]小$Z$的袜子——普通莫队

题目大意

给出一个有$n$个数的数列$A:a_1,a_2,a_3\dots a_n$，询问$m$次

每次询问给出一个区间$[l,r]$，询问区间$[l,r]$内抽到一对数值相等的数的概率大小

数据范围

$n,m\leqslant 50000$，$1\leqslant l< r\leqslant n$，$a_i\leqslant n$

题解

不妨设区间$[l,r]$里元素个数为$len$，显然，抽一对数的情况总数为$C_{len}^2$

同时区间里只有$k$种数值，每种数值对应的元素有$s_1,s_2\dots s_k$个，抽一对数值相等的数的情况总数为$C_{s_1}^2+C_{s_2}^2+\dots C_{s_k}^2$

则答案为$$\frac{C_{s_1}^2+C_{s_2}^2+\dots C_{s_k}^2}{C_{len}^2}=\frac{s_1(s_1-1)+s_2(s_2-1)+\dots s_k(s_k-1)}{len(len-1)}=\frac{s_1^2+s_2^2+\dots s_k^2-len}{len(len-1)}$$

那么现在问题简化为，如何即时地统计所有的$s_1,s_2\dots s_k$

这个时候引入一个东西，莫队算法，是莫涛前几年提出的算法，适用于解决离线区间查询问题

Question Ⅰ：这个算法怎么用啊？

假设已经得到了区间$[l,r]$需要统计的信息，可以在常数级别的时间内转移到区间$[l-1,r]$、区间$[l+1,r]$、区间$[l,r-1]$、区间$[l,r+1]$

那么可以在$O(n\sqrt n)$的时间复杂度求得所有答案

Question Ⅱ：这个时间复杂度？

我们可以调整一下处理每个查询的顺序，保证最优的顺序之下转移区间

将$n$个数分成$\sqrt n$块

按区间排序，以左端点所在块内为第一关键字，右端点为第二关键字，进行排序

然后按这个排序直接暴力，复杂度分析是这样的：

1. $i$与$i+1$在同一块内，$r$单调递增，所以$r$是$O(n)$的，由于有$\sqrt n$块，所以这一部分时间复杂度是$n\sqrt n$

2. $i$与$i+1$跨越一块，$r$最多变化$n$，由于有$\sqrt n$块，所以这一部分时间复杂度是$n\sqrt n$

3. $i$与$i+1$在同一块内，$l$变化不超过$\sqrt n$，跨越一块也不会超过$\sqrt n \times 2$

由于有$m$次询问（和$n$同级），所以时间复杂度是$n\sqrt n$

阅读更多……

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

阅读更多……

【poj2104】$K-th\ Number$——无修改区间第K小问题

题目大意

给出一个有$n$个数的数列，执行$m$次询问

每次询问在区间$[l,r]$中第$k$小的数

数据范围

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 5000$

题解

由于操作只有询问，不执行修改，那么可以直接套用可持久化线段树即可

Question Ⅰ：可持久化线段树是啥？

可持久化线段树也叫主席树，它的特点就是能够充分利用历史信息

对于这道题，具体做法就是，建$n$棵权值线段树，第$i$棵树记录在数列区间$[1,i]$中权值出现的个数

然后由于这$n$棵权值线段树的结构都是相似的，所以询问区间$[l,r]$时，可以用第$r$棵权值线段树对应减去第$l-1$棵权值线段树，得到$[l,r]$区间权值的信息，最后沿着新树直接向下查找得到第$k$小的数

Question Ⅱ：建n棵权值线段树，不会空间溢出吗？

直接大力造$n$棵权值线段树肯定会空间溢出啦，但可持久化线段树利用历史信息可以节省大量空间

具体来说，第$i$棵权值线段树和第$i-1$棵权值线段树相比，只是多更新了一个权值

那么这个权值在权值线段树中只是影响了单条路径而已，因此可以在第$i$棵线段树中把不影响的子节点直接指向第$i-1$棵线段树的对应节点，就可以节省好多好多空间啦！

Question Ⅲ：建立权值线段树，那么边界范围不会过大导致自取灭亡吗？

离散化大法好！

阅读更多……