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题不会，大概是个组合数学。