← 返回题目列表

Codeforces · 1344/F

F. 皮特的调色板

中文机器翻译题面 查看原题

皮特·蒙德里安 (Piet Mondrian) 是一位以其极简主义作品而闻名的艺术家,其作品仅由红、黄、蓝、白四种颜色组成。大多数人将此归因于他的风格,但事实是他的颜料表现得非常奇怪,混合两种原色只会产生另一种原色!

一个鲜为人知的作品,题为“自命不凡的矩形”

原色序列(红、黄、蓝)混合如下。虽然至少有两种颜色,但看看前两种。如果它们不同,请用缺少的颜色替换它们。如果它们相同,则将它们从序列中删除。最后,如果有一种颜色,那就是最终的颜色。否则,如果序列为空,我们称结果颜色为白色。以下是两个混合示例:

Piet 有一个调色板,单元格编号从 $$$1$$$ 到 $$$n$$$。每个单元格包含一种原色或为空。 Piet 非常神秘,不会与您分享他的调色板,因此您不知道每个单元格属于什么颜色。

然而,他确实执行了 $$$k$$$ 操作。有四种操作:

1. 在混合操作中,Piet 选择细胞子集并按某种顺序将它们的颜色混合在一起。该顺序不一定是通过增加索引来实现的。他记录了最终的颜色。空单元格会被跳过,对混合过程没有影响。混合不会改变存储在单元格中的颜色值。
2. 在 RY 操作中,Piet 选择单元格子集。该子集中的任何红细胞都会变成黄色,而该子集中的任何黄色细胞都会变成红色。蓝色和空单元格保持不变。
3. 在 RB 操作中,Piet 选择单元的子集。该子集中的任何红色细胞都会变成蓝色,该子集中的任何蓝色细胞都会变成红色。黄色和空单元格保持不变。
4. 在 YB 操作中,Piet 选择细胞子集。该子集中的任何黄色细胞都会变成蓝色,该子集中的任何蓝色细胞都会变成黄色。红色和空单元格保持不变。

Piet 仅告诉您他按时间顺序执行的操作列表、涉及的索引以及每个混合操作的结果颜色。对于每个混合操作,您还知道单元格混合的顺序。根据此信息,确定初始调色板中每个单元格的颜色。也就是说,您应该找到调色板的一种可能状态(在执行任何操作之前),或者说所描述的情况是不可能的。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le n,k\le 1000$$$) - 分别是调色板中的单元格数量和操作数量。

接下来的 $$$k$$$ 行描述了操作。第 $$$i$$$ 行以第 $$$i$$$ 操作的名称和一个整数 $$$m$$$ ($$$1\le m\le n$$$) — 涉及的索引数量开始。然后跟随 $$$m$$$ 整数 $$$j_1,\ldots,j_m$$$ ($$$1\le j_i\le n$$$) — 操作的索引。保证所有 $$$j_i$$$ 在操作中都是不同的。如果是混合操作,则索引按颜色混合的顺序列出,并且该行还以代表结果颜色的字符结尾:“R”表示红色,“Y”表示黄色,“B”表示蓝色,“W”表示白色。

输出

如果解存在则输出“YES”,否则输出“NO”。您可以以任何大小写(大写或小写)打印每个字符。

如果答案为“YES”,则在下一行输出一个长度为 $$$n$$$ 的字符串,由字符“R”、“Y”、“B”和“.”组成,代表初始调色板的 $$$n$$$ 单元格中的绘画颜色(分别为红色、黄色、蓝色和空)。如果有多个解决方案,请打印其中一个。您可以以任何大小写(大写或小写)打印每个字符。

示例

输入 #1

3 2
mix 2 2 1 R
mix 2 1 3 Y

输出 #1

YES
YB.

输入 #2

2 3
mix 1 2 Y
RB 1 2
mix 1 2 W

输出 #2

NO

输入 #3

1 3
RY 1 1
YB 1 1
mix 1 1 B

输出 #3

YES
R

输入#4

3 8
mix 2 1 2 R
mix 2 1 3 Y
RY 2 2 3
RB 3 1 2 3
YB 3 1 2 3
mix 1 1 W
mix 1 2 B
mix 1 3 Y

输出#4

YES
.RY

注意

对于第一个测试用例,答案为“YB”。与两种混合一致。第一次混合“BY”产生红色,而第二次混合“Y”产生黄色(空单元格被忽略)。其他有效的解决方案包括“BYR”和“.RY”。

对于第二个测试用例,我们可以证明不存在解决方案。

对于第三个测试用例,答案“R”与所有操作一致。在前两个操作中,它更改为“Y”,然后更改为“B”。在最终操作中,混合“B”产生蓝色。

对于第四个测试用例,答案“.RY”与所有操作一致。前两个混合是“R”和“Y”,分别产生红色和黄色。在接下来的三个操作中,调色板依次更改为“.YR”、“.YB”、“.BY”。最后的三种混合与这个调色板一致。