【题目】

【题意】n场游戏，有三种车ABC，给定长度为n的字符串，'a'表示不能选A，'b''c'同理，'x'表示不限，至多d个'x'。有m个限制(i,hi,j,hj)表示如果第i场选择车hi，那么第j场必须选择车hj。求可行方案，或无解。n<=10^5，d<=8。

【算法】2-sat

【题解】枚举'x'是'a'或'b'（如果直接枚举选那辆车复杂度太高，不如利用2-sat来做），这样有2^d种状态。

这样确定字符串后，每场比赛就只有两种选项和m种限制，进行2-sat即可，复杂度O(2^d*m)。（因为每次要初始化，常数还挺大的，UOJ很容易被卡TLE）

2-sat算法：连边后tarjan，如果一个点和对应点属于同一个SCC则无解，否则选择所属SCC编号较小的点。（dfs出栈序就是一种逆拓扑序）

实现细节：直接对每个点开3倍点，然后标记一个点不用，标记使用点为另外两个点。还有就是如果x和x'必须强制选x'的话，x向x'连有向边就可以了（不连对称边，这样虽然没有对称性，但是不影响）。

#include
      
       #include
       
        #include
        
         using namespace std;const int N=300010;int first[N],f[N],a[N],dfn[N],low[N],st[N],belong[N],dfsnum,TOT,tot,top,A[N],B[N],C[N],D[N],n,d,m;int id[N],op[N];char s[N];struct edge{
    int v,from;}e[N*2];void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}void tarjan(int x){    dfn[x]=low[x]=++dfsnum;st[++top]=x;    for(int i=first[x];i;i=e[i].from)if(!dfn[e[i].v]){        tarjan(e[i].v);        low[x]=min(low[e[i].v],low[x]);    }else if(!belong[e[i].v])low[x]=min(dfn[e[i].v],low[x]);    if(dfn[x]==low[x]){        TOT++;        while(st[top]!=x)belong[st[top--]]=TOT;        belong[st[top--]]=TOT;    }}bool solve(int o){    memset(f,0,sizeof(f));    memset(first,0,sizeof(first));    memset(dfn,0,sizeof(dfn));    memset(belong,0,sizeof(belong));//    tot=0;top=0;TOT=0;dfsnum=0;    for(int i=0;i
         
          >=1;else a[i]=s[i]-'a';        f[a[i]*n+i]=1;        id[i]=(a[i]+1)%3*n+i;op[id[i]]=(a[i]+2)%3*n+i;op[op[id[i]]]=id[i];    }    for(int i=1;i<=m;i++){        int x=B[i]*n+A[i]-1,y=D[i]*n+C[i]-1;        if(f[x]||x==y)continue;        if(A[i]==C[i]||f[y])insert(x,op[x]);        else insert(x,y),insert(op[y],op[x]);    }    for(int i=0;i