题解 P3825 【[NOI2017]游戏】

· · 题解

真心感觉其他题解有一点误人子弟...

显然，对于a,b,c类型的跑道，只有两种取值。所以可以转换为2-SAT。

那么有x型跑道怎么办呢？

别的题解会讲：搜索枚举每一个x是选AB还是选AC，BC不用枚举，因为已经包含了。

这里着重讲一下x型跑道为什么只用枚举两次。

算法1:

注意到d很小，所以我们可以爆搜枚举x到底选什么。

我们可以考虑枚举每一个x的取值范围——跑道类型。

假设我们现在枚举第i个x类型跑道。

如果我们当前枚举它是a类型跑道（当前x赛道开的车是B或C）

所以这个x一定不选A。所以对于每一个关于这个x的限制：

第一种：如果第i个跑道A，则第j个跑道选...

由于这个跑道不选A，所以这条限制作废。

第二种：如果第j个跑道选X类型，则第i个跑道选A，

由于这个跑道不选A，所以第j个跑道一定不选X类型。

注意这两种可能是搭配的，可能第j个跑道和第i个跑道都是x型。

我们成功断绝了A对于这个点的影响（m个限制）。

这样子我们就可以用2-SAT求解，来判断选B或选C是否可行了（即是否有解）。

枚举第i个x类型跑道是b,c型也是一样的。

时间复杂度O(3^d(n+m))。无法通过此题。

算法2:

讲了个错解有什么用呢？

发现算法1是枚举：

最终x选择的赛车类型是固定的。

所以在枚举只有B,C两种选择的时候，由于断绝了A对于i的所有联系（如果你不明白可以看看处理A赛车的方式，上述方式使得枚举过程和A变得毫无关系，即绝对不选A），所以我们相当于判断了第i个位置选B是否可行，以及选C是否可行。

综上所述，若枚举“只有A,C两种选择”“只有B,C两种选择”两种情况，我们就遍历了三种情况：选B是否可行，选C是否可行，以及选A是否可行。

复杂度将降为O(2^d(n+m))，可以通过此题。

代码：

#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#define gc getchar
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
struct edge{
    int to,nxt;
}g[2000001];
int tot,head[2000001],len,n,A,B,m,col[2000001];
int pre[1000001],id,a1[1000001],b1[1000001];
int vis[2000001],pos[11],all,d,dfn[2000001],low[2000001];
char s[1000001],a2[1000001],b2[1000001];
stack<int> S;
inline void made(int from,int to){
    g[++tot].to=to;g[tot].nxt=head[from];head[from]=tot;
}
void tarjan(int u){
    low[u]=dfn[u]=++id;S.push(u);vis[u]=1;
    for (int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if (!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if (vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if (low[u]==dfn[u]){
        len++;
        while (S.top()!=u){
            int x=S.top();S.pop();
            col[x]=len;vis[x]=0;
        }
        col[u]=len;S.pop();vis[u]=0;
    }
}
inline int trans(int a,char B){
    char A=s[a];
    if (A=='c'){
        if (B=='A') return 0;
        else return 1;
    }else if (A=='b'){
        if (B=='A') return 0;
        else return 1;
    }else if (A=='a'){
        if (B=='B') return 0;
        else return 1;
    }else{
        if (B=='C') return 1;
        return 0;
    }
}
inline char upr(char y){
    return (char)(y-32);
}
signed main(){
    n=read(),d=read();
    for (int i=1;i<=n;i++){
        char ch=gc();
        while (!isalpha(ch)) ch=getchar();
        s[i]=ch;
        if (s[i]=='x') pre[i]=++all;
    }
    m=read();
    for (int i=1;i<=m;i++){
        a1[i]=read();char ch=gc();
        while (!isalpha(ch)) ch=getchar();
        a2[i]=ch;b1[i]=read();ch=gc();
        while (!isalpha(ch)) ch=getchar();
        b2[i]=ch;
    }
    int MX=(1<<d)-1;
    for (int zt=0;zt<=MX;zt++){
        //0 AC    1 BC
        tot=id=len=0;
        while (!S.empty()) S.pop();
        for (int i=1;i<=2*n;i++){
            head[i]=low[i]=col[i]=dfn[i]=vis[i]=0;
        }
        for (int i=1;i<=m;i++){
            if (s[a1[i]]=='x'&&s[b1[i]]=='x'){
                int zta=(zt&(1<<(pre[a1[i]]-1)));
                int ztb=(zt&(1<<(pre[b1[i]]-1)));
                if (!zta&&a2[i]=='B') continue;
                if (zta&&a2[i]=='A') continue;
                int I=trans(a1[i],a2[i]),J=trans(b1[i],b2[i]);
                if (!ztb&&b2[i]=='B'){
                    made(a1[i]+n*I,a1[i]+n*(I^1));continue;
                }
                if (ztb&&b2[i]=='A'){
                    made(a1[i]+n*I,a1[i]+n*(I^1));continue;
                }
                made(a1[i]+n*I,b1[i]+n*J);made(b1[i]+n*(J^1),a1[i]+n*(I^1));
            }else if (s[a1[i]]!='x'&&s[b1[i]]=='x'){
                int ztb=(zt&(1<<(pre[b1[i]]-1)));
                int I=trans(a1[i],a2[i]),J=trans(b1[i],b2[i]);
                if (upr(s[a1[i]])==a2[i]) continue;
                if (!ztb&&b2[i]=='B'){
                    made(a1[i]+n*I,a1[i]+n*(I^1));continue;
                }
                if (ztb&&b2[i]=='A'){
                    made(a1[i]+n*I,a1[i]+n*(I^1));continue;
                }
                made(a1[i]+n*I,b1[i]+n*J);made(b1[i]+n*(J^1),a1[i]+n*(I^1));
            }else if (s[a1[i]]=='x'&&s[b1[i]]!='x'){
                int zta=(zt&(1<<(pre[a1[i]]-1)));
                int I=trans(a1[i],a2[i]),J=trans(b1[i],b2[i]);
                if (!zta&&a2[i]=='B') continue;
                if (zta&&a2[i]=='A') continue;
                if (upr(s[b1[i]])==b2[i]){
                    made(a1[i]+n*I,a1[i]+n*(I^1));continue;
                }
                made(a1[i]+n*I,b1[i]+n*J);made(b1[i]+n*(J^1),a1[i]+n*(I^1));
            }else{
                int I=trans(a1[i],a2[i]),J=trans(b1[i],b2[i]);
                if (upr(s[a1[i]])==a2[i]) continue;
                if (upr(s[b1[i]])==b2[i]){
                    made(a1[i]+n*I,a1[i]+n*(I^1));continue;
                }
                made(a1[i]+n*I,b1[i]+n*J);made(b1[i]+n*(J^1),a1[i]+n*(I^1));
            }
        }
        for (int i=1;i<=2*n;i++){
            if (!dfn[i]) tarjan(i);
        }
        bool flag=1;
        for (int i=1;i<=n;i++){
            if (col[i]==col[i+n]){
                flag=0;break;
            }
        }
        if (!flag) continue;
        for (int i=1;i<=n;i++){
            int op=(col[i]>col[i+n]);
            if (s[i]=='x'){
                int ZT=(zt&(1<<(pre[i]-1)));
                if (!ZT){
                    if (op) printf("C");
                    else printf("A");
                }else{
                    if (op) printf("C");
                    else printf("B");
                }
            }else{
                if (s[i]=='a'){
                    if (op) printf("C");
                    else printf("B");
                }else if (s[i]=='b'){
                    if (op) printf("C");
                    else printf("A");
                }else{
                    if (op) printf("B");
                    else printf("A");
                }
            }
        }
        return 0;
    }
    printf("-1");
    return 0;
}