「NOI2017」游戏
解题思路 :
考虑没有 \(x\) 存在的情况所有地图只有两种可以选择的车辆，而限制条件是诸如选了 \(A\) 就要选 \(B\) 这种，不难发现是一个 \(2-sat\) 问题
设 \(A\) 表示 \(A\) 地图能用的第一辆车，\(A'\) 表示 \(A\) 地图能用的第二辆车
如果 \(A\) 选了就必须要选 \(B\) 的话，那么显然有 \(A’\) 选了就必须要选 \(B'\) 其他情况同理，这里可以直接连一条边
此外考虑一些特殊情况，如果选了 \(A\) 就必须选 \(B\) 但是 \(B\) 不能选的话，显然 \(A\) 也不能选，于是直接连一条 \(A\rightarrow A'\) 把选 \(A\) 的可能性否决掉
如果给出的限制\(A\) 不能选的话，可以直接无视掉这条限制，因为 \(A\) 本身就不在进行 \(Tarjan\) 的点中
至此我们就已经解决了没有 \(x\) 的情况，考虑有 \(x\) 怎么做
观察到 \(d\) 很小，可以暴力枚举 \(x\) 对应的地图是 \(a\) 还是 \(b\) 还是 \(c\) ，这样复杂度是 \(O(3^d(n+m))\) ，有可能会超时
但实际上当枚举到 \(x = a\) 和 \(x = b\) 的情况时，就已经枚举到了 \(x\) 选的车的所有情况 \((A,C) \cup (B,C)=(A,B,C)\)
所以可以直接枚举 \(x =a\) 或者 \(b\) 总复杂度 \(O(2^d(n+m))\)
/*program by mangoyang*/
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int f = 0, ch = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
#define Rint register int
const int N = 150005;
char s[N];
vector<int> g[N];
int dfn[N], low[N], f[25], st[N], ins[N], ban[N], bel[N], Index, top, id;
int A[N], B[N], m1[N], m2[N], c1[N], c2[N], ans[N], n, m, d, cnt;
inline void tarjan(int u){
dfn[u] = low[u] = ++Index, st[++top] = u, ins[u] = 1;
for(Rint i = 0; i < g[u].size(); i++){
int v = g[u][i];
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]){
++id;
while(st[top] != u) ins[st[top]] = 0, bel[st[top--]] = id;
ins[st[top]] = 0, bel[st[top--]] = id;
}
}
inline int check(){
memset(dfn, 0, sizeof(dfn)), id = 0, Index = 0;
for(Rint i = 1; i <= 3 * n; i++) g[i].clear();
for(Rint i = 1; i <= m; i++){
if(A[m1[i]] != c1[i] && B[m1[i]] != c1[i]) continue;
int o1 = A[m1[i]] != c1[i] ? A[m1[i]] : B[m1[i]];
int o2 = A[m2[i]] != c2[i] ? A[m2[i]] : B[m2[i]];
if(A[m2[i]] != c2[i] && B[m2[i]] != c2[i]){
g[m1[i]+c1[i]].push_back(m1[i] + o1);
continue;
}
if(m1[i] == m2[i]){
if(c1[i] == c2[i]) continue;
g[m1[i]+c1[i]].push_back(m2[i]+c2[i]);
continue;
}
g[m2[i]+o2].push_back(m1[i] + o1);
g[m1[i]+c1[i]].push_back(m2[i] + c2[i]);
}
for(Rint i = 1; i <= 3 * n; i++) if(!dfn[i]) tarjan(i);
for(Rint i = 1; i <= n; i++){
if(bel[i+A[i]] == bel[i+B[i]]) return 0;
ans[i] = bel[i+A[i]] < bel[i+B[i]] ? A[i] : B[i];
}
for(Rint i = 1; i <= n; i++){
if(ans[i] == 0) putchar('A');
if(ans[i] == n) putchar('B');
if(ans[i] == 2 * n) putchar('C');
}
exit(0);
}
inline void dfs(int x){
if(x == cnt + 1) return (void) (check());
A[f[x]] = 0, B[f[x]] = n, dfs(x + 1);
A[f[x]] = 0, B[f[x]] = 2 * n, dfs(x + 1);
}
int main(){
read(n), read(d), scanf("%s", s + 1), read(m);
for(Rint i = 1; i <= m; i++){
read(m1[i]), c1[i] = getchar(), read(m2[i]), c2[i] = getchar();
c1[i] = (c1[i] - 'A') * n, c2[i] = (c2[i] - 'A') * n;
}
for(Rint i = 1; i <= n; i++) if(s[i] == 'x') f[++cnt] = i;
else{
if(s[i] == 'c') A[i] = 0, B[i] = n;
if(s[i] == 'b') A[i] = 0, B[i] = 2 * n;
if(s[i] == 'a') A[i] = n, B[i] = 2 * n;
}
dfs(1), cout << -1 << endl;
return 0;
}