洛谷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;
}