思路:考虑将字符L看作+1,R看作-1。那么四种碎片对应的值分别为:LL为+2,RR为-2,LR和RL皆为0。 那么我们可以发现,如果a,b不相等,那么答案一定是NO。因为整个字符串中L和R的数量不相等,一定不是平衡串。 如果d > 0 但 a == 0,那么答案也是NO。因为这样的话,我们的d碎片中的L会导致前缀无法满足平衡条件。 其他情况下,答案是YES。 一种构造合法序列的方式是: 先放所有类型A的碎片,再放所有类型D的碎片,再放所有类型B的碎片,最后放所有类型C的碎片。
小蓝有四种由字符 L 和 R 组成的长度均为 2 的字符串碎片:类型 A 为 LL,类型 B 为 RR,类型 C 为 LR,类型 D 为 RL。他分别拥有 a 个类型 A、b 个类型 B、c 个类型 C 和 d 个类型 D。现在他想将这些碎片按任意顺序拼接成一个长字符串。
一个字符串被称为平衡串,当且仅当:对于它的每个前缀,前缀中字符 L 的数量都不小于字符 R 的数量;并且整个字符串中字符 L 的数量与字符 R 的数量恰好相等。
请判断小蓝能否利用手头的碎片拼出一个平衡串。
数据范围:
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.