[NOI2017]游戏 题解
![[NOI2017]游戏 题解](https://ksmeow.moe/wp-content/uploads/2018/07/180716a.jpg "180716a")
题目地址：洛谷：【P3825】[NOI2017]游戏 – 洛谷、BZOJ：Problem 4945. — [Noi2017]游戏
题目描述
狂野飙车是小 L 最喜欢的游戏。与其他业余玩家不同的是，小 L 在玩游戏之余，还精于研究游戏的设计，因此他有着与众不同的游戏策略。
小 L 计划进行 n 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。
小 L 的赛车有三辆，分别用大写字母A、B、C表示。地图一共有四种，分别用小写字母x、a、b、c表示。其中，赛车A不适合在地图a上使用，赛车B不适合在地图b上使用，赛车C不适合在地图c上使用，而地图x则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有d张。
n 场游戏的地图可以用一个小写字母组成的字符串描述。例如：S=xaabxcbc表示小 L 计划进行 8 场游戏，其中第 1 场和第 5 场的地图类型是x，适合所有赛车，第 2 场和第 3 场的地图是a，不适合赛车A，第 4 场和第 7 场的地图是b，不适合赛车B，第 6 场和第 8 场的地图是c，不适合赛车C。
小 L 对游戏有一些特殊的要求，这些要求可以用四元组 (i,hi,j,hj) 来描述，表示若在第 i 场使用型号为 hi 的车子，则第 j 场游戏要使用型号为 hj 的车子。
你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “-1’’（不含双引号）。
题意简述
你正在玩一个赛车游戏，一共有3种车型，每一场有不适合的车型，有的比赛没有不适合的车型，这种比赛的数量$\leq 8$。有一些限制条件，表示某场比赛如果使用某种车型，那么另一场比赛必须使用另种车型。求是否存在每场比赛采用的车型的安排符合上述所有条件。
输入输出格式
输入格式：
输入第一行包含两个非负整数 n,d 。
输入第二行为一个字符串 S 。 n,d,S 的含义见题目描述，其中 S 包含 n 个字符，且其中恰好 d 个为小写字母 x 。
输入第三行为一个正整数 m ，表示有 m 条用车规则。接下来 m 行，每行包含一个四元组 i,hi,j,hj ，其中 i,j 为整数， hi,hj 为字符a、b或c，含义见题目描述。
输出格式：
输出一行。
若无解输出 “-1’’（不含双引号）。
若有解，则包含一个长度为 n 的仅包含大写字母A、B、C的字符串，表示小 L 在这 n 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。
输入输出样例
输入样例#1：
3 1 xcc 1 1 A 2 B
输出样例#1：
ABA
说明
![game noi17 - [NOI2017]游戏 题解](https://ksmeow.moe/wp-content/uploads/2018/07/game_noi17.png "[NOI2017]游戏 题解")
题解
本题可以使用2-SAT解决。
如果不存在可以使用三种的游戏，那么我们按如下方式建图。
- 如果$h_i$是$i$不能用的车型，则不作任何操作；
- 如果不满足1，且$h_j$是$j$不能用的车型，则标注$(i, h_i)$为“不可能选择”的方案，即连接它与$i$的另外一个选项；
- 如果不满足1和2，则有两种选择，即选$(i, h_i)$必须选$(j, h_j)$，选$j$的另外一个选项必须选$i$的另外一个选项，如此建边即可。
跑完2-SAT输出方案就好。对于可以使用三种车型的游戏，则枚举它不能使用某种车型，就转变为类似普通游戏的模型，枚举到一个方案判断一次即可。
代码
// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
return res * neg;
}
inline char readsingle() {
char c;
while(!isgraph(c = fgc())) {}
return c;
}
const int MAXN = 100005;
int n, m;
char s[MAXN], s1[MAXN];
struct Info {
int i, j;
char hi, hj;
} infos[MAXN];
struct Edge {
int to, nxt;
} gra[MAXN << 1], gran[MAXN << 1];
int head[MAXN], headn[MAXN], tot, totn;
inline void addedge(int u, int v) {
gra[tot] = Edge {v, head[u]}; head[u] = tot++;
}
inline void addedgen(int u, int v) {
gran[totn] = Edge {v, headn[u]}; headn[u] = totn++;
}
inline void reset() {
tot = totn = 0;
memset(head, -1, sizeof(head));
memset(headn, -1, sizeof(headn));
}
int dfn[MAXN], low[MAXN], clk, sno[MAXN], scc, op[MAXN];
std::stack<int> sta;
bool insta[MAXN];
void tarjan(int u) {
dfn[u] = low[u] = ++clk;
sta.push(u); insta[u] = true;
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(!dfn[v]) {
tarjan(v);
low[u] = std::min(low[u], low[v]);
} else if(insta[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]) {
scc++;
int p;
do {
p = sta.top(); sta.pop();
insta[p] = false;
sno[p] = scc;
} while(p != u);
}
}
int deg[MAXN];
std::queue<int> que;
int mark[MAXN];
void dfs_mark(int u) {
if(mark[u]) return;
mark[u] = -1;
for(int i = headn[u]; ~i; i = gran[i].nxt) {
int v = gran[i].to;
dfs_mark(v);
}
}
inline void toposort() {
for(int i = 1; i <= scc; i++) {
if(!deg[i]) que.push(i);
}
while(!que.empty()) {
int u = que.front(); que.pop();
if(mark[u]) continue;
mark[u] = 1;
dfs_mark(op[u]);
for(int i = headn[u]; ~i; i = gran[i].nxt) {
int v = gran[i].to;
if(!--deg[v]) que.push(v);
}
}
}
inline int id(int x, char y) {
if(s1[x] == 'a') {
if(y == 'B') return x;
else return x + n;
} else {
if(y == 'A') return x;
else return x + n;
}
}
inline char choice(int x) {
int xx = x > n ? x - n : x;
if(s1[xx] != 'a' && id(xx, 'A') == x) return 'A';
else if(s1[xx] != 'b' && id(xx, 'B') == x) return 'B';
else if(s1[xx] != 'c' && id(xx, 'C') == x) return 'C';
}
inline int oppo(int x) {
if(x > n) return x - n;
else return x + n;
}
inline bool work() {
reset();
for(int i = 1; i <= m; i++) {
Info x = infos[i];
if(s1[x.i] == tolower(x.hi)) {
continue;
} else if(s1[x.j] == tolower(x.hj)) {
addedge(id(x.i, x.hi), oppo(id(x.i, x.hi)));
} else {
addedge(id(x.i, x.hi), id(x.j, x.hj));
addedge(oppo(id(x.j, x.hj)), oppo(id(x.i, x.hi)));
}
}
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
for(int i = 1; i <= n * 2; i++) {
if(!dfn[i]) tarjan(i);
}
for(int i = 1; i <= n; i++) {
if(sno[i] == sno[i + n]) return false;
op[sno[i]] = sno[i + n];
op[sno[i + n]] = sno[i];
}
memset(deg, 0, sizeof(deg));
for(int u = 1; u <= n * 2; u++) {
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(sno[u] != sno[v]) {
addedgen(sno[v], sno[u]);
deg[sno[u]]++;
}
}
}
toposort();
for(int i = 1; i <= n; i++) {
if(mark[sno[i]] == 1) putchar(choice(i));
else putchar(choice(i + n));
}
return true;
}
bool dfs_s(int step) {
if(step > n) return work();
if(s[step] != 'x') {
s1[step] = s[step];
if(dfs_s(step + 1)) return true;
} else {
s1[step] = 'a';
if(dfs_s(step + 1)) return true;
s1[step] = 'b';
if(dfs_s(step + 1)) return true;
s1[step] = 'c';
if(dfs_s(step + 1)) return true;
}
}
int main() {
n = readint(); readint();
for(int i = 1; i <= n; i++) {
s[i] = readsingle();
}
m = readint();
for(int i = 1; i <= m; i++) {
infos[i].i = readint();
infos[i].hi = readsingle();
infos[i].j = readint();
infos[i].hj = readsingle();
}
if(!dfs_s(1)) puts("-1");
return 0;
}
