• Lost Cows(线段树)

    Lost Cows(线段树)

    3:LostCows对问题的分析设计过程考虑拥有最小代号的奶牛所在的位置,可以发现其一定位于最右侧的计数器为0的位置上。然后考虑将其移出队列,位置比他大的位置的计数器都会减一,可以以此类推求出其他奶牛的代号。若将移出队列变成将其计数器变为$\infty$,则该题变成了支持序列的如下操作:找区间最小值所在位置区间减法单点修改即可用线段树来解决此问题。程序中用到的数据机构和算法本程序使用带懒标记的线段树实现。详细原理请...

    02017年10月15日48线段树
  • K-th Number(主席树)

    K-th Number(主席树)

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

  • A Simple Problem with Integers(线段树)

    A Simple Problem with Integers(线段树)

    题目链接对问题的分析设计过程题目要求对序列进行下列操作区间加法区间求和因此可以考虑使用两个树状数组或带懒标记维护的线段树来实现程序中用到的数据机构和算法该程序使用了带懒标记的线段树来实现上述操作。具体来说对线段树上的每个节点新增一个属性Lazy表示该区间被同时加上Lazy。在更新时若该节点区间被更新区间覆盖则直接更新Lazy,无需继续对其子节点进行修改。查询时在访问其儿子节点的同时将其Lazy下传至儿子节点。...

    02017年10月12日56线段树
  • BZOJ 3653: 谈笑风生(DFS序+可持久化线段树)

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

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

  • Codeforces Round #372 +#373 部分题解

    Codeforces Round #372 +#373 部分题解

    用了两场比赛上Div1感觉自己好腊鸡的说。。。以下是这两场比赛的部分题解(不得不说有个黄学长来抱大腿还是非常爽的)Round#372:Div2A:CrazyComputer题意:给定N个输入和一个时间长度M,每次输入屏幕上增加一个字符,若两个输入间隔大于M则屏幕上的字符会被清空,问结束时屏幕上还有多少个字符直接模拟没有什么好说的代码:[crayon-5a301c1670be5265746538/] Div2B:CompletetheWord题意:给定一个字符串,其中某些字...

  • 4105: [Thu Summer Camp 2015]平方运算

    4105: [Thu Summer Camp 2015]平方运算

    首先嘛这道题目只要知道一个东西就很容易了:所有循环的最小公约数<=60,成一条链的长度最大为11,那么我们就可以用一个很裸的方法。对于在链上的数,我们修改直接暴力找出并修改。对于在环上的数,我们对每一步建立一颗线段树,那么修改就变成了交换60棵线段树的某个子树。然后我们就可以愉快的写啦~~~在想的时候被同学坑了,他说最长的循环不超过60.。。。在实现方面,我用一个map+树状数组维护链上的答案,然后用60棵线段树来...

    02015年6月18日175树状数组,线段树,老的存档
  • BZOJ 4085:[Sdoi2015]quality(round 2 音质检测)(数据结构)

    BZOJ 4085:[Sdoi2015]quality(round 2 音质检测)(数据结构)

    居然在考场上把这道题打出来了觉得自己也是有点吊啊(虽然后面就没时间做其他题了囧而且还被卡常数了。。。)题解自己写了一份TEX的就直接放上来吧。。。。好啦,在谈点什么别的什么?你在bz上TLE了?注意一下你的矩阵乘法,这个程序的大部分时间几乎都是跑矩阵乘法的,我是从900000次到600000次在到300000次最后预处理那些2的次幂才过的。把OJ卡了好久真是对不起啊QAQCODE:[crayon-5a301c167116c037319998/]...

    02015年6月10日216矩阵乘法,线段树,老的存档
  • Codeforce 水题报告(2)

    Codeforce 水题报告(2)

    又水了一发Codeforce,这次继续发发题解顺便给自己PKUSC攒攒人品吧CodeForces438C:TheChildandPolygon:描述:给出一个多边形,求三角剖分的方案数(n<=200)。首先很明显可能是区间dp,我们可以记f[i][j]为从i到j的这个多边形的三角剖分数,那么f[i][j]=f[i][k]f[j][k](i,j,k是否为1个合格的三角形)Code:[crayon-5a301c16713d3553395949/]CodeForces438D:TheChildandSequence描述:给一个序列,要求支持区...

  • CQOI2015 解题报告

    CQOI2015 解题报告

    CQOI2015终于全做完了~~~,讲一下题吧首先这套题比起其他省选还是比较水的,就是5道题比较蛋疼T1:[CQOI2015]选数这道题还是比较神的。首先给个比较神的题解:popoqqq大神的blog这个莫比乌斯反演真的不会我们记f[i]为gcd=ik时的个数,可以得到若数都不相等的话,i一定小于1e5(辗转相减法可得),那么当数都不相等时,答案显然为(r/(ki)-l/(ki)+1)^n-(r/(ki)-l/(ki)+1)-sigma(f[ij])然后就能愉快的推出来啦,还有就是当l=...

  • SDOI Day2

    SDOI Day2

    今天做了SDOI Day2觉得自己萌萌哒==题目真的有点水,一点编程复杂度都没有T1:星际战争描述:http://www.lydsy.com/JudgeOnline/problem.php?id=3993这道题是这两天最容易的题了吧。。可以发现这是一个二分图,考虑二分答案,那么人们在这段时间的输出伤害就能够确定了,用最大流判断是否所有的机器人护甲值都为0,即可。数据较良心跑得飞快Code:[crayon-5a301c1671ad0887587191/]ViewCode T2:约数个数和描...

1 / 2 1 2 下一页 »