Educational Codeforces Round 116 (Rated for Div. 2)

本文主要是介绍Educational Codeforces Round 116 (Rated for Div. 2)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Educational Codeforces Round 116 (Rated for Div. 2)

A. AB Balance

易得至多改一个位置。

然后枚举改哪个位置，特判不改。

对于一个字符串，每次扫一遍就可以算出ab和ba的个数。

B. Update Files

每一轮最大的增量会是这样变化的：1 2 4 8 ... k k k ...

前面倍增的轮数不会太多，直接模拟。

到达k后就可以直接算剩余轮数。

C. Banknotes

肯定是尽量用面额较小的，这样组出来的才会小。

假设\(c * a_i = a_{i+1}\)，则\(a_i\)至多用\(c - 1\)次。因为\(a_i\)用了\(c\)次得到的答案，肯定可以用1个\(a_j\)替换\(c\)个\(a_i\)，然后再凑到。

当剩余次数\(k >= c\)时，就使用\(c - 1\)张\(a_i\)。

否则，再使用\(k + 1\)张\(a_i\)就是凑不到的数。

D. Red-Blue Matrix

假设将行重新排列，红色的更靠上方。结合题目，就是将原矩阵划分成4个部分，且左上大于左下，右下大于右上。

这里，\(A\)大于\(B\)相当于\(\min(A) > \max(B)\)。根据这一点，我们可以只关注最大最小值，所以可以将每行的前缀最大最小值和后缀最大最小值求出来。分别记为\(prefixMin，prefixMax\)和\(suffixMin,suffixMax\)。

不妨先将矩阵划分为左和右两部分。枚举划分的列数，即枚举前\(i\)行为左侧。由于只关注最大最小值，左侧的行可以用行的前缀最大和最小值代替，右侧类似。之后只需要关心行的划分。

对于左侧的红色行而言，其中的最小值越大越好。不妨对于左侧，将行按最小值降序排序。

现在再去枚举划分的行数，即枚举前\(i\)行为红色。

由于只关注最大最小值，对于左侧，红色的行可以用前缀最小值代替，蓝色可以用后缀最大值代替。右侧类似。分别记为\(LeftUpMin, LeftDownMax, RightUpMax, RightDownMin\)。

如果满足\(leftUpMin > leftDownMax \and rightUpMax < rightDOwnMin\)，就是可行的方案。

E. Arena

TBA。

吐槽

疏于训练，代码能力直线下滑。

C想了半天，D一下就想到正解但是代码绕半天写不出来。

E题不会，大概是个组合数学。

这篇关于Educational Codeforces Round 116 (Rated for Div. 2)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！