Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)做题记录


终于把这场补完了。。。最后一个题不知道为什么,我的写法貌似比别人的要慢一点。。。比赛的时候卡C卡了很久,后来旁边大爷说b数组没用只用找最小值就可以了,然后写了个mapT了。。后来发现原来是[]运算符的锅。。。E只剩十分钟的时候才会,写完交上去wa5,才发现是个重要的地方没有判断。。。实在遗憾。。。

A. Unimodal Array

三个while循环走一遍,如果最后位置不是最后就是错误的。

B. Keyboard Layouts

用map实现就好了。

C. Jury Marks

其实在之前写过了。一开始想的是n*k^2的暴力,但是其实我们可以通过枚举b序列最小值出现的位置,从而确定出起始值,然后带着算一遍check就好了,这样就是k^2的复杂度了。

D. Office Keys

题意:n个人要去一个地方p,给出每个人的坐标a[i],去这个地方需要一把钥匙,总共有k把钥匙,给出每把钥匙的坐标b[i],问n个人最后都到达了这个地方需要多少经过多少时间,每个人走一个单位距离需要一个单位时间。

可以贪心也可以dp。dp就是前i个人从前j把钥匙选择出i把的最大时间进行n^2的dp。

贪心就是发现最优的取钥匙方案一定是一段连续的区间(因为假如只有n把钥匙,一定是一一对应的是最优)。所以我们可以枚举区间起始点,然后O(n)扫一遍人序列求出时间,最后取个min就好了。

复杂度应该都是O(n^2)的。

E. Cards Sorting

题意:给出n张扑克牌,每次拿第一张牌如果他是当前序列中最小的,就把它扔掉,否则就放到最后,问最终需要操作多少次。N<=100000

用set存下来一个pair<卡牌数字,位置>,然后每次从set的第一个值确定出来当前需要选的数,但是会出现相同的数字不止一张的情况,所以我们还需要找到第一张在当前位置之后的这个数字的卡牌。然后计算的过程可以用树状数组加速。

F. Bamboo Partition

题意:给出n(n<=100)个竹子,以及一个限制长度k(k<=1e11),告诉你每个竹子nice的高度a[i]。竹子一开始的高度都是0,每天长1个高度,一个人每隔d天去check这些竹子,并且对于长度高于nice的竹子砍掉至a[i],并且这个竹子不会再生长。问最大的间隔d使得切下来的部分竹子之和不超过k。a[i]<=1e9。

一开始以为是有单调性的,但是后来发现傻逼了。

然后推式子:

随着d的增大这个函数实际上是一个分段的函数,在和式的值不变的情况下随着d增大,但当和式值变化的时候出现间断点。

那个和式根据余数之和那道题目的思想,最多有O(sqrt(a[i]))级别个。所以处理出来O(nsqrt(a[i]))个间断点,然后一个个带进去check好了。但是有个问题最后合法的一段可能只有最小值合法,最大值不合法,但最小值不一定是最大的。所以存一下和式的值,然后通过上式右边计算d就好了。

但是我写的常数好大的感觉= =

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注