# Codeforces Educational Round 128 (ABC+EF)(Codeforces Educational Round 128 (ABC+EF))-其他

## Codeforces Educational Round 128 (ABC+EF)(Codeforces Educational Round 128 (ABC+EF))

### CF1680F Lenient Vertex Cover

————————

This D is so awesome

### CF1680A Minimums and Maximums

If the interval \ ([l_1, r_1] \) intersects with \ ([l_2, r_2] \), just choose any number and let it be all in the sequence.

The answer is \ (\ max (l_1, l_2) \). Otherwise, the answer is \ (l_1 + l_2 \). AC Code

### CF1680B Robots

Process how far each robot can go to the left and up at most, and then enumerate which robot moves last. AC Code

### CF1680C Binary String

Two point answer. If the answer is \ (x \), you can use 2pointers to calculate how far \ (R \) each \ (L \) can get at most. Just maintain the prefix and judge.

Time complexity \ (O (n \ log n) \). AC Code

### CF1680D Dog Walking

No, I’ll make it up later

### CF1680E Moving Chips

Hu made a DP: set \ (f (I, s) \) as the minimum number of operations that only consider the first \ (I \) column, and the first \ (i-1 \) column is empty, and the state of the last column is \ (s \). Where \ (s \ in \ {\ varnothing, \ {0 \}, \ {1 \}, \ {0,1 \} \} \).

Then it needs a huge multi-point discussion to transfer. After writing f on the field, there is no time to write. send

### CF1680F Lenient Vertex Cover

Isn’t this the simple graph topic I’ve YY talked about before jpg

First of all, if this graph is a bipartite graph, it is obviously OK. Otherwise, we are equivalent to selecting an edge, eliminating this edge, and then making the remaining edges form a bipartite graph.

It is easy to find that the selected edge must be the intersection of all odd rings, and if it is selected, it cannot be on an even ring.

Find any DFS spanning tree, and then judge whether this edge constitutes an odd ring or an even ring for each atavistic edge. Just make a chain addition. This can be maintained by differential maintenance on the tree. Finally, run the bipartite graph coloring again and you’re done.

Time complexity \ (O (n + m) \), a little detail, WA took two rounds. AC Code