Educational Codeforces Round #105 ABCDE ​Solutions

A. ABC String

Solution:

Obviously, a certain letter appears twice as often as the other two letters. But for the convenience of implementation, we only find the letter that appears the most and mark it as t.

Then, if this t itself is in the first place, then t is replaced with (; the other two letters are replaced with ).
Otherwise, the two letters are in the first place, which is (; t is ).
(Here we temporarily ignore the fact that t should be the last digit and it should be ), just pay attention to the above conclusion is correct.)

Based on the above conclusion, run a pair of brackets. Yes, if it matches, NO if it doesn’t match.

Code:

B. Berland Crossword

Solution:

There are actually only two cases that will cause NO: one is to apply $n$, and the other is to apply $n-1$. We consider the number of grids that this side is forced to paint as $require[i]$, where $i=(0,1,2,3)$ represents the four directions of URDL.

So $(i+1) mod 4$ and $(i+3) mod 4$ can represent the sides on both sides of $i$.

Sort the four edges from largest to smallest.

If he wants to paint $n$, then $require[(i+1)%4]++$ and $require[(i+3)%4]++$ (the number of grids that are forced to be painted on the left and right sides) +1).

If you want to paint $n-1$, then $require[(i+1)%4]++$ and $require[(i+3)%4]++$ execute one of them. We execute our plan on the side with the more squares to be painted.

After that, check whether the planned number of paints meets the number of forced paints.

Code:

C. 1D Sokoban

Just a classic binary search problem. On the one hand, the implementation is a little complex. On the other hand, it needs binary search twice. So still funny.

D. Dogeforces

Dynamic disjoint set is really funny. But not a complex problem.

E. A-Z Graph

This question may seem a very hard problem, but it is actually a simple one. Because the vertices can be repeated, it will quickly be equivalent to the simplest construction method.