081017模拟

发布于 2017-10-08  14.26k 次阅读


[toggle hide="yes" title="题目" color=""][ttl2v]081017[/ttl2v][/toggle]

T1 Blue

这道题结论性非常强,考试的时候想到一种可行的贪心策略是每次选择最远的石头跳,但是没去仔细想就去搞后面了,结果最后打了个暴力查找,50分。正解可以使用多种数据结构来找下一个位置,将O(n)变成O(logn),比如用set然后每次删除,或者是二分右端点+线段树(单点修改+区间最小值查询),于是这样就可过了(虽然用set还得卡(强)卡(开)常(O)数(3))。

 

T2 Weed

其实今天写博客主要是为了这道题。考试的时候没读明白题意,一直以为是不真正修改,然后调了快一个小时暴力(中间电脑关机一次),感觉自己好蠢。。。

实际上,每个加数和删除的操作可以看作是入栈和弹栈操作,之后可以用线段树维护多个操作间的关系。线段树上维护四个信息:

s:区间内加数总和(仅考虑区间内部影响);

nd:当前区间向前删除数字的数量;

na:当前区间内“净”加的元素数。

sd:当前区间被右兄弟删除后的总和。  ※仅对左儿子维护此信息。

我们通过维护以上四个标记,就可以得到答案(root->s)。现在我们考虑如何维护。

首先,在建树或修改时,只需要将叶子节点的前三个标记维护好即可;在递归返回时,再计算最后一个。如果左儿子不够右儿子删,那么非常简单,直接利用这几个标记计算即可,l->sd=0。比较麻烦的是左儿子不被删光的情况。我们先实现一个函数cal(x),利用sd标记计算在当前区间中删去x个元素后的和。

考虑cal(x)的实现(当前节点为o):

1.若r->na>x,那么返回l->sd+r->cal(x)。

2.若r->na<x,那么右儿子不够删,返回l->cal(x-r->na+r->nd)

※这里非常重要,一定要再删掉右儿子要删的

3.若r->na==x,直接返回l->sd。

有了这个函数,我们就可以非常方便地计算左儿子的sd,维护其他标记了,不再赘述。

 

T3 Drink

算算时间复杂度,大(强)力(开)卡(O)常(3)+用char减少耗时居然卡过去了(其实本来以为过不去的),跑得比标程还快,但是正解貌似只有wq会大模拟做法,据说5k...但是出题人非常不良心,数据上的范围比标注的大很多,好像有2000。。。


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974