• K-th Number(主席树)

    K-th Number(主席树)

    2:K-thNumber对问题的分析设计过程题目要求找区间第k大,是一道典型的可持久化权值线段树的例题。程序中用到的数据机构和算法本程序使用可持久化权值线段树实现,在权值的离散化上直接使用动态申请权值线段树节点来解决该问题。可持久化权值线段树(又称主席树)的详细实现方法可自行百度或参考代码。程序的运行情况该程序提交了一次即通过。在实习过程中得到的经验和体会可持久化权值线段树在维护某些区间信息上有很大的作用,是...

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

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

    题目链接首先嘛,还是太弱了,想了好久QAQ然后,这道题么,明显就是求sigma(size[x])(x是y的儿子且层树小于k)然后就可以发现:把前n个节点按深度建可持久化线段树,就能用前缀和维护了其实不难打==Code:[crayon-5a301c220667a907208877/] ...

  • HNOI2015 Day 2题解

    HNOI2015 Day 2题解

    昨天做了HNOIday2,感觉好像还是可做的,想当年什么splay还是高级算法,现在点剖什么就老考了简直丧病,虽然第二题还没写那就先当下嘴巴选手吧==T1:[HNOI2015]落忆枫音描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4011这道题还是挺神奇的,首先如果是个DAG的话我们可以把所有点的入度相乘就得到答案。那么现在加上了一条边x->y,也就是说答案=原来的答案+用上这条边的答案,我们可以发现,如果我们把...

  • HNOI2015 Day 1

    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])^jf[i+1][j-1]+=f[i][j]*(1-(1-p[i])^j)就可以完美解决这个问题了这道题的重点是...