https://codeforces.com/contest/1837
https://codeforces.com/contest/1837/problems
利益相关:上紫祭。
真的不要以为这道题放在 F 就不敢做。
压线过题的感觉真好。
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\)。
标签:Educational,Rated,1837,contest,题解,codeforces,括号,https,com From: https://www.cnblogs.com/RB16B/p/17435599.html