K-th Number(主席树)

2:K-th Number

  1. 对问题的分析设计过程

    题目要求找区间第k大,是一道典型的可持久化权值线段树的例题。

  2. 程序中用到的数据机构和算法

    本程序使用可持久化权值线段树实现,在权值的离散化上直接使用动态申请权值线段树节点来解决该问题。可持久化权值线段树(又称主席树)的详细实现方法可自行百度或参考代码。

  3. 程序的运行情况

    该程序提交了一次即通过。0E0D469A-5839-4D00-A632-9AB4B92CAD25

  4. 在实习过程中得到的经验和体会

    可持久化权值线段树在维护某些区间信息上有很大的作用,是一种非常好的思路。

Code:

 

BZOJ 3653: 谈笑风生(DFS序+可持久化线段树)

题目链接

首先嘛,还是太弱了,想了好久QAQ

然后,这道题么,明显就是求sigma(size[x]) (x是y的儿子且层树小于k) 然后就可以发现:把前n个节点按深度建可持久化线段树,就能用前缀和维护了

其实不难打= =

Code:

 

HNOI2015 Day 2题解

昨天做了HNOI day 2,感觉好像还是可做的,想当年什么splay还是高级算法,现在点剖什么就老考了简直丧病,虽然第二题还没写那就先当下嘴巴选手吧= =

T1:[HNOI2015]落忆枫音

描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4011

这道题还是挺神奇的,首先如果是个DAG的话我们可以把所有点的入度相乘就得到答案。

那么现在加上了一条边x->y,也就是说答案=原来的答案+用上这条边的答案,

我们可以发现,如果我们把x到根的链拿出来,其他点其实和DAG图上一样也可以入度直接相乘而得到答案,也就是S/prod(in[x])x为链上的点,可以发现如果记f[x]为所以到x的链上的1/prod(in[x])(也就是逆元啦)之和,我们可以用拓扑序来进行dp维护,就可以解决本题啦

我打的有点复杂,我是先把整个图的入度相乘然后再删去不合法的情况,也就是找y->x的链上的1/prod(in[x])之和,比较难打,但是总体思想差不多也就这样啦。

CODE:

View Code

 

T2:[HNOI2015]开店

描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4012

又是CLJ的神题,数据结构一般都是被很多数据结构大神用各种方法秒,吾等蒟蒻只能被秒了= =

解法一:

首先有一种比较高端的做法,就是用线段树那样维护虚树,每个节点维护l~r的虚树(一共log n层每次直接nlogn暴力重构一共O(n log^2 n)),那么求答案可以在每棵虚数中单独求解。

接下来我们考虑如何求答案。对虚树上的节点分别记录子树中点的距离和down,子树外点的距离和up,以及子树中的节点数size。对于每一个查询,我们先找到在dfs序中比他前的点以及比他后的点,选择lca深度较大的点进行转移(因为这样才不会影响答案)。记从点x转移到点y,那么答案为down+up+(dist[y]-dist[x])size-(dist[y]-dist[x])(tot-size)(dist为该点的深度,tot为总节点树)

解法二:

我们可以先点剖一下然后考虑用可持久化线段树维护,对于每个点他至多被log n个重心覆盖,我们分别对每个重心ai进行查询,要求路径x,y必须穿过重心ai,记i的子树中l~r的节点数为count[i],dist[u]为u到重心的距离,sum[i]表示i子树中l~r的节点的dist之和,那么该子树ai的答案为count[ai]dist[u]+sum[x]-count[y]dis[u]-sum[y], 其中y为包含u的x的儿子节点,那么我们只需对重心已经他们的儿子节点维护一个线段树即可。

但是这样会爆空间,注意到每个点的儿子最多只有3个,那么我们可以直接维护他的儿子节点,不用维护其儿子节点即可

UPD:其实不用线段树的= =,开个vector记录子树节点然后排下序用前缀和,然后每次二分查询就行,感觉特别STL,初始化部分之间可以照搬CLJ ZJOI2015幻想乡战略游戏,几乎一模一样,写完不用3kb= =

两种做法时间均为O(N log^2 N)

CODE:

View Code

 

T3:[HNOI2015]实验比较

描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4013

首先对于这道题,我们可以发现如果u=v,那么我们可以将其两个点缩为同一个点,若u<v,那么我们可以连一条u向v的边,可以证明最后的图上每个联通块一定是一个环或者树。

如果是一个环的话答案显然为零。如果是一棵树的话,我们考虑使用树形dp,如果我们已知所有子树的答案,如何更新这棵树。

观察一个序列,我们可以发现该序列总是被若干个<分割成若干块,那么我们可以记f[i][j]为以i 为根节点的子树序列中有j个块的方案数一共有多少种,可得对两个不相干的树x,y结合的话,记答案为g[k],可得f[x][i],f[y][j]对g[k]的贡献为C(k,i)C(i,i+j-k)f[x][i]*f[y][j](可以这样认为,i个人先占据i个方格,那么剩下k-i个方格必须由j个人去占领,所以最后i+j-k个人就必须与之前的i个人一起了)

每次更新的时间复杂度为O(n^3),总的时间复杂度为O(n^4),可以通过这道题

CODE:

View Code

 

HNOI2015 Day 1

HNOI2015的题还是非常漂亮的,几道题都有很大的借鉴意义,都有很强的思考性

T1亚瑟王(概率论)

描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4008

我们可以发现这个模型可以转化成有r个机会给n个人,每个人对每个机会都有一定的概率拿,求收益的期望

那么记f[i][j]为第i个人有j个机会的概率,那么可以得出

f[i+1][j]+=f[i][j]*(1-p[i])^j

f[i+1][j-1]+=f[i][j]*(1-(1-p[i])^j)

就可以完美解决这个问题了

这道题的重点是把这个模型进行转化(可以直观了理解吧n和r对换过来),否则按 f[i][j]为第i轮到第j个的概率的话搞到死都做不出(我就是这样QAQ),在做概率题的时候模型转换是第一步也是最重要的一步

Code:

View Code

T2:接水果(数据结构)

描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4009

ORZ clj出的神题

由于省特派员送温暖,各种写法都水过了QAQ

连暴力在八中都能过这是什么回事QAQ

先讲下水法把= =

解法一:(暴力)

直接读入每个盘子后排下序,用lca判断覆盖就离线tarjan搞,复杂度O(n^2),水过了!!!

解法二:(树链剖分+主席树+可持久化treap)

先把那棵树树链剖分掉,然后考虑在没有主席树的远古时代人们用的方法——平衡树,那么我们对每一个树节点建立一棵主席树,每个主席树树节点维护一个可持久化Treap,存起点在该点在该树节点的重链上,终点在主席树的该区间中所有盘子的w值,那么我们每次就可以二分答案,把log n棵主席树,每棵主席树中的log n个区间中小于该答案的盘子数算出来= =总的时间复杂度O(n log^4 n)~~~

解法三:(点剖+树链剖分+主席树套权值线段树)

由于某同学的口胡,我至今仍搞不清为何要先点剖= =,大致思想跟解法二差不多,但是就吧treap换成权值线段树,总时间复杂度貌似为(O(n log^3 n)(某同学说的))

解法四:(树上莫队+平衡树)

既然题目允许离线那就考虑用树上莫队解决,对当前的两个询问点u,v维护他们的相对差(也就是u到根的信息-v到根的信息),lca上的信息需要特判一下,如果我的盘子的起点和终点都在我的相对差中就加入平衡树,然后在log n查询即可,分块上每根号n个一块即可通过本题,总的时间复杂度O(nsqrt(n)log n)

解法五:(正解,扫描线+树状数组套权值线段树)

还是离线,把每个点重标号为其dfs序,每个询问抽象成二维平面坐标中的点(u,v)。可发现每个盘子所控制的坐标为若干个矩形区域。

具体来说,如果两个盘子的坐标与其lca不同,那么就是起点与终点在u,v的子树中是符合要求的

否则,就是一个在子树中,另一个不在lca的那个子树中

那么问题就变成了一个经典问题:询问在某点上的矩形的第k大

扫描线+树状数组套权值线段树秒过

时间复杂度O(n log^2 n)

Code:

View Code

T3:菜肴制作(拓扑序,贪心,构造)

描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4010

首先判环这个就不用说了吧

然后我们必须优先让最小的尽量前,那么我们就必须且只能把最小的点反向边所能遍历到的点删掉

考虑删最小的点的前一个点,一定是去掉最小点反向边入度为0的最大点删去

可以继续贪心构造

那么我们每次就反向遍历求出联通块再做次拓扑序即可

优先队列 O(n log n)解决

Code: