Codeforces Round # 555 (Div3)

2019/04/28 18:29
阅读数 5

1157A. Reachable Numbers

给一个数n,每次可以给n加1,得到去除末尾0之后的数,输出总共可以到达多少个数。

按题意直接模拟(出题人说最多答案只有91个)。

https://codeforces.com/contest/1157/submission/53429096

1157B. Long Number

给一个仅含$1 \sim 9$的数字串,与映射$f(x) = a_x, (1 \leq x,a_x \leq 9)$,可以连续的对这个序列操作任意次,输出可得的最大的序列。

按题意直接模拟,只能更改变大的第一个块。

https://codeforces.com/contest/1157/submission/53429096

1157C. Increasing Subsequence

C1,C2只有构造条件不同。

给$n$个数,每次只能取头尾,构造出一个符合要求的严格递增序列,输出序列长度和每次操作是$L$(从左端取数)或是$R$(从右端取数)。

C1. easy version(没有两个相同的数)

每次选左端和右端中小的那个数必是最优的。

https://codeforces.com/contest/1157/submission/53429151

C2. hard version (可能有相同的数)

依旧每次选左端和右端中较小的,当左右相同时,之后都只能选择一个方向的数,因此选择选左端和选右端两中方案中更优的答案。

https://codeforces.com/contest/1157/submission/53429184(我写了个DFS,其实相当于没有,可以看看别人的代码)

1157D. N Problems During K Days

给一个数$n$和天数$k$,每天有一个值$a_i$且$a_i \neq 0$,要求$\sum_{i=1}^k a_i = n$。对每天的值,第一天可以是任意的,其后$a_{i-1} < a_i \leq 2a_{i-1},  (1 \leq i \leq k)$。

因为第一天可以是任意的,那么$k$天的下限值就等于$1+2+3+...+k$,如果$n$小于下限值一定不能构造,此时的上限值是$2^(k) - 1$。然后第一天的值会影响上限值和下限值,我们只要找到下限值小于$n$,上限值大于$n$的第一天的值,按题意暴力构造即可。

https://codeforces.com/contest/1157/submission/53384652

1157E. Minimum Array

给两个长度为$n$的数字序列$a$和$b$,你可以使用$b$中第$j$位与$a$中第$i$位配对,$a$中该位数字变为$a_i = (a_i + b_j) % n$,$b$中每个数字只能使用一次,输出可得的字典序最小的$a$。

我们只要对$a$中每一位都配上$b$中当前剩下数的求和取模后最小的那个数,使用multiset维护即可。

PS:set和multiset的二分查找请用stl方法 .lower_bound 和 .upper_bound,否则$O(n)$。

https://codeforces.com/contest/1157/submission/53368317

1157F. Maximum Balanced Circle

给$n$个数,用其中若干个数构成一个序列,要求相邻的数相差不超过1,其中头尾视为相邻。

对原序列排序,然后双指针找出合法的最长的部分,对这部分进行构造,唯一的难度在于找出最长的起尾。

https://codeforces.com/contest/1157/submission/53429014

1157G - Inverse of Rows and Columns

给一个$n \times m$的01矩阵,要求在行列各进行任意次操作后,得到一个非递减矩阵,这个矩阵拉平后是前一部分全0,后面全1的,输出是否可以得到这样的矩阵,行的操作序列,列的操作序列(反转用1表示,否则为0)。

(这是$O(n^2m^2)$的方法)暴力对矩阵的每一个位置枚举,这个位置之前的全为0,其他为1,检测是否可以操作得到这样的非递减矩阵。

https://codeforces.com/contest/1157/submission/53427481

(学习了$O(nm)$)的方法,更新一下。

我们想一下可以发现,如果存在答案,那么构造出的矩阵必定满足以下两种情况之一或全部:

①第一行全为0;②最后一行全为1。

所以我们只需要检查这两种情况是否有一个或全成立即可。

https://codeforces.com/contest/1157/submission/53375413

(还没有搞皮肤,先黑白过渡一下)

展开阅读全文
c++
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部