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

这场的 D 好牛逼啊

CF1680A Minimums and Maximums

若区间 \([l_1,r_1]\) 与 \([l_2,r_2]\) 有交,那么随便选一个数,让序列里全是这个数就行了。

此时答案为 \(\max(l_1,l_2)\)。否则,答案为 \(l_1+l_2\)。AC Code

CF1680B Robots

处理出来每个 robot 最多能向左向上走多远,然后枚举最后动的是哪个 robot 就行了。AC Code

CF1680C Binary String

二分答案。设答案为 \(x\),那么可以用 2pointers 算出来每个 \(l\) 最多能取到多远的 \(r\),维护前缀和判断一下就行了。

时间复杂度 \(O(n\log n)\)。AC Code

CF1680D Dog Walking

不会,场后来补

CF1680E Moving Chips

胡了一个 dp:设 \(F(i,S)\) 为只考虑前 \(i\) 列,并且前 \(i-1\) 列都是空的,并且最后一列状态为 \(S\) 的最小操作次数。其中 \(S\in \{\varnothing,\{0\},\{1\},\{0,1\}\}\)。

然后需要一个巨大多分讨来转移,场上写完 F 没时间写了。寄

CF1680F Lenient Vertex Cover

这不是我以前 yy 过的简单图论题吗.jpg

首先如果这个图就是二分图那显然可以。否则,我们相当于要选一条边,把这条边干掉,然后使得剩下的边构成二分图。

容易发现选的这条边必须是所有奇环的交集,并且如果选他,那么他不能在一个偶环上。

随便求一个 DFS 生成树,然后对每个返祖边判断一下这条边构成了奇环还是偶环,做一个链加就行了。这个可以用树上差分维护。最后再跑一遍二分图染色就完事了。

时间复杂度 \(O(n+m)\),有点细节,wa 了两发才过。AC Code

————————

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