Solution [NOI2017]游戏
题目大意：有三种赛车，给定 (n) 场游戏，每场游戏要么每种赛车都可以上场，要么只有一种赛车不能上场。以及给定 (m) 个约束条件，形如如果在第 (i) 场游戏使用了 (h_i) 型赛车，那么在第 (j) 场游戏就必须使用 (h_j) 型赛车。求方案
2-SAT
分析：
首先如果 (d=0)，那么每个游戏能选取的赛车只有两种，这就是一个 2-SAT 问题。
而对于 (d>0) 的情况，有一个比较 naive 的想法是直接 (3^d) 去枚举每一个能随意使用赛车的游戏的选择，这样显然是过不去的
但发现我们没有必要枚举具体选哪一种车，而是枚举不选哪一种车，然后按照 (d=0) 的方法解决。这样枚举的复杂度就降到了 (2^d)（因为选择 (AB) 或者选择 (BC) 就已经涵盖了所有的情况了）
自己实现的过程中遇到了一个小插曲，就是形如若 (a) 则 (b) 这种限制条件，是可以推出若非 (b)，则非 (a) 的。这样才能保证建图的对称性。
#include <cstdio>
#include <cctype>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 100;
inline int read(){
int x = 0;char c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c))x = x * 10 + c - '0',c = getchar();
return x;
}
inline char getch(){
char c = getchar();
while(!isalpha(c))c = getchar();
return c;
}
vector<int> G[maxn];
inline void addedge(int u,int v){G[u].push_back(v);}
int dfn[maxn],low[maxn],scc[maxn],instk[maxn],dfs_tot,scc_tot;
stack<int> stk;
inline void tarjan(int u){
dfn[u] = low[u] = ++dfs_tot;
stk.push(u),instk[u] = 1;
for(int v : G[u])
if(!dfn[v])tarjan(v),low[u] = min(low[u],low[v]);
else if(instk[v])low[u] = min(low[u],dfn[v]);
if(dfn[u] == low[u]){
int t;
scc_tot++;
do{
t = stk.top();stk.pop(),instk[t] = 0;
scc[t] = scc_tot;
}while(t != u);
}
}
struct node{int i,j;char hi,hj;}tmp;
vector<node> vec;
int n,d,tot,p[maxn];
char str[maxn];
inline bool chk(const int pos,const char c){
return toupper(str[pos]) != c;
}
inline int encode(const int pos,const char c){
if(str[pos] == 'a')return c == 'C';
if(str[pos] == 'b')return c == 'C';
if(str[pos] == 'c')return c == 'B';
}
inline char decode(const int pos,const int v){
if(str[pos] == 'a')return "BC"[v];
if(str[pos] == 'b')return "AC"[v];
if(str[pos] == 'c')return "AB"[v];
}
inline void clear(){
for(int i = 1;i <= 2 * n;i++){
dfn[i] = low[i] = scc[i] = instk[i] = 0;
G[i].clear();
}
scc_tot = dfs_tot = 0;
}
inline void solve(const int mask){
for(int i = 0;i < d;i++)str[p[i]] = "ab"[(mask >> i) & 1];
clear();
for(auto it : vec)
if(chk(it.i,it.hi))
if(chk(it.j,it.hj))addedge(it.i + n * encode(it.i,it.hi),it.j + n * encode(it.j,it.hj)),addedge(it.j + n * (1 - encode(it.j,it.hj)),it.i + n * (1 - encode(it.i,it.hi)));
else addedge(it.i + n * encode(it.i,it.hi),it.i + n * (1 - encode(it.i,it.hi)));
for(int i = 1;i <= 2 * n;i++)
if(!dfn[i])tarjan(i);
for(int i = 1;i <= n;i++)
if(scc[i] == scc[n + i])return;
for(int i = 1;i <= n;i++)
putchar(decode(i,scc[i] > scc[i + n]));
exit(0);
}
int main(){
n = read(),d = read();
scanf("%s",str + 1);
for(int i = 1;i <= n;i++)
if(str[i] == 'x')p[tot++] = i;
const int m = read();
for(int i = 1;i <= m;i++)
tmp.i = read(),tmp.hi = getch(),tmp.j = read(),tmp.hj = getch(),vec.push_back(tmp);
for(int i = 0;i < (1 << d);i++)solve(i);
return puts("-1"),0;
}