CF Round #555 (Div.3)

博客目录

2019-04-29 15:26 CST

2019-09-30 13:46 CST

太菜了连Div.3都不会做……

A - Reachable Numbers

问对一个初始值不断做先+1后移去后缀0的操作,最多可以遍历多少个数。

大暴力,终止条件是$n < 10$。

B - Long Number

问把一个数的每一位按某个函数映射,能够得到的最大的数是多少。

贪心。

C - Increasing Subsequence

问一个序列每次可以从最左端或者最右端取数,能够得到的最长的上升子序列是什么。

一开始觉得是递归、DP卡了好久后来发现这题还是超级大暴力。每次从左边或者右边拿小的那个数,如果两边一样大那么接下来只能一直从某一边拿,$O(2n)$判断一下就结束了。

D - N Problems During K Days

求一个长度为$k$的数列,满足初始值为1,$ai < a{i+1} \leqslant 2a_i$,且总和为$n$。

构造一个$1, 2, \dots, k$的等差序列,然后判断$n - \dfrac{k(k+1)}{2}$的值。如果小于零不存在这样的序列,否则倒叙遍历整个数列,每次更新$\Delta = \min(2ai - a{i+1}, ni)$,即尽可能的增大$a{i+1}$,并更新剩余的$n$值。遍历后如果$n_0 > 0$,说明不存在这样的序列,否则肯定有$n_0 = 0$。

E - Minimum Array

给两个序列$A$和$B$,通过改变$B$的顺序使得$A + B$(模运算)的结果字典序最小。

大暴力(然而被hack掉TLE了)。用STL库的multiset就可以轻松暴力找到最小的元素而且不用怕超时了。

F - Maximum Balanced Circle

给定$n$个数,求一个最长序列$ai$,满足$\vert a{i{j}} - a{i_{j + 1}} \vert \leqslant 1$,即相邻两个元素之差不超过1(包括头尾之差)。

首先找出$n$个数中的所有的值(unique(a.begin(), a.end()))和所有值出现的次数;然后用双指针$l, r$来判断最长可行的取值区间。

$l$不动且$r$指针向后移动的条件是:

  • $a[i+1] = a[i] + 1$
  • $cnt[i] \geqslant 2$

否则把$r$赋值给$l$,继续向后寻找。

G - Inverse Rows and Columns

给一个$n \times m$的0-1矩阵,问是否存在某种操作,仅将某些行、列取反,使得$a{11} a{12} \dots a{1m} a{21} \dots a{2m} \dots \dots a{n1} a{n2} \dots a{nm}$为递增序列。

如果$n=1$,一定存在;否则如果存在这样的操作,只可能有两种结果:

  • 第一行全为0,或者
  • 最后一行全为1

两个分别$O(nm)$暴力判断是否可行即可。