洛谷 P3825 [NOI2017]游戏
传送门
#include <bits/stdc .h>using namespace std;using ll = long long;using p = pair<int, int>;const int maxn(1e5 10);const int maxm(2e5 10);int pos[10];char s[maxn];int ecnt, head[maxn];int tim, dfn[maxn], low[maxn];int scnt, id[maxn];bool vis[maxn];stack<int> st;struct edge { int to, nxt;} edges[maxm];struct opt { int x, y; char a, b;} op[maxm];template<typename T = int>inline const T read(){ T x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 3) (x << 1) ch - '0'; ch = getchar(); } return x * f;}template<typename T>inline void write(T x, bool ln){ if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x / 10, false); putchar(x % 10 '0'); if (ln) putchar(10);}inline void addEdge(int u, int v){ edges[ecnt].to = v; edges[ecnt].nxt = head[u]; head[u] = ecnt ;}inline int getId(int x, char b, bool t, int n){ int a = s[x] - 'a'; b -= 'A'; if (((a 1) % 3 not_eq b) ^ t) { return x n; } return x;}inline char getCh(int x, int t){ int y = s[x] - 'a'; return 'A' ((y t) % 3);}void tarjan(int u){ dfn[u] = low[u] = tim; st.push(u); vis[u] = true; for (int i = head[u]; compl i; i = edges[i].nxt) { int v = edges[i].to; if (not dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (vis[v]) { low[u] = min(low[u], dfn[v]); } } if (dfn[u] == low[u]) { scnt; int v = -1; do { v = st.top(); st.pop(); vis[v] = false; id[v] = scnt; } while (u not_eq v); }}bool judge(int n, int m){ memset(head, -1, sizeof head); memset(dfn, 0, sizeof dfn); tim = scnt = ecnt = 0; for (int i = 0; i < m; i) { int x = op[i].x - 1, y = op[i].y - 1; char a = op[i].a, b = op[i].b; if (s[x] not_eq a 32) { if (s[y] not_eq b 32) { addEdge(getId(x, a, false, n), getId(y, b, false, n)); addEdge(getId(y, b, true, n), getId(x, a, true, n)); } else { addEdge(getId(x, a, false, n), getId(x, a, true, n)); } } } for (int i = 0; i < n * 2; i) { if (not dfn[i]) { tarjan(i); } } for (int i = 0; i < n; i) { if (id[i] == id[i n]) { return false; } } return true;}int main(){#ifdef ONLINE_JUDGE#else freopen("input.txt", "r", stdin);#endif int n = read(), d = read(); scanf("%s", s); for (int i = 0, j = 0; i < n; i) { if (s[i] == 'x') { pos[j ] = i; } } int m = read(); for (int i = 0; i < m; i) { scanf("%d %c %d %c", &op[i].x, &op[i].a, &op[i].y, &op[i].b); } bool flag = false; for (int i = 0; i < (1 << d); i) { for (int j = 0; j < d; j) { if ((i >> j) & 1) { s[pos[j]] = 'a'; } else { s[pos[j]] = 'b'; } } if (judge(n, m)) { flag = true; break; } } if (not flag) { puts("-1"); } else { for (int i = 0; i < n; i) { if (id[i] < id[i n]) { putchar(getCh(i, 1)); } else { putchar(getCh(i, 2)); } } putchar(10); } return 0;} 赞 (0)