[原创]Codeforces Round #424 Div. 2 【ABCDEF】[补完]

2017-07-14 23:27:34 Tabris_ 阅读数:296


博客爬取于2020-06-14 22:39:41
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/75138225


好吧 、我也只能做个嘴炮选手了,,,

A Unimodal Array

——————————————————————————————————————
日常傻逼题,注意明确题意在写、

B Keyboard Layouts

——————————————————————————————————————
有一个加密方式,把26字母分别映射成一个字母,然后给你密文,让你输出原文


映射一下就好了。注意1~0和大写的情况。、

C Jury Marks

——————————————————————————————————————
给你n个评委打分的情况,和其中k次分数,问你初始分数的可能数


首先处理出打分的前缀和,能知道到第i个人评分后距离初试分数的差值
然后排序。从小到小枚举 不同的差值。

然后从小到大枚举可能分数,做一个类似双指针的东西 ,找分数相匹配的个数 比n大 则有一个初始分数的可能性

D Office Keys

——————————————————————————————————————
有n个人,m个keys,目的地p,
每个人要拿一个keys到达p,
没走1m花费1个单位时间,
问所有人到达p的最小时间


首先考虑这是在直线上,从最左边的人开始枚举,那么为了方便其他人,他所拿的keys一定是尽可能靠左的

所以二分答案 check就行了

E Cards Sorting

——————————————————————————————————————
有n张卡片,成一个队列,每次操作如果队头是队列中最小的就拿出去,否则放到队尾。
问等队列为空 操作了多少次


其实就是个模拟。

但是直接模拟复杂度是O(n2)O(n^2)的 显然不可取

然后考虑如何维护。

首先由于有删除点,首先想到SPLAY维护,将该删除的删除,或者放到意义上的最后。
每次找当前意义上对头后面的最近的最小值

复杂度大概是O(nlognlogn)O(n\log n\log n) 而且实现起来有一定难度,

然后想每一次删除相当于存在,或者不存在, 想到用BIT维护 即可求意义上的两次删点的操作次数。

找最小值,看到1e6的范围想到桶排,然后同样大小的 要记录位置,所以开vector数组即可

维护一个意义上队头,然后二分找那个位置最近。不断维护即可

复杂度是O(nlogn)O(n\log n)

F Bamboo Partition

——————————————————————————————————————
有n个植物,最开始均为0米。每天长1米。可以认为修剪,且修建后植物不生长,。
每隔d天需要人去修剪照看。
问你在剪下去的长度和小于k的情况下 d最大为多少


最先有$ \dfrac{k+\displaystyle\sum_{i=1}^{0}a_i}{n}$ 如果大于max{a[x]x[1,n]}max\{a[x] \Big|x\in[1,n]\} 那么就是d的一种可能性

其实就是求[i=1n{d×aidai}<=k]\Big[\displaystyle \sum_{i=1}^{n} \{d\times \lceil \frac{a_i}{d} \rceil- {a_i} \} <=k \Big]其中d的最大值

先排序

考虑暴力的情况,枚举答案是1~a[n] ,然后判定,

然后想二分,但是发现 不满足单调性,所以不行。

考虑如何优化这个枚举过程。

首先考虑这个式子

i=1n{d×aidai}<=ki=1nd×aidi=1nai<=kd×i=1naid<=k+i=1naid<=k+i=10aii=1naid\displaystyle \sum_{i=1}^{n} \{d\times \lceil \frac{a_i}{d} \rceil- {a_i} \} <=k \\ \displaystyle \sum_{i=1}^{n} d\times \lceil \frac{a_i}{d} \rceil-\displaystyle \sum_{i=1}^{n} {a_i} <=k \\ \displaystyle d\times \sum_{i=1}^{n} \lceil \frac{a_i}{d} \rceil<=k+\displaystyle \sum_{i=1}^{n} {a_i} \\ d<= \dfrac{k+\displaystyle\sum_{i=1}^{0}a_i}{\displaystyle \sum_{i=1}^{n} \lceil \frac{a_i}{d} \rceil} \\

然后考虑分段枚举d的时候对于aid\frac{a_i}{d}只有sqrtsqrt{}种情况, 不知道的话 可以先做做这道题<–戳这里

于是枚举dd即可,考虑d<=k+i=10aii=1naidd<= \dfrac{k+\displaystyle\sum_{i=1}^{0}a_i}{\displaystyle \sum_{i=1}^{n} \lceil \frac{a_i}{d} \rceil} \\这个限制的同时不断维护最大值

注意d对每个a[i] 分段枚举的时候要满足所有的a[i] ,所以要取最小的.

复杂度O(n×max{a[x]x[1,n]})O(n\times \sqrt{max\{a[x] \Big|x\in[1,n]\} })