YZOJ P3195 [NOI2017]游戏

时间限制：1000MS      内存限制：524288KB

难度： \(6.4\)

• 题目描述

小 L 计划进行 \(n\) 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 \(A\)、\(B\)、\(C\) 表示。地图一共有四种，分别用小写字母 \(x\)、\(a\)、\(b\)、\(c\) 表示。其中，赛车 \(A\) 不适合在地图 \(a\) 上使用，赛车 \(B\) 不适合在地图 \(b\) 上使用，赛车 \(C\) 不适合在地图 \(c\) 上使用，而地图 \(x\) 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 \(d\) 张。

\(n\) 场游戏的地图可以用一个小写字母组成的字符串描述。例如：\(S=\underline{\mathrm{xaabxcbc}}\) 表示小 L 计划进行 \(8\) 场游戏，其中第 \(1\) 场和第 \(5\) 场的地图类型是 \(x\)，适合所有赛车，第 \(2\) 场和第 \(3\) 场的地图是 \(a\)，不适合赛车 \(A\)，第 \(4\) 场和第 \(7\) 场的地图是 \(b\)，不适合赛车 \(B\)，第 \(6\) 场和第 \(8\) 场的地图是 \(c\)，不适合赛车 \(C\) 。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 \((i,h_i,j,h_j)\) 来描述，表示若在第 \(i\) 场使用型号为 \(h_i\) 的车子，则第 \(j\) 场游戏要使用型号为 \(h_j\) 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “\(-1\)”（不含双引号）。

• 输入格式

输入第一行包含两个非负整数 \(n,d\) 。

输入第二行为一个字符串 \(S\) 。

\(n,d,S\) 的含义见题目描述，其中 \(S\) 包含 \(n\) 个字符，且其中恰好 \(d\) 个为小写字母 \(x\) 。

输入第三行为一个正整数 \(m\)，表示有 \(m\) 条用车规则。接下来 \(m\) 行，每行包含一个四元组 \(i,h_i,j,h_j\) ，其中 \(i,j\) 为整数，\(h_i,h_j\) 为字符 \(A\) 、\(B\) 或 \(C\)，含义见题目描述。

• 输出格式

输出一行。

若无解，输出 “\(-1\)”（不含双引号）。

若有解，则包含一个长度为 \(n\) 的仅包含大写字母 \(A\)、\(B\)、\(C\) 的字符串，表示小 L 在这 \(n\) 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。

• 样例输入

• 样例输出

• 样例解释

小 L 计划进行 \(3\) 场游戏，其中第 \(1\) 场的地图类型是 \(x\)，适合所有赛车，第 \(2\) 场和第 \(3\) 场的地图是 \(c\)，不适合赛车 \(C\) 。

小 L 希望：若第 \(1\) 场游戏使用赛车 \(A\)，则第 \(2\) 场游戏使用赛车 \(B\) 。

那么为这 \(3\) 场游戏分别安排赛车 \(A\)、\(B\)、\(A\) 可以满足所有条件。

若依次为 \(3\) 场游戏安排赛车为 \(BBB\) 或 \(BAA\) 时，也可以满足所有条件，也被视为正确答案。但依次安排赛车为 \(AAB\) 或 \(ABC\) 时，因为不能满足所有条件，所以不被视为正确答案。

• 数据规模与约定

\(n \leq 50000, m \leq 100000, d \leq 8\)

 

 

 

---

 

 

 

注意到 \(d \leq 8\)，所以可以 \(O(2^d)\)（去掉重复状态）枚举其字符，然后就是一个裸的 2-SAT 。

每场游戏两个点表示第一个/第二个可以取的字符，然后按照套路连边。

输出方案数的时候可以直接按照找出强连通块的编号大小判断取不取，因为 Tarjan 缩出来的连通块编号就是按照拓扑逆序的。