Codeforces Round #702 Div3题解

虽然我的确是很不想刷Div3的水题,但是我发现其实搜Div3题解的人数似乎高于Div2和Div1。想了想,Div3也还是可以做一做的……

对于Div3搜索量似乎比Div2和Div1高这一点可以试着做一波用户画像。首先做Div3的我估计大概有如下特征:1. 是这方面没有什么基础的同学;2. 可能还没有意识到看题解的危害;3. 显然人数上比Div2和Div1多很多;4. Div3题多。而反观Div1的用户:1. 不就是Div1 E题吗,大不了多想一会儿;2. 得卡成什么样子,才会连官方题解都不够?3. 人少;4. 我能搞定的题数少。

而我,毕竟也不是随时能掏出一段状态不错的连续时间来刷Div1。而且,毕竟久了没刷,确实比之前都还要更弱一些了。偶尔刷刷Div3,找找感觉,防止老年痴呆也是不错的。

最后,如果你是WA了之后想着看题解,快回头是岸,自己好好想想,到底为啥出问题了。这样才有提高,也才能获得做题的快乐。


A. Dense Array

题意

给一个长度为n的数组a。如果对于任意的i,都有$\frac{\max({a_i}, {a_{i+1}})}{\min({a_i}, {a_{i+1}})}\leq2$那么这个数组就是美的。

现在你可以往a里面随便差入数字。问你最少插几个,才能让这个数组变成美的。

题解

发现>2直接倍增往里面插就完事了。

代码

Submission #111639857 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Balanced Remainders

题意

给你一个长度为n的数组a。其中n保证能被3整除。现在定义数组c,c[x]表示a里面被3除余x的个数。如果c里面的每个数都相等,则这个串a就是美的。

现在你每一步可以把a里面某个数+1。问你最少走几步,才能让这个数组变美。

题解

直接找一个$c_i>\frac{n}{3}$的i。然后开始往(i+1)%3挪多余的部分,然后i++考虑他挪了之后的那个是不是超了。

唯一一个小陷阱。这个操作要做2轮,因为最开始选的i可能不够i+1吃饱。(啥时候开始Div3 B题都要给挖坑了?)

代码

Submission #111642201 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. Sum of Cubes

题意

给你一个x,问你x能不能是2个整数a,b的立方和。

题解

暴力+二分。暴力在1-10000之间枚举a。然后把$x-a^3$剩下的拿来给b二分。

不过有另外个思路我没试。还是枚举a,但是把剩下的直接开立方得到一个不准确的double,然后枚举这个double附近$\pm5$的整数。

代码

Submission #111643445 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Permutation Transformation

题意

给你一个长度为n的序列a。a里面的数字是1-n,且不重复。现在用这个序列构建一个树。规则如下:

  1. 将当前序列/子序列中最大的值作为当前的树/子树的根。
  2. 在原序列中,在这个根左边的子序列,放左子树继续按此规则构建。右边的放右子树按此规则继续构建。

然后让你打印每个节点的深度。

题解

对a按值的大小排序,依次遍历。每次遍历到一个a[i]时,这个a[i]一定是当前树的新叶子节点。完了之后再按下标排序回来就是。

代码

Submission #111644826 - Codeforces
Codeforces. Programming competitions and contests, programming community

E. Accidental Victory

题意

有n个人参加比赛。每个人手上的筹码是a[i]。比赛过程中,筹码多更多的人获胜,如果筹码数目一样,就随机一个人获胜。获胜者会赢得失败者的全部筹码。比赛顺序完全随机。问哪些人有可能获胜?

题解

我弱,我WA了一发。

很显然,排序之后从小的往上看就好了。只要吃掉比自己小的的所有筹码之后,不比我上一个人小就可以了。然后注意,中途如果某一个人吃完了下面之后还是上不去,那原来他下面的人都没机会了。

代码

Submission #111646868 - Codeforces
Codeforces. Programming competitions and contests, programming community

F. Equalize the Array

题意

给你一个长度为n的数组a。如果这个a里面存在这样的C,使得a里面的数字要么出现C次,要么就出现0次,则称这个数组是美的。

现在你能删除从a里面删除一些值。问你最少删多少个可以使a变美。

题解

直接统计每个数字出现的次数排序,然后遍历一次。当遍历到第i个数字的时候,i前面的(出现次数都比i多)都删到和i一样的出现频率。i后面的全删。

代码

Submission #111648672 - Codeforces
Codeforces. Programming competitions and contests, programming community

G. Old Floppy Drive

题意

给你一个长度为n的数组a。有m个查询,每次查询输入一个x。

具体查询是这样的:当指针指向第i个数的时候,首先把当前指向的数累加到sum中,如果$sum\geq{x}$的话就结束。否则花费1的时间把指针右移1位,如果i=n,则重新回到第1个。每次查询问的时候指针最初都是指向第1个。

问每次查询需要的时间是多少,如果永远达不到x,输出-1。

题解

二分+模拟。脑子不清醒又WA了一发。

首先考虑不用走满一整圈的情况,此时我们维护前缀最大值,直接二分,找到第一个大于等于x的地方就好。

如果我们发现一圈以内无法解决,那么再看一圈下来的总体和sum。如果$sum\leq{0}$,那没治,直接-1。

最后走能有解,但需要多圈的。一开始我是想着直接除以sum,然后剩下的按第一种情况考虑。结果就挂了。因为其实是应该走到第一次剩下max[n]以内的值就不再需要走一整圈了。

代码

Submission #111652034 - Codeforces
Codeforces. Programming competitions and contests, programming community

唉。越来越弱,居然WA两发了。

展示评论