代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
//#define int long long
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
typedef long long ll;

int n, d, m;
struct qwq {
	int a, c;
	char b, d;
} q[N], q2[N];
int idx, x[N];
string s, s2;
vector<int> g[N];
void add(int a, int b) { g[a].push_back(b);
// cout << "link: "<< a << ' ' << b << '\n';
 } 

int get(char o, char t) {
	if(o == t) return -1;
	if(o == 'a') return t == 'C';
	if(o == 'b') return t == 'C';
	if(o == 'c') return t == 'B';
}
char back(char o, int t) {
	if(o == 'a') return (t ? 'C' : 'B');
	if(o == 'b') return (t ? 'C' : 'A');
	if(o == 'c') return (t ? 'B' : 'A');
}
#define rev(x) (x > n ? x - n : x + n)
void link(int i) {
	int x = get(s[q[i].a], q[i].b), y = get(s[q[i].c], q[i].d);
	int a = (x ? q[i].a + 1 + n : q[i].a + 1), b = (y ? q[i].c + 1 + n : q[i].c + 1);
//	cout << a << ' ' << b << '\n';
	if(s[q[i].a] - 'a' == q[i].b - 'A') return ;
	else if(s[q[i].c] - 'a' == q[i].d - 'A') add(a, (rev(a)));
	else add(a, b), add(rev(b), rev(a));
}

int dfn[N], low[N], timestamp, scc, id[N], stk[N], top, ins[N];
void tarjan(int u) {
	dfn[u] = low[u] = ++ timestamp, stk[++top] = u, ins[u] = 1;
	for(auto v : g[u]) {
		if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
		else if(ins[v]) low[u] = min(low[u], dfn[v]);
	}
	if(dfn[u] == low[u]) {
		int y;
		scc ++;
		do {
			y = stk[top --], id[y] = scc, ins[y] = 0;
		} while(y != u);
	}
}

bool flg;
void work(int h) {
	memcpy(q, q2, sizeof q2);
	s = s2, timestamp = 0, scc = 0, top = 0;
	memset(dfn, 0, sizeof dfn);
	for(int i = 1; i <= n * 2; i ++) g[i].clear();
	for(int i = 0; i < idx; i ++)
		if((1 << i) & h) s[x[i + 1]] = 'a';
		else s[x[i + 1]] = 'b';
	for(int i = 1; i <= m; i ++) 
		link(i);
	for(int i = 1; i <= n * 2; i ++)
		if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= n; i ++) if(id[i] == id[i + n]) return ;
	flg = 1;
	for(int i = 1; i <= n; i ++) {
		if(id[i] < id[i + n]) cout << back(s[i - 1], 0);
		else cout << back(s[i - 1], 1);
	}
	exit(0);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> d >> s >> m;
	s2 = s;
	for(int i = 0; i < n; i ++) if(s[i] == 'x') x[++ idx] = i;
	for(int i = 1; i <= m; i ++) 
		cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d, q[i].a --, q[i].c --;
	memcpy(q2, q, sizeof q);
	work(0);
	for(int s = 1; s < (1 << idx); s ++) work(s);
	cout << -1 << '\n';
	return 0;
} 

评测结果