Lost Cows(线段树)

3:Lost Cows

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

    考虑拥有最小代号的奶牛所在的位置,可以发现其一定位于最右侧的计数器为0的位置上。然后考虑将其移出队列,位置比他大的位置的计数器都会减一,可以以此类推求出其他奶牛的代号。

    若将移出队列变成将其计数器变为$\infty$,则该题变成了支持序列的如下操作:

    • 找区间最小值所在位置
    • 区间减法
    • 单点修改

    即可用线段树来解决此问题。

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

    本程序使用带懒标记的线段树实现。详细原理请参考第一题。

  3. 程序的运行情况

    该程序提交了一次即通过

    1507796908309

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

    线段树的写法需要形成自己的风格,才能提高速度与准确性。

Code:

 

K-th Number(主席树)

2:K-th Number

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

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

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

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

  3. 程序的运行情况

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

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

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

Code:

 

A Simple Problem with Integers(线段树)

题目链接

对问题的分析设计过程

题目要求对序列进行下列操作

  • 区间加法
  • 区间求和

因此可以考虑使用两个树状数组带懒标记维护的线段树来实现

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

该程序使用了带懒标记的线段树来实现上述操作。具体来说对线段树上的每个节点新增一个属性Lazy表示该区间被同时加上Lazy。在更新时若该节点区间被更新区间覆盖则直接更新Lazy,无需继续对其子节点进行修改。查询时在访问其儿子节点的同时将其Lazy下传至儿子节点。可证明单次修改以及查询其时间复杂度均为$O(\log n)$。总时间复杂度为$O(n+q\log n)$。 详细实现过程见代码。

程序的运行情况

该程序一共提交了3次,运行情况如下图所示:

错了两次的主要原因是因为对于lazy操作有点不太熟悉。

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

线段树真的好用好写,在维护序列上强无敌。

Lazy操作需要考虑许许多多各种各样的方面需要小心一点

Code:

 

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

题目链接

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

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

其实不难打= =

Code:

 

Codeforces Round #372 +#373 部分题解

用了两场比赛上Div 1感觉自己好腊鸡的说。。。以下是这两场比赛的部分题解(不得不说有个黄学长来抱大腿还是非常爽的)

Round #372 :

Div 2 A:Crazy Computer

题意:给定N个输入和一个时间长度M,每次输入屏幕上增加一个字符,若两个输入间隔大于M则屏幕上的字符会被清空,问结束时屏幕上还有多少个字符

直接模拟没有什么好说的

代码:

 Div 2 B:Complete the Word

题意:给定一个字符串,其中某些字符未知,要求给出一个可能的字符串,使得存在一个包含26个大写字母的长度为26的连续子串

这题也是直接乱搞吧大概,我的思路就是统计每个子串中是否有重复,没有就说明合理然后随便构造一个答案就行了

代码:

Div 2 C and Div 1 A:Plus and Square Root

题意:给定一个数和两个操作,一个操作为+k,另一个操作为开根号然后k=k+1,初始时数为1,k=1,求达到k=n+1时的操作数

考虑构造一个可行方案,设执行开方操作后那个数为t,那么有$t=mk,m\in \mathbb N$(若不满足则下一次无法开方)同时考虑开方操作前有$t^2=n(k-1),n \in \mathbb N$所以令$t=k(k-1)$ 即可

代码:

Div 2 D and Div 1 B:Complete The Graph

题意:给定一张图,其中某些边的长度未知,求是否存在一种方案,使得最短路为L

先分层建图,求出经过k条未知边的最短路,然后从经过未知边数从小到大开始处理,直接构造出经过k条未知边,最短路为L的路径,可以得出,若无法构造出小于k条未知边的最短路为L的路径,那么该构造方式不会出现更短的路径。

这道题在考试时没秒出来,考完才发现写成大根堆+构图构太大MLE了囧。。。(不然说不定一场DIV 1了哼~)

代码:

Round #373 :

这一场好像数据出了好多错结果Div 1 unrated了。。。。不过还好Div 2没死然后自己就上Div 1辣(开心),黄学长也因此逃过了掉rate的命运。。。

Div 2 A:Vitya in the Countryside

题意:给定一个月亮阴晴圆缺的序列,求判断接下来月亮是变圆还是变缺

直接判断序列是上升还是下降即可,注意0和15即可

代码:

Div 2 B:Anatoly and Cockroaches

题意:给定一串珠子,有两种操作:给一个珠子涂色,交换2个珠子位置,求使这串珠子黑白相间的最小操作

分黑白黑白黑和白黑白黑白考虑咯,然后每次只判断奇位或偶位,看是不是那种颜色,如果不是再考虑要涂色还是交换(有点口胡写的代码也很挫。。。)

代码:

Div 2 C and Div 1 A Efim and Strange Grade

题意:给定一个浮点数,有n次四舍五入的机会,求获得最大的数大小

从高位到低位找到第一个大于5的数位进位即可,主要注意输出格式和进位问题就没了

代码:

Div 2 D and Div 1 B

虽然是一道错题不过解法还是挺机智的

题意:有N个复印机,每个复印机复印文件要ti秒,现在有m个任务,每个任务要求需要x个副本,求复印所需要的最小时间

先把  每个复印机投入工作的时间计算出来记为si,然后二分时间T,那么时间T内的副本数就为$\sum_{i=1}^n \lfloor \frac{T-si}{ti} \rfloor$但因为复印机数太多所以还是过不了,考虑到$1<=ti<=1000$ 那么就把复印时间相同的复印机放在一起处理

Div 2 E and Div 1 C Sasha and Array

题意:给定一个序列,支持区间加法和区间求其斐波那契数之和

线段树+矩阵乘法裸题,注意点优化就行了,例如lazy直接存斐波那契数的矩阵什么的就没问题了

代码:

 

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

首先嘛这道题目只要知道一个东西就很容易了:所有循环的最小公约数<=60,成一条链的长度最大为11,那么我们就可以用一个很裸的方法。对于在链上的数,我们修改直接暴力找出并修改。对于在环上的数,我们对每一步建立一颗线段树,那么修改就变成了交换60棵线段树的某个子树。然后我们就可以愉快的写啦~~~

在想的时候被同学坑了,他说最长的循环不超过60.。。。

在实现方面,我用一个map+树状数组维护链上的答案,然后用60棵线段树来维护这个环。懂了之后还是很好写哒~~~

Code:

 

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

居然在考场上把这道题打出来了觉得自己也是有点吊啊(虽然后面就没时间做其他题了囧而且还被卡常数了。。。)

题解自己写了一份TEX的就直接放上来吧。。。。

好啦,在谈点什么别的

什么?你在bz上TLE了?注意一下你的矩阵乘法,这个程序的大部分时间几乎都是跑矩阵乘法的,我是从900000次到600000次在到300000次最后预处理那些2的次幂才过的。把OJ卡了好久真是对不起啊QAQ

CODE:

Codeforce 水题报告(2)

又水了一发Codeforce ,这次继续发发题解顺便给自己PKUSC攒攒人品吧

CodeForces 438C:The Child and Polygon:

描述:给出一个多边形,求三角剖分的方案数(n<=200)。

首先很明显可能是区间dp,我们可以记f[i][j]为从i到j的这个多边形的三角剖分数,那么f[i][j]=f[i][k]f[j][k](i,j,k是否为1个合格的三角形)

Code:

CodeForces 438D:The Child and Sequence

描述:给一个序列,要求支持区间取模,区间求和,单点修改(n<=10^5)

考虑如何用线段树来搞这个东西,很明显对于所有区间取模操作都必须用搞到点,但是如果我们加入一个小优化(只有区间序列的最大值大于那个区间的话,才往下传递)然后我们就可以解决这个问题啦。

为啥?我们可以发现当一个数取模的时候至少变小一半,因此每个数最多取模log a[i]次,所以总的时间复杂度为$n log^2 n$

Code:

CodeForces 434D:Nanami’s Power Plant

描述:有n个节点,每个节点可以取一个xi(li<=xi<=ri)xi为整数,然后对于每个节点的权值为aix^2+bix同时需要满足某些xu-xv<=w的限制

既然是整数那么我们就可以直接用网络流啦,对每个节点的每个取值拆下,然后连边权为权值的边,然后就是最小割啦。接下来再考虑那些限制的条件,我们可以对所有相邻的东西可以直接连一个x[u]->x[v]+w,流量为inf的边,就可以限制到啦

Code:

CodeForces 543C:Remembering Strings

描述:给定一堆字符串,改变某个字符需要一定的花费,求使所有的字符串都是好记的(存在一位的字符是该位中的唯一一个)(n<=20,len<=20)

很神奇的一道题,考虑用数位dp来解决这道题。我们考虑如何使一个字符串变成好记的,很简单只要改变某一位的字符即可,或者需要把这种字符都改变的话,那么花费是sum-mx(除了花费最大的不变,其他都需要改变)然后就行啦

实现的话用了一直比较鬼畜的写法,结果意外的短,详情可以看代码

Code:

CodeForces 543D:Road Improvement

已知有一颗树,对所有点求删去某些边,使得其他点到该点至多经过一条坏边的方案数(n<=2*10^5)

很明显是树形dp,那么f[x]=pai(f[ch[x]]+1)

考虑怎么从祖先的答案算出自己的答案,很明显吧自己除去就能把祖先当自己的子树干了

除的时候不能直接用乘法逆元(f[x]可能为0 ), 需要存一个前缀和还有后缀和

Code:

CodeForces 546E:Soldier and Traveling

描述:有n个城市和m条道路,每个城市有一定的士兵,士兵可以移动到相邻的城市,求是否存在一种移动方式使得每个城市的驻兵数为某个值(n<=100,m<=200)

很明显是网络流吧,拆点然后随便搞搞即可

Code:

CodeForces 534D:Handshakes

描述:有个房子,有n个人按顺序进去,一个人进去就会跟房间中空闲的人握手,每3个人可以组队做事,给定握手数,求方案

我们从0开始,每次看+1的有没有人,没有就-3,完了

Code: