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

Tabris

CSDNcodeforces套题

发布于：2017年7月14日

次浏览

[原创]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(n^2)的 显然不可取

然后考虑如何维护。

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

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

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

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

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

复杂度是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] \Big|x\in[1,n]\} 那么就是 d 的一种可能性

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

先排序

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

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

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

首先考虑这个式子

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

于是枚举d即可，考虑d<= \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\times \sqrt{max\{a[x] \Big|x\in[1,n]\} })

本页文档最后更新于：2021年5月16日

CSDN

codeforces