洛谷P3825 [NOI2017] 游戏 题解

题目链接：P3825 [NOI2017] 游戏

题意：

小 L 计划进行 $n$ 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 $A$、$B$、$C$ 表示。地图一共有四种，分别用小写字母 $x$、$a$、$b$、$c$ 表示。

其中，赛车 $A$ 不适合在地图 $a$ 上使用，赛车 $B$ 不适合在地图 $b$ 上使用，赛车 $C$ 不适合在地图 $c$ 上使用，而地图 $x$ 则适合所有赛车参加。

适合所有赛车参加的地图并不多见，最多只会有 $d$ 张。

$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。例如：$S=\texttt{xaabxcbc}$ 表示小L计划进行 $8$ 场游戏，其中第 $1$ 场和第 $5$ 场的地图类型是 $x$，适合所有赛车，第 $2$ 场和第 $3$ 场的地图是 $a$，不适合赛车 $A$，第 $4$ 场和第 $7$ 场的地图是 $b$，不适合赛车 $B$，第 $6$ 场和第 $8$ 场的地图是 $c$，不适合赛车 $C$。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $ (i, h_i, j, h_j) $ 来描述，表示若在第 $i$ 场使用型号为 $h_i$ 的车子，则第 $j$ 场游戏要使用型号为 $h_j$ 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。

如果无解，输出 -1。

什么恶心卡常题，心态要崩了。

这篇题解在uoj是过不了Extra Test 12的，但是洛谷可以过hack数据。

显然 $\mathtt{2-SAT}$ ，但是 x 的出现意味这道题还要加一个 $\mathtt{3-SAT}$

众所周知， $\mathtt{k-SAT}$ 在 $k>2$ 时被证明是NP完全的

因此只能暴力枚举所有 x 的选法

这里的暴力可以优化为枚举每个 x 地图为 a 地图还是 b 地图

这样为什么对呢？

因为 a 适合 BC ，b 适合 AC ，然后我们就把填 ABC 的三种情况都试过了

考虑没有 x 的部分怎么做

• 如果 $i$ 的位置适合 $h_i$ 赛车，但 $j$ 不适合 $h_j$ 赛车

  则把 $u_i$ 向 $u_{i}^{\prime}$ 连有向边，表示如果选了 $h_i$ 一定无解

• 如果 $i$ 的位置适合 $h_i$ 赛车，$j$ 的位置适合 $h_j$ 赛车

  那就把 $u_i$ 向 $v_i$ 连有向边，$v_{i}^{\prime}$ 向 $u_{i}^{\prime}$ 连有向边，显然。

时间复杂度 $O(2^d \times (n+m))$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    // #define gc() readchar()
    #define gc() getchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
    void readc(char &ch)
    {
        char t=getchar();
        while(!isupper(t)) t=gc();
        ch=t;
    }
}using namespace FastIO;
#define N ((int)(2e5+15))

bitset<N> vis,ins;
mt19937 rd(time(0));
int n,m,d,scnt,top,dfncnt,pos=1;
char s[N],col[N],a2[N],b2[N];
int head[N],id[N],a1[N],b1[N],stk[N],dfn[N],low[N],scc[N];
struct Edge{int u,v,next;} e[N];
int tran(int x,char c)
{
    if(s[x]=='a') return c=='B'?x:x+n;
    if(s[x]=='b'||s[x]=='c') return c=='A'?x:x+n;
    if(c=='C') return x+n; return x;
}
int neg(int x){return x > n ? x-n : x+n;}
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
bool Tarjan(int u)
{
    dfn[u]=low[u]=++dfncnt;
    ins[stk[++top]=u]=vis[u]=1;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(!vis[v])
        {
            if(!Tarjan(v)) return 0;
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        int v; scc[u]=++scnt; ins[u]=0;
        while(v=stk[top--],v!=u)
        {
            scc[v]=scnt,ins[v]=0;
            if(scc[v]==scc[neg(v)]) return 0;
        }
    }
    return 1;
}
bool solve()
{
    scnt=dfncnt=top=0; pos=1; vis=ins=0;
    for(int i=1; i<=(n<<1); i++) scc[i]=head[i]=dfn[i]=0;
    for(int i=1; i<=m; i++)
    {
        if(s[a1[i]] != 'x' && s[b1[i]] != 'x')
        {
            if(a2[i] == s[a1[i]]-32) continue;
            int u=tran(a1[i],a2[i]),v;
            if(b2[i] == s[b1[i]]-32) {addEdge(u,neg(u)); continue;}
            v=tran(b1[i],b2[i]); addEdge(u,v);
            addEdge(neg(v),neg(u));
        }else
        {
            char o = s[a1[i]], p = s[b1[i]];
            int u,v, x=id[a1[i]], y=id[b1[i]];
            if(o == 'x' && p == 'x')
            {
                if(a2[i] == col[x]) continue;
                u=tran(a1[i],a2[i]);
                if(b2[i] == col[y]) {addEdge(u,neg(u)); continue;}
                v=tran(b1[i],b2[i]); addEdge(u,v);
                addEdge(neg(v),neg(u));
            }
            else if(o == 'x' && p != 'x')
            {
                if(a2[i] == col[x]) continue;
                u=tran(a1[i],a2[i]);
                if(b2[i] == s[b1[i]]-32) {addEdge(u,neg(u)); continue;}
                v=tran(b1[i],b2[i]); addEdge(u,v);
                addEdge(neg(v),neg(u));
            }
            else
            {
                if(a2[i] == s[a1[i]]-32) continue;
                u=tran(a1[i],a2[i]);
                if(b2[i] == col[y]) {addEdge(u,neg(u)); continue;}
                v=tran(b1[i],b2[i]); addEdge(u,v);
                addEdge(neg(v),neg(u));
            }
        }
    }
    for(int i=1; i<=(n<<1); i++) if(!vis[i]&&!Tarjan(i)) return 0;
    for(int i=1; i<=n; i++)
    {
        if(scc[i]<scc[i+n])
        {
            if(s[i]=='a') pc('B');
            else if(s[i]=='b'||s[i]=='c') pc('A');
            else if(col[id[i]]=='A') pc('B');
            else pc('A');
        }else
        {
            if(s[i]=='a'||s[i]=='b') pc('C');
            else if(s[i]=='c') pc('B');
            else if(col[id[i]]=='A') pc('C');
            else pc('B');
        }
    }
    puts("");
    return 1;
}
signed main()
{
    int st=clock();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _; read(n); read(_); scanf("%s",s+1); read(m);
    for(int i=1; i<=n; i++) if(s[i]=='x') id[i]=++d;
    for(int i=1; i<=m; i++) read(a1[i]),readc(a2[i]),read(b1[i]),readc(b2[i]);
    for(int i=0; i<(1<<d); i++)
    {
        for(int j=0; j<d; j++) col[j+1]=((i>>j)&1)?'B':'A';
        if(solve()) return 0;
    }
    puts("-1");
    // printf("times used %.3lf s",(1.0*clock()-st)/CLOCKS_PER_SEC);
    return 0;
}