526互联

Educational Codeforces Round 149 (Rated for Div. 2) 题解

发布时间 2023-05-26 19:01:10作者: SF71-H

https://codeforces.com/contest/1837

https://codeforces.com/contest/1837/problems

利益相关：上紫祭。

真的不要以为这道题放在 F 就不敢做。

压线过题的感觉真好。

image

image

image

ABC 题都过水，就不写了。

代码丢在这里：

A：https://codeforces.com/contest/1837/submission/207156920

B：https://codeforces.com/contest/1837/submission/207180946

C：https://codeforces.com/contest/1837/submission/207186832

D. Bracket Coloring

首先猜测一个结论：\(k \leq 2\)，其中 \(k\) 是答案的颜色种数。

然后可以写一个程序验证：比如说对于每一个长度为 \(10\) 的，( 数量和 ) 数量均为 \(5\)，然后枚举染色验证即可。

接下来讲如何构造方案（其实构造方案就可以证明结论）：

如果左括号数量不等于右括号数量，就直接暴毙，输出 \(-1\) 即可。

否则如果 \(s\) 本身就是 beautiful 的，\(k = 1\)。

否则 \(k = 2\)。

构造策略：

枚举每一个左括号（下标为 \(x\)），贪心找还没有染色的最右边的右括号（下标为 \(y\)），就将 \(x, y\) 都染为颜色 \(1\)。

剩下的染为颜色 \(2\)。